Source-linked AI summary
On Graduated Optimization for Stochastic Non-Convex Problems
Elad Hazan, Kfir Y. Levy, Shai Shalev-Shwartz
TL;DR
Graduated optimization is popular for non-convex problems, but rigorous convergence analysis and stochastic-setting results have been limited. This paper analyzes a first-order graduated method for σ-nice functions and extends it to noisy value feedback, reporting theoretical guarantees and initial MNIST evidence of accelerated neural-network training.
Problem
Graduated optimization is popular for non-convex optimization, but the paper identifies gaps in convergence analysis and in understanding its use with noisy feedback.
Source: §1 · p. 1Method
The paper characterizes σ-nice functions and analyzes a graduated algorithm that accesses smoothed objectives by sampling, with noisy-gradient and noisy-value variants.
Source: §1 · p. 2, §4 · p. 4, §4.2 · p. 6Results
The noisy-gradient method guarantees ε-optimality in O(1/σ^2ε^2) iterations on σ-nice functions, while the value-feedback variant guarantees it in O(d^2/σ^2ε^4).
Source: §1 · p. 2Takeaways & Limitations
Initial MNIST experiments support the theoretical guarantees and report accelerated convergence in neural-network training.
Source: §1 · p. 2The convergence guarantees concern σ-nice functions, and whether σ-niceness is necessary or can be weakened remains open.
Source: §2 · p. 3, §8 · p. 16
Abstract
from arXiv · showhide
The graduated optimization approach, also known as the continuation method, is a popular heuristic to solving non-convex problems that has received renewed interest over the last decade. Despite its popularity, very little is known in terms of theoretical convergence analysis. In this paper we describe a new first-order algorithm based on graduated optimiza- tion and analyze its performance. We characterize a parameterized family of non- convex functions for which this algorithm provably converges to a global optimum. In particular, we prove that the algorithm converges to an {\epsilon}-approximate solution within O(1/\epsilon^2) gradient-based steps. We extend our algorithm and analysis to the setting of stochastic non-convex optimization with noisy gradient feedback, attaining the same convergence rate. Additionally, we discuss the setting of zero-order optimization, and devise a a variant of our algorithm which converges at rate of O(d^2/\epsilon^4).
1 Introduction
Graduated optimization addresses local optima by optimizing successively finer smoothed versions of a non-convex objective. The paper analyzes a gradient-based method, characterizes functions supporting global convergence, and extends the approach to value-only feedback.
1 Introduction
- Non-convex objectives, including those arising in deep-network training, can be multimodal, and convex-optimization machinery may lead to local optima.The introduction frames the need for methods that address local optima in these settings.Source: §1 · p. 1
- Graduated optimization smooths the objective, then refines it in stages, initializing each finer problem from the previous stage's solution.The initial coarse-grained problem is described as easier to solve.Source: §1 · p. 1
- Prior analysis lacked rigorous running-time guarantees or conditions for global convergence, and Gaussian-kernel smoothing was considered prohibitively inefficient in high dimensions.The paper also identifies a lack of analysis for stochastic feedback, where only noisy gradients or values are available.Source: §1 · p. 2
- The paper characterizes σ-nice non-convex multimodal functions and gives a stochastic gradient-update algorithm with an O(1/σ^2ε^2) iteration guarantee.The algorithm accesses smoothed objectives by random sampling and requires only a noisy gradient oracle.Source: §1 · p. 2
- For noisy value-oracle access, a zero-order variant guarantees an ε-optimal solution within O(d^2/σ^2ε^4) iterations.This setting is also called bandit feedback.Source: §1 · p. 2
1.1 Related Work
- Prior continuation applications were task-specific and lacked solution guarantees; Mobahi and Fisher III (2015b) assumed efficient smoothing and optimization and guaranteed only fixed precision.The paper contrasts its arbitrarily precise solutions with that fixed-precision guarantee.Source: §1.1 · p. 3
2 Setting
The setting is non-convex loss minimization over a convex domain, evaluated by the excess loss of the final chosen point. It considers both noisy gradient and noisy value feedback.
2 Setting
- The objective is a non-convex loss f over a convex set K ⊆ R^d, queried for T rounds before selecting a final point x̄_T.Performance is measured by the excess loss, defined after the final-point selection.Source: §2 · p. 3
- The target class is σ-nice loss functions, for which algorithms are sought that achieve ε-excess loss with high probability in poly(1/ε) rounds.The passage points to Section 4.2 for the characterization of σ-niceness.Source: §2 · p. 3
- The setting includes noisy gradient feedback and noisy value (bandit) feedback, each formed by adding noise to the queried objective information.The gradient noise is specified as independent, zero-mean, and bounded; the value-feedback passage is truncated after its noise notation.Source: §2 · p. 3
3 Preliminaries and Notation
The preliminaries establish notation for Euclidean balls and spheres and introduce strong convexity over a convex set. They also state an inequality for a minimizer of a strongly convex function.
3 Preliminaries and Notation
- B and S denote the unit Euclidean ball and sphere in R^d, while B_r(x) and S_r(x) denote radius-r balls and spheres centered at x.The notation section also uses u ∼ A for a random variable uniformly distributed over A.Source: §3 · pp. 3–4
3.1 Strong-Convexity
- A function is σ-strongly convex over K according to Definition 3.1, and the text states an inequality for a minimizer over K.The stated justification combines strong convexity with the condition ∇F(x*)⊤(x − x*) ≥ 0 for all x ∈ K.Source: §3.1 · p. 4
4 Smoothing and σ-Nice functions
The section develops local smoothing and an efficient sampling approach to access smoothed gradients, then characterizes σ-nice functions whose structure supports graduated optimization.
4.1 Smoothing
- Local averaging constructs progressively finer smoothed versions of the objective function.The δ-smooth version is introduced for an L-Lipschitz function.Source: §4.1 · p. 4
4.1.1 Implicit Smoothing using Sampling
- Sampling gradients or values provides unbiased, bounded estimates of the smoothed gradient, including with noisy feedback.The oracle assumes queries and function bounds remain valid in K + δB.Source: §4.1.1 · pp. 5–6
4.2 σ-Nice Functions
- σ-nice functions combine centering and local strong convexity of the smoothed function, so optimizing at scale δ is a useful start at scale δ/2.The section illustrates a one-dimensional σ-nice function and its smoothed versions.Source: §4.2 · p. 6, Figure 3 · p. 7
5 Graduated Optimization with a Gradient Oracle
The gradient-oracle algorithm applies stochastic optimization to successively smoothed objectives. Under the stated σ-nice and Lipschitz conditions, it achieves an ε-optimal point with high probability.
5 Graduated Optimization with a Gradient Oracle
- Õ(1/σ²ε²) rounds suffice for Algorithm 1 to output an ε-optimal point with probability greater than 1 − p.The guarantee assumes a convex decision set and an L-Lipschitz σ-nice objective.Source: §5 · p. 7
- Each epoch uses SGOG estimates to run Suffix-SGD on a smoothed objective, initializing from the point reached in the previous epoch.The epoch optimization proceeds until the iterate is close enough to the next smoothed objective's minimizer.Source: §5 · p. 7
5.1 Analysis
- Suffix-SGD's guarantee applies when its oracle returns unbiased, bounded gradient estimates for a σ-strongly convex objective.The section uses this result to analyze each smoothed objective's epoch.Source: §5.1 · pp. 8–9
- With probability at least 1 − p, each epoch's smoothed objective is σ-strongly convex on its restricted set, which contains its minimizer.The analysis allocates failure probability below p/M to each of M epochs.Source: §5.1 · pp. 9–10
6 Graduated Optimization with a Value Oracle
The value-oracle variant uses sampled value feedback to estimate smoothed gradients. For bounded, L-Lipschitz σ-nice objectives, its stated query guarantee is Õ(d²/σ²ε⁴).
6 Graduated Optimization with a Value Oracle
- SGOV supplies unbiased, bounded estimates of the smoothed gradient from noisy value-oracle feedback.The analysis uses an estimate bound of dC/δ_m for smoothing scale δ_m.Source: §6 · p. 11, §6.1 · p. 11
- Õ(d²/σ²ε⁴) rounds suffice for Algorithm 3 to output an ε-optimal point with probability greater than 1 − p.The theorem assumes a convex decision set, an L-Lipschitz σ-nice objective, and max_x |f(x)| ≤ C.Source: §6 · p. 11
6.1 Analysis
- The analysis establishes that each smoothed objective is σ-strongly convex on its restricted set, which contains its minimizer.The proof is described as similar to the gradient-oracle analysis.Source: §6.1 · p. 11
7 Experiments
The experiments train a single-hidden-layer neural network on down-sampled MNIST and examine whether smoothing helps optimization escape high-loss stall points. GradOptG progresses quickly and yields a much better solution than MSGD.
7 Experiments
- The test case is a single-hidden-layer network with 30 units, trained on 10 × 10 down-sampled MNIST images using ReLU and square loss.The experimental setup follows Dauphin et al. (2014).Source: §7 · p. 13
7.1 Smoothing the NN
- MSGD frequently stalls at relatively high loss, and the stall point lies in a narrow valley that obscures the best-found weights x*.The objective around x* appears strongly convex in the direction of the stall point.Source: §7.1 · pp. 13–14
- At δ = 3 smoothing leaves the valley but nudges the gradient toward x*; at δ = 7 it dissolves the valley and directs the gradient toward x*.Figure 4 compares the objective near a stall point at δ = 0, 3, and 7.Source: §7.1 · p. 14, Figure 4 · p. 14
7.2 Graduated Optimization of NN
- Fixed smoothing trades convergence speed against solution quality: smaller δ converges more slowly but reaches a better solution than larger δ.Larger δ produces sharper optimization leaps, while smoothing increases bias and can leave higher-error solutions.Source: §7.2 · pp. 14–15
- GradOptG progresses very fast and yields a much better solution than MSGD.The comparison starts with δ = 7 and decays smoothing according to GradOptG.Source: Figure 6 · p. 15, §7.2 · p. 15
8 Discussion
The paper presents a family of non-convex functions that can be efficiently optimized through graduated optimization and gives a rigorous first-order analysis in the stochastic setting. The discussion frames σ-niceness and faster methods as open directions.
8 Discussion
- The paper describes non-convex functions that admit efficient graduated optimization and gives the first rigorous analysis of a first-order algorithm in the stochastic setting.The authors characterize this as an initial step toward provable non-convex optimization.Source: §8 · pp. 15–16
- Whether σ-niceness is necessary for first-order convergence to a global optimum, or can be replaced by a more lenient property, remains open.The authors also ask whether the smoothing-to-strong-convexity or centering parameters in the two σ-niceness properties can be relaxed.Source: §8 · p. 16
- Whether second-order or other methods can yield faster convergence for stochastic or offline σ-nice non-convex optimization remains an open question.Source: §8 · p. 16