Recent Theoretical Advances in Non-Convex Optimization

1 Introduction

• General non-convex problems offer no hope of theoretical guarantees for finding a global minimizer in reasonable time, despite the practical performance of general-purpose methods.The global complexity of methods such as L-BFGS is not well understood.Source: §1 · p. 2
• The survey covers deterministic and stochastic non-convex optimization, including randomized first-order methods motivated by large-dimensional variables and datasets.Randomized methods such as stochastic gradient descent avoid scanning the full dataset at each step.Source: §1 · p. 3
• It presents structural approaches that can find global solutions and relaxations targeting stationary points or local extrema instead.It also considers broad function classes with guarantees and higher-order or derivative-free methods.Source: §1 · p. 3

2 Preliminaries

• The preliminaries frame non-convexity as arising from either the feasible set or the objective and motivate relaxations such as approximate stationarity or added assumptions.They also preview the classification of general non-convex problems.Source: §2 · pp. 3–4

2.1 Global Optimization is NP-hard

• Checking whether the constructed objective has global minimum zero is equivalent to a subset-sum problem, making even its minimum value NP-hard to find.The example uses a positive-semidefinite objective whose zero condition encodes the subset-sum instance.Source: §2.1 · p. 4

2.2 Lower Complexity Bound for Global Optimization

• A Lipschitz non-convex objective can require Ω(M^n ε^-n) iterations to find an ε-approximate global minimum; a uniform-grid method attains this lower bound.This makes high-dimensional global minimization impractical without additional assumptions.Source: §2.2 · p. 5

2.3 Examples of Non-Convex Problems

• Non-convex problems are grouped into those with hidden convexity or analytic solutions and those with provable global solutions.The survey presents this as a non-exhaustive overview of tractable formulations and applications.Source: §2.3 · p. 6

2.3.1 Problems with Hidden Convexity or Analytic Solutions

• Under restricted isometry conditions, an s-sparse solution to Ax=b is the unique minimum ℓ1-norm solution; Gaussian matrices can satisfy the restricted isometry property with stated probability.The survey also notes that sparse recovery by minimizing the ℓ0 count is NP-hard, though it may sometimes be replaced by a convex problem.Source: §2.3.1 · pp. 8–9

2.3.2 Problems with Convergence Results

• The survey’s examples of convergence-bearing problems include phase retrieval and low-rank matrix completion, with reported global optimality or nearly linear convergence results under stated assumptions.For phase retrieval, the global minimum is not clear even if one exists; cited results include alternating minimization and gradient descent guarantees for related recovery problems.Source: §2.3.2 · pp. 9–10

2.3.3 Geometry of non-convex optimization problems

• Non-convex problems with rotational or discrete symmetry include phase retrieval and related low-rank problems, and blind deconvolution and tensor decomposition, respectively.The survey attributes this classification to another survey.Source: §2.3.3 · p. 11

3.1 Unconstrained Minimization

• For L-smooth objectives, finding an ε-stationary point takes N ∼ ε^-2 iterations, and this dependence on ε and L is unimprovable for arbitrary first-order methods.Source: §3.1 · p. 12
• An approximate stationary point may be a saddle point or maximum, although adding noise can let gradient descent escape saddles and reach a local minimum for almost all initial points.Source: §3.1 · p. 12

3.2 Incorporating Simple Constraints

• With simple convex constraints, a prox-function generalizes the gradient step into a gradient mapping; a small mapping norm certifies approximate stationarity under the stated conditions.The universal method avoids knowing ν and Lν.Source: §3.2 · pp. 13–14
• The constrained stationarity guarantee does not imply a small gradient norm, so it does not conflict with the exponential lower bound for finding a global minimum.Source: §3.2 · p. 13

3.3 Incorporating Momentum for Acceleration

• Heavy-ball momentum can improve practical efficiency on ill-conditioned problems, but its theoretical guarantee is no better than gradient descent’s.Source: §3.3 · p. 15
• Line-search acceleration uses full one-dimensional relaxation and local information to make the method parameter-free and uniform across convex and non-convex smooth optimization.Inexact line-search is also allowed with an estimated sufficient accuracy.Source: §3.3 · p. 15
• Accelerated alternating minimization has optimal complexity for convex and non-convex smooth problems when blockwise minimization is explicit; negative-curvature acceleration improves first-order complexity under Lipschitz higher-derivative assumptions.Source: §3.3 · pp. 16–17

