Source-linked AI summary
Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization
Saeed Ghadimi, Guanghui Lan, Hongchao Zhang
TL;DR
The paper addresses constrained nonconvex stochastic composite optimization with a differentiable component, a potentially nonsmooth convex component, and noisy gradient access. It proposes randomized mini-batch projected-gradient methods using generalized distance functions, with stated oracle-complexity guarantees and extensions to zeroth-order information.
Problem
The paper studies constrained stochastic composite problems where the objective combines a possibly nonconvex differentiable function with a possibly nonsmooth convex function, using only noisy gradients.
Method
It develops randomized stochastic projected-gradient algorithms using iteration-dependent mini-batches and a general distance function, alongside a gradient-free extension.
Results
The RSPG method preserves O(σ2/ǫ2) stochastic first-order oracle calls for obtaining a point with expected generalized projected-gradient norm at most ǫ.
Takeaways & Limitations
The framework unifies constrained composite stochastic optimization with geometry-aware projection and supports both first-order and zeroth-order stochastic information.
Takeaways & Limitations
The analysis assumes a closed convex feasible set, Lipschitz-continuous gradients, a simple convex nonsmooth component, and a finite lower objective bound.
Abstract
from arXiv · showhide
This paper considers a class of constrained stochastic composite optimization problems whose objective function is given by the summation of a differentiable (possibly nonconvex) component, together with a certain non-differentiable (but convex) component. In order to solve these problems, we propose a randomized stochastic projected gradient (RSPG) algorithm, in which proper mini-batch of samples are taken at each iteration depending on the total budget of stochastic samples allowed. The RSPG algorithm also employs a general distance function to allow taking advantage of the geometry of the feasible region. Complexity of this algorithm is established in a unified setting, which shows nearly optimal complexity of the algorithm for convex stochastic programming. A post-optimization phase is also proposed to significantly reduce the variance of the solutions returned by the algorithm. In addition, based on the RSPG algorithm, a stochastic gradient free algorithm, which only uses the stochastic zeroth-order information, has been also discussed. Some preliminary numerical results are also provided.
1 Introduction
The paper studies constrained nonconvex stochastic composite optimization with noisy gradients and develops randomized mini-batch methods to address limitations of unconstrained stochastic gradient approaches.
- Problem setting: The target problem combines a continuously differentiable, possibly nonconvex function with a simple convex component that may be nonsmooth over a closed convex set.Examples of the nonsmooth component include the l1 norm and the zero function.
- Problem setting: Only noisy gradients of the differentiable component are available through a stochastic first-order oracle.The oracle returns a stochastic gradient for each queried input, under assumptions including a finite lower bound on the objective.
- Motivation: Nonconvex stochastic programming remains limited and immature compared with the extensively studied stochastic programming literature.Earlier randomized stochastic gradient methods addressed unconstrained nonconvex problems, while their convergence was not guaranteed for constrained composite problems.
- Contributions: The RSPG algorithm uses mini-batches to solve constrained nonconvex stochastic composite problems while preserving O(σ2/ǫ2) stochastic first-order oracle calls.It returns a point whose expected generalized projected-gradient norm is at most ǫ.
- Contributions: RSPG uses a general distance function rather than only Euclidean distance, allowing the method to adapt to feasible-set geometry.The paper also presents a stochastic gradient-free extension for settings with only noisy function values.
2 Some properties of generalized projection
The paper replaces ordinary Euclidean projection with a prox-function-based generalized projection whose properties support constrained composite optimization and later algorithmic analysis.
- Prox-function and projection: A distance-generating prox-function defines a generalized projection that can exploit the geometry of the feasible set and facilitate efficient projection solutions.Different prox-functions produce different generalized distances; the Euclidean choice recovers ordinary projection.
- Properties of projection: The generalized projected-gradient mapping extends the gradient concept to constraints and nonsmooth convex terms.When the feasible set is all of Rn and h vanishes, it reduces to the ordinary gradient.
- Properties of projection: The generalized projection is Lipschitz continuous with respect to its gradient argument.The proposition gives the bound in terms of the prox-function's strong-convexity modulus α.
- Properties of projection: Projection optimality and convexity of h provide inequalities that characterize the generalized projection and bound the projected-gradient mapping.These properties are used as foundational tools for subsequent convergence proofs.
3 Deterministic first-order methods
The deterministic first-order section develops a projected-gradient method using exact gradients as the basis for the paper's stochastic algorithms.
- Deterministic first-order methods: The deterministic method assumes the exact gradient of f is available at each iterate and provides a foundation for the later stochastic first-order algorithms.It solves the composite constrained problem using projected-gradient steps.
A projected gradient (PG) algorithm
The PG algorithm generates projected iterates and outputs the one with the smallest generalized projected-gradient norm, with convergence established under bounded stepsizes.
- A projected gradient (PG) algorithm: The PG algorithm starts from x1 in X, runs for N iterations, and uses positive stepsizes to compute projected updates.The update is based on the generalized projection framework.
- A projected gradient (PG) algorithm: The algorithm outputs the iterate having the minimum norm of the generalized projected gradient.This selection rule is defined after computing the generalized projected-gradient quantities across the trajectory.
- A projected gradient (PG) algorithm: Theorem 1 allows stepsizes satisfying 0 < γk ≤ 2α/L, with strict inequality for at least one iteration.Under these conditions, the theorem provides the method's convergence bound.
- A projected gradient (PG) algorithm: With the constant policy γk = α/L, Corollary 1 gives a specialized complexity result for the PG algorithm.The corollary specializes the general convergence result to one proper constant stepsize choice.
4 Stochastic first-order methods
The paper develops stochastic first-order methods for constrained composite optimization without requiring objective convexity. Its weaker requirements also allow stochastic noise to depend on the iterates.
- The method uses noisy stochastic gradients because the exact gradient of f is unavailable.The stochastic first-order oracle supplies G(xk, ξk) at each iteration.
- The proposed RSPG algorithm is a stochastic projected-gradient method with randomized stopping, while 2-RSPG adds a post-optimization phase.The two-phase variant targets large deviations from a single RSPG run.
- The analysis does not require objective convexity and permits random noises to depend on the iterates.This relaxes a common requirement in stochastic approximation analyses.
A randomized stochastic projected gradient (RSPG) algorithm
RSPG randomly selects a stopping iteration, using mini-batch stochastic gradients, prescribed stepsizes, and a probability distribution over iterations. Its analysis establishes expected and high-probability complexity results, with two-phase post-optimization improving large-deviation behavior.
- Algorithm: RSPG samples a random termination index and averages mini-batch stochastic gradients before updating the iterate.The algorithm specifies an initial point, iteration limit, stepsizes, batch sizes, and a probability mass function for the stopping index.
- Analysis: The convergence analysis uses the stochastic projected gradient and conditional mean-zero noise properties.The proof controls projected-gradient terms by conditioning on the generated history and summing iteration-wise inequalities.
- Mini-batching: For nonconvex problems, single-sample batches may fail to guarantee convergence, motivating multiple samples at each iteration.The paper explains that mini-batching is needed because the relevant bound may remain bounded away from zero when mk=1.
- Complexity: With a fixed stochastic-oracle budget, batch size should be balanced against iteration count because both affect the resulting bounds.The number of iterations is at most N=⌊N̄/m⌋ when each iteration uses m oracle calls.
- Complexity: The prescribed stepsizes, stopping distribution, and sample count provide one strategy for convex and nonconvex stochastic programming.For smooth convex stochastic programming, the resulting rate is described as nearly optimal.
- Two-phase method: The two-phase method generates independent RSPG candidates and selects among them in post-optimization to reduce dependence on Λ.The target is an (ε,Λ)-solution satisfying a probability condition on the stochastic projected gradient.
A two phase RSPG (2-RSPG) algorithm
The 2-RSPG method combines multiple independent RSPG runs with post-optimization selection to obtain solutions with controlled projected-gradient behavior and improved large-deviation complexity.
- Optimization and selection: The algorithm runs RSPG independently across S trials, then selects the candidate with the smallest estimated projected-gradient norm.The post-optimization phase uses additional stochastic-gradient samples to estimate candidate quality.
- Oracle budget: The 2-RSPG procedure allocates at most S × N̄ oracle calls to optimization and S × T calls to post-optimization.These two phases determine the total stochastic first-order-oracle budget.
- Guarantee: Under Assumption A1, the selected output is an (ε, Λ)-solution after the parameter choices specified in Theorem 3.An (ε, Λ)-solution satisfies Prob{∥g_X(x)∥^2 ≤ ε} ≥ 1 − Λ.
- Complexity: The complexity bound can be smaller than the earlier bound by a factor of 1/[Λ^2 log^2(1/Λ)] when the second terms dominate.This comparison is stated after discarding constant factors.
- Light-tail refinement: Under the additional light-tail Assumption A2, the complexity bound for finding an (ε, Λ)-solution is further improved.The corresponding oracle-call guarantee is stated in Corollary 5.
5 Stochastic zeroth-order methods
The paper extends its stochastic projected-gradient framework to noisy function-value access by smoothing the objective and constructing approximate stochastic gradients.
- Oracle model: The zeroth-order method accesses f only through a stochastic zeroth-order oracle that returns noisy function values.The method assumes the sampled functions are continuously differentiable with Lipschitz gradients and uses the Euclidean norm.
- Randomized smoothing: Randomized smoothing defines a smooth approximation f_μ using a Gaussian perturbation with smoothing parameter μ.Different smoothing distributions yield different approximations, but this section uses a standard Gaussian vector.
- Smoothing properties: The smoothed function f_μ remains Lipschitz continuously differentiable, with a gradient Lipschitz constant depending on dimension and the original smoothness constant.The cited result gives the corresponding dimension-dependent bound.
- Gradient construction: The approximated stochastic gradient is formed from the smoothed function, and G(x_k, ξ_k) is defined as the gradient of the sampled function.The expectation is taken over both the smoothing vector and stochastic-oracle randomness.
- Algorithm: The resulting RSPGF algorithm uses only zeroth-order information to solve the constrained stochastic composite problem.It is obtained by specializing the RSPG framework to the smoothed objective.
A randomized stochastic projected gradient free (RSPGF) algorithm
RSPGF adapts RSPG to noisy function values by replacing stochastic gradients with smoothed-gradient estimates, while retaining randomized projected updates and complexity guarantees.
- Algorithmic construction: At each iteration, RSPGF calls the stochastic zeroth-order oracle in a mini-batch to construct an approximate gradient for the smoothed objective.The algorithm uses a random stopping index and prescribed stepsizes, batch sizes, and sampling distribution.
- Convergence: Theorem 4 establishes nonconvex and convex convergence bounds under Assumptions A1 and A3, with bounded gradients required for the stated result.The bounds are expressed in expectation over the stopping index, oracle randomness, and Gaussian perturbations.
- Budget allocation: Corollary 7 selects the smoothing parameter and per-iteration sample size under a fixed total SZO budget to obtain explicit complexity bounds.The resulting bounds depend on the total oracle budget, smoothing, dimension, and gradient-size parameters.
- Comparison with first-order methods: RSPGF has complexity dependence similar to first-order RSPG in the total number of stochastic-oracle calls, but additionally depends on dimension and gradient magnitude.The smoothing parameter also affects the zeroth-order bounds.
- Convex complexity: For convex problems, the zeroth-order oracle complexity can be O(n/ε^2), improving on the O(n^2/ε^2) bound cited for general convex stochastic programming.This comparison is stated for sufficiently small ε.
6 Numerical Results
Experiments evaluate RSPG and its two-phase variants on nonconvex least-squares and semi-supervised classification problems, emphasizing solution quality and variance.
- Experimental problems: The experiments study a nonconvex penalized least-squares problem and a nonconvex semi-supervised support-vector-machine problem.The second problem is reformulated with a smooth approximation and a constraint.
- Algorithmic schemes: The implementation compares RSPG, 2-RSPG, 2-RSPG-V, and corresponding RSG variants using multiple independent runs and post-optimization evaluation.The 2-RSPG implementation uses five runs, candidate selection, and an additional large evaluation sample.
- Least-squares setup: The least-squares experiments vary problem dimension across n = 100, 500, and 1,000 and noise levels across σ̄ = 0.1 and 1.They also use sparse data and assess gradient norms and recovery of true zeros.
- Variance and quality: The two-phase variants significantly reduce RSPG solution variance, and 2-RSPG-V provides better solution quality than 2-RSPG for fixed N_S.The reported explanation is that 2-RSPG-V uses more iterations for the same optimization-phase budget.
- RSPG versus RSG: RSPG solutions are reported to have less variance than corresponding RSG solutions, while their mean solution values are comparable.The paper attributes the variance difference to mini-batch stochastic-gradient approximation.
7 Conclusion
The paper proposes RSPG, a mini-batch stochastic projected-gradient method for constrained nonconvex stochastic composite optimization, with geometry-aware gradient projection. The conclusion also points to numerical evaluations summarized for the semi-supervised support vector machine problem.
- RSPG uses mini-batches at each iteration to handle constraints in nonconvex stochastic composite optimization.The method permits a more general gradient projection adapted to the geometry of the constraint set.
- Table 3 reports estimated projected-gradient norms for the semi-supervised support vector machine problem with K = 75,000.
- Table 4 reports average objective values at the solutions summarized in Table 3.