Convergence of Stochastic Proximal Gradient Algorithm

1. Introduction.

• Stochastic gradient estimates replace exact gradients in proximal splitting, a setting relevant to statistical learning, stochastic optimization, and incremental optimization.In online learning, one gradient estimate is used at each step.Source: §1 · p. 1

1.1. Contribution and Previous Work.

• The introduction situates the method among stochastic approximation, mirror-descent methods, and stochastic accelerated proximal-gradient methods.The paper contrasts its iterate-focused analysis with prior approaches that often study averaged iterates.Source: §1.1 · p. 2
• The method is a basic, non-accelerated stochastic proximal gradient algorithm; its relaxation step distinguishes it from FOBOS, and it does not average iterates.The paper notes that averaging can harm sparsity and may negatively affect convergence rates in strongly convex settings.Source: §1.1 · p. 2
• The analysis focuses on iterate convergence and non-asymptotic expectation bounds in an infinite-dimensional setting, without requiring bounded iterates.For strongly convex objectives it obtains an O(1/n) error bound, matching the rate available for function values with accelerated methods.Source: §1.1 · p. 2
• The paper establishes expectation convergence rates and almost-sure convergence using extensions of deterministic convex-optimization techniques rather than regret analysis and online-to-batch conversion.The analysis also finds that acceleration does not improve rates in the stochastic case.Source: §1.1 · p. 2

2.1. Problem.

• Composite optimization minimizes the sum of a smooth convex function and a possibly nonsmooth convex function whose proximity operator is available or easily computed.The general problem assumes a differentiable convex term with Lipschitz-continuous gradient and a nonempty solution set.Source: §2.1 · p. 3
• SPG takes a stochastic gradient step, applies the proximity operator, and relaxes toward the resulting point; it generalizes FOBOS by adding relaxation and assuming a smooth first component.With exact gradients, the algorithm reduces to proximal forward-backward splitting.Source: §2.1 · p. 4
• The gradient estimate is conditionally unbiased, while the paper’s noise condition is weaker than typical boundedness requirements on gradient estimates.The stated comparison includes bounded conditional second moments and uniform boundedness of the estimates.Source: §2.1 · p. 4

2.2. Special cases.

• The framework includes unconstrained minimization, constrained minimization via an indicator function, expectation minimization, and finite-sum objectives sampled by selecting a component.The finite-sum setting is especially relevant when the number of component functions is large.Source: §2.2 · p. 5

2.3. Application to Machine Learning.

• In machine learning, SPG can target either regularized expected loss or regularized empirical risk, with convex nonsmooth penalties including sparsity-inducing and structured-sparsity terms.An elastic-net penalty can supply stronger convexity, while high- or infinite-dimensional risks are typically not strongly convex.Source: §2.3 · p. 6

3.1. Convergence in Expectation of SPG algorithm.

• Theorem 3.2 gives an explicit non-asymptotic bound on expected squared distance from a solution under strong convexity and conditions on the stochastic gradients and stepsizes.The result extends a stochastic-gradient bound to nonsmooth composite objectives.Source: §3 · p. 6, §3.1 · p. 7
• With θ = 1 and c1 chosen so c > 1, the expected squared iterate error is O(n^-1).The rate depends on the stepsize’s asymptotic behavior and a constant determined by the strong-convexity parameters; choosing c1 too small affects the rate, while choosing it too large affects the bound’s constants.Source: §3.1 · pp. 7–8
• In the strongly convex case, accelerated and non-accelerated methods have the same iterate-convergence rate, and averaging is unnecessary because the iterates themselves converge.The paper notes that averaging or linear combinations can prevent sparsity of iterates.Source: §3.1 · p. 8
• If the objective is continuous, its values along the iterates converge to the minimum; the stated rates are O(n^-1/2) for Lipschitz objectives and O(n^-1) for differentiable objectives with Lipschitz gradient.These conclusions are given in the comparison with deterministic stochastic proximal forward-backward methods with errors.Source: §3.1 · pp. 8–9

3.2. Almost sure convergence of SPG algorithm.

• Almost-sure convergence of the full sequence holds when L is uniformly convex at the solution; with strict convexity and weakly continuous gradient, a subsequence converges weakly almost surely.Without weak continuity, the theorem does not ensure weak convergence of a subsequence unless the objective values converge to the minimum.Source: §3.2 · p. 9
• The almost-sure analysis uses random quasi-Fejér sequences and probabilistic quasi-martingale techniques, under additional stepsize and regularity conditions.The paper presents this as an extension of analysis for stochastic projected subgradient methods.Source: §3.2 · p. 9