• The section treats both expectation minimization and finite-sum minimization, settings commonly arising in machine learning and mathematical statistics.Source: §4 · p. 17
• For the general stochastic non-convex setting, the best one can expect in the worst case is an approximate stationary point.Source: §4 · p. 18
• The survey presents a unified analysis of deterministic and stochastic first-order methods, then reviews SGD variants, variance-reduced methods, and adaptive stochastic methods.Source: §4 · p. 18

4.1 General View on Optimal Deterministic and Stochastic First-Order Methods for Non-Convex Optimization

• The analysis of first-order schemes is organized around tight bounds on the error between the gradient and its estimator, or the expected error.Source: §4.1 · p. 19

4.1.1 Deterministic Case

• In the deterministic case, the method stops after the derived iteration bound, which is optimal up to constant factors.Source: §4.1.1 · p. 20

4.1.2 Stochastic Case: Uniformly Bounded Variance

• With uniformly bounded variance, the stochastic bound is optimal up to constant factors, and the method outputs an iterate chosen uniformly at random.Source: §4.1.2 · p. 21

4.1.3 Stochastic Case: Finite Sum Minimization

• For finite sums with L-smooth summands, the SPIDER variant uses three component-gradient calculations per iteration up to a constant factor after its initial period.Source: §4.1.3 · pp. 21–22

4.2.1 Assumptions on the Stochastic Gradient

• Expected Smoothness provides a unified framework for stochastic-gradient assumptions, with special cases including bounded variance, growth conditions, and gradient confusion.Under this framework, the survey reports sharp rates for known special cases.Source: §4.2.1 · pp. 26–27

4.2.2 The Choice of the Stepsize

• For non-convex SGD, periodically decreasing stepsizes have theoretical support, while the theory behind warmup and cyclical schedules remains limited.Warmup increases stepsizes after initially small values; cyclical schedules vary them between lower and upper bounds.Source: §4.2.2 · p. 29

4.2.3 Over-Parameterized Models

• Under interpolation or expected strong growth, SGD can match gradient descent’s iteration complexity up to smoothness or growth factors, with line-search and stochastic Polyak variants also available.With expected strong growth, SGD can also be accelerated, and the accelerated version matches Nesterov’s iteration complexity up to the growth factor.Source: §4.2.3 · pp. 29–30

4.2.4 Proximal Variants

• Prox-SGD extends stochastic optimization to composite objectives with a smooth possibly non-convex term and a possibly nonsmooth convex regularizer.One cited analysis required large batches of order O(ε^-2); later work established the same bound without that batch-size requirement.Source: §4.2.4 · p. 31

4.2.5 Momentum-SGD

• Momentum-SGD has the same stated non-convex complexity guarantee as SGD under uniformly bounded variance, although it often performs better in practice and navigates ravines and saddle points better.The cited analysis also favors gradually reducing momentum over stepsize and gradual parameter changes over sudden ones.Source: §4.2.5 · p. 32

4.2.6 Random Reshuffling

• Random reshuffling uses a fresh random permutation each epoch, and recent analyses provide theoretical bounds that can outperform corresponding SGD bounds under stated conditions.The survey notes its gradients are biased because sampling is without replacement.Source: §4.2.6 · pp. 32–33

4.3 Variance-reduced Methods

• Variance-reduced methods target SGD’s oscillation around a solution neighborhood, which can be reduced by shrinking stepsizes or enlarging batches but at a speed or iteration-cost trade-off.The oscillation-region size is proportional to hσ^2/r.Source: §4.3 · pp. 33–34
• With batch size r=m^2/3, SAGA and SVRG achieve O(m^2/3ε^-2), improving the dependence on m by m^1/3 over gradient descent’s bound.At r=1, both guarantee only O(mε^-2), the same rate stated for gradient descent.Source: §4.3 · p. 35
• SPIDER is presented as an optimal method for the small-data regime, while SpiderBoost offers simpler analysis, larger constant stepsizes, and easier composite generalization.The survey notes SPIDER’s very small stepsize can lead to poor practical behavior.Source: §4.3 · p. 35
• Variance-reduced methods often perform worse than SGD or momentum in deep-network training, and may be unnecessary when over-parameterization or small-noise growth conditions make SGD as fast as gradient descent.The survey identifies batch normalization, data augmentation, and dropout as common training tricks associated with poor variance-reduction behavior.Source: §4.3 · pp. 35–36

