The Power of Normalization: Faster Evasion of Saddle Points

1 Introduction

• Offline, Saddle-NGD reaches η-approximately local optimality in ˜O(η−3/2) iterations versus noisy-GD's ˜O(η−2), and reaches a local-minimum basin in ˜O(d3) versus ˜O(d4).Source: §1 · p. 2
• Saddle-NGD combines normalized-gradient directions with noise perturbations to approach local minima while evading saddles in strict-saddle functions.Source: §1 · p. 2
• Online tensor decomposition is the experimental setting because it has saddle points while every local minimum is global.Source: §1 · p. 2

1.1 Related Work

• Prior methods include second-order saddle avoidance and perturbed GD (Ge et al. (2015)); NGD guarantees covered convex or quasiconvex settings (Nesterov (1984); Kiwiel (2001)).Agarwal et al. (2016) gives second-order local-minimum guarantees but is practical only when Hessian-vector products can be done efficiently.Source: §1.1 · p. 3

• At each round, the procedure queries a point and receives its gradient, aiming for a point with small objective gap to a local minimum.Source: §2 · p. 3
• For a strict-saddle function, every point has a large gradient, lies near a local minimum, or is near a saddle; the local-minimum neighborhood is strongly convex.Tensor decomposition is identified as an objective family with the strict-saddle property.Source: §2 · pp. 3–4
• The assumptions include β-smoothness and ρ-Lipschitz Hessians; vector norms are ℓ2 norms and matrix norms are spectral norms.Source: §2 · p. 4

3 Saddle-NGD algorithm and Main Results

• Periodic zero-mean Gaussian perturbations accompany normalized-gradient updates, making the negative-curvature direction sufficiently large near a saddle for fast evasion.The algorithm sets the noise level to ˜Θ(η) and injects noise every ˜Θ(η^-1/2) rounds.Source: §3 · pp. 4–5
• With probability at least 1−ξ, Saddle-NGD reaches an ˜O(√η)-close local minimum in ˜O(η^-3/2) steps, versus noisy-GD's ˜O(η^-2) steps for ˜O(η)-approximate local optimality.The theorem assumes a strict-saddle, β-smooth function with ρ-Lipschitz Hessian and bounded function values, and a sufficiently small learning rate.Source: §3 · pp. 4–5
• For η=min{ηmax, ˜O(r²)}, Saddle-NGD reaches an r-close local minimum in ˜O(η^-3/2) steps, compared with noisy-GD's ˜O(d^4) steps.The analysis gives ηmax=˜O(1/d²).Source: §3 · p. 5

3.1 Stochastic Version of Saddle-NGD

• In the stochastic setting, ensuring convergence requires minibatches of size poly(1/η), so Saddle-NGD has no better guarantees than noisy-GD.In practice, its stochastic version performs better than noisy-GD even with a moderate minibatch in online tensor decomposition.Source: §3.1 · p. 6

4 Analysis Overview

• When the gradient is sufficiently large, Lemma 5 guarantees improvement in function value within one step.The condition is ∥g0∥≥β√η.Source: §4 · p. 6
• Once within r of a local minimum and with a sufficiently small gradient, the iterates remain nearby for up to ˜O(η^-3/2) steps with probability at least 1−ξ.Lemma 6 requires ∥g0∥≤β√η≤ν.Source: §4 · p. 6
• Near a saddle with λmin(∇²f(x0))≤−γ and a sufficiently small gradient, Lemma 7 gives improvement within ˜O(η^-1/2) steps with probability at least 1−ξ.The condition includes ∥g0∥≤β√η≤ν.Source: §4 · p. 7
• Lemmas 5 and 7 yield average per-round improvement of ˜Ω(η^3/2) before reaching a local minimum; Lemma 6 then keeps the iterates within ˜O(√η) of it.Smoothness converts that proximity into a function-value gap of ˜O(η).Source: §4 · pp. 6–7

5.1 Large Gradients

• For large-gradient points, the analysis uses a noisy update and requires η=˜O(1/d²) and β√η≤ν for the other scenarios.The noise contribution is bounded under this learning-rate choice.Source: §5.1 · p. 8

5.2 Local Minimum

• The local-minimum analysis assumes the starting point is within radius r of a minimum and simplifies the proof by considering noiseless updates.The general case of Lemma 6 is deferred to Appendix B.Source: §5.2 · p. 8

5.3 Saddle Points

• Near a saddle, normalized gradients act like an approximate power method on the local Hessian; noise helps seed components in negative-eigenvalue directions.When gradients are small, the most-negative-eigenvalue component grows by a factor 1+O(√η) per round, reaching a threshold within ˜O(η^-1/2) rounds.Source: Intuition and Proof Sketch · pp. 9–11

