Source-linked AI summary
Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity
Hilal Asi, John C. Duchi
TL;DR
Stochastic subgradient methods can be stepsize-sensitive and may diverge on objectives outside their convergence criteria. The paper develops aProx model-based methods and reports stronger theoretical guarantees and empirical performance than naive stochastic subgradient methods.
Problem
Stochastic subgradient methods can be sensitive to stepsize selection and can diverge on objectives that do not meet their convergence criteria.
Source: §1 · p. 1Method
The aProx family solves stochastic convex optimization through model-based updates, with stochastic gradient and proximal point methods as special cases.
Source: §1 · pp. 2–3Results
The aProx methods have substantially better theoretical guarantees and empirical performance than naive stochastic subgradient methods.
Source: §1 · p. 2Takeaways & Limitations
Under shared minimizers and the lower-bound condition, aProx methods make progress toward the optimal set and can achieve near-linear convergence on easy problems.
Source: §1 · p. 3, §4 · p. 14A stated regularity assumption requires measurable subgradient selections and E[∂f(x; S)] = ∂F(x) for x ∈ X.
Source: §1 · p. 3
Abstract
from arXiv · showhide
We develop model-based methods for solving stochastic convex optimization problems, introducing the approximate-proximal point, or aProx, family, which includes stochastic subgradient, proximal point, and bundle methods. When the modeling approaches we propose are appropriately accurate, the methods enjoy stronger convergence and robustness guarantees than classical approaches, even though the model-based methods typically add little to no computational overhead over stochastic subgradient methods. For example, we show that improved models converge with probability 1 and enjoy optimal asymptotic normality results under weak assumptions; these methods are also adaptive to a natural class of what we term easy optimization problems, achieving linear convergence under appropriate strong growth conditions on the objective. Our substantial experimental investigation shows the advantages of more accurate modeling over standard subgradient methods across many smooth and non-smooth optimization problems.
1 Introduction
The paper introduces aProx, a family of model-based stochastic convex optimization methods, to address the sensitivity and instability of stochastic subgradient methods. It develops stability, fast-convergence, and empirical results for these methods, alongside context on related stochastic optimization work.
1 Introduction
- Stochastic subgradient methods are widely used but can be stepsize-sensitive, fail to converge on objectives outside their criteria, and lack adaptation to nuanced problem structure.The paper gives F(x) = x^4 as an example of an objective on which the method can diverge.Source: §1 · p. 1
- aProx iterates remain stable under Assumption A1, supporting convergence even when gradient estimates vary substantially and optimal-covariance asymptotic normality under weaker conditions than classical analyses.The gradient may grow super-exponentially in the norm of the iterate; the asymptotic normality result holds so long as iterates are bounded.Source: §1 · p. 3
- For easy problems with a minimizer shared by all sampled functions, a simple lower-bound condition on models yields (near) linear convergence without added computational complexity beyond stochastic gradient methods.The paper cites interpolation, consistent over-parameterized linear systems, and convex-set intersection as examples of this shared-minimizer setting.Source: §1 · p. 3
- Under restricted strong convexity, stochastic proximal point methods achieve fast convergence with only weak moment conditions on subgradients.The paper presents this as an advantage of accurate modeling.Source: §1 · p. 3
- Across smooth, non-smooth, and super-polynomially growing convex problems, experiments report greater stepsize robustness from slightly improved aProx models and fast convergence where stochastic gradient methods fail.The experiments include regression, logistic and Poisson regression, and projection onto intersections of halfspaces.Source: §1 · p. 4
1.1 Related work
- Earlier work studies stochastic proximal point and model-based methods, while prior stochastic-gradient analyses document stepsize sensitivity and transient divergence.Related work also describes proximal-point analyses with restrictive global Lipschitz and strong-convexity assumptions [57, 58].Source: §1 · p. 2, §1.1 · p. 4
2 Methods
The methods section presents aProx as a family of updates that minimize regularized models of sampled functions. It catalogs linear, exact-function, truncated, and bundle models, with additional accuracy conditions used to obtain stronger guarantees.
2 Methods
- The aProx catalogue includes stochastic subgradient updates based on first-order models and proximal-point updates that use the true sampled function.The proximal-point model satisfies all the conditions provided in the paper.Source: §2 · p. 5
- For nonnegative losses, truncated models avoid negative model values; when the samplewise infimum is available, the paper also considers models using that lower bound.Such samplewise infima are available in cited regression and classification examples.Source: §2 · pp. 5–6
- Relatively accurate models satisfy an additional condition intended to support stronger stability and convergence guarantees while allowing less accuracy than the exact proximal-point model.The required approximation scales with the regularization parameter, with higher accuracy needed as it decreases.Source: §2 · p. 6
- Bundle methods construct piecewise-linear models from affine lower bounds, and are one approach to achieving the relative-accuracy condition.The paper notes that it does not analyze how many bundle iterations are needed to satisfy that condition.Source: §2 · pp. 6–7
3 Stability and its consequences
This section examines how appropriately accurate aProx models stabilize iterates, including on problems where stochastic subgradient methods may diverge, and how stability supports almost-sure convergence and asymptotic optimality. It also covers asymptotic normality under additional local assumptions and Theorem 2’s unimprovable convergence guarantee under essentially bounded iterates.
3.1 Stability of (approximate) proximal methods
- With Conditions (C.i)–(C.ii) and updated-point accuracy (C.iv), aProx methods have non-divergent expected distance to the solution set and iterates that remain bounded with probability 1.The full stochastic proximal point method and bundle models satisfy the stated conditions.Source: §3.1 · p. 8
3.1.1 Proof of Theorem 1
- Under Condition (C.i), each step of method (4) satisfies a one-step squared-distance bound: half the squared distance from xk+1 to any x ∈ X is at most half the squared distance from xk to x, minus αk times the model-loss difference and half the squared step length.Source: §3.1.1 · p. 9
3.2 Convergence of aProx methods
- When iterates are bounded and standard stepsize summability conditions hold, methods satisfying (C.i)–(C.ii) converge almost surely to an optimum, with objective values converging to its value.The convergence result applies on the event that the iterates’ distances to the solution set are bounded.Source: §3.2 · p. 10
3.3 Asymptotic normality
- Under Assumptions A1–A3, bounded iterates, and stepsizes α_k = α_0 k^-β with β in (1/2, 1), the analysis establishes asymptotic normality for averaged iterates.The proof uses convergence of bounded iterates and a local gradient approximation, then applies techniques of Polyak and Juditsky.Source: §3.3 · pp. 12–13
- Theorem 2 attains the local asymptotic minimax bound for stochastic optimization, analogous to Fisher information in classical statistics [33, 60, Sec. 8.7].The passage describes this asymptotic convergence guarantee as unimprovable.Source: §3.3 · p. 13
- Unlike stochastic gradient schemes, Theorem 2 requires essentially only that the iterates remain bounded.Source: §3.3 · p. 13
- With appropriately accurate models, the aProx family guarantees stability, which enables model-based iteration schemes (4) to be asymptotically optimal.Source: §3.3 · p. 13
4 Fast convergence for easy problems
For easy problems with shared minimizers, aProx models satisfying a lower-bound condition make progress toward the optimum and adapt to sharp or quadratic growth. Under the corresponding conditions, the paper establishes fast convergence and illustrates it on linear systems, convex-set intersections, and interpolation.
4 Fast convergence for easy problems
- With shared minimizers, models satisfying (C.i)–(C.iii) make progress toward the optimal set, providing a basis for fast convergence results on easy problems.The section illustrates this framework with overdetermined linear systems, intersections of convex sets, and data interpolation.Source: §4 · p. 14
4.1 Sharp growth with shared minimizers
- Under expected sharp growth and the stated model and stepsize conditions, aProx converges linearly with probability 1; the paper contrasts this with subgradient jamming on F(x) = |x|.For that subgradient example, convergence can be no faster than O(αk) without careful stepsize choices.Source: §4.1 · p. 15
4.2 Quadratic growth with shared minimizers
- Under quadratic growth, aProx achieves nearly linear convergence on easy problems when the models satisfy the lower-bound condition, and its convergence adapts to whether strong growth holds.The paper contrasts this adaptivity with stochastic-gradient analyses requiring precise stepsizes reflecting typically unknown constants.Source: §4.2 · pp. 16–17
4.3.1 Overdetermined linear systems and Kaczmarz algorithms
- For feasible overdetermined systems, the mean absolute error objective typically satisfies sharp growth, so truncated-model aProx converges linearly, though specialized Kaczmarz methods can be slightly faster.The stated additional benefit is adaptivity: aProx also converges outside linear systems.Source: §4.3.1 · p. 17
4.3.2 Finding a point in the intersection of convex sets
- For finding a point in an intersection of convex sets, a Hoffman-type error bound yields geometric convergence of the aProx iterates toward the intersection.The passage gives the bound lim sup dist(xk, X*)^2/(1 − λ/m)^k < ∞ under its stated condition.Source: §4.3.2 · p. 18
4.3.3 Interpolation problems
- For underdetermined least squares with the stated matrix and stepsize conditions, truncated-model aProx achieves nearly linear convergence while retaining convergence beyond the narrow easy-problem class.The paper contrasts this with gradient methods whose recommended stepsizes give linear convergence but can fail outside that class.Source: §4.3.3 · p. 19
5 Non asymptotic convergence results
The section gives non-asymptotic guarantees for aProx under Lipschitzian assumptions and for stochastic proximal point under restricted strong convexity. The latter applies even to non-Lipschitz, nonsmooth objectives and requires a finite subgradient second moment only at the optimum.
5 Non asymptotic convergence results
- Under the Lipschitzian assumption, the paper extends stochastic-gradient convergence results to aProx models satisfying (C.i)–(C.ii), with an additional claim for compact X.The authors identify the compact-X claim as their contribution beyond Davis and Drusvyatskiy [14].Source: §5 · pp. 19–20
- Under restricted strong convexity, stochastic proximal point makes progress irrespective of objective smoothness and has non-asymptotic guarantees for non-Lipschitz, nonsmooth objectives.The proposition's stated assumptions also include A1 and A7.Source: §5 · pp. 20–21
- For the stochastic proximal-point result, the subgradient at the optimum need only have finite second moment, rather than a global second-moment bound.The passage also states that the result holds no matter the stepsize sequence.Source: §5 · p. 21
6 Experiments
The experiments compare four aProx models across smooth and non-smooth problems, varying stepsizes and problem settings. Across these examples, more accurate models generally tolerate a wider range of stepsizes and often converge faster than stochastic gradient methods.
6.1 Linear Regression
- For κ(A) = 15 linear regression, SGM never reaches ϵ = .05, while better models retain the advantages seen at κ(A) = 1.At κ(A) = 1, proximal and truncated models converge across a stepsize range spanning six orders of magnitude in the noiseless setting; noisy proximal updates are less robust.Source: §6.1 · p. 23
6.2 Absolute Loss Regression
- In absolute-loss regression, proximal, truncated, and multi-line models converge very quickly on noiseless easy problems, while improved models have a smaller advantage with noise.With noise, better approximations converge over a slightly larger stepsize range; experiments at κ(A) = 15 are reported as parallel.Source: §6.2 · p. 24
6.3 Logistic Regression
- In logistic regression, truncated and proximal models converge over a wider range of stepsizes than SGM, including with noisy labels.More accurate models also benefit the noiseless setting, where the objective has no finite optimizer.Source: §6.3 · p. 24
6 Experiments
- Across the experiments, more accurate aProx models generally show greater stepsize robustness and faster convergence than naive subgradient methods.The comparisons span linear and absolute-loss regression, logistic regression, multi-class hinge loss, and Poisson regression.Source: §6.2 · p. 24, §6.3 · p. 24, §6.4 · p. 26
6.4 Multi Class Hinge Loss
- For multi-class hinge loss, better aProx models are significantly more stepsize-robust and generally converge faster than naive subgradient methods.The experiments compare label-randomization probabilities p = 0 and p = 0.01.Source: Figure 7 · p. 25, §6.4 · p. 26
6.5 Poisson Regression
- In Poisson regression, the truncated model converges nearly as robustly as the stochastic proximal point method despite being substantially easier to calculate.The authors report that SGM also converges in low-noise cases with sufficiently small stepsizes.Source: §6.5 · p. 26
A Proof of Theorem 2
The proof organizes the iteration into a leading stochastic term and error terms, then controls the model-gradient discrepancy and the errors needed for the theorem. Its arguments use local behavior near the solution and bounds on the movement of individual iterates.
A Proof of Theorem 2
- The proof decomposes the iterates into a leading term and several errors, with the model subgradient's implicit dependence on the next iterate posing the main challenge.A gradient-comparison result controls this discrepancy so the model subgradients approximate ∇f near the current iterate.Source: A Proof of Theorem 2 · pp. 27–28
- Individual update lengths are bounded by the stepsize times a sampled subgradient norm, helping control the final error terms.The proof obtains this movement bound from the model update and convexity, then uses it alongside the gradient comparison.Source: A Proof of Theorem 2 · p. 28
A.1 Proof of Lemma A.1
- The proof uses local strong convexity to relate objective error to squared distance from the solution.On a local neighborhood, the passage gives F(x) − F(x⋆) ≥ λ_r/2 · ∥x − x⋆∥².Source: §A.1 · p. 28, §A.2 · p. 29
A.2 Proof of Lemma A.2
- A local quadratic bound on the remainder R(x) supports the almost-sure argument, which applies a recursive estimate and then the Kronecker lemma.The argument uses stopping times and requires a finite random radius within which the iterates remain.Source: §A.2 · pp. 28–29
A.3 Proof of Lemma A.3
This proof controls normalized accumulated error terms using martingale convergence and local bounds. The next lemma applies a convex-function comparison result under local conditions near the solution.
A.3 Proof of Lemma A.3
- The proof localizes the error variables within a radius r and bounds their size using the distance to x⋆ and sample-dependent Lipschitz terms.The argument uses stopping times and truncation to establish convergence in probability before concluding almost-sure convergence.Source: §A.3 · pp. 29–30
- Several normalized accumulated error terms are shown to converge or vanish almost surely, using martingale arguments and bounds on their increments.The proof establishes convergence of the normalized sums involving V_i,r and ζ_i, then uses continuity to obtain the stated almost-sure result.Source: §A.3 · pp. 30–31
A.4 Proof of Lemma A.4
- Under ||x−x⋆||≤ε/4 and ||x₀−x⋆||≤ε/4, Lemma A.8 chooses γ=1/2||x−x₀||≤ε/4; then ||x−b x||≤2γ≤ε/2 implies ||b x−x⋆||≤3ε/4<ε.Source: §A.4 · p. 31
A.5 Proof of Lemma A.6
The proof controls the model-gradient error by combining local gradient comparison with bounds on iterate movement and accumulated terms. A technical recursion bound is used to support those estimates.
A.5 Proof of Lemma A.6
- When consecutive iterates lie near x⋆, the model-gradient discrepancy is controlled by Lemma A.4, and the proof shows the relevant terms vanish almost surely.The argument uses the single-step movement bound and bounds on sums involving sampled Lipschitz constants.Source: §A.5 · p. 32
- The proof bounds accumulated error terms using finite second moments and a stepsize schedule α_k = α₀k^-β with β ∈ (1/2, 1).On bounded iterates, the Robbins-Siegmund lemma yields convergence of the auxiliary sequence Z_k to a finite random variable.Source: §A.5 · p. 32
A.6 Proof of Lemma A.7
- When λα₁ ≤ 1, inequality (22) allows C₀ = 1, yielding the lemma’s second result; decreasing αₖ also ensures λαₖ ≤ 1 for all k > K₀ for some K₀.Source: §A.6 · pp. 32–33
B.1 Proof of Lemma 4.1
The proof bounds the iterate’s distance to an optimizer by combining the model condition with the unconstrained model minimizer and a guarded stepsize.
B.1 Proof of Lemma 4.1
- The model lower bound and unconstrained minimizer yield an inequality controlling the update’s distance to an optimizer.The proof assumes f(x⋆; s)=0 for every optimizer and uses Condition (C.iii).Source: §B.1 · p. 33
- The guarded stepsize makes the model term equal fk−λk∥gk∥².This identity is used to obtain the subsequent distance bound.Source: §B.1 · p. 33
- When fk/∥gk∥²≤αk, the guarded stepsize is λk=fk/∥gk∥².Source: §B.1 · p. 34
B.2 Proof of Proposition 2
The proof uses bounds on distance to the solution set to establish convergence, including an almost-sure conclusion under the stated assumptions.
B.2 Proof of Proposition 2
- Under Assumption A4, Lemma 4.1 supplies bounds for Dk, the distance from xk to the solution set, with D1≥Dk.The proof uses that Dk is measurable with respect to Fk−1.Source: §B.2 · p. 34
- For β>0, the proof uses that the partial sums of the stepsizes grow on the order of k^(1−β).The bound is stated up to constants depending on α0, β, λ0, and λ1.Source: §B.2 · p. 34
- The proof handles β=0 separately from β>0, noting that the β=0 case is similar.Source: §B.2 · p. 34
- The proof obtains an almost-sure convergence conclusion by applying the Robbins–Siegmund lemma to Vk.The argument uses that the relevant coefficient is eventually zero with probability one and is Fk−1-measurable.Source: §B.2 · p. 34
B.3 Proof of Lemma 4.2
The proof invokes boundedness and a distributional nondegeneracy condition on random vectors, then uses a VC argument to obtain a high-probability bound.
B.3 Proof of Lemma 4.2
- The proof sets Δ=x−x⋆ and uses that fi(x⋆)=0.Source: §B.3 · p. 34
- The random vectors ai are assumed to satisfy ∥ai∥2≤M.Source: §B.3 · p. 35
- Their distribution also satisfies P(|⟨ai,Δ⟩|≥c∥Δ∥2)≥pc>0; a VC-dimension argument gives a bound with probability at least 1−e^(−t).The proof states that the linear-function class has VC-dimension O(n).Source: §B.3 · p. 35
C.1 Proof of Proposition 4
The proof derives expected objective bounds by applying a one-step inequality, summing over iterations, and using convexity and boundedness assumptions.
C.1 Proof of Proposition 4
- The one-step inequality bounds expected squared distance by its current value, minus αk times the objective gap, plus αk²M²/2.It is stated conditionally on Fk−1.Source: §C.1 · p. 35
- Summing and telescoping the inequality, then dividing by the stepsize sum and using convexity, gives the proposition’s first result.Source: §C.1 · p. 35
- For the second result, the proof sums the rearranged inequality and uses the assumed bound on squared distance, followed by Jensen’s inequality.The excerpt identifies the assumed bound as R².Source: §C.1 · p. 35
C.2 Proof of Lemma 5.1
The proof derives a one-step bound involving squared distances, covariance terms, and the sampled model gap. It then uses Young’s inequality and a choice of η_k based on λmax(Σ_k) to obtain a bound on the next iterate’s distance.
C.2 Proof of Lemma 5.1
- Inequality (25) relates the next iterate’s squared distance and covariance-weighted error to the previous distance, sampled model gap, step norm, and covariance terms.Source: §C.2 · pp. 35–36
- Young’s inequality gives an upper bound on the next squared distance involving I − α_k(1 − η)Σ_k and the sampled model gap.Source: §C.2 · p. 36
- Choosing η_k = 2α_kλmax(Σ_k)/(1 + 2α_kλmax(Σ_k)) yields the stated bound on the next squared distance.Source: §C.2 · p. 36
- The proof applies Lemma 3.2 with y = x⋆ and then takes expectations, using E[⟨f′(x⋆; S), x⋆−x⟩] ≤ 0 for all x.Source: §C.2 · p. 36