PaperlayerView exact revision on arXiv

Source-linked AI summary

ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization

Nhan H. Pham, Lam M. Nguyen, Dzung T. Phan, Quoc Tran-Dinh

arXiv:1902.05679v2math.OCcs.LGstat.ML

TL;DR

The paper addresses stochastic composite nonconvex optimization in both finite-sum and expectation settings. It proposes a SARAH-based proximal-gradient framework with averaging and flexible sampling and step-size choices. The authors report best-known theoretical complexity bounds and competitive or superior empirical performance, especially in the single-sample case.

  • Problem

    Stochastic composite nonconvex optimization requires methods covering both finite-sum and expectation settings while closing complexity gaps under standard smoothness assumptions.

  • Method

    The framework combines the SARAH estimator with proximal-gradient and averaging steps, supporting constant or adaptive step-sizes and single-sample or mini-batch updates.

  • Results

    The authors establish best-known complexity bounds across the covered cases and report methods that are comparable to or outperform existing methods, especially in the single-sample case.

  • Takeaways & Limitations

    The framework provides flexibility to trade off step-sizes and mini-batch sizes while extending stochastic proximal-gradient methods to composite applications such as neural-network training.

  • Takeaways & Limitations

    The expectation-case guarantee relies on bounded variance, and one stated best-known complexity applies when σ satisfies a specific upper-bound condition.

Abstract

from arXiv · show

We propose a new stochastic first-order algorithmic framework to solve stochastic composite nonconvex optimization problems that covers both finite-sum and expectation settings. Our algorithms rely on the SARAH estimator introduced in (Nguyen et al, 2017) and consist of two steps: a proximal gradient and an averaging step making them different from existing nonconvex proximal-type algorithms. The algorithms only require an average smoothness assumption of the nonconvex objective term and additional bounded variance assumption if applied to expectation problems. They work with both constant and adaptive step-sizes, while allowing single sample and mini-batches. In all these cases, we prove that our algorithms can achieve the best-known complexity bounds. One key step of our methods is new constant and adaptive step-sizes that help to achieve desired complexity bounds while improving practical performance. Our constant step-size is much larger than existing methods including proximal SVRG schemes in the single sample case. We also specify the algorithm to the non-composite case that covers existing state-of-the-arts in terms of complexity bounds. Our update also allows one to trade-off between step-sizes and mini-batch sizes to improve performance. We test the proposed algorithms on two composite nonconvex problems and neural networks using several well-known datasets.

1. Introduction

The paper develops a SARAH-based stochastic proximal-gradient framework for composite nonconvex optimization in finite-sum and expectation settings. It combines averaging, flexible constant or adaptive step-sizes, and adjustable sampling to target best-known complexity bounds.

  • Problem setting: The framework targets stochastic composite nonconvex problems in both expectation and finite-sum formulations, including regularized empirical risk minimization.The composite formulation includes a smooth stochastic objective term and a proper, closed, convex regularizer; the finite-sum case is common in machine learning and finance.
  • Algorithmic framework: The method uses the SARAH recursive estimator with a proximal-gradient step and an additional averaging step.The averaging step evaluates the proximal step at the averaging point, distinguishing the method from related stochastic proximal-gradient schemes.
  • Complexity: In finite-sum problems, the method reaches a complexity bound matching the lower-bound worst-case complexity up to a constant factor when n ≤ O(...).The framework also offers nearly optimal complexity in another regime and retains the same number of proximal-operator calls as ProxSVRG and ProxSVRG+.
  • Complexity: In expectation problems, the method achieves the best-known complexity under smoothness and bounded variance assumptions, for both single-sample and mini-batch cases.The composite expectation result is stated for ε-stationary points in expectation and depends on the variance bound σ^2.
  • Algorithmic framework: The framework supports constant and adaptive step-sizes, full-gradient or mini-batch outer updates, and single-sample or mini-batch inner iterations.The inner mini-batch size can be selected flexibly, while adaptive step-sizes increase along inner iterations rather than diminish.
  • Practical flexibility: The method allows trade-offs among step-sizes, epoch length, and batch sizes, while experiments report comparable or better performance than existing methods, especially with single samples.The paper applies the framework to composite problems including sparsity or weight constraints and to neural-network training.

2. Mathematical tools and preliminary results