6 Experiments

• Tensor decomposition has many saddle points, yet every local minimum is also a global minimum, motivating its use in the experiments.The online setting uses sequential samples and aims to decompose a tensor represented as an expectation of multilinear operators.Source: §6 · pp. 14, 16
• Noisy-GD improves faster initially, but Saddle-NGD eventually outperforms it; the crossover occurs within ≈400 iterations for η0∈{0.05, 0.1} and after ≈2·10^4 iterations for η0=0.01.Figure 2 compares the methods on online ICA; the reported reconstruction errors average 10 runs.Source: Figure 2 · p. 15, §6 · pp. 16–17
• The ICA experiment uses dimension d=10 and compares Saddle-NGD against the noisy-GD method of Ge et al. (2015).Both methods use minibatches of size 500 for gradient estimates.Source: §6 · p. 16

7 Discussion

• The open question is whether saddle-evasion rates better than Saddle-NGD’s are achievable using only first-order information.The paper frames this question after reporting empirical and theoretical benefits of normalized gradients for a family of non-convex objectives.Source: §7 · p. 17

A Proof of Theorem 3

• Within ˜O(η^-3/2) rounds, the proof gives probability at least 1−ξ of reaching a point ˜O(√η) from a local minimum.β-smoothness then implies the objective value is ˜O(η) from the local minimum’s value.Source: A Proof of Theorem 3 · pp. 20–21
• The proof partitions points into large-gradient, saddle, and local-minimum cases, using strict-saddle structure to identify the local-minimum region.It seeks to reach that region within ˜O(η^-3/2) rounds.Source: A Proof of Theorem 3 · p. 20
• Boundedness of f converts a per-epoch success probability of at least 1/2 into success probability at least 1−ξ after Θ(log(1/ξ)) epochs.The proof also uses that, once reached, the ˜O(√η) neighborhood of a local minimum is maintained with probability at least 1−ξ.Source: A Proof of Theorem 3 · pp. 20–21

B Proof of Lemma 6 (Local Minimum)

• After a noisy update, Algorithm 1 uses noiseless updates for the following Ω(η^-1/2) rounds.Source: B Proof of Lemma 6 (Local Minimum) · p. 21
• The proof bounds the distance increase from the first noisy update using local strong convexity, a high-probability noise bound, and η ≤ Õ(1/d).The noise norm is bounded with probability at least 1−ξ, while the starting distance is O(√η).Source: B Proof of Lemma 6 (Local Minimum) · p. 22
• The distance argument uses the smoothness bound ∥g_t∥ ≤ β∥x_t−x*∥ and invokes Lemma 9.Source: B Proof of Lemma 6 (Local Minimum) · p. 22
• Within Θ(η^-1/2) noiseless updates, the distance to the local minimum decreases to β√η.The proof considers the case where the first noisy update pushes the distance beyond that threshold.Source: B Proof of Lemma 6 (Local Minimum) · pp. 21–22

B.1 Proof of Lemma 9

• The proof of Lemma 9 applies strong-convexity inequalities at x and x*, then sums the resulting equations.The passage also uses ∇F(x*)⊤(x−x*) ≥ 0 from the optimality of x*.Source: §B.1 · p. 22

C.1 Proof of Lemma 10

• The proof of Lemma 10 assumes noiseless updates for the remainder after bounding the effect of noisy rounds, then uses induction to establish its claims.Source: §C.1 · pp. 23, 25

C.2 Proof of Lemma 11

• The proof of Lemma 11 bounds the change due to noisy rounds, then combines two established relations to conclude the lemma.Source: §C.2 · pp. 25–27

C.3 Proof of Corollary 12

• The proof of Corollary 12 divides into cases according to the size of |g⁽ⁱ⁾₀| and invokes Lemma 10.It notes that including the Õ(η) factors yields similar guarantees.Source: §C.3 · pp. 27–28

C.4 Proof of Corollary 13

• The proof of Corollary 13 uses a simplified Lemma 11 bound that omits Õ(η) factors from noisy updates.The passage says retaining those factors adds a term −Õ(η^3/2 + η²T), which simplifies to −Õ(η^3/2) for T = Õ(η^-1/2).Source: §C.4 · p. 28

C.5 Proof of Lemma 14

• Under conditions (31) and (32), the gradient rises beyond 2β√η in fewer than N₀ rounds.Repeating the process for log(1/ξ) epochs gives the stated high-probability guarantee.Source: §C.5 · pp. 29–31

C.6 Proof of Lemma 15

• The proof relates f to its quadratic approximation around x₀ and establishes that f̃(x_t) ≤ f̃(x₀)−Ω(η).The proof concludes by taking η = Õ(1/d²).Source: §C.6 · pp. 31, 33