<p>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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10957_2025_2771_Article_IEq1.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="10" /> </InlineMediaObject> <EquationSource Format="TEX">$\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation>-stationary point at a rate of <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10957_2025_2771_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="57" /> </InlineMediaObject> <EquationSource Format="TEX">${\mathcal {O}}(1/T)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">/</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <i>T</i> 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-<InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="MediaObjects/10957_2025_2771_IEq3_HTML.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="120" Type="Linedraw" Width="13" /> </InlineMediaObject> </InlineEquation>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.</p>

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

期刊论文
发表日期：

2025年7月17日

查看全文

Yue-Hong He,
Gao-Xi Li,
Xian-Jun Long

摘要

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.