4.3.1 Convex and Weakly Convex Sums of Non-Convex Functions

• For convex or weakly convex sums of non-convex functions, added structure yields tighter lower bounds than general non-convex bounds, with optimal or near-optimal methods reported for each case.The discussed cases include convex, weakly convex, or individually weakly convex summands.Source: §4.3.1 · p. 37

4.4 Adaptive Methods

• Adaptive methods are motivated by the difficulty of tuning stepsizes and batch sizes, and are described as more robust to parameter choices than other SGD or variance-reduced variants.The survey focuses on AdaGrad, Adam, and their variants.Source: §4.4 · p. 37

4.4.1 AdaGrad and Adam

• AdaGrad is robust to stepsize choice and works well with sparse data, but its stepsizes rapidly decrease in dense settings, slowing convergence.The survey says it often works well in practice with the default h=10^-2.Source: §4.4.1 · p. 38
• Despite observed practical advantages, AdaGrad, Adam, and their modifications have best-known non-convex complexity bounds that are no better than SGD’s and rely on more restrictive assumptions.The survey also notes Adam’s proof flaw led to the convergent variant AMSGrad.Source: §4.4.1 · p. 39

4.4.2 Adaptive SGD

• Adaptive Armijo-type methods for stochastic non-convex optimization achieve iteration and oracle complexities matching non-adaptive counterparts up to logarithmic factors.The approach locally estimates the Lipschitz constant and can adaptively select stepsizes; convex-problem variants can also adapt batch sizes.Source: §4.4.2 · p. 40

5.1 Polyak–Łojasiewicz Condition

• Under the PŁ condition, every stationary point is a global minimum, though minima need not be unique; for L-smooth objectives, gradient descent converges linearly to a global minimum.Source: §5.1 · pp. 41–42

5.1.1 Stochastic First-Order Methods under Polyak–Łojasiewicz Condition

• Stochastic first-order methods have complexity analyses under PŁ, with some results relying on expected-residual assumptions or bounded component gradients for Random Reshuffling.The survey summarizes these results in Table 4.Source: §5.1.1 · p. 42, Table 4 · p. 44

5.2 Star-convexity and α-weak-quasi-convexity

• For star-convex L-smooth functions, analyze convergence, while [128] gives an optimal O(α^-1 L^1/2 R ε^-1/2) iteration bound for α-weakly-quasi-convex functions.The optimality claim is supported by a matching lower complexity bound; the method also uses a logarithmic-factor-equivalent number of function and gradient evaluations.Source: §5.2 · p. 43

5.2.1 Stochastic Methods and α-weak-quasi-convexity

• For SGD under α-weak-quasi-convexity, derives bounds under an expected-residual assumption; interpolation simplifies the bound and supports convergence of a generalized stochastic Polyak stepsize.Source: §5.2.1 · p. 45

5.2.2 Further Generalizations

• Approximately homogeneous functions form a broader class covering α-weakly-quasi-convex functions, and good convex models can yield complexity similar to convex optimization.The survey also notes that many results in do not require a finite-sum structure.Source: §5.2.2 · pp. 45–46

6.1 Second-Order Methods

• Cubic regularization reaches an (ε,δ)-second-order stationary point in O(ε^-3/2) iterations, but full Hessians are difficult to compute in large-scale machine-learning problems.Hessian-vector products can be computed as efficiently as gradients in many cases; trust-region methods are another approach, and both method families extend to linear and conic constraints.Source: §6.1 · p. 46

6.2 Stochastic Second-Order Methods

• A stochastic method using gradients and Hessian-vector products finds an (ε,δ)-second-order stationary point in O(ε^-3.5) oracle evaluations, improving on SGD's O(ε^-4) rate.The survey says this matches the best-known rate for finding local minima without delicate acceleration or variance reduction; such methods also calculate fewer Hessians and can parallelize them.Source: §6.2 · pp. 48–49
• For finite sums, subsampled gradients and Hessians achieve gradient complexity ˜O(mε^-3/2∧ε^-7/2) and Hessian complexity ˜O(mε^-3/2∧ε^-5/2).The survey collects stochastic variance-reduced cubic-method rates in Table 5.Source: §6.2 · p. 49, Table 5 · p. 49