• For a solution w, Proposition 4.5 bounds the next squared distance by a weighted combination of the current squared distance and that of y_n.Its strongly convex case also bounds ||y_n − w||² using the stochastic gradient difference and a factor involving γ_nν.Source: §4 · pp. 10–11
• The quasi-Fejér result implies that expected squared distances converge and that the iterates are almost surely bounded with nonempty weak cluster points.These conclusions are stated for a random sequence satisfying the proposition's hypotheses and a nonempty closed target set.Source: §4 · p. 12
• Under (A1)–(A4), expected squared distances to any solution converge to a finite value, and the squared distances converge almost surely.The proof also identifies the iterates as a random quasi-Fejér sequence with respect to the minimizer set.Source: §4 · pp. 12–13
• The iterates converge almost surely to the minimizer when L is uniformly convex at that minimizer and (λ_nγ_n) is not summable.The proof extracts a subsequence approaching the minimizer, then uses convergence of the squared distances to conclude convergence of the full sequence.Source: §4 · p. 14
• When L is strictly convex, the iterates converge weakly almost surely to an optimal solution.The proof identifies every weak cluster point with the solution using weak continuity and strict monotonicity of ∇L.Source: §4 · pp. 14–15

5.1. Properties of SPG.

• In the toy parameter study, convergence is faster with larger strong convexity and lower noise variance, while the step-size constant strongly affects behavior.Performance is measured by |w_n − 10| over the first 100 iterations across repeated realizations.Source: §5.1 · p. 15, Figure 5.1 · p. 15

5.2. Comparison with other methods.

• SPG and FOBOS require step-size choices, whereas SAGE has no free parameter; the experiments compare accuracy by iteration count at basically equal per-iteration cost.The comparison uses elastic-net-regularized problems; the bounded-gradient assumption for FOBOS is not satisfied, although the iterates are bounded.Source: §5.2 · p. 16

5.3. Toy example.

• On the toy example, SPG and SAGE behave similarly, while FOBOS is slower.The comparison runs for 1,000 iterations with the stated Gaussian noise and step-size choices.Source: §5.3 · p. 16, Figure 5.2 · p. 16

5.4. Regression problems with random design.

• For random-design regression, the three methods produce almost indistinguishable regression functions.The comparisons use polynomial and trigonometric dictionaries.Source: §5.4 · p. 17, Figure 5.4 · p. 18
• For random-design regression, SAGE performs best with the polynomial dictionary, while SPG is fastest with the trigonometric dictionary.Averaging mitigates oscillations but slows convergence in the reported comparison.Source: §5.4 · p. 18, Figure 5.5 · p. 18

5.5. Deconvolution problems.

• In deconvolution, SAGE converges fastest, SPG is slightly worse, and FOBOS is slower.The comparison uses iterates initialized at zero; SPG and FOBOS use specified diminishing step sizes.Source: §5.5 · p. 19, Figure 5.7 · p. 19
• The final deconvolution iterates have 937 zero components for SPG and SAGE, versus 438 for FOBOS.SPG and SAGE generate sparse iterates after a few iterations in this example.Source: §5.5 · pp. 19–20, Figure 5.8 · p. 20

6. Conclusion.

• The proposed method applies stochastic proximal splitting to composite minimization with a smooth term and a convex term, using stochastic gradient estimates.The setting is relevant to online learning and stochastic or incremental optimization.Source: §6 · p. 20
• The analysis provides convergence rates in expectation and establishes almost-sure convergence for the proposed stochastic proximal gradient method.The paper also notes that, unlike in the deterministic case, acceleration does not improve rates in the stochastic case.Source: §6 · p. 20
• Relaxing strong convexity to convex objectives and deriving high-probability rather than expectation bounds are identified as future work.Source: §6 · p. 20

Appendix A. Proofs of auxiliary results.

• The appendix proves results about random quasi-Fejér sequences and an upper bound for a numerical sequence satisfying a lemma’s assumptions.Source: Appendix A · p. 21
• A positive quasi-Fejér argument establishes convergence of the expected squared distance sequence to a real limit.The proof uses summability of the errors and finite expected squared distance from the initial point.Source: Appendix A · p. 21
• The proof shows that the sequence r_n is a supermartingale and converges almost surely to an integrable random variable.Source: Appendix A · p. 21
• The appendix estimates recursive bounds by applying the recursion repeatedly when its terms are positive, then treating cases for the parameter α.Source: Appendix A · pp. 21–22