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

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.