6.3 Tensor Methods

• Third-order methods have an O(ε^-4/3) rate, compared with O(ε^-3/2) for second-order methods, and are therefore faster in iteration count.Stochastic tensor methods use subsampled derivatives and tensor-vector products; the survey reports far fewer derivative computations while retaining full-batch convergence speed.Source: §6.3 · pp. 50–52
• For sum-type problems, stochastic tensor methods can sharply reduce Hessian and third-order derivative computations, but lower bounds remain far from upper bounds for second-order methods.The survey identifies variance reduction and combining tensor methods with first- or second-order methods as possible research directions.Source: §6.3 · pp. 51–53

7.1 Random Directions Gradient Estimations

• Gaussian smoothing preserves convexity and Lipschitz constants, and a non-convex scheme under a Lipschitz-continuous gradient has an expected step bound of O(n/ε^2).The convergence result concerns the smoothed function; the passage also describes noisy-oracle extensions that preserve rates for sufficiently small noise.Source: §7.1 · pp. 54–55
• Random-direction estimates can support convergence analysis, but these methods require more samples than standard finite differences, and sphere smoothing has a bound of Ω(n/θ^2 · log[(n+1)/δ]).A line-search method using estimates that satisfy the norm condition is shown to converge.Source: §7.1 · pp. 58–60

7.2 Variance-Reduced Zeroth-Order Methods

• ZO-SVRG adapts SVRG to non-convex finite-sum problems by replacing true gradients with zeroth-order estimates, whose bias complicates convergence analysis.The methods considered use random directions on a sphere or deterministic coordinate estimates.Source: §7.2 · pp. 61–62
• In tests, ZO-SVRG with random sphere directions beats its averaged-random-direction and coordinate-estimation variants in training loss versus function queries.The coordinate-estimation variant nevertheless achieves the convergence rates of the original SVRG.Source: §7.2 · p. 63
• For ZO-SVRG-Coord, replacing BSG with CFD requires n more oracle calls but yields more accurate gradient estimation, while the convergence rate stays O(1/N).Source: §7.2 · p. 64
• ZO-SPIDER-Coord replaces GSG with CFD and keeps the same convergence rate while allowing a stepsize h_k = 1/[4L] independent of ε. [134]The passage describes the larger, ε-independent stepsize as better in practice.Source: §7.2 · p. 64
• For non-stationary online optimization, residual feedback enables one-point estimation, and regret bounds also extend to the stochastic case under assumptions of the same form.The objective is time-varying, limiting the setting to one-point estimators; conventional one-point estimates can have variance that explodes as μ approaches zero.Source: §7.2 · pp. 64–65
• Experiments find one-point residual feedback performs worse than two-point feedback but better than conventional one-point feedback, with lower variance than the two-point approach. [281]The passage notes it can be used in practice, unlike two-point feedback.Source: §7.2 · p. 65

8 Globalization Techniques

• The section frames these techniques as practical routes to global performance guarantees, which remain available only for some subclasses of non-convex problems.It follows the preceding discussion of guarantees for stationary points or local extrema.Source: §8 · p. 65

8.1 Multistart Technique

• With a global-minimum attraction basin of measure μ, multistart needs an expected ˜O(1/μ) initial points; if the basin is a radius-r ball, μ ∼ r^n, making the approach impractical as n grows.The starting points are sampled uniformly on [0,1]^n.Source: §8.1 · p. 66

8.2 Multidimensional Bisection

• Multidimensional bisection selects new starting points by minimizing a Lipschitz-based minorant built from previous evaluations, using an estimate of the Lipschitz constant.In higher dimensions it is harder to implement, tends to slow as n increases, and is sensitive to the Lipschitz estimate's accuracy.Source: §8.2 · pp. 66–67

8.3 Langevin Dynamics

• Langevin dynamics has a distribution that concentrates around global minima as temperature tends to zero; discretized methods have non-asymptotic convergence results for an approximate global minimum.The cited non-asymptotic result assumes a constant temperature parameter.Source: §8.3 · p. 67