This section establishes notation, assumptions, stationarity criteria, and stochastic gradient estimators used to analyze composite nonconvex optimization.

  • Assumptions: The analysis assumes objectives are bounded below, with a proper closed convex regularizer whose domain intersects the objective domain.
  • Assumptions: The objective term satisfies L-average smoothness, which is weaker than requiring every finite-sum component to have the same individual smoothness bound.For finite sums, average smoothness yields an expected squared-gradient-difference bound; individual smoothness implies this condition.
  • Assumptions: Expectation problems additionally assume uniformly bounded stochastic-gradient variance, while finite-sum problems may use full gradients when the batch contains all samples.The framework also applies to online settings through the bounded-variance formulation.
  • Optimality conditions: Stationarity is characterized through the gradient mapping, which reduces to the ordinary gradient when the regularizer is zero.The target is an ε-approximate stationary point measured through this mapping.
  • Stochastic estimators: The standard single-sample estimator is unbiased but has fixed variance, whereas SVRG is unbiased with variance reduced around snapshot points.
  • Stochastic estimators: SARAH provides a biased recursive estimator with variance-reduction properties, and mini-batches interpolate between stochastic estimates and full gradients.When the batch size equals n in the finite-sum setting, the estimator becomes the exact full gradient and the corresponding variance terms vanish.

3. ProxSARAH framework and convergence analysis

ProxSARAH combines stochastic recursive gradient estimators with a proximal step and an additional averaging step, supporting finite-sum and expectation settings with constant or adaptive step-sizes. Its analyses provide best-known or nearly optimal complexity bounds under the stated assumptions, while exposing trade-offs among step-size, mini-batch size, and epoch length.

  • Framework: ProxSARAH is a unified framework for stochastic composite nonconvex optimization using recursive SARAH gradient estimators.The framework is specified for both finite-sum and expectation problems.
  • Framework: The method performs a proximal update followed by an additional weighted averaging step, distinguishing it from SARAH and vanilla proximal gradient variants.When ψ = 0, ProxSARAH reduces to SARAH with an effective step-size γ_tη_t.
  • Step-sizes: γ_t = 1/(L√(ωm)) and η_t = 2√(ωm)/(4√(ωm)+1) provide a constant-step-size choice tied to the mini-batch size and epoch length.The analysis derives these parameters from inner-loop estimates and a descent property.
  • Algorithm design: The algorithm uses outer snapshots and inner single-sample or mini-batch updates, with fixed inner mini-batch sizes in the analyzed variants.Outer batches may use full gradients or mini-batches, while inner loops support a broad range of mini-batch sizes.
  • Complexity and trade-offs: The finite-sum analysis matches a lower-bound complexity up to a constant factor, while the non-composite specialization matches SPIDER in complexity.The framework also permits step-size and mini-batch trade-offs, and its single-sample step-size exceeds ProxSVRG's.

4. Adaptive methods for non-composite problems

The non-composite specialization modifies ProxSARAH's update and uses recursively computed adaptive step-sizes for finite-sum and expectation problems. The finite-sum variant attains nearly optimal complexity, while the adaptive rule can reach a large terminal step-size 1/L.

  • Specialization: The non-composite specialization sets ψ = 0 and modifies the analysis to exploit an additional inner-loop term.It applies to both finite-sum and expectation instances.
  • Adaptive update: The adaptive step-size η̂_t is computed backward from t = m to t = 0, with the recursion specified for both problem settings.The finite-sum and expectation cases use different ρ values determined by their mini-batch structures.
  • Finite-sum case: The finite-sum variant requires at most 2L[f(ŵ_0)−f⋆]√n/ε^2 outer iterations to reach an ε-stationary point in expectation.This bound is stated for full-gradient snapshots with m set proportional to √n.
  • Adaptive update: The adaptive rule increases the step-size toward η̂_m = 1/L, avoiding the relatively small constant step-size used in the cited prior finite-sum method.The cited prior method studies only the finite-sum problem.
  • Complexity: The finite-sum non-composite variant achieves nearly optimal complexity by matching the cited lower-bound complexity up to the stated regime.The result applies when n ≤ O(...), as specified in the passage.

5. Numerical experiments

