Non-Asymptotic Analysis of Hybrid SPG for Non-Convex Stochastic Composite Optimization

Yue-Hong He (), Gao-Xi Li () and Xian-Jun Long ()
Additional contact information
Yue-Hong He: Sichuan University
Gao-Xi Li: Chongqing Technology and Business University
Xian-Jun Long: Chongqing Technology and Business University

Journal of Optimization Theory and Applications, 2025, vol. 207, issue 1, No 19, 30 pages

Abstract: Abstract This paper focuses on the stochastic composite optimization problem, wherein the objective function comprises a smooth non-convex term and a non-smooth, possibly non-convex regularizer. Existing algorithms for addressing such problems remain limited and mostly have unsatisfactory complexity. To improve the sample complexity, we propose a hybrid stochastic proximal gradient algorithm and its restarting variant for both expectation and finite-sum problems. Our approach relies on a novel hybrid stochastic estimator that effectively balances variance and bias, avoiding unnecessary computation waste. Under mild assumptions, we prove that the proposed algorithms non-asymptotically converge to an $$\epsilon $$ ϵ -stationary point at a rate of $${\mathcal {O}}(1/T)$$ O ( 1 / T ) , where T denotes the number of iterations. The sample complexity manifests as a piecewise function, which outperforms some existing state-of-the-art results. Additionally, we derive the linear convergence of the restarting algorithm based on the Kurdyka- ojasiewicz property with an exponent of 1/2. To validate the effectiveness of our algorithm, we apply them to solve large-scale linear regression and regularized loss minimization problems, demonstrating certain superiority over several existing methods.

Keywords: Stochastic proximal gradient algorithm; Hybrid stochastic estimator; Non-asymptotic convergence; Non-smooth non-convex regularizer; Complexity; 90C33; 90C15; 65K15 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-025-02771-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:207:y:2025:i:1:d:10.1007_s10957-025-02771-9

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-025-02771-9

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().