The numerical experiments evaluate ProxSARAH variants against established methods on constrained nonconvex, sparse classification, and neural-network problems. Across settings, adaptive or mini-batch ProxSARAH variants generally perform strongly, with dataset- and loss-dependent differences.

  • Experimental setup: The experiments implement eight ProxSARAH variants and compare them with ProxSVRG, ProxSpiderBoost, ProxSGD, and ProxGD.Implementations use single-sample and mini-batch configurations, with experiments run on CPU and GPU systems.
  • 5.1 Nonnegative principal component analysis: ProxSARAH-A-v1 outperforms ProxSARAH-v1 and other methods in single-sample tests on mnist, rcv1-binary, and real-sim.ProxSVRG is slow because its theoretical step-size 1/(3nL) is small.
  • 5.1 Nonnegative principal component analysis: ProxSpiderBoost is comparable with ProxSARAH-A-v2 in mini-batch tests, while ProxSGD saturates near 10^-5 relative objective accuracy.ProxSARAH variants with large γ resemble ProxSpiderBoost in performance.
  • 5.2 Sparse binary classification with nonconvex losses: ProxSARAH-A-v2 is most effective on the sparse-classification mini-batch tests and preserves the best-known complexity O...Adaptive variants normally outperform corresponding fixed-step-size variants, while ProxSpiderBoost also performs well.
  • 5.2 Sparse binary classification with nonconvex losses: On large datasets, ProxSARAH-A-v2 achieves the best performance, while ProxSpiderBoost also performs well and ProxSVRG is comparable with selected ProxSARAH variants.The large-dataset comparison uses url_combined, avazu-app, and kddb-raw.
  • 5.3 Feedforward Neural Network Training problem: For neural-network training, ProxSARAH variants achieve lower and less oscillatory gradient-mapping norms than ProxSGD in the reported comparisons.On the mnist example, ProxSGD performs best for training loss and test accuracy, while ProxSVRG is slower than ProxSpiderBoost.

6. Conclusions

The paper presents ProxSARAH as a unified stochastic proximal-gradient framework for composite expectation and finite-sum problems. The methods provide step-size and mini-batch flexibility, and experiments find performance comparable to or better than existing methods, especially with single samples.

  • 6. Conclusions: ProxSARAH unifies stochastic proximal-gradient methods for composite expectation and finite-sum problems using the SARAH estimator and an additional averaging step.The framework differs from existing methods such as ProxSVRG and ProxSpiderBoost through this averaging step.
  • 6. Conclusions: The methods allow trade-offs between step-sizes and mini-batch sizes to obtain good practical performance.This flexibility is presented as a practical consequence of the framework.
  • 6. Conclusions: Numerical experiments show performance comparable to or better than existing methods, especially in the single-sample case.This conclusion summarizes the reported experimental comparisons.

Appendix A. Technical lemmas

Appendix A supplies technical lemmas and proofs supporting the stochastic-estimator analysis and step-size construction. It includes conditions for constant and increasing adaptive step-sizes and completes the relevant derivations.

  • Technical lemmas: The appendix provides missing proofs for Lemma 2 and Lemma 10 used in the analysis.It also states that the full proof of the Section 3 results is provided separately.
  • Technical lemmas: The technical conditions include a sequence inequality involving γ_t, δ, and L that must hold across inner iterations.The stated condition is j=t+1 γ_j − δ + Lγ_t ≤ 0 for t=0,...,m−1.
  • Technical lemmas: The adaptive construction yields increasing step-sizes satisfying γ_0 < γ_1 < ··· < γ_m.The appendix also gives a lower bound for γ_0.
  • Technical lemmas: For constant step-sizes, setting γ_t := γ reduces the required condition to a quadratic equation whose positive solution determines γ.The resulting expression is derived by solving νL^2γ^2m − δ + Lγ = 0.
  • Technical lemmas: The proofs analyze recursive stochastic-gradient differences using conditional expectations and the update rule.These steps establish the estimator properties used in the convergence analysis.

Appendix B. The proof of technical results in Section 3

Appendix B states that it provides the complete proofs of the results in Section 3. It serves as the proof supplement for the main convergence analysis.

  • Proofs of Section 3: Appendix B provides the full proof of the results presented in Section 3.The statement identifies the appendix as the proof supplement for the main theoretical results.

B.1 The proof of Lemma 3: The analysis of the inner loop

The inner-loop proof combines smoothness, proximal optimality, nonexpansiveness, and expectation arguments to derive the lemma’s final inequality. It treats finite-sum and expectation cases separately before combining them through a shared parameterization.

  • Initial inequalities: The proof begins from the L-smoothness of f and the proximal-gradient mapping of F.It also invokes the nonexpansiveness of proxηψ to control successive iterates.
  • Initial inequalities: Proximal optimality and auxiliary positive parameters are used to transform intermediate inequalities into bounds on the inner-loop terms.The argument introduces rt and ct and combines scaled inequalities across the proof.
  • Case analysis: After summing over t and taking full expectations, the proof substitutes the resulting estimate into the preceding inequality to obtain the claimed bound.The final step identifies the resulting expression with equation (24).
  • Case analysis: The analysis handles |Ω| = n and |Ω| ≠ n separately, corresponding to the finite-sum and expectation settings.The two cases use different expressions for ρ before the resulting bounds are combined.

B.2 The proof of Lemma 4: The selection of constant step-sizes

The constant-step-size proof fixes the auxiliary parameters and synchronizes coefficients so that the aggregate term Tm is nonpositive. It then derives an admissible constant choice of η and γ.

  • Parameter selection: The proof fixes ct = rt = 1, γt = γ ∈ (0, 1], ηt = η > 0, and st = γ.These constants define the setting for the subsequent coefficient conditions.
  • Parameter selection: The finite-sum and expectation cases use separate expressions for ρ before being substituted into the lemma’s inequality.The proof then simplifies the resulting condition to a requirement involving Tm.
  • Coefficient conditions: The parameters are chosen so that Tm ≤ 0, using synchronized coefficients of the terms indexed by a(s).The proof rewrites Tm and imposes conditions on the coefficient sequences.
  • Coefficient conditions: The step-size conditions require 2η^−1 − Lγ − 3 ≥ 0, and setting the corresponding expression to 1 yields η = 2/(Lγ + 4).Because Lγ > 0, the proof further bounds η by 1/2.
  • Conclusion: With this step-size choice, the proof derives the final constant-step-size estimate.The resulting inequality is identified with the stated result.

B.3 The proof of Theorem 5: The adaptive step-size case

The adaptive-step-size proof selects parameter sequences to cancel coefficient terms and maintain the required inequality. It then specializes the construction to obtain a gradient-evaluation complexity bound.

  • Adaptive parameter construction: The proof chooses parameters so that Tm ≤ 0 and imposes a recurrence linking γj, δ, and Lγt.The adaptive construction uses ηt = η ∈ (0, 2/3) and δ := 2/η − 3 > 0.
  • Adaptive parameter construction: The resulting sequence satisfies δ/[L(1 + ωηδm)] < γ0 < γ1 < ··· < γm.The proof also defines the aggregate quantity Σm from this sequence.
  • Theorem specialization: For the theorem’s specialization, δ = 1 and ωη = 3(n−b̂)/[2b̂(n−1)].The proof then sets p(s−1)m+t := γt SΣm and bs = n.
  • Complexity bound: When b̂ ≤ √n, the proof bounds the terms involving ωm and substitutes that bound into the estimate from equation (31).This produces the displayed gradient-evaluation estimate involving 6L√n[F(ẽw0) − F⋆]/ε^2.
  • Complexity bound: The resulting stochastic-gradient complexity is stated as Tgrad = O(…).The cited passage gives the asymptotic form but not the complete expression in the extracted text.

B.4 The proof of Theorem 6: The constant step-size case

The constant-step-size proof applies Lemma 4 with fixed γ and η, updates the associated estimate, and then derives a stochastic-gradient complexity bound after choosing the epoch length.

  • Constant-step-size specialization: The proof fixes (γt, ηt) = (γ, η) for every inner-loop index and applies Lemma 4 to update the bound.This establishes the constant-step-size specialization used in the remainder of the proof.
  • Constant-step-size specialization: The updated estimate contains the variance term 4(m + 1)σ̄(s).The extracted passage preserves this term as part of the resulting bound.
  • Complexity derivation: With T := (m + 1)S and bs = n, the proof converts the estimate into a total gradient-evaluation bound.The argument uses the full-batch setting bs = n for the stated specialization.
  • Complexity derivation: The proof lower-bounds γη^2 using ωm and then sets m := ⌊n/b̂⌋ to overestimate the remaining expression.This parameter choice is used to guarantee the required bound on the expected objective measure.
  • Complexity derivation: The final step estimates Tgrad after relating the bound to F(ẽw0) − F⋆.The extracted passage states the role of Tgrad but omits the complete final formula.

B.5 The proof of Theorem 7: The expectation problem

The proof derives convergence bounds for the expectation-case algorithm by selecting parameter updates and summing per-iteration inequalities. It then specializes these bounds to obtain outer-iteration and stochastic-gradient evaluation estimates.

  • Parameter choices: The proof fixes ct = rt = 1 and sets ρ := 1/ˆb, yielding an adaptive update with θ < 3.The resulting sequence satisfies 1/[L(1+ρm)] < ˆη0 < ˆη1 < ··· < ˆηm.
  • Convergence bound: The analysis lower-bounds Σm by 2(m+1)/[L(√(2ρm+1)+1)] to simplify the convergence inequalities.This bound is used after substituting estimates and applying the update defined in (40).
  • Expectation setting: For the expectation problem, the proof chooses b := 75σ2/(8ε2) and m := σ2 ˆb/ε2.These choices follow from the conditions needed to guarantee the preceding bound.
  • Complexity: The resulting outer-loop bound is S := 4Lσ2[F( ew0) − F⋆]/ε2, followed by a bound on stochastic gradient evaluations.The proof expresses the evaluation count as Tgrad := Sb + 2S(m+1)ˆb before simplifying it further.
Loading 1902.05679v2…