Introduction
Sharpness-Aware Minimization (SAM) was introduced to improve generalization by seeking parameters whose training loss remains low throughout a local neighborhood [12 ] . It pursues this objective through a simple two-step procedure: first perturb the parameters in a direction of increasing loss, then update the original parameters using the gradient evaluated at the perturbed point. The choice of perturbation therefore determines how the resulting update departs from ordinary gradient descent. For a differentiable objective f : R d → R f:\mathbb{R}^{d}\to\mathbb{R} f : R d → R r r r ρ \rho ρ [3 ] :
y t = x t + r ∇ f ( x t ) ∥ ∇ f ( x t ) ∥ , x t + 1 = x t − η t ∇ f ( y t ) , (SAM) y_t = x_t + r \frac{\nabla f(x_t)}{\lVert\nabla f(x_t)\rVert}, \qquad x_{t+1} = x_t - \eta_t \nabla f(y_t), \qquad\text{(SAM)} y t = x t + r ∥ ∇ f ( x t )∥ ∇ f ( x t ) , x t + 1 = x t − η t ∇ f ( y t ) , (SAM) y t = x t + ρ ∇ f ( x t ) , x t + 1 = x t − η t ∇ f ( y t ) , (USAM) y_t = x_t + \rho\nabla f(x_t), \qquad x_{t+1} = x_t - \eta_t \nabla f(y_t), \qquad\text{(USAM)} y t = x t + ρ ∇ f ( x t ) , x t + 1 = x t − η t ∇ f ( y t ) , (USAM) with radius r > 0 r > 0 r > 0 ρ ≥ 0 \rho\ge0 ρ ≥ 0 η t > 0 \eta_t > 0 η t > 0 x t x_t x t y t y_t y t
Throughout, we consider the problem
min x ∈ R d f ( x ) , f ⋆ : = inf x ∈ R d f ( x ) > − ∞ , (1) \min_{x \in\mathbb{R}^{d}} f(x), \qquad f_{\star} := \inf_{x \in\mathbb{R}^{d}} f(x) > -\infty, \tag*{(1)} x ∈ R d min f ( x ) , f ⋆ := x ∈ R d inf f ( x ) > − ∞ , (1) where f : R d → R f : \mathbb{R}^{d} \to\mathbb{R} f : R d → R x x x f f f ∥ ∇ 2 f ( x ) ∥ \lVert\nabla^{2} f(x) \rVert ∥ ∇ 2 f ( x )∥ x x x L > 0 L > 0 L > 0
∥ ∇ 2 f ( x ) ∥ ≤ L ∀ x ∈ R d . (2) \lVert\nabla^{2} f(x) \rVert\le L \qquad\forall x \in\mathbb{R}^{d}. \tag*{(2)} ∥ ∇ 2 f ( x )∥ ≤ L ∀ x ∈ R d . (2) Classical L L L [2 ] . Motivated by empirical observations that local curvature grows with the gradient norm during neural-network training, Zhang et al. [2020b] introduced ( L 0 , L 1 ) (L_0, L_1) ( L 0 , L 1 ) [32 ] imply ( L 0 , L 1 ) (L_0, L_1) ( L 0 , L 1 ) ( H 0 , H 1 ) (H_0, H_1) ( H 0 , H 1 ) ℓ 2 \ell_2 ℓ 2 [2 ] . These findings motivate the gradient-dependent and loss-dependent curvature bounds considered here:
∥ ∇ 2 f ( x ) ∥ ≤ M L ( x ) : = L 0 + L 1 ∥ ∇ f ( x ) ∥ , ( L 0 , L 1 ) -smoothness , (3) \lVert\nabla^{2} f(x) \rVert\le M_L(x) := L_0 + L_1 \lVert\nabla f(x) \rVert, \qquad(L_0,L_1)\text{-smoothness}, \tag*{(3)} ∥ ∇ 2 f ( x )∥ ≤ M L ( x ) := L 0 + L 1 ∥ ∇ f ( x )∥ , ( L 0 , L 1 ) -smoothness , (3) ∥ ∇ 2 f ( x ) ∥ ≤ M H ( x ) : = H 0 + H 1 ( f ( x ) − f ⋆ ) , ( H 0 , H 1 ) -smoothness , (4) \lVert\nabla^{2} f(x) \rVert\le M_H(x) := H_0 + H_1\left(f(x)-f_{\star}\right), \qquad(H_0,H_1)\text{-smoothness}, \tag*{(4)} ∥ ∇ 2 f ( x )∥ ≤ M H ( x ) := H 0 + H 1 ( f ( x ) − f ⋆ ) , ( H 0 , H 1 ) -smoothness , (4) for every x ∈ R d x \in\mathbb{R}^{d} x ∈ R d L 0 > 0 L_0 > 0 L 0 > 0 L 1 ≥ 0 L_1 \ge0 L 1 ≥ 0 H 0 , H 1 ≥ 0 H_0, H_1 \ge0 H 0 , H 1 ≥ 0 L 1 = 0 L_1 = 0 L 1 = 0 H 1 = 0 H_1 = 0 H 1 = 0 M L : = M L ( x ) M_L := M_L(x) M L := M L ( x ) M H : = M H ( x ) M_H := M_H(x) M H := M H ( x ) curvature scale ; M L M_L M L M H M_H M H
The difficulty is that the curvature bound must control the gradient change along the perturbation, as well as the subsequent descent step. Even under classical smoothness, a fixed perturbation radius can prevent exact convergence: Bartlett et al. [ [5 ] analyzed cycling of fixed-radius SAM on convex quadratics, and Si and Yun [ [29 ] established stationarity neighborhoods in several settings. The inexact-gradient viewpoint of Khanh et al. [ [18 ] makes the perturbation-induced error explicit, while the clipped rule of Adly and Le [ [1 ] controls it near stationarity by making the perturbation proportional to the gradient. Under (3), however, a gradient-proportional perturbation can also become too large when the gradient grows. Thus, extending SAM to generalized smoothness requires control at both ends of the gradient scale.
For ordinary gradient methods, adapting to curvature growth is already well studied. The ( L 0 , L 1 ) (L_0, L_1) ( L 0 , L 1 ) [6 , 9 , 20 , 22 ] (Zhang et al. 2020a). In particular, Gorbunov et al. [ [13 ] and Vankov et al. [ [34 ] analyzed steps inversely proportional to gradient-dependent curvature bounds. The loss-dependent model has likewise been used to explain learning-rate warm-up [2 ] and to analyze line search and adaptive gradient methods [35 ] (Vaswani et al. 2026). These results motivate scaling the outer descent step by a curvature bound. The remaining question for SAM is how that bound should also determine the perturbation.
Main Contributions
that of USAM can become unbounded as the gradient grows. Proposition 2.1 gives explicit examples within the ( L 0 , L 1 ) (L_0, L_1) ( L 0 , L 1 )
◇ Curvature-Scaled Sharpness-Aware Minimization. In § 2.2 , we construct CS-SAM, which, for a curvature scale M M M
y t = x t + ρ M ( x t ) ∇ f ( x t ) , x t + 1 = x t − γ M ( y t ) ∇ f ( y t ) , y_t = x_t + \frac{\rho}{M(x_t)} \nabla f(x_t), \qquad x_{t+1} = x_t - \frac{\gamma}{M(y_t)} \nabla f(y_t), y t = x t + M ( x t ) ρ ∇ f ( x t ) , x t + 1 = x t − M ( y t ) γ ∇ f ( y t ) , (CS-SAM)
with perturbation multiplier ρ / M ( x t ) \rho/M(x_t) ρ / M ( x t ) γ / M ( y t ) \gamma/M(y_t) γ / M ( y t ) ρ ≥ 0 \rho\ge0 ρ ≥ 0 γ > 0 \gamma> 0 γ > 0 M M M M L M_L M L M H M_H M H e ρ − 1 e^\rho- 1 e ρ − 1
◇ Convergence under generalized smoothness. We establish convergence guarantees for CS-SAM under ( L 0 , L 1 ) (L_0, L_1) ( L 0 , L 1 ) M = M L M = M_L M = M L ( H 0 , H 1 ) (H_0, H_1) ( H 0 , H 1 ) M = M H M = M_H M = M H O ( 1 / T ) O(1/T) O ( 1/ T ) O ( 1 / T ) O(1/T) O ( 1/ T ) ∥ ∇ f ( x ) ∥ 2 / 2 ≥ μ ( f ( x ) − f ⋆ ) \lVert\nabla f(x) \rVert^2/2 \ge\mu(f(x) - f_\star) ∥ ∇ f ( x ) ∥ 2 /2 ≥ μ ( f ( x ) − f ⋆ ) x x x μ > 0 \mu> 0 μ > 0
◇ Recovery of gradient descent guarantees for ρ = 0 \rho= 0 ρ = 0 Setting ρ = 0 \rho= 0 ρ = 0 γ / M ( x t ) \gamma/M(x_t) γ / M ( x t ) [13 , 34 ] , and the convex and PL rates for loss-dependent steps [2 ] , while allowing larger step sizes in the latter case. Thus the analysis extends existing gradient descent guarantees to positive sharpness-aware perturbations.
◇ Numerical Evaluation. In § 4.1 , we verify Proposition 2.1 and Theorem 2.5: SAM cycles and USAM diverges, whereas CS-SAM converges with a distortion below e ρ − 1 e^\rho- 1 e ρ − 1 § 4.2 , we evaluate minibatch variants beyond the deterministic setting of our theory on ResNet-20/32 and CIFAR-10/100. Both use two gradient evaluations per iteration. Against tuned constant-step and cosine annealing-scheduled SAM and USAM, the loss-dependent variant achieves the highest mean best-test accuracy in all four settings, while the gradient-dependent variant exceeds all these baselines in three of four settings.
Table 1 summarizes the distortion control and convergence guarantees alongside prior work.
Table 1. Comparison with the closest prior work. D ( x , d ) = ∥ ∇ f ( x + d ) − ∇ f ( x ) ∥ / ∥ ∇ f ( x ) ∥ D(x,d)=\|\nabla f(x+d)-\nabla f(x)\|/\|\nabla f(x)\| D ( x , d ) = ∥∇ f ( x + d ) − ∇ f ( x ) ∥/∥∇ f ( x ) ∥ d d d § 2.1 ). Curvature models: L L L ∥ ∇ 2 f ( x ) ∥ ≤ L \|\nabla^2 f(x)\|\le L ∥ ∇ 2 f ( x ) ∥ ≤ L ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) ∥ ∇ 2 f ( x ) ∥ ≤ L 0 + L 1 ∥ ∇ f ( x ) ∥ \|\nabla^2 f(x)\|\le L_0+L_1\|\nabla f(x)\| ∥ ∇ 2 f ( x ) ∥ ≤ L 0 + L 1 ∥∇ f ( x ) ∥ ( H 0 , H 1 ) (H_0,H_1) ( H 0 , H 1 ) ∥ ∇ 2 f ( x ) ∥ ≤ H 0 + H 1 ( f ( x ) − f ⋆ ) \|\nabla^2 f(x)\|\le H_0+H_1(f(x)-f_\star) ∥ ∇ 2 f ( x ) ∥ ≤ H 0 + H 1 ( f ( x ) − f ⋆ ) f ⋆ = inf x f ( x ) f_\star=\inf_x f(x) f ⋆ = inf x f ( x ) ✓ \checkmark ✓ D D D × \mathord{\times} × T T T f ( x T ) − f ⋆ f(x_T)-f_\star f ( x T ) − f ⋆
From gradient distortion to curvature-scaled SAM
In this section, we define relative gradient distortion and explain how it controls the difference between a sharpness-aware direction and the gradient used by gradient descent. We then show that SAM and USAM can lose this control at opposite ends of the gradient scale, and derive a necessary condition for keeping it uniformly bounded. This condition motivates the CS-SAM update, for which we prove a uniform distortion bound under both generalized smoothness models. The proofs are deferred to Appendix § 10 ; the distortion bound follows from the auxiliary lemmas in Appendix § 9 .
Relative gradient distortion and the failures of SAM and USAM
The outer step of SAM and USAM is a gradient step that uses ∇ f ( y t ) \nabla f(y_t) ∇ f ( y t ) ∇ f ( x t ) \nabla f(x_t) ∇ f ( x t ) ∇ f ( x ) ≠ 0 \nabla f(x)\ne0 ∇ f ( x ) = 0 d d d relative gradient distortion
D ( x , d ) : = ∥ ∇ f ( x + d ) − ∇ f ( x ) ∥ ∥ ∇ f ( x ) ∥ . (5) D(x,d):=\frac{\|\nabla f(x+d)-\nabla f(x)\|}{\|\nabla f(x)\|}. \tag*{(5)} D ( x , d ) := ∥∇ f ( x ) ∥ ∥∇ f ( x + d ) − ∇ f ( x ) ∥ . (5) Let us explain why this is the right quantity. If D ( x , d ) ≤ δ < 1 D(x,d)\le\delta<1 D ( x , d ) ≤ δ < 1 ∇ f ( x + d ) \nabla f(x+d) ∇ f ( x + d ) ∇ f ( x ) \nabla f(x) ∇ f ( x ) ⟨ ∇ f ( x ) , ∇ f ( x + d ) ⟩ ≥ ( 1 − δ ) ∥ ∇ f ( x ) ∥ 2 \langle\nabla f(x),\nabla f(x+d)\rangle\ge(1-\delta)\|\nabla f(x)\|^2 ⟨ ∇ f ( x ) , ∇ f ( x + d )⟩ ≥ ( 1 − δ ) ∥∇ f ( x ) ∥ 2 ( 1 − δ ) ∥ ∇ f ( x ) ∥ ≤ ∥ ∇ f ( x + d ) ∥ ≤ ( 1 + δ ) ∥ ∇ f ( x ) ∥ (1-\delta)\|\nabla f(x)\|\le\|\nabla f(x+d)\|\le(1+\delta)\|\nabla f(x)\| ( 1 − δ ) ∥∇ f ( x ) ∥ ≤ ∥∇ f ( x + d ) ∥ ≤ ( 1 + δ ) ∥∇ f ( x ) ∥ D ( x , d ) ≤ δ < 1 D(x,d)\le\delta<1 D ( x , d ) ≤ δ < 1 every point. Controlling the perturbation-induced gradient error is also the viewpoint of the inexact-gradient analyses of Khanh et al. [ [18 ] , and relative control of this error near stationarity is what the clipped rule of Adly and Le [ [1 ] enforces; the quantity itself is therefore not new. Our question is which perturbation rules keep it uniformly bounded under generalized smoothness.
We first record what the two base rules can guarantee. Under (2) we have
D S A M ≤ L r ∥ ∇ f ( x ) ∥ , D U S A M ≤ L ρ . (6) D_{\mathrm{SAM}}\le\frac{Lr}{\|\nabla f(x)\|},\qquad D_{\mathrm{USAM}}\le L\rho. \tag*{(6)} D SAM ≤ ∥∇ f ( x ) ∥ L r , D USAM ≤ L ρ . (6) Note that the bound for SAM degenerates as ∥ ∇ f ( x ) ∥ → 0 \|\nabla f(x)\|\to0 ∥∇ f ( x ) ∥ → 0 (3) , for L 1 > 0 L_1>0 L 1 > 0 § 10 ):
D S A M ≤ ( e L 1 r − 1 ) ( 1 + L 0 L 1 ∥ ∇ f ( x ) ∥ ) , D U S A M ≤ L 0 + L 1 ∥ ∇ f ( x ) ∥ L 1 ∥ ∇ f ( x ) ∥ ( e L 1 ρ ∥ ∇ f ( x ) ∥ − 1 ) . (7) D_{\mathrm{SAM}}\le\left(e^{L_1r}-1\right)\left(1+\frac{L_0}{L_1\|\nabla f(x)\|}\right),\qquad D_{\mathrm{USAM}}\le\frac{L_0+L_1\|\nabla f(x)\|}{L_1\|\nabla f(x)\|}\left(e^{L_1\rho\|\nabla f(x)\|}-1\right). \tag*{(7)} D SAM ≤ ( e L 1 r − 1 ) ( 1 + L 1 ∥∇ f ( x ) ∥ L 0 ) , D USAM ≤ L 1 ∥∇ f ( x ) ∥ L 0 + L 1 ∥∇ f ( x ) ∥ ( e L 1 ρ ∥∇ f ( x ) ∥ − 1 ) . (7) The bound for SAM tends to the constant e L 1 r − 1 e^{L_1r}-1 e L 1 r − 1 ∥ ∇ f ( x ) ∥ → 0 \|\nabla f(x)\|\to0 ∥∇ f ( x ) ∥ → 0 ρ L 0 \rho L_0 ρ L 0 ∥ ∇ f ( x ) ∥ → 0 \|\nabla f(x)\|\to0 ∥∇ f ( x ) ∥ → 0 ∥ ∇ f ( x ) ∥ → + ∞ \|\nabla f(x)\|\to+\infty ∥∇ f ( x ) ∥ → + ∞
Proposition 2.1. Both perturbations can fail on one-dimensional convex objectives: SAM admits a nonzero two-cycle on a quadratic, and USAM diverges for large initializations on a quartic.
(i) Let f ( x ) = x 2 / 2 f(x)=x^2/2 f ( x ) = x 2 /2 (2) with L = 1 L=1 L = 1 r > 0 r>0 r > 0 η ∈ ( 0 , 2 ) \eta\in(0,2) η ∈ ( 0 , 2 ) x ≠ 0 x\ne0 x = 0
D S A M ( x ) : = D ( x , r sign ( x ) ) = r ∣ x ∣ , x t + 1 = [ 1 − η ( 1 + D S A M ( x t ) ) ] x t . (8) D_{\mathrm{SAM}}(x):=D(x,r\operatorname{sign}(x))=\frac{r}{\lvert x\rvert},\qquad x_{t+1}=\left[1-\eta\left(1+D_{\mathrm{SAM}}(x_t)\right)\right]x_t. \tag*{(8)} D SAM ( x ) := D ( x , r sign ( x )) = ∣ x ∣ r , x t + 1 = [ 1 − η ( 1 + D SAM ( x t ) ) ] x t . (8) Let a = η r / ( 2 − η ) a=\eta r/(2-\eta) a = η r / ( 2 − η ) ∣ x t + 1 ∣ < ∣ x t ∣ \lvert x_{t+1}\rvert<\lvert x_t\rvert ∣ x t + 1 ∣ < ∣ x t ∣ ∣ x t ∣ > a \lvert x_t\rvert>a ∣ x t ∣ > a ∣ x t + 1 ∣ > ∣ x t ∣ \lvert x_{t+1}\rvert>\lvert x_t\rvert ∣ x t + 1 ∣ > ∣ x t ∣ 0 < ∣ x t ∣ < a 0<\lvert x_t\rvert<a 0 < ∣ x t ∣ < a x t + 1 = − x t x_{t+1}=-x_t x t + 1 = − x t ∣ x t ∣ = a \lvert x_t\rvert=a ∣ x t ∣ = a ± a \pm a ± a
(ii) Let f ( x ) = x 4 / 4 f(x)=x^4/4 f ( x ) = x 4 /4 (3) with ( L 0 , L 1 ) = ( 4 , 1 ) (L_0,L_1)=(4,1) ( L 0 , L 1 ) = ( 4 , 1 ) ρ > 0 \rho>0 ρ > 0 η > 0 \eta>0 η > 0 x ≠ 0 x\ne0 x = 0
D U S A M ( x ) : = D ( x , ρ x 3 ) = ( 1 + ρ x 2 ) 3 − 1 , x t + 1 = [ 1 − η ( 1 + D U S A M ( x t ) ) x t 2 ] x t . (9) D_{\mathrm{USAM}}(x):=D(x,\rho x^3)=(1+\rho x^2)^3-1,\qquad x_{t+1}=\left[1-\eta\left(1+D_{\mathrm{USAM}}(x_t)\right)x_t^2\right]x_t. \tag*{(9)} D USAM ( x ) := D ( x , ρ x 3 ) = ( 1 + ρ x 2 ) 3 − 1 , x t + 1 = [ 1 − η ( 1 + D USAM ( x t ) ) x t 2 ] x t . (9) Consequently, if ∣ x 0 ∣ > ( 2 / ( η ρ 3 ) ) 1 / 8 \lvert x_0\rvert>(2/(\eta\rho^3))^{1/8} ∣ x 0 ∣ > ( 2/ ( η ρ 3 ) ) 1/8 x t + 1 x_{t+1} x t + 1 x t x_t x t ∣ x t + 1 ∣ > ∣ x t ∣ \lvert x_{t+1}\rvert>\lvert x_t\rvert ∣ x t + 1 ∣ > ∣ x t ∣ t t t ∣ x t ∣ → ∞ \lvert x_t\rvert\to\infty ∣ x t ∣ → ∞
The quadratic construction can be viewed as an exact illustration of established late-stage phenomena: Bartlett et al. [ [5 ] showed that fixed-radius SAM typically approaches a two-cycle on convex quadratics, and Si and Yun [ [29 ] established unavoidable stationarity neighborhoods for practical fixed-radius SAM in several settings. Our point is the complementarity: the distortion can become unbounded at opposite ends of the gradient scale, with nonconvergence for these fixed-parameter updates. The following theorem addresses all perturbations along the gradient whose nonnegative multiplier depends only on the gradient norm: it gives a necessary condition for uniform boundedness of the relative distortion over the whole class of objectives in (3) .
Theorem 2.2. Let L 0 > 0 L_0>0 L 0 > 0 L 1 > 0 L_1>0 L 1 > 0 d ( x ) = α ( ∥ ∇ f ( x ) ∥ ) ∇ f ( x ) d(x)=\alpha(\lVert\nabla f(x)\rVert)\nabla f(x) d ( x ) = α (∥ ∇ f ( x )∥) ∇ f ( x ) (3) and every point with nonzero gradient, D ( x , d ( x ) ) ≤ δ D(x,d(x))\le\delta D ( x , d ( x )) ≤ δ s > 0 s>0 s > 0
α ( s ) ≤ min { δ L 0 , log ( 1 + δ ) L 1 s } . (10) \alpha(s)\le\min\left\{\frac{\delta}{L_0},\frac{\log(1+\delta)}{L_1s}\right\}. \tag*{(10)} α ( s ) ≤ min { L 0 δ , L 1 s log ( 1 + δ ) } . (10) Note that the theorem covers SAM with α ( s ) = r / s \alpha(s)=r/s α ( s ) = r / s α ( s ) = ρ \alpha(s)=\rho α ( s ) = ρ α ( s ) s \alpha(s)s α ( s ) s s = 0 s=0 s = 0 s s s r / s → ∞ r/s\to\infty r / s → ∞ s → 0 s\to0 s → 0 ρ s → ∞ \rho s\to\infty ρ s → ∞ s → ∞ s\to\infty s → ∞ ρ ∇ f ( x ) \rho\nabla f(x) ρ ∇ f ( x ) L 0 + L 1 ∥ ∇ f ( x ) ∥ L_0+L_1\lVert\nabla f(x)\rVert L 0 + L 1 ∥ ∇ f ( x )∥ α ( s ) = ρ / ( L 0 + L 1 s ) \alpha(s)=\rho/(L_0+L_1s) α ( s ) = ρ / ( L 0 + L 1 s ) s s s δ = e ρ − 1 \delta=e^\rho-1 δ = e ρ − 1
Admissible scales and the CS-SAM update
Theorem 2.2 motivates a perturbation that divides the gradient by a local curvature upper bound. In this subsection we isolate the properties of such a bound that our analysis uses, state the update, and prove that it keeps the distortion bounded for any scale with these properties.
Definition 2.3 (Admissible curvature scale). Let κ ≥ 0 \kappa\ge0 κ ≥ 0 M : R d → ( 0 , ∞ ) M:\mathbb{R}^d\to(0,\infty) M : R d → ( 0 , ∞ ) κ \kappa κ f f f
@%timeout 彩娱乐彩票 if, for all x , y ∈ R d x,y \in\mathbb{R}^{d} x , y ∈ R d
∥ ∇ 2 f ( x ) ∥ ≤ M ( x ) , M ( y ) ≤ M ( x ) e κ ∥ y − x ∥ , κ ∥ ∇ f ( x ) ∥ ≤ M ( x ) . (11) \lVert\nabla^{2} f(x) \rVert\le M(x), \qquad M(y) \le M(x)e^{\kappa\lVert y-x\rVert}, \qquad\kappa\lVert\nabla f(x) \rVert\le M(x). \tag*{(11)} ∥ ∇ 2 f ( x )∥ ≤ M ( x ) , M ( y ) ≤ M ( x ) e κ ∥ y − x ∥ , κ ∥ ∇ f ( x )∥ ≤ M ( x ) . (11) Let us read the three conditions in (11) . The first says that M M M ∇ f ( x ) / M ( x ) \nabla f(x)/M(x) ∇ f ( x ) / M ( x ) (3) , the scale M L ( x ) = L 0 + L 1 ∥ ∇ f ( x ) ∥ M_L(x)=L_0+L_1\lVert\nabla f(x)\rVert M L ( x ) = L 0 + L 1 ∥ ∇ f ( x )∥ L 1 L_1 L 1 (2) and (4) .
Proposition 2.4 (Properties of the curvature scales).
(i) Under (2) , the constant scale M ≡ L M\equiv L M ≡ L κ = 0 \kappa=0 κ = 0
(ii) Under (3) , the scale M L M_L M L κ = L 1 \kappa=L_1 κ = L 1
(iii) Under (4) , either M H ≡ 0 M_H\equiv0 M H ≡ 0 f f f M H > 0 M_H>0 M H > 0 M H M_H M H κ = H 1 \kappa=\sqrt{H_1} κ = H 1
(iv) Under (3) , for every x ∈ R d x\in\mathbb{R}^{d} x ∈ R d
L 0 + L 1 ∥ ∇ f ( x ) ∥ ≤ 3 2 L 0 + 3 L 1 2 2 ( 2 log 2 − 1 ) ( f ( x ) − f ⋆ ) . (12) L_0+L_1\lVert\nabla f(x)\rVert\le\frac{3}{2}L_0+\frac{3L_1^2}{2(2\log2-1)}(f(x)-f_\star). \tag*{(12)} L 0 + L 1 ∥ ∇ f ( x )∥ ≤ 2 3 L 0 + 2 ( 2 log 2 − 1 ) 3 L 1 2 ( f ( x ) − f ⋆ ) . (12) In particular, (3) implies (4) with the constants H 0 = 3 L 0 / 2 H_0=3L_0/2 H 0 = 3 L 0 /2 H 1 = 3 L 1 2 / ( 2 ( 2 log 2 − 1 ) ) H_1=3L_1^2/(2(2\log2-1)) H 1 = 3 L 1 2 / ( 2 ( 2 log 2 − 1 ))
Items (i)–(iii) say that the three curvature bounds in (2) , (3) and (4) are admissible, with κ = 0 \kappa=0 κ = 0 κ = L 1 \kappa=L_1 κ = L 1 κ = H 1 \kappa=\sqrt{H_1} κ = H 1 f f f M H M_H M H (3) also satisfies (4) , with H 0 = 3 L 0 / 2 H_0=3L_0/2 H 0 = 3 L 0 /2 H 1 = 3 L 1 2 / ( 2 ( 2 log 2 − 1 ) ) H_1=3L_1^2/(2(2\log2-1)) H 1 = 3 L 1 2 / ( 2 ( 2 log 2 − 1 )) [2 ] and as Proposition 3 of Vaswani and Babanezhad Harikandeh [ [35 ] , with different constants.
The update. Given an admissible curvature scale M M M ρ ≥ 0 \rho\ge0 ρ ≥ 0 γ > 0 \gamma>0 γ > 0 x 0 x_0 x 0
y t = x t + ρ M ( x t ) ∇ f ( x t ) , x t + 1 = x t − γ M ( y t ) ∇ f ( y t ) . y_t=x_t+\frac{\rho}{M(x_t)}\nabla f(x_t), \qquad x_{t+1}=x_t-\frac{\gamma}{M(y_t)}\nabla f(y_t). y t = x t + M ( x t ) ρ ∇ f ( x t ) , x t + 1 = x t − M ( y t ) γ ∇ f ( y t ) . Here, ρ ≥ 0 \rho\ge0 ρ ≥ 0 γ > 0 \gamma>0 γ > 0 ρ / M ( x t ) \rho/M(x_t) ρ / M ( x t ) γ / M ( y t ) \gamma/M(y_t) γ / M ( y t ) same curvature scale, each evaluated at the point where the corresponding gradient is taken. If ∇ f ( x t ) = 0 \nabla f(x_t)=0 ∇ f ( x t ) = 0 x t x_t x t Table 2 . With the gradient scale M = M L M=M_L M = M L ρ / ( L 0 + L 1 ∥ ∇ f ( x t ) ∥ ) \rho/(L_0+L_1\lVert\nabla f(x_t)\rVert) ρ / ( L 0 + L 1 ∥ ∇ f ( x t )∥) γ / ( L 0 + L 1 ∥ ∇ f ( y t ) ∥ ) \gamma/(L_0+L_1\lVert\nabla f(y_t)\rVert) γ / ( L 0 + L 1 ∥ ∇ f ( y t )∥) α ( s ) = ρ / ( L 0 + L 1 s ) \alpha(s)=\rho/(L_0+L_1s) α ( s ) = ρ / ( L 0 + L 1 s ) M = M H M=M_H M = M H ρ / ( H 0 + H 1 ( f ( x t ) − f ⋆ ) ) \rho/(H_0+H_1(f(x_t)-f_\star)) ρ / ( H 0 + H 1 ( f ( x t ) − f ⋆ )) γ / ( H 0 + H 1 ( f ( y t ) − f ⋆ ) ) \gamma/(H_0+H_1(f(y_t)-f_\star)) γ / ( H 0 + H 1 ( f ( y t ) − f ⋆ )) not covered by Theorem 2.2. Like SAM and USAM, CS-SAM costs two gradient evaluations per iteration; the scale M L M_L M L M H M_H M H f ⋆ f_\star f ⋆
Table 2: The curvature scales associated with (2) , (3) and (4) as instances of CS-SAM. For each scale we list the assumption under which it is a curvature scale, the admissibility constant κ \kappa κ ρ = 0 \rho= 0 ρ = 0 § 2.2 ).
Table 2.
Let us highlight the degenerate case. For ρ = 0 \rho=0 ρ = 0 y t = x t y_t=x_t y t = x t γ / M ( x t ) \gamma/M(x_t) γ / M ( x t )
x t + 1 = x t − γ M ( x t ) ∇ f ( x t ) . x_{t+1}=x_t-\frac{\gamma}{M(x_t)}\nabla f(x_t). x t + 1 = x t − M ( x t ) γ ∇ f ( x t ) . CS-SAM is thus a generalization of CS-GD, whose instances at the three scales are listed in the last column of Table 2 , and in § 3 we compare its guarantees with known gradient descent results.
In contrast to SAM and USAM, the relative distortion of CS-SAM is uniformly bounded for any admissible curvature scale, as we now show.
Theorem 2.5. Let M M M κ \kappa κ ρ ≥ 0 \rho\ge0 ρ ≥ 0 γ > 0 \gamma> 0 γ > 0 ∇ f ( x t ) ≠ 0 \nabla f(x_t) \ne0 ∇ f ( x t ) = 0
e − ρ M ( x t ) ≤ M ( y t ) ≤ e ρ M ( x t ) , ∥ ∇ f ( y t ) − ∇ f ( x t ) ∥ ∥ ∇ f ( x t ) ∥ ≤ e ρ − 1. (13) e^{-\rho}M(x_t) \le M(y_t) \le e^{\rho}M(x_t), \qquad\frac{\lVert\nabla f(y_t) - \nabla f(x_t) \rVert}{\lVert\nabla f(x_t) \rVert} \le e^{\rho} - 1. \tag*{(13)} e − ρ M ( x t ) ≤ M ( y t ) ≤ e ρ M ( x t ) , ∥ ∇ f ( x t )∥ ∥ ∇ f ( y t ) − ∇ f ( x t )∥ ≤ e ρ − 1. (13) In particular, D C S − S A M ≤ e ρ − 1 D_{\mathrm{CS-SAM}} \le e^{\rho} - 1 D CS − SAM ≤ e ρ − 1
Let us highlight what Theorem 2.5 says. The curvature scale at the perturbed point stays within a factor e ± ρ e^{\pm\rho} e ± ρ e ρ − 1 e^{\rho} - 1 e ρ − 1 (6) , (7) , and Proposition 2.1 show SAM and USAM lack: the bound does not degenerate as ∥ ∇ f ( x t ) ∥ → 0 \lVert\nabla f(x_t) \rVert\to0 ∥ ∇ f ( x t )∥ → 0 ∥ ∇ f ( x t ) ∥ → ∞ \lVert\nabla f(x_t) \rVert\to\infty ∥ ∇ f ( x t )∥ → ∞ κ \kappa κ ( L 0 , L 1 ) (L_0, L_1) ( L 0 , L 1 ) ( H 0 , H 1 ) (H_0, H_1) ( H 0 , H 1 ) δ = e ρ − 1 \delta= e^{\rho} - 1 δ = e ρ − 1 § 2.1 , D C S − S A M < 1 D_{\mathrm{CS-SAM}} < 1 D CS − SAM < 1 ρ < log 2 \rho< \log2 ρ < log 2 § 3 : the condition χ ( ρ , γ ) > 0 \chi(\rho, \gamma) > 0 χ ( ρ , γ ) > 0 (14) under which they hold forces ρ < log 2 \rho< \log2 ρ < log 2
Convergence rates
In this section, we present convergence rates for CS-SAM run with the curvature scales M L M_L M L (3) and M H M_H M H (4) . We first fix the constants and the function classes that appear in the bounds. Then, § 3.1 states the rates for the gradient scale M L M_L M L § 3.2 those for the loss scale M H M_H M H § 9 .
Constants. For u ≥ 0 u \ge0 u ≥ 0 ω ( u ) : = ( e u − 1 − u ) / u 2 \omega(u) := (e^u - 1 - u)/u^2 ω ( u ) := ( e u − 1 − u ) / u 2 u > 0 u > 0 u > 0 ω ( 0 ) : = 1 / 2 \omega(0) := 1/2 ω ( 0 ) := 1/2
χ ( ρ , γ ) : = 2 − e ρ − γ ω ( γ ) e 3 ρ , c 0 : = 1 − ρ ( e ρ − 1 ) 2 log 2 − 1 − γ e 3 ρ 2 ( 2 log 2 − 1 ) . (14) \chi(\rho,\gamma) := 2 - e^\rho- \gamma\omega(\gamma)e^{3\rho}, \qquad c_0 := 1 - \frac{\rho(e^\rho- 1)}{2\log2 - 1} - \frac{\gamma e^{3\rho}}{2(2\log2 - 1)}. \tag*{(14)} χ ( ρ , γ ) := 2 − e ρ − γ ω ( γ ) e 3 ρ , c 0 := 1 − 2 log 2 − 1 ρ ( e ρ − 1 ) − 2 ( 2 log 2 − 1 ) γ e 3 ρ . (14) The condition χ ( ρ , γ ) > 0 \chi(\rho,\gamma) > 0 χ ( ρ , γ ) > 0 ρ < log 2 \rho< \log2 ρ < log 2 χ ( ρ , γ ) > 0 \chi(\rho,\gamma) > 0 χ ( ρ , γ ) > 0 c 0 ≥ 0 c_0 \ge0 c 0 ≥ 0 ρ = 0 \rho= 0 ρ = 0 χ ( 0 , γ ) = 1 + 2 γ − e γ \chi(0,\gamma) = 1 + 2\gamma- e^\gamma χ ( 0 , γ ) = 1 + 2 γ − e γ c 0 = 1 − γ / ( 2 ( 2 log 2 − 1 ) ) c_0 = 1 - \gamma/(2(2\log2 - 1)) c 0 = 1 − γ / ( 2 ( 2 log 2 − 1 ))
Function classes. We say that f f f convex with a minimizer if f f f f ⋆ f_\star f ⋆ x ⋆ x_\star x ⋆ f f f μ \mu μ PL condition for some μ > 0 \mu> 0 μ > 0
1 2 ∥ ∇ f ( x ) ∥ 2 ≥ μ ( f ( x ) − f ⋆ ) ∀ x ∈ R d . (15) \frac{1}{2}\lVert\nabla f(x)\rVert^2 \ge\mu\left(f(x)-f_\star\right) \qquad\forall x \in\mathbb{R}^d. \tag*{(15)} 2 1 ∥ ∇ f ( x ) ∥ 2 ≥ μ ( f ( x ) − f ⋆ ) ∀ x ∈ R d . (15) ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) M = M L M=M_L M = M L Throughout this subsection f f f (3) and CS-SAM is run with the curvature scale M = M L M=M_L M = M L ρ / ( L 0 + L 1 ∥ ∇ f ( x t ) ∥ ) \rho/(L_0+L_1\lVert\nabla f(x_t)\rVert) ρ / ( L 0 + L 1 ∥ ∇ f ( x t )∥) γ / ( L 0 + L 1 ∥ ∇ f ( y t ) ∥ ) \gamma/(L_0+L_1\lVert\nabla f(y_t)\rVert) γ / ( L 0 + L 1 ∥ ∇ f ( y t )∥)
Theorem 3.1. Let f f f (3) , let ρ ≥ 0 \rho\ge0 ρ ≥ 0 γ > 0 \gamma> 0 γ > 0 χ ( ρ , γ ) > 0 \chi(\rho,\gamma)>0 χ ( ρ , γ ) > 0 ( x t ) t ≥ 0 (x_t)_{t\ge0} ( x t ) t ≥ 0 M = M L M=M_L M = M L T ≥ 1 T\ge1 T ≥ 1
(i) (Nonconvex rate )
min 0 ≤ t < T ∥ ∇ f ( x t ) ∥ 2 ≤ ( e ρ L 0 ( f ( x 0 ) − f ⋆ ) γ χ ( ρ , γ ) T + e ρ L 1 ( f ( x 0 ) − f ⋆ ) γ χ ( ρ , γ ) T ) 2 . (16) \min_{0\le t<T}\lVert\nabla f(x_t)\rVert^2 \le\left(\sqrt{\frac{e^{\rho}L_0(f(x_0)-f_\star)}{\gamma\chi(\rho,\gamma)T}}+\frac{e^{\rho}L_1(f(x_0)-f_\star)}{\gamma\chi(\rho,\gamma)T}\right)^2. \tag*{(16)} 0 ≤ t < T min ∥ ∇ f ( x t ) ∥ 2 ≤ ( γ χ ( ρ , γ ) T e ρ L 0 ( f ( x 0 ) − f ⋆ ) + γ χ ( ρ , γ ) T e ρ L 1 ( f ( x 0 ) − f ⋆ ) ) 2 . (16) (ii) (Convex rate ) If in addition f f f x ⋆ x_\star x ⋆ c 0 ≥ 0 c_0\ge0 c 0 ≥ 0
f ( x T ) − f ⋆ ≤ e ρ ( L 0 ∥ x 0 − x ⋆ ∥ 2 + L 1 ∥ x 0 − x ⋆ ∥ ( f ( x 0 ) − f ⋆ ) ) γ χ ( ρ , γ ) T . (17) f(x_T)-f_\star\le\frac{e^{\rho}\left(L_0\lVert x_0-x_\star\rVert^2+L_1\lVert x_0-x_\star\rVert(f(x_0)-f_\star)\right)}{\gamma\chi(\rho,\gamma)T}. \tag*{(17)} f ( x T ) − f ⋆ ≤ γ χ ( ρ , γ ) T e ρ ( L 0 ∥ x 0 − x ⋆ ∥ 2 + L 1 ∥ x 0 − x ⋆ ∥ ( f ( x 0 ) − f ⋆ ) ) . (17) (iii) (PL rate ) If in addition f f f μ \mu μ (15) , then
f ( x T ) − f ⋆ ≤ ( 1 − 2 μ γ e − ρ χ ( ρ , γ ) L 0 + L 1 2 μ ( f ( x 0 ) − f ⋆ ) ) T ( f ( x 0 ) − f ⋆ ) . (18) f(x_T)-f_\star\le\left(1-\frac{2\mu\gamma e^{-\rho}\chi(\rho,\gamma)}{L_0+L_1\sqrt{2\mu(f(x_0)-f_\star)}}\right)^T(f(x_0)-f_\star). \tag*{(18)} f ( x T ) − f ⋆ ≤ ( 1 − L 0 + L 1 2 μ ( f ( x 0 ) − f ⋆ ) 2 μ γ e − ρ χ ( ρ , γ ) ) T ( f ( x 0 ) − f ⋆ ) . (18) Let us read the three items in turn. Item (i) shows that the best squared gradient norm decays as O ( 1 / T ) O(1/T) O ( 1/ T ) e ρ L 0 ( f ( x 0 ) − f ⋆ ) / ( γ χ ( ρ , γ ) T ) e^{\rho}L_0(f(x_0)-f_\star)/(\gamma\chi(\rho,\gamma)T) e ρ L 0 ( f ( x 0 ) − f ⋆ ) / ( γ χ ( ρ , γ ) T ) L 0 L_0 L 0 L 1 L_1 L 1 T T T (3) and χ ( ρ , γ ) > 0 \chi(\rho,\gamma)>0 χ ( ρ , γ ) > 0 L 0 , L 1 L_0,L_1 L 0 , L 1 O ( 1 / T ) O(1/T) O ( 1/ T ) L 0 ∥ x 0 − x ⋆ ∥ 2 L_0\lVert x_0-x_\star\rVert^2 L 0 ∥ x 0 − x ⋆ ∥ 2 L 1 ∥ x 0 − x ⋆ ∥ ( f ( x 0 ) − f ⋆ ) L_1\lVert x_0-x_\star\rVert(f(x_0)-f_\star) L 1 ∥ x 0 − x ⋆ ∥ ( f ( x 0 ) − f ⋆ ) c 0 ≥ 0 c_0\ge0 c 0 ≥ 0 x ⋆ x_\star x ⋆ Lemma B.6 ), and it is the only place where the second constant of (14) enters. Item (iii) gives a linear rate under the PL condition.
Comparison with gradient methods at ρ = 0 \rho=0 ρ = 0 Let us now compare our guarantees with the known ones in the degenerate case. For ρ = 0 \rho=0 ρ = 0 M = M L M=M_L M = M L γ / ( L 0 + L 1 ∥ ∇ f ( x t ) ∥ ) \gamma/(L_0+L_1\lVert\nabla f(x_t)\rVert) γ / ( L 0 + L 1 ∥ ∇ f ( x t )∥) e ρ / ( γ χ ( ρ , γ ) ) e^\rho/(\gamma\chi(\rho,\gamma)) e ρ / ( γ χ ( ρ , γ )) 1 / ( 1 + 2 γ − e γ ) 1/(1+2\gamma-e^\gamma) 1/ ( 1 + 2 γ − e γ ) 1 / ( 2 log 2 − 1 ) ≈ 2.59 1/(2\log2-1)\approx2.59 1/ ( 2 log 2 − 1 ) ≈ 2.59 γ = log 2 \gamma=\log2 γ = log 2 [34 ] and Gorbunov et al. [ [13 ] , and Theorem 3.1(i)–(ii) give the same rates as Theorems 3.1 and 3.2 of Vankov et al. [ [34 ] : the best squared gradient norm decays as 1 / T 1/T 1/ T L 1 L_1 L 1 1 / T 1/T 1/ T L 1 ∥ x 0 − x ⋆ ∥ L_1\lVert x_0-x_\star\rVert L 1 ∥ x 0 − x ⋆ ∥ T T T ρ = 0 \rho=0 ρ = 0 ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 )
( H 0 , H 1 ) (H_0,H_1) ( H 0 , H 1 ) M = M H M=M_H M = M H Throughout this subsection f f f (4) and is nonconstant, so that M H > 0 M_H>0 M H > 0 CS-SAM is run with the curvature scale M = M H M=M_H M = M H ρ / ( H 0 + H 1 ( f ( x t ) − f ⋆ ) ) \rho/(H_0+H_1(f(x_t)-f_\star)) ρ / ( H 0 + H 1 ( f ( x t ) − f ⋆ )) γ / ( H 0 + H 1 ( f ( y t ) − f ⋆ ) ) \gamma/(H_0+H_1(f(y_t)-f_\star)) γ / ( H 0 + H 1 ( f ( y t ) − f ⋆ )) f ⋆ f_\star f ⋆ § 3.1 .
Theorem 3.2. Let f f f (4) and be nonconstant, let ρ ≥ 0 \rho\geq0 ρ ≥ 0 γ > 0 \gamma>0 γ > 0 χ ( ρ , γ ) > 0 \chi(\rho,\gamma)>0 χ ( ρ , γ ) > 0 ( x t ) t ≥ 0 (x_t)_{t\geq0} ( x t ) t ≥ 0 CS-SAM with M = M H M=M_H M = M H T ≥ 1 T\geq1 T ≥ 1
(i) (Nonconvex rate )
min 0 ≤ t < T ∥ ∇ f ( x t ) ∥ 2 ≤ e ρ ( H 0 + H 1 ( f ( x 0 ) − f ⋆ ) ) ( f ( x 0 ) − f ⋆ ) γ χ ( ρ , γ ) T (19) \min_{0\leq t<T}\|\nabla f(x_t)\|^2\leq\frac{e^\rho(H_0+H_1(f(x_0)-f_\star))(f(x_0)-f_\star)}{\gamma\chi(\rho,\gamma)T} \tag*{(19)} 0 ≤ t < T min ∥∇ f ( x t ) ∥ 2 ≤ γ χ ( ρ , γ ) T e ρ ( H 0 + H 1 ( f ( x 0 ) − f ⋆ )) ( f ( x 0 ) − f ⋆ ) (19) (ii) (Convex rate ) If in addition f f f x ⋆ x_\star x ⋆ c 0 ≥ 0 c_0\geq0 c 0 ≥ 0
f ( x T ) − f ⋆ ≤ e ρ ( H 0 + H 1 ( f ( x 0 ) − f ⋆ ) ) ∥ x 0 − x ⋆ ∥ 2 γ χ ( ρ , γ ) T (20) f(x_T)-f_\star\leq\frac{e^\rho(H_0+H_1(f(x_0)-f_\star))\|x_0-x_\star\|^2}{\gamma\chi(\rho,\gamma)T} \tag*{(20)} f ( x T ) − f ⋆ ≤ γ χ ( ρ , γ ) T e ρ ( H 0 + H 1 ( f ( x 0 ) − f ⋆ )) ∥ x 0 − x ⋆ ∥ 2 (20) (iii) (PL rate ) If in addition f f f μ \mu μ (15) , then
f ( x T ) − f ⋆ ≤ ( 1 − 2 μ γ e − ρ χ ( ρ , γ ) H 0 + H 1 ( f ( x 0 ) − f ⋆ ) ) T ( f ( x 0 ) − f ⋆ ) . (21) f(x_T)-f_\star\leq\left(1-\frac{2\mu\gamma e^{-\rho}\chi(\rho,\gamma)}{H_0+H_1(f(x_0)-f_\star)}\right)^T(f(x_0)-f_\star). \tag*{(21)} f ( x T ) − f ⋆ ≤ ( 1 − H 0 + H 1 ( f ( x 0 ) − f ⋆ ) 2 μ γ e − ρ χ ( ρ , γ ) ) T ( f ( x 0 ) − f ⋆ ) . (21) The three items have the same shape as in Theorem 3.1, with one difference worth pointing out: the dependence on the curvature parameters is different. Item (i) bounds the best squared gradient norm by O ( 1 / T ) O(1/T) O ( 1/ T ) ( H 0 + H 1 ( f ( x 0 ) − f ⋆ ) ) ( f ( x 0 ) − f ⋆ ) (H_0+H_1(f(x_0)-f_\star))(f(x_0)-f_\star) ( H 0 + H 1 ( f ( x 0 ) − f ⋆ )) ( f ( x 0 ) − f ⋆ ) L 1 L_1 L 1 H 1 H_1 H 1 1 / T 1/T 1/ T O ( 1 / T ) O(1/T) O ( 1/ T ) ( H 0 + H 1 ( f ( x 0 ) − f ⋆ ) ) ∥ x 0 − x ⋆ ∥ 2 (H_0+H_1(f(x_0)-f_\star))\|x_0-x_\star\|^2 ( H 0 + H 1 ( f ( x 0 ) − f ⋆ )) ∥ x 0 − x ⋆ ∥ 2 c 0 ≥ 0 c_0\geq0 c 0 ≥ 0 § 3.1 . Item (iii) gives a linear rate under the PL condition, with contraction factor 1 − 2 μ γ e − ρ χ ( ρ , γ ) / ( H 0 + H 1 ( f ( x 0 ) − f ⋆ ) ) 1-2\mu\gamma e^{-\rho}\chi(\rho,\gamma)/(H_0+H_1(f(x_0)-f_\star)) 1 − 2 μ γ e − ρ χ ( ρ , γ ) / ( H 0 + H 1 ( f ( x 0 ) − f ⋆ ))
**Comparison with gradient methods at ρ = 0. ∗ ∗ F o r \rho=0.** For ρ = 0. ∗ ∗ F or CS-SAM with M = M H M=M_H M = M H γ / ( H 0 + H 1 ( f ( x t ) − f ⋆ ) ) \gamma/(H_0+H_1(f(x_t)-f_\star)) γ / ( H 0 + H 1 ( f ( x t ) − f ⋆ )) § 3.1 , the constant e ρ / ( γ χ ( ρ , γ ) ) e^\rho/(\gamma\chi(\rho,\gamma)) e ρ / ( γ χ ( ρ , γ )) 1 / ( 2 log 2 − 1 ) ≈ 2.59 1/(2\log2-1)\approx2.59 1/ ( 2 log 2 − 1 ) ≈ 2.59 γ = log 2 \gamma=\log2 γ = log 2 [2 ] , who took 1 / ( 10 H 0 + 20 H 1 ( f ( x t ) − f ⋆ ) ) 1/(10H_0+20H_1(f(x_t)-f_\star)) 1/ ( 10 H 0 + 20 H 1 ( f ( x t ) − f ⋆ )) 1 / T 1/T 1/ T γ = log 2 \gamma=\log2 γ = log 2 1 / log 2 ≈ 1.44 1/\log2\approx1.44 1/ log 2 ≈ 1.44 ρ = 0 \rho=0 ρ = 0 χ ( ρ , γ ) > 0 \chi(\rho,\gamma)>0 χ ( ρ , γ ) > 0 ( H 0 , H 1 ) (H_0,H_1) ( H 0 , H 1 )
Remark 3.3. As we show in Proposition 2.4(iv), every objective satisfying (3) also satisfies (4) with H 0 = 3 L 0 / 2 H_0=3L_0/2 H 0 = 3 L 0 /2 H 1 = 3 L 1 2 / ( 2 ( 2 log 2 − 1 ) ) H_1=3L_1^2/(2(2\log2-1)) H 1 = 3 L 1 2 / ( 2 ( 2 log 2 − 1 )) CS-SAM with M = M L M=M_L M = M L CS-SAM with M = M H M=M_H M = M H M L M_L M L M H M_H M H
Numerical experiments
In this section, we first verify the results of § 2 on the two one-dimensional objectives of Proposition 2.1 (§ 4.1 ), and we then test CS-SAM on the training of deep neural networks against tuned SAM and USAM baselines (§ 4.2 ). The complete protocols are given in Appendix § 12 .
Verification of Section 2
The experiments of this subsection are deterministic and one-dimensional, with exact function values and gradients. We use the quadratic f ( x ) = x 2 / 2 f(x)=x^2/2 f ( x ) = x 2 /2 f ( x ) = x 4 / 4 f(x)=x^4/4 f ( x ) = x 4 /4 M L = M H ≡ 1 M_L=M_H\equiv1 M L = M H ≡ 1 M L ( x ) = 4 + ∣ x ∣ 3 M_L(x)=4+|x|^3 M L ( x ) = 4 + ∣ x ∣ 3 M H ( x ) = 3 + 3 x 4 / 4 M_H(x)=3+3x^4/4 M H ( x ) = 3 + 3 x 4 /4 ( L 0 , L 1 ) = ( 4 , 1 ) (L_0,L_1)=(4,1) ( L 0 , L 1 ) = ( 4 , 1 ) ( H 0 , H 1 ) = ( 3 , 3 ) (H_0,H_1)=(3,3) ( H 0 , H 1 ) = ( 3 , 3 ) 3 x 2 3x^2 3 x 2 x x x § 12 .§ 1 ). Throughout, CS-SAM is run with ρ = γ = 1 / 8 \rho=\gamma=1/8 ρ = γ = 1/8 χ ( ρ , γ ) > 0 \chi(\rho,\gamma)>0 χ ( ρ , γ ) > 0 c 0 ≥ 0 c_0\ge0 c 0 ≥ 0 Figure 1 .
Figure 1. Verification of § 2 on the objectives of Proposition 2.1. (a) Iterates of SAM on f ( x ) = x 2 / 2 f(x)=x^2/2 f ( x ) = x 2 /2 ∣ x t ∣ |x_t| ∣ x t ∣ f ( x ) = x 4 / 4 f(x)=x^4/4 f ( x ) = x 4 /4 (5) against the gradient norm and the bound e ρ − 1 e^\rho-1 e ρ − 1
Two-cycle and divergence. We first run the three methods on the two objectives. On the quadratic, SAM with r = 1 r=1 r = 1 η = 0.2 \eta=0.2 η = 0.2 x 0 = 3 x_0=3 x 0 = 3 ± a \pm a ± a a = η r / ( 2 − η ) = 1 / 9 a=\eta r/(2-\eta)=1/9 a = η r / ( 2 − η ) = 1/9 ρ = 1 / 8 \rho=1/8 ρ = 1/8 η = 1 / 32 \eta=1/32 η = 1/32 x 0 = 4 x_0=4 x 0 = 4 ( 2 / ( η ρ 3 ) ) 1 / 8 ≈ 3.67 (2/(\eta\rho^3))^{1/8}\approx3.67 ( 2/ ( η ρ 3 ) ) 1/8 ≈ 3.67 Figure 1 a and Figure 1 b show the iterates. We observe that SAM oscillates between ± 1 / 9 \pm1/9 ± 1/9 ∣ x 2 ∣ ≈ 10 11 |x_2|\approx10^{11} ∣ x 2 ∣ ≈ 1 0 11
Uniform distortion control. We next evaluate the relative gradient distortion (5) of each perturbation as a function of the gradient norm, no outer step enters this measurement. Here SAM uses r = 1 / 8 r=1/8 r = 1/8 ρ = 1 / 8 \rho=1/8 ρ = 1/8 1 / 8 1/8 1/8 Figure 1 c and Figure 1 d show the distortion together with the bound e ρ − 1 ≈ 0.133 e^\rho-1\approx0.133 e ρ − 1 ≈ 0.133 § 2.1 : the distortion of SAM equals ρ / ∥ ∇ f ( x ) ∥ \rho/\lVert\nabla f(x)\rVert ρ / ∥ ∇ f ( x )∥ ( 1 + ρ x 2 ) 3 − 1 (1+\rho x^2)^3-1 ( 1 + ρ x 2 ) 3 − 1 e ρ − 1 e^\rho-1 e ρ − 1 ρ \rho ρ
DNN experiments
In this subsection, we test CS-SAM on the training of deep neural networks and compare it with tuned SAM and USAM baselines. We go beyond the deterministic setting of § 4.1 and of our guarantees: the networks are trained with minibatch gradients, and the curvature scales are evaluated on minibatch quantities. The experiments are designed to test whether the two scales are competitive in practice. The complete grids and the per-run configurations are given in Appendix § 12 .§ 2 .
We train ResNet-20 and ResNet-32 with batch normalization on CIFAR-10 and CIFAR-100 for 200 epochs with batch size 128, random-crop and horizontal-flip augmentation without cutout, and the cross-entropy loss. Momentum and weight decay are 0 for every method, so that the comparison isolates the update rules. In the minibatch setting the M L M_L M L L 0 + L 1 ∥ ∇ f i ( x ) ∥ L_0 + L_1 \lVert\nabla f_i(x) \rVert L 0 + L 1 ∥ ∇ f i ( x )∥ M H M_H M H H 0 + H 1 [ f i ( x ) − ℓ i ∗ ] + H_0 + H_1[f_i(x) - \ell_i^*]_+ H 0 + H 1 [ f i ( x ) − ℓ i ∗ ] + ℓ i ∗ \ell_i^* ℓ i ∗ f i f_i f i [ z ] + = max { z , 0 } [z]_+ = \max\{z, 0\} [ z ] + = max { z , 0 } ℓ i ∗ = 0 \ell_i^* = 0 ℓ i ∗ = 0 4 × 4 4 \times4 4 × 4 × \times × M L M_L M L ρ ∈ { 0.2 , 0.4 , 0.8 , 1.6 } \rho\in\{0.2, 0.4, 0.8, 1.6\} ρ ∈ { 0.2 , 0.4 , 0.8 , 1.6 } γ ∈ { 0.2 , 0.4 , 0.8 } \gamma\in\{0.2, 0.4, 0.8\} γ ∈ { 0.2 , 0.4 , 0.8 } L 0 ∈ { 0.02 , 0.5 , 2 } L_0 \in\{0.02, 0.5, 2\} L 0 ∈ { 0.02 , 0.5 , 2 } M H M_H M H ρ , γ ∈ { 0.3 , 1 , 3 } \rho, \gamma\in\{0.3, 1, 3\} ρ , γ ∈ { 0.3 , 1 , 3 } H 1 ∈ { 1 , 3 , 10 , 30 } H_1 \in\{1, 3, 10, 30\} H 1 ∈ { 1 , 3 , 10 , 30 } Table 3 reports, for each method and cell, the mean and standard deviation over the three seeds of the best test accuracy. We observe that both curvature scales are competitive: CS-SAM with M H M_H M H M L M_L M L
Table 3 : Best test accuracy (%, maximum over 200 epochs), mean ± \pm ±
Table 3. Best test accuracy (%, maximum over 200 epochs), mean ± \pm ±
Conclusion
In this work, we studied sharpness-aware minimization under generalized smoothness through the relative gradient distortion. We showed that the distortion of SAM and USAM can become unbounded at opposite ends of the gradient scale, derived a necessary condition for uniform distortion control, and introduced CS-SAM, which scales the perturbation and the descent step by the same admissible curvature scale and keeps the distortion bounded. Under ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) ( H 0 , H 1 ) (H_0,H_1) ( H 0 , H 1 ) O ( 1 / T ) O(1/T) O ( 1/ T ) ρ = 0 \rho= 0 ρ = 0 f ⋆ f_\star f ⋆
AI use statement
We used generative AI tools to suggest proof ideas, which the authors checked and wrote up, and to streamline and edit the wording of some paragraphs and sentences. We take responsibility for the final content of this work.
Acknowledgments
The authors’ contribution to this work was supported by NSF CAREER 2542902, and AFOSR YIP FA9550-26-1-B353.
Supplementary Material
The appendix is organized as follows. In Appendix § 8 , we give a more detailed discussion of related work. In Appendix § 9 , we collect the auxiliary lemmas on admissible curvature scales and on a single iteration of CS-SAM that all proofs rely on. Appendix § 10 presents the proofs for § 2 : the verification of the distortion bounds (6) and (7) , and the proofs of Proposition 2.1, Theorem 2.2, Proposition 2.4, and Theorem 2.5. Appendix § 11 presents the proofs for § 3 , with Appendix § 11 .§ 1 for the ( L 0 , L 1 ) (L_0, L_1) ( L 0 , L 1 ) § 11 .§ 2 for the ( H 0 , H 1 ) (H_0, H_1) ( H 0 , H 1 ) § 12 gives the experimental details for § 4 .
Further Related Work
In this section, we complement the discussion of related work in § 1 with a more detailed survey. We proceed from the broader literature on the dynamics of SAM and on adaptive perturbation rules to the lines closest to our work: relative control of the perturbation-induced gradient error, optimization under the curvature models (3) and (4) , and relative gradient models. We close each paragraph with a brief comparison with our results.
SAM, normalization, and optimization dynamics. Sharpness-Aware Minimization replaces the gradient at the current iterate with a gradient evaluated after a parameter perturbation, motivated by minimizing the loss over a fixed local neighborhood [12 ] . Subsequent work has shown that its behavior cannot be understood solely as ordinary descent on a smooth objective. Andriushchenko and Flammarion [ [3 ] studied the implicit bias of SAM and the role of stochastic sharpness, while Dai et al. [ [10 ] identified stabilization and continued motion along manifolds of minima as important effects of the gradient normalization. Bartlett et al. [ [5 ] showed that fixed-radius SAM typically approaches a two-cycle on convex quadratics and that analogous oscillations can induce drift toward regions with smaller Hessian spectral norm on nonquadratic landscapes. Si and Yun [ [29 ] established unavoidable stationarity neighborhoods for practical fixed-radius SAM in several settings, and Park et al. [ [26 ] showed that SAM can converge to points at which the perturbed-point gradient vanishes even though the original gradient does not. Our quadratic construction in Proposition 2.1(i) should therefore be viewed as an exact illustration of established late-stage phenomena. Our new point is that the low-gradient failure of SAM and the high-gradient amplification of USAM are complementary consequences of expressing the perturbation budget in inappropriate units, which Theorem 2.2 makes precise.
Unified and adaptive perturbation rules. Unified SAM [24 ] interpolates between SAM and USAM through a fixed normalization rule and provides deterministic and stochastic convergence guarantees under several sampling and step-size choices. Other methods adapt the perturbation: ASAM [21 ] rescales the parameter-space neighborhood to obtain scale invariance, whereas Fisher SAM [19 ] replaces the Euclidean ball by a Fisher-information geometry. LETS [Wang et al., 2024] learns the perturbation radius through a bilevel training–validation objective, LightSAM [7 ] adapts the perturbation radius and the outer learning rate using AdaGrad- and Adam-style statistics, and LE-SAM [Wang et al., 2026] replaces the fixed parameter-space radius by a fixed loss-space budget. More recent methods adapt the radius from the observed Taylor-approximation error [11 ] or redistribute a fixed global radius across parameter blocks using moving averages of blockwise gradient energy [17 ] . Polyak-type SAM schedulers instead adapt the outer step from function values under classical smoothness [25 ] . In contrast, CS-SAM adapts the perturbation through one scalar quantity, an upper bound on the local curvature (Definition 2.3 ), rather than through validation performance, optimizer statistics, parameter scale, blockwise gradient energy, or a loss-space budget. Moreover, the scaling of the perturbation is derived rather than chosen: it is motivated by the necessary condition of Theorem 2.2 for uniformly bounded relative gradient distortion, and Theorem 2.5 shows that it meets this requirement for every admissible scale. Finally, the same curvature scale sets the outer step, so that a single quantity controls both the perturbation and the descent step.
Relative-error control and exact stationarity. Inexact-gradient analysis provides a natural framework for studying gradients evaluated at perturbed points. Khanh et al. [ [18 ] used this perspective to establish convergence results for several normalized and unnormalized SAM variants, including conditions that control the perturbation-induced gradient error. Adly and Le [ [1 ] analyzed the deterministic family
y t = x t + ρ ∇ f ( x t ) ∥ ∇ f ( x t ) ∥ α , 0 ≤ α ≤ 1 , y_t = x_t + \rho\frac{\nabla f(x_t)}{\lVert\nabla f(x_t) \rVert^\alpha}, \qquad0 \le\alpha\le1, y t = x t + ρ ∥ ∇ f ( x t ) ∥ α ∇ f ( x t ) , 0 ≤ α ≤ 1 , under classical smoothness (2) . They identified stationarity floors for constant-parameter rules and proposed a clipped perturbation that agrees with the original rule away from stationarity but becomes gradientproportional near stationary points, yielding ∥ ∇ f ( x t ) ∥ → 0 \lVert\nabla f(x_t) \rVert\to0 ∥ ∇ f ( x t )∥ → 0
Optimization beyond uniform smoothness. The ( L 0 , L 1 ) (L_0,L_1) ( L 0 , L 1 ) [6 , 9 , 13 , 20 , 22 , 34 ] (Zhang et al. 2020a). Curvature-scaled ordinary gradient steps are therefore established machinery rather than a contribution of this paper. The same model has also been extended to variational inequalities and root-finding problems, with adaptive-stepsize and extragradient-type methods [8 , 14 , 33 ] (Yoon et al. 2026). The loss-dependent condition {(4)} has likewise been used to explain learning-rate warm-up [2 ] and to analyze line search, steepest descent, and adaptive methods [35 ] (Vaswani et al. 2026). Our contribution is to use the same machinery for the perturbation: in CS-SAM, the curvature scale that sets the descent step also sets the perturbation, and Theorem 2.5 shows that this keeps the relative gradient distortion uniformly bounded. The resulting rates have the same asymptotic orders in T T T ρ = 0 \rho= 0 ρ = 0 § 3 ).
Relative gradient models and curvature geometry. Gradient-normalized smoothness characterizes the neighborhood in which the gradient admits a reliable relative approximation, and uses it to globalize methods based on approximate Hessians [28 ] . We specialize this relative-locality principle to a first-order sharpness-aware perturbation, with an explicit rule based on a scalar curvature scale and a necessity result for perturbations in the gradient direction (Theorem 2.2). The exponential local models of {(11)} are also reminiscent of generalized self-concordance, where controlled curvature growth replaces a uniform Hessian bound [31 ] ; unlike that convex, Newton-oriented framework, our analysis certifies a two-gradient SAM update on nonconvex objectives.
Geometry, generalization, and scope. Parameter-space sharpness is sensitive to neural-network reparameterization, and empirical evaluations show that no single sharpness measure universally predicts generalization [4 , 21 ] . Fisher SAM and μ P 2 \mu P^2 μ P 2 [16 , 19 ] . Moreover, late-stage SAM can be especially effective for selecting flatter minima [Zhou et al., 2025], while standard parameter-space SAM can optimize spurious notions of sharpness in language modeling [30 ] . CS-SAM should therefore be viewed as an optimization method rather than a parameterization-invariant theory of generalization. The present analysis is deterministic, assumes exact gradients and function values, and uses a global Euclidean scalar curvature scale.
Auxiliary lemmas
In this section, we collect the lemmas used in Appendices C and D. All of them are stated for a general κ \kappa κ M M M Definition 2.3 ), with three exceptions: Lemma B.1 is the differential form of Grönwall’s inequality, Lemmas B.7 and B.8 concern the loss scale M H M_H M H (4) and Lemma B.9 is an elementary fact about sequences.
Conventions for the proofs. The constants χ ( ρ , γ ) \chi(\rho,\gamma) χ ( ρ , γ ) c 0 c_0 c 0 (14) . If the method stops at some x t x_t x t ∇ f ( x t ) = 0 \nabla f(x_t)=0 ∇ f ( x t ) = 0 x t x_t x t ∇ f ( x t ) ≠ 0 \nabla f(x_t)\ne0 ∇ f ( x t ) = 0 t t t χ ( ρ , γ ) > 0 \chi(\rho,\gamma)>0 χ ( ρ , γ ) > 0 2 − e ρ > γ ω ( γ ) e 3 ρ > 0 2-e^\rho>\gamma\omega(\gamma)e^{3\rho}>0 2 − e ρ > γ ω ( γ ) e 3 ρ > 0 ρ < log 2 \rho<\log2 ρ < log 2 γ e − ρ χ ( ρ , γ ) > 0 \gamma e^{-\rho}\chi(\rho,\gamma)>0 γ e − ρ χ ( ρ , γ ) > 0 ω ( u ) = ∑ k ≥ 0 u k ( k + 2 ) ! \omega(u)=\sum_{k\ge0}\frac{u^k}{(k+2)!} ω ( u ) = ∑ k ≥ 0 ( k + 2 )! u k ω \omega ω [ 0 , ∞ ) [0,\infty) [ 0 , ∞ )
u + u 2 ω ( u ) = e u − 1 , u − u 2 ω ( u ) = 1 + 2 u − e u ( u ≥ 0 ) . (22) u+u^2\omega(u)=e^u-1,\qquad u-u^2\omega(u)=1+2u-e^u\qquad(u\ge0). \tag*{(22)} u + u 2 ω ( u ) = e u − 1 , u − u 2 ω ( u ) = 1 + 2 u − e u ( u ≥ 0 ) . (22) We begin with the differential form of Grönwall’s inequality [15 ] , stated for absolutely continuous functions because the gradient scale M L M_L M L
Lemma B.1 (Grönwall’s inequality; see [15 ] ). Let c ≥ 0 c\ge0 c ≥ 0 g : [ 0 , 1 ] → [ 0 , ∞ ) g:[0,1]\to[0,\infty) g : [ 0 , 1 ] → [ 0 , ∞ ) g ′ ( s ) ≤ c g ( s ) g'(s)\le cg(s) g ′ ( s ) ≤ c g ( s ) s ∈ [ 0 , 1 ] s\in[0,1] s ∈ [ 0 , 1 ] g ( s ) ≤ g ( 0 ) e c s g(s)\le g(0)e^{cs} g ( s ) ≤ g ( 0 ) e cs s ∈ [ 0 , 1 ] s\in[0,1] s ∈ [ 0 , 1 ]
Proof. The function h ( s ) : = e − c s g ( s ) h(s):=e^{-cs}g(s) h ( s ) := e − cs g ( s ) [ 0 , 1 ] [0,1] [ 0 , 1 ] h ′ ( s ) = e − c s ( g ′ ( s ) − c g ( s ) ) ≤ 0 h'(s)=e^{-cs}(g'(s)-cg(s))\le0 h ′ ( s ) = e − cs ( g ′ ( s ) − c g ( s )) ≤ 0 s s s h ( s ) = h ( 0 ) + ∫ 0 s h ′ ( u ) d u ≤ h ( 0 ) = g ( 0 ) h(s)=h(0)+\int_0^s h'(u)\,\mathrm{d}u\le h(0)=g(0) h ( s ) = h ( 0 ) + ∫ 0 s h ′ ( u ) d u ≤ h ( 0 ) = g ( 0 ) g ( s ) ≤ g ( 0 ) e c s g(s)\le g(0)e^{cs} g ( s ) ≤ g ( 0 ) e cs
Lemma B.2. Let M M M κ \kappa κ f f f x , d ∈ R d x,d\in\mathbb{R}^d x , d ∈ R d
∥ ∇ f ( x + d ) − ∇ f ( x ) ∥ ≤ M ( x ) e κ ∥ d ∥ − 1 κ ∥ d ∥ ∥ d ∥ , \lVert\nabla f(x+d)-\nabla f(x)\rVert\le M(x)\frac{e^{\kappa\lVert d\rVert}-1}{\kappa\lVert d\rVert}\lVert d\rVert, ∥ ∇ f ( x + d ) − ∇ f ( x )∥ ≤ M ( x ) κ ∥ d ∥ e κ ∥ d ∥ − 1 ∥ d ∥ , ∣ f ( x + d ) − f ( x ) − ⟨ ∇ f ( x ) , d ⟩ ∣ ≤ M ( x ) ω ( κ ∥ d ∥ ) ∥ d ∥ 2 , (23) \left|f(x+d)-f(x)-\langle\nabla f(x),d\rangle\right|\le M(x)\omega(\kappa\lVert d\rVert)\lVert d\rVert^2, \tag*{(23)} ∣ f ( x + d ) − f ( x ) − ⟨ ∇ f ( x ) , d ⟩ ∣ ≤ M ( x ) ω ( κ ∥ d ∥) ∥ d ∥ 2 , (23) where the quotient is interpreted as 1 1 1 κ ∥ d ∥ = 0 \kappa\lVert d\rVert=0 κ ∥ d ∥ = 0
Proof. By the fundamental theorem of calculus and the first two admissibility conditions,
∥ ∇ f ( x + d ) − ∇ f ( x ) ∥ ≤ ∫ 0 1 ∥ ∇ 2 f ( x + s d ) ∥ ∥ d ∥ d s ≤ ∥ d ∥ ∫ 0 1 M ( x ) e κ s ∥ d ∥ d s = M ( x ) ∥ d ∥ e κ ∥ d ∥ − 1 κ ∥ d ∥ . \begin{aligned}
\lVert\nabla f(x+d)-\nabla f(x)\rVert\le\int_0^1\lVert\nabla^2 f(x+sd)\rVert\lVert d\rVert\,\mathrm{d}s \\
&\le\lVert d\rVert\int_0^1M(x)e^{\kappa s\lVert d\rVert}\,\mathrm{d}s=M(x)\lVert d\rVert\frac{e^{\kappa\lVert d\rVert}-1}{\kappa\lVert d\rVert}.
\end{aligned} ∥ ∇ f ( x + d ) − ∇ f ( x )∥ ≤ ∫ 0 1 ∥ ∇ 2 f ( x + s d )∥ ∥ d ∥ d s ≤ ∥ d ∥ ∫ 0 1 M ( x ) e κ s ∥ d ∥ d s = M ( x ) ∥ d ∥ κ ∥ d ∥ e κ ∥ d ∥ − 1 . For the second inequality, write
f ( x + d ) − f ( x ) − ⟨ ∇ f ( x ) , d ⟩ = ∫ 0 1 ⟨ ∇ f ( x + s d ) − ∇ f ( x ) , d ⟩ d s f(x+d)-f(x)-\langle\nabla f(x),d\rangle=\int_0^1\langle\nabla f(x+sd)-\nabla f(x),d\rangle\,\mathrm{d}s f ( x + d ) − f ( x ) − ⟨ ∇ f ( x ) , d ⟩ = ∫ 0 1 ⟨ ∇ f ( x + s d ) − ∇ f ( x ) , d ⟩ d s and apply the first inequality with d = s d d=sd d = s d
∥ ∇ f ( x + s d ) − ∇ f ( x ) ∥ ≤ M ( x ) ∥ d ∥ e s κ ∥ d ∥ − 1 κ ∥ d ∥ . \lVert\nabla f(x+sd)-\nabla f(x)\rVert\le M(x)\lVert d\rVert\frac{e^{s\kappa\lVert d\rVert}-1}{\kappa\lVert d\rVert}. ∥ ∇ f ( x + s d ) − ∇ f ( x )∥ ≤ M ( x ) ∥ d ∥ κ ∥ d ∥ e s κ ∥ d ∥ − 1 . Integrating,
∣ f ( x + d ) − f ( x ) − ⟨ ∇ f ( x ) , d ⟩ ∣ ≤ M ( x ) ∥ d ∥ 2 ∫ 0 1 e s κ ∥ d ∥ − 1 κ ∥ d ∥ d s = M ( x ) ∥ d ∥ 2 e κ ∥ d ∥ − 1 − κ ∥ d ∥ ( κ ∥ d ∥ ) 2 = M ( x ) ω ( κ ∥ d ∥ ) ∥ d ∥ 2 . \begin{aligned}
\left|f(x+d)-f(x)-\langle\nabla f(x),d\rangle\right|\le M(x)\lVert d\rVert^2\int_0^1\frac{e^{s\kappa\lVert d\rVert}-1}{\kappa\lVert d\rVert}\,\mathrm{d}s \\
&=M(x)\lVert d\rVert^2\frac{e^{\kappa\lVert d\rVert}-1-\kappa\lVert d\rVert}{(\kappa\lVert d\rVert)^2}=M(x)\omega(\kappa\lVert d\rVert)\lVert d\rVert^2.
\end{aligned} ∣ f ( x + d ) − f ( x ) − ⟨ ∇ f ( x ) , d ⟩ ∣ ≤ M ( x ) ∥ d ∥ 2 ∫ 0 1 κ ∥ d ∥ e s κ ∥ d ∥ − 1 d s = M ( x ) ∥ d ∥ 2 ( κ ∥ d ∥ ) 2 e κ ∥ d ∥ − 1 − κ ∥ d ∥ = M ( x ) ω ( κ ∥ d ∥) ∥ d ∥ 2 . Lemma B.3. Let M M M κ \kappa κ f f f x ∈ R d x \in\mathbb{R}^{d} x ∈ R d
f ( x ) − f ⋆ ≥ ( 2 log 2 − 1 ) ∥ ∇ f ( x ) ∥ 2 M ( x ) . (24) f(x)-f_{\star} \ge(2\log2-1)\frac{\lVert\nabla f(x)\rVert^{2}}{M(x)}. \tag*{(24)} f ( x ) − f ⋆ ≥ ( 2 log 2 − 1 ) M ( x ) ∥ ∇ f ( x ) ∥ 2 . (24) Proof. Fix α ≥ 0 \alpha\ge0 α ≥ 0 x − α ∇ f ( x ) / M ( x ) x-\alpha\nabla f(x)/M(x) x − α ∇ f ( x ) / M ( x ) κ ∥ α ∇ f ( x ) / M ( x ) ∥ = α κ ∥ ∇ f ( x ) ∥ / M ( x ) ≤ α \kappa\lVert\alpha\nabla f(x)/M(x)\rVert=\alpha\kappa\lVert\nabla f(x)\rVert/M(x)\le\alpha κ ∥ α ∇ f ( x ) / M ( x )∥ = α κ ∥ ∇ f ( x )∥ / M ( x ) ≤ α Lemma B.2 , the monotonicity of ω \omega ω (22) ,
f ⋆ ≤ f ( x − α ∇ f ( x ) M ( x ) ) ≤ f ( x ) − α ∥ ∇ f ( x ) ∥ 2 M ( x ) + M ( x ) ω ( α ) α 2 ∥ ∇ f ( x ) ∥ 2 M ( x ) 2 = f ( x ) − ( α − α 2 ω ( α ) ) ∥ ∇ f ( x ) ∥ 2 M ( x ) = f ( x ) − ( 1 + 2 α − e α ) ∥ ∇ f ( x ) ∥ 2 M ( x ) . \begin{aligned}
f_{\star}\le f\left(x-\alpha\frac{\nabla f(x)}{M(x)}\right)\le f(x)-\alpha\frac{\lVert\nabla f(x)\rVert^{2}}{M(x)}+M(x)\omega(\alpha)\alpha^{2}\frac{\lVert\nabla f(x)\rVert^{2}}{M(x)^{2}} \\
&= f(x)-\left(\alpha-\alpha^{2}\omega(\alpha)\right)\frac{\lVert\nabla f(x)\rVert^{2}}{M(x)}
= f(x)-\left(1+2\alpha-e^{\alpha}\right)\frac{\lVert\nabla f(x)\rVert^{2}}{M(x)}.
\end{aligned} f ⋆ ≤ f ( x − α M ( x ) ∇ f ( x ) ) ≤ f ( x ) − α M ( x ) ∥ ∇ f ( x ) ∥ 2 + M ( x ) ω ( α ) α 2 M ( x ) 2 ∥ ∇ f ( x ) ∥ 2 = f ( x ) − ( α − α 2 ω ( α ) ) M ( x ) ∥ ∇ f ( x ) ∥ 2 = f ( x ) − ( 1 + 2 α − e α ) M ( x ) ∥ ∇ f ( x ) ∥ 2 . Thus we get f ( x ) − f ⋆ ≥ ( 1 + 2 α − e α ) ∥ ∇ f ( x ) ∥ 2 / M ( x ) f(x)-f_{\star}\ge(1+2\alpha-e^{\alpha})\lVert\nabla f(x)\rVert^{2}/M(x) f ( x ) − f ⋆ ≥ ( 1 + 2 α − e α ) ∥ ∇ f ( x ) ∥ 2 / M ( x ) α ≥ 0 \alpha\ge0 α ≥ 0 α = log 2 \alpha=\log2 α = log 2 2 log 2 − 1 2\log2-1 2 log 2 − 1
Lemma B.4. Let M M M κ \kappa κ f f f ρ ≥ 0 \rho\ge0 ρ ≥ 0 x t x_t x t
e − ρ M ( x t ) ≤ M ( y t ) ≤ e ρ M ( x t ) , ∥ ∇ f ( y t ) − ∇ f ( x t ) ∥ ≤ ( e ρ − 1 ) ∥ ∇ f ( x t ) ∥ , (25) e^{-\rho}M(x_t)\le M(y_t)\le e^{\rho}M(x_t),\qquad\lVert\nabla f(y_t)-\nabla f(x_t)\rVert\le(e^{\rho}-1)\lVert\nabla f(x_t)\rVert, \tag*{(25)} e − ρ M ( x t ) ≤ M ( y t ) ≤ e ρ M ( x t ) , ∥ ∇ f ( y t ) − ∇ f ( x t )∥ ≤ ( e ρ − 1 ) ∥ ∇ f ( x t )∥ , (25) ∥ ∇ f ( y t ) ∥ ≤ e ρ ∥ ∇ f ( x t ) ∥ , ⟨ ∇ f ( x t ) , ∇ f ( y t ) ⟩ ≥ ( 2 − e ρ ) ∥ ∇ f ( x t ) ∥ 2 . (26) \lVert\nabla f(y_t)\rVert\le e^{\rho}\lVert\nabla f(x_t)\rVert,\qquad\langle\nabla f(x_t),\nabla f(y_t)\rangle\ge(2-e^{\rho})\lVert\nabla f(x_t)\rVert^{2}. \tag*{(26)} ∥ ∇ f ( y t )∥ ≤ e ρ ∥ ∇ f ( x t )∥ , ⟨ ∇ f ( x t ) , ∇ f ( y t )⟩ ≥ ( 2 − e ρ ) ∥ ∇ f ( x t ) ∥ 2 . (26) Proof. For ρ = 0 \rho=0 ρ = 0 y t = x t y_t=x_t y t = x t ρ > 0 \rho>0 ρ > 0 κ ∥ y t − x t ∥ = ρ κ ∥ ∇ f ( x t ) ∥ / M ( x t ) ≤ ρ \kappa\lVert y_t-x_t\rVert=\rho\kappa\lVert\nabla f(x_t)\rVert/M(x_t)\le\rho κ ∥ y t − x t ∥ = ρ κ ∥ ∇ f ( x t )∥ / M ( x t ) ≤ ρ x t x_t x t y t y_t y t y t y_t y t x t x_t x t M ( y t ) ≤ M ( x t ) e κ ∥ y t − x t ∥ ≤ e ρ M ( x t ) M(y_t)\le M(x_t)e^{\kappa\lVert y_t-x_t\rVert}\le e^{\rho}M(x_t) M ( y t ) ≤ M ( x t ) e κ ∥ y t − x t ∥ ≤ e ρ M ( x t ) M ( x t ) ≤ e ρ M ( y t ) M(x_t)\le e^{\rho}M(y_t) M ( x t ) ≤ e ρ M ( y t ) Lemma B.2 with d = y t − x t d=y_t-x_t d = y t − x t
∥ ∇ f ( y t ) − ∇ f ( x t ) ∥ ≤ M ( x t ) e κ ∥ y t − x t ∥ − 1 κ ∥ y t − x t ∥ ρ ∥ ∇ f ( x t ) ∥ M ( x t ) ≤ ρ ∥ ∇ f ( x t ) ∥ e ρ − 1 ρ = ( e ρ − 1 ) ∥ ∇ f ( x t ) ∥ , \begin{aligned}
\lVert\nabla f(y_t)-\nabla f(x_t)\rVert\le M(x_t)\frac{e^{\kappa\lVert y_t-x_t\rVert}-1}{\kappa\lVert y_t-x_t\rVert}\frac{\rho\lVert\nabla f(x_t)\rVert}{M(x_t)} \\
&\le\rho\lVert\nabla f(x_t)\rVert\frac{e^{\rho}-1}{\rho}=(e^{\rho}-1)\lVert\nabla f(x_t)\rVert,
\end{aligned} ∥ ∇ f ( y t ) − ∇ f ( x t )∥ ≤ M ( x t ) κ ∥ y t − x t ∥ e κ ∥ y t − x t ∥ − 1 M ( x t ) ρ ∥ ∇ f ( x t )∥ ≤ ρ ∥ ∇ f ( x t )∥ ρ e ρ − 1 = ( e ρ − 1 ) ∥ ∇ f ( x t )∥ , since u ↦ ( e u − 1 ) / u u\mapsto(e^{u}-1)/u u ↦ ( e u − 1 ) / u κ ∥ y t − x t ∥ ≤ ρ \kappa\lVert y_t-x_t\rVert\le\rho κ ∥ y t − x t ∥ ≤ ρ (26) follow from the triangle and Cauchy–Schwarz inequalities:
∥ ∇ f ( y t ) ∥ ≤ ∥ ∇ f ( x t ) ∥ + ∥ ∇ f ( y t ) − ∇ f ( x t ) ∥ ≤ e ρ ∥ ∇ f ( x t ) ∥ , \lVert\nabla f(y_t)\rVert\le\lVert\nabla f(x_t)\rVert+\lVert\nabla f(y_t)-\nabla f(x_t)\rVert\le e^{\rho}\lVert\nabla f(x_t)\rVert, ∥ ∇ f ( y t )∥ ≤ ∥ ∇ f ( x t )∥ + ∥ ∇ f ( y t ) − ∇ f ( x t )∥ ≤ e ρ ∥ ∇ f ( x t )∥ , ⟨ ∇ f ( x t ) , ∇ f ( y t ) ⟩ = ∥ ∇ f ( x t ) ∥ 2 + ⟨ ∇ f ( x t ) , ∇ f ( y t ) − ∇ f ( x t ) ⟩ ≥ ∥ ∇ f ( x t ) ∥ 2 − ( e ρ − 1 ) ∥ ∇ f ( x t ) ∥ 2 . \begin{aligned}
\langle\nabla f(x_t),\nabla f(y_t)\rangle=\lVert\nabla f(x_t)\rVert^{2}+\langle\nabla f(x_t),\nabla f(y_t)-\nabla f(x_t)\rangle\\
&\ge\lVert\nabla f(x_t)\rVert^{2}-(e^{\rho}-1)\lVert\nabla f(x_t)\rVert^{2}.
\end{aligned} ⟨ ∇ f ( x t ) , ∇ f ( y t )⟩ = ∥ ∇ f ( x t ) ∥ 2 + ⟨ ∇ f ( x t ) , ∇ f ( y t ) − ∇ f ( x t )⟩ ≥ ∥ ∇ f ( x t ) ∥ 2 − ( e ρ − 1 ) ∥ ∇ f ( x t ) ∥ 2 . Lemma B.5. Let M M M κ \kappa κ f f f ρ ≥ 0 \rho\ge0 ρ ≥ 0 γ > 0 \gamma>0 γ > 0 χ ( ρ , γ ) > 0 \chi(\rho,\gamma)>0 χ ( ρ , γ ) > 0 x t x_t x t
f ( x t + 1 ) ≤ f ( x t ) − χ ( ρ , γ ) γ M ( y t ) ∥ ∇ f ( x t ) ∥ 2 ≤ f ( x t ) − γ e − ρ χ ( ρ , γ ) ∥ ∇ f ( x t ) ∥ 2 M ( x t ) . (27) f(x_{t+1})\le f(x_t)-\chi(\rho,\gamma)\frac{\gamma}{M(y_t)}\lVert\nabla f(x_t)\rVert^{2}\le f(x_t)-\gamma e^{-\rho}\chi(\rho,\gamma)\frac{\lVert\nabla f(x_t)\rVert^{2}}{M(x_t)}. \tag*{(27)} f ( x t + 1 ) ≤ f ( x t ) − χ ( ρ , γ ) M ( y t ) γ ∥ ∇ f ( x t ) ∥ 2 ≤ f ( x t ) − γ e − ρ χ ( ρ , γ ) M ( x t ) ∥ ∇ f ( x t ) ∥ 2 . (27) In particular, f ( x t ) − f ⋆ f(x_t)-f_{\star} f ( x t ) − f ⋆ t t t
Proof. By the third admissibility condition at y t y_t y t x t + 1 − x t = − γ ∇ f ( y t ) / M ( y t ) x_{t+1}-x_t=-\gamma\nabla f(y_t)/M(y_t) x t + 1 − x t = − γ ∇ f ( y t ) / M ( y t )
κ ∥ x t + 1 − x t ∥ = γ κ ∥ ∇ f ( y t ) ∥ M ( y t ) ≤ γ . \kappa\lVert x_{t+1}-x_t\rVert=\gamma\kappa\frac{\lVert\nabla f(y_t)\rVert}{M(y_t)}\le\gamma. κ ∥ x t + 1 − x t ∥ = γ κ M ( y t ) ∥ ∇ f ( y t )∥ ≤ γ . Lemma B.2 at x t x_t x t ω \omega ω
f ( x t + 1 ) ≤ f ( x t ) − γ M ( y t ) ⟨ ∇ f ( x t ) , ∇ f ( y t ) ⟩ + M ( x t ) ω ( γ ) γ 2 M ( y t ) 2 ∥ ∇ f ( y t ) ∥ 2 . f(x_{t+1})\le f(x_t)-\frac{\gamma}{M(y_t)}\langle\nabla f(x_t),\nabla f(y_t)\rangle+M(x_t)\omega(\gamma)\frac{\gamma^{2}}{M(y_t)^{2}}\lVert\nabla f(y_t)\rVert^{2}. f ( x t + 1 ) ≤ f ( x t ) − M ( y t ) γ ⟨ ∇ f ( x t ) , ∇ f ( y t )⟩ + M ( x t ) ω ( γ ) M ( y t ) 2 γ 2 ∥ ∇ f ( y t ) ∥ 2 . By Lemma B.4 , ⟨ ∇ f ( x t ) , ∇ f ( y t ) ⟩ ≥ ( 2 − e ρ ) ∥ ∇ f ( x t ) ∥ 2 \langle\nabla f(x_t), \nabla f(y_t) \rangle\ge(2-e^\rho)\lVert\nabla f(x_t)\rVert^2 ⟨ ∇ f ( x t ) , ∇ f ( y t )⟩ ≥ ( 2 − e ρ ) ∥ ∇ f ( x t ) ∥ 2 M ( x t ) / M ( y t ) ≤ e ρ M(x_t)/M(y_t) \le e^\rho M ( x t ) / M ( y t ) ≤ e ρ ∥ ∇ f ( y t ) ∥ 2 ≤ e 2 ρ ∥ ∇ f ( x t ) ∥ 2 \lVert\nabla f(y_t)\rVert^2 \le e^{2\rho}\lVert\nabla f(x_t)\rVert^2 ∥ ∇ f ( y t ) ∥ 2 ≤ e 2 ρ ∥ ∇ f ( x t ) ∥ 2
f ( x t + 1 ) ≤ f ( x t ) − γ M ( y t ) [ 2 − e ρ − γ ω ( γ ) e 3 ρ ] ∥ ∇ f ( x t ) ∥ 2 = f ( x t ) − χ ( ρ , γ ) γ M ( y t ) ∥ ∇ f ( x t ) ∥ 2 . \begin{aligned}
f(x_{t+1}) &\le f(x_t)-\frac{\gamma}{M(y_t)}\left[2-e^\rho-\gamma\omega(\gamma)e^{3\rho}\right]\lVert\nabla f(x_t)\rVert^2 \\
&=f(x_t)-\chi(\rho,\gamma)\frac{\gamma}{M(y_t)}\lVert\nabla f(x_t)\rVert^2.
\end{aligned} f ( x t + 1 ) ≤ f ( x t ) − M ( y t ) γ [ 2 − e ρ − γ ω ( γ ) e 3 ρ ] ∥ ∇ f ( x t ) ∥ 2 = f ( x t ) − χ ( ρ , γ ) M ( y t ) γ ∥ ∇ f ( x t ) ∥ 2 . Since χ ( ρ , γ ) > 0 \chi(\rho,\gamma)>0 χ ( ρ , γ ) > 0 M ( y t ) ≤ e ρ M ( x t ) M(y_t)\le e^\rho M(x_t) M ( y t ) ≤ e ρ M ( x t ) (27) follows.
Lemma B.6. Let f f f x ⋆ x_\star x ⋆ M M M κ \kappa κ f f f ρ ≥ 0 \rho\ge0 ρ ≥ 0 γ > 0 \gamma>0 γ > 0 x t x_t x t
∥ x t + 1 − x ⋆ ∥ 2 ≤ ∥ x t − x ⋆ ∥ 2 − 2 c 0 γ M ( y t ) ( f ( x t ) − f ⋆ ) . (28) \lVert x_{t+1}-x_\star\rVert^2\le\lVert x_t-x_\star\rVert^2-2c_0\frac{\gamma}{M(y_t)}\left(f(x_t)-f_\star\right). \tag*{(28)} ∥ x t + 1 − x ⋆ ∥ 2 ≤ ∥ x t − x ⋆ ∥ 2 − 2 c 0 M ( y t ) γ ( f ( x t ) − f ⋆ ) . (28) In particular, if c 0 ≥ 0 c_0\ge0 c 0 ≥ 0 ∥ x t − x ⋆ ∥ ≤ ∥ x 0 − x ⋆ ∥ \lVert x_t-x_\star\rVert\le\lVert x_0-x_\star\rVert ∥ x t − x ⋆ ∥ ≤ ∥ x 0 − x ⋆ ∥ t t t
Proof. Expanding the square,
∥ x t + 1 − x ⋆ ∥ 2 = ∥ x t − x ⋆ ∥ 2 − 2 γ M ( y t ) ⟨ ∇ f ( y t ) , x t − x ⋆ ⟩ + γ 2 M ( y t ) 2 ∥ ∇ f ( y t ) ∥ 2 . \lVert x_{t+1}-x_\star\rVert^2=\lVert x_t-x_\star\rVert^2-2\frac{\gamma}{M(y_t)}\langle\nabla f(y_t),x_t-x_\star\rangle+\frac{\gamma^2}{M(y_t)^2}\lVert\nabla f(y_t)\rVert^2. ∥ x t + 1 − x ⋆ ∥ 2 = ∥ x t − x ⋆ ∥ 2 − 2 M ( y t ) γ ⟨ ∇ f ( y t ) , x t − x ⋆ ⟩ + M ( y t ) 2 γ 2 ∥ ∇ f ( y t ) ∥ 2 . Convexity at y t y_t y t ⟨ ∇ f ( y t ) , y t − x ⋆ ⟩ ≥ f ( y t ) − f ⋆ \langle\nabla f(y_t),y_t-x_\star\rangle\ge f(y_t)-f_\star ⟨ ∇ f ( y t ) , y t − x ⋆ ⟩ ≥ f ( y t ) − f ⋆ x t x_t x t f ( y t ) ≥ f ( x t ) + ⟨ ∇ f ( x t ) , y t − x t ⟩ = f ( x t ) + ρ ∥ ∇ f ( x t ) ∥ 2 / M ( x t ) f(y_t)\ge f(x_t)+\langle\nabla f(x_t),y_t-x_t\rangle=f(x_t)+\rho\lVert\nabla f(x_t)\rVert^2/M(x_t) f ( y t ) ≥ f ( x t ) + ⟨ ∇ f ( x t ) , y t − x t ⟩ = f ( x t ) + ρ ∥ ∇ f ( x t ) ∥ 2 / M ( x t ) x t − x ⋆ = ( y t − x ⋆ ) − ρ ∇ f ( x t ) / M ( x t ) x_t-x_\star=(y_t-x_\star)-\rho\nabla f(x_t)/M(x_t) x t − x ⋆ = ( y t − x ⋆ ) − ρ ∇ f ( x t ) / M ( x t )
⟨ ∇ f ( y t ) , x t − x ⋆ ⟩ ≥ f ( y t ) − f ⋆ − ρ M ( x t ) ⟨ ∇ f ( y t ) , ∇ f ( x t ) ⟩ ≥ f ( x t ) − f ⋆ − ρ M ( x t ) ⟨ ∇ f ( y t ) − ∇ f ( x t ) , ∇ f ( x t ) ⟩ ≥ f ( x t ) − f ⋆ − ρ ( e ρ − 1 ) M ( x t ) ∥ ∇ f ( x t ) ∥ 2 ≥ ( 1 − ρ ( e ρ − 1 ) 2 log 2 − 1 ) ( f ( x t ) − f ⋆ ) , \begin{aligned}
\langle\nabla f(y_t),x_t-x_\star\rangle\ge f(y_t)-f_\star-\frac{\rho}{M(x_t)}\langle\nabla f(y_t),\nabla f(x_t)\rangle\\
&\ge f(x_t)-f_\star-\frac{\rho}{M(x_t)}\langle\nabla f(y_t)-\nabla f(x_t),\nabla f(x_t)\rangle\\
&\ge f(x_t)-f_\star-\frac{\rho(e^\rho-1)}{M(x_t)}\lVert\nabla f(x_t)\rVert^2
\ge\left(1-\frac{\rho(e^\rho-1)}{2\log2-1}\right)(f(x_t)-f_\star),
\end{aligned} ⟨ ∇ f ( y t ) , x t − x ⋆ ⟩ ≥ f ( y t ) − f ⋆ − M ( x t ) ρ ⟨ ∇ f ( y t ) , ∇ f ( x t )⟩ ≥ f ( x t ) − f ⋆ − M ( x t ) ρ ⟨ ∇ f ( y t ) − ∇ f ( x t ) , ∇ f ( x t )⟩ ≥ f ( x t ) − f ⋆ − M ( x t ) ρ ( e ρ − 1 ) ∥ ∇ f ( x t ) ∥ 2 ≥ ( 1 − 2 log 2 − 1 ρ ( e ρ − 1 ) ) ( f ( x t ) − f ⋆ ) , where we used the Cauchy–Schwarz inequality with Lemma B.4 , and then Lemma B.3 in the form ∥ ∇ f ( x t ) ∥ 2 / M ( x t ) ≤ ( f ( x t ) − f ⋆ ) / ( 2 log 2 − 1 ) \lVert\nabla f(x_t)\rVert^2/M(x_t)\le(f(x_t)-f_\star)/(2\log2-1) ∥ ∇ f ( x t ) ∥ 2 / M ( x t ) ≤ ( f ( x t ) − f ⋆ ) / ( 2 log 2 − 1 ) Lemmas B.3 and B.4 ,
∥ ∇ f ( y t ) ∥ 2 M ( y t ) ≤ e 2 ρ ∥ ∇ f ( x t ) ∥ 2 e − ρ M ( x t ) = e 3 ρ ∥ ∇ f ( x t ) ∥ 2 M ( x t ) ≤ e 3 ρ 2 log 2 − 1 ( f ( x t ) − f ⋆ ) . \frac{\lVert\nabla f(y_t)\rVert^2}{M(y_t)}\le\frac{e^{2\rho}\lVert\nabla f(x_t)\rVert^2}{e^{-\rho}M(x_t)}=e^{3\rho}\frac{\lVert\nabla f(x_t)\rVert^2}{M(x_t)}\le\frac{e^{3\rho}}{2\log2-1}(f(x_t)-f_\star). M ( y t ) ∥ ∇ f ( y t ) ∥ 2 ≤ e − ρ M ( x t ) e 2 ρ ∥ ∇ f ( x t ) ∥ 2 = e 3 ρ M ( x t ) ∥ ∇ f ( x t ) ∥ 2 ≤ 2 log 2 − 1 e 3 ρ ( f ( x t ) − f ⋆ ) . Substituting both bounds into the expansion,
∥ x t + 1 − x ⋆ ∥ 2 ≤ ∥ x t − x ⋆ ∥ 2 − 2 γ M ( y t ) [ 1 − ρ ( e ρ − 1 ) 2 log 2 − 1 − γ e 3 ρ 2 ( 2 log 2 − 1 ) ] ( f ( x t ) − f ⋆ ) . \lVert x_{t+1}-x_\star\rVert^2\le\lVert x_t-x_\star\rVert^2-2\frac{\gamma}{M(y_t)}\left[1-\frac{\rho(e^\rho-1)}{2\log2-1}-\frac{\gamma e^{3\rho}}{2(2\log2-1)}\right](f(x_t)-f_\star). ∥ x t + 1 − x ⋆ ∥ 2 ≤ ∥ x t − x ⋆ ∥ 2 − 2 M ( y t ) γ [ 1 − 2 log 2 − 1 ρ ( e ρ − 1 ) − 2 ( 2 log 2 − 1 ) γ e 3 ρ ] ( f ( x t ) − f ⋆ ) . and the bracket equals c 0 c_0 c 0 f ( x t ) − f ⋆ ≥ 0 f(x_t)-f_\star\ge0 f ( x t ) − f ⋆ ≥ 0
The next two lemmas concern the loss scale M H M_H M H (4) only.
Lemma B.7. Under (4) , for every x ∈ R d x\in\mathbb{R}^d x ∈ R d
∥ ∇ f ( x ) ∥ 2 ≤ 2 H 0 ( f ( x ) − f ⋆ ) + H 1 ( f ( x ) − f ⋆ ) 2 , H 1 ∥ ∇ f ( x ) ∥ ≤ M H ( x ) . (29) \lVert\nabla f(x)\rVert^2\le2H_0(f(x)-f_\star)+H_1(f(x)-f_\star)^2,\qquad\sqrt{H_1}\lVert\nabla f(x)\rVert\le M_H(x). \tag*{(29)} ∥ ∇ f ( x ) ∥ 2 ≤ 2 H 0 ( f ( x ) − f ⋆ ) + H 1 ( f ( x ) − f ⋆ ) 2 , H 1 ∥ ∇ f ( x )∥ ≤ M H ( x ) . (29) Proof. If ∇ f ( x ) = 0 \nabla f(x)=0 ∇ f ( x ) = 0 H 1 = 0 H_1=0 H 1 = 0 H 0 = 0 H_0=0 H 0 = 0 ∇ 2 f ≡ 0 \nabla^2f\equiv0 ∇ 2 f ≡ 0 f f f ∇ f ( x ) = 0 \nabla f(x)=0 ∇ f ( x ) = 0 H 0 > 0 H_0>0 H 0 > 0 f f f H 0 H_0 H 0 x − ∇ f ( x ) / H 0 x-\nabla f(x)/H_0 x − ∇ f ( x ) / H 0 f ⋆ ≤ f ( x − ∇ f ( x ) / H 0 ) ≤ f ( x ) − ∥ ∇ f ( x ) ∥ 2 / ( 2 H 0 ) f_\star\le f(x-\nabla f(x)/H_0)\le f(x)-\lVert\nabla f(x)\rVert^2/(2H_0) f ⋆ ≤ f ( x − ∇ f ( x ) / H 0 ) ≤ f ( x ) − ∥ ∇ f ( x ) ∥ 2 / ( 2 H 0 ) H 1 > 0 H_1 > 0 H 1 > 0 f ≥ f ⋆ f \ge f_\star f ≥ f ⋆ ∥ ∇ f ( x ) ∥ \lVert\nabla f(x)\rVert ∥ ∇ f ( x )∥ t ≥ 0 t \ge0 t ≥ 0
ψ ( t ) : = f ( x − t ∇ f ( x ) ∥ ∇ f ( x ) ∥ ) − f ⋆ + H 0 H 1 . \psi(t) := f\left(x - t\frac{\nabla f(x)}{\lVert\nabla f(x)\rVert}\right) - f_\star+ \frac{H_0}{H_1}. ψ ( t ) := f ( x − t ∥ ∇ f ( x )∥ ∇ f ( x ) ) − f ⋆ + H 1 H 0 . Then ψ ≥ H 0 / H 1 \psi\ge H_0/H_1 ψ ≥ H 0 / H 1 ψ ( 0 ) = f ( x ) − f ⋆ + H 0 / H 1 \psi(0) = f(x) - f_\star+ H_0/H_1 ψ ( 0 ) = f ( x ) − f ⋆ + H 0 / H 1 ψ ′ ( 0 ) = − ∥ ∇ f ( x ) ∥ \psi'(0) = -\lVert\nabla f(x)\rVert ψ ′ ( 0 ) = − ∥ ∇ f ( x )∥ (4) ,
ψ ′ ′ ( t ) ≤ ∥ ∇ 2 f ( x − t ∇ f ( x ) ∥ ∇ f ( x ) ∥ ) ∥ ≤ H 0 + H 1 ( f ( x − t ∇ f ( x ) ∥ ∇ f ( x ) ∥ ) − f ⋆ ) = H 1 ψ ( t ) . \psi''(t) \le\left\lVert\nabla^2 f\left(x - t\frac{\nabla f(x)}{\lVert\nabla f(x)\rVert}\right)\right\rVert\le H_0 + H_1\left(f\left(x - t\frac{\nabla f(x)}{\lVert\nabla f(x)\rVert}\right) - f_\star\right) = H_1\psi(t). ψ ′′ ( t ) ≤ ∇ 2 f ( x − t ∥ ∇ f ( x )∥ ∇ f ( x ) ) ≤ H 0 + H 1 ( f ( x − t ∥ ∇ f ( x )∥ ∇ f ( x ) ) − f ⋆ ) = H 1 ψ ( t ) . Let q q q q ′ ′ = H 1 q q'' = H_1q q ′′ = H 1 q q ( 0 ) = ψ ( 0 ) q(0) = \psi(0) q ( 0 ) = ψ ( 0 ) q ′ ( 0 ) = ψ ′ ( 0 ) q'(0) = \psi'(0) q ′ ( 0 ) = ψ ′ ( 0 )
q ( t ) = ψ ( 0 ) cosh ( H 1 t ) − ∥ ∇ f ( x ) ∥ H 1 sinh ( H 1 t ) . q(t) = \psi(0)\cosh\left(\sqrt{H_1}t\right) - \frac{\lVert\nabla f(x)\rVert}{\sqrt{H_1}}\sinh\left(\sqrt{H_1}t\right). q ( t ) = ψ ( 0 ) cosh ( H 1 t ) − H 1 ∥ ∇ f ( x )∥ sinh ( H 1 t ) . The difference ψ − q \psi-q ψ − q t = 0 t=0 t = 0 ( ψ − q ) ′ ′ − H 1 ( ψ − q ) = ψ ′ ′ − H 1 ψ ≤ 0 (\psi-q)'' - H_1(\psi-q) = \psi'' - H_1\psi\le0 ( ψ − q ) ′′ − H 1 ( ψ − q ) = ψ ′′ − H 1 ψ ≤ 0
ψ ( t ) − q ( t ) = ∫ 0 t sinh ( H 1 ( t − s ) ) H 1 ( ψ ′ ′ ( s ) − H 1 ψ ( s ) ) d s ≤ 0. \psi(t)-q(t) = \int_0^t \frac{\sinh\left(\sqrt{H_1}(t-s)\right)}{\sqrt{H_1}}\left(\psi''(s)-H_1\psi(s)\right)\,ds \le0. ψ ( t ) − q ( t ) = ∫ 0 t H 1 sinh ( H 1 ( t − s ) ) ( ψ ′′ ( s ) − H 1 ψ ( s ) ) d s ≤ 0. Hence q ( t ) ≥ ψ ( t ) ≥ H 0 / H 1 q(t) \ge\psi(t) \ge H_0/H_1 q ( t ) ≥ ψ ( t ) ≥ H 0 / H 1 t ≥ 0 t \ge0 t ≥ 0 ∥ ∇ f ( x ) ∥ > H 1 ψ ( 0 ) \lVert\nabla f(x)\rVert> \sqrt{H_1}\psi(0) ∥ ∇ f ( x )∥ > H 1 ψ ( 0 ) q ( t ) → − ∞ q(t) \to-\infty q ( t ) → − ∞ t → ∞ t \to\infty t → ∞ ∥ ∇ f ( x ) ∥ ≤ H 1 ψ ( 0 ) \lVert\nabla f(x)\rVert\le\sqrt{H_1}\psi(0) ∥ ∇ f ( x )∥ ≤ H 1 ψ ( 0 ) inf t ≥ 0 q ( t ) = ψ ( 0 ) 2 − ∥ ∇ f ( x ) ∥ 2 / H 1 \inf_{t\ge0}q(t) = \sqrt{\psi(0)^2 - \lVert\nabla f(x)\rVert^2/H_1} inf t ≥ 0 q ( t ) = ψ ( 0 ) 2 − ∥ ∇ f ( x ) ∥ 2 / H 1 H 0 / H 1 H_0/H_1 H 0 / H 1
∥ ∇ f ( x ) ∥ 2 ≤ H 1 ( ψ ( 0 ) 2 − H 0 2 H 1 2 ) = H 1 ( f ( x ) − f ⋆ + H 0 H 1 ) 2 − H 0 2 H 1 = H 1 ( f ( x ) − f ⋆ ) 2 + 2 H 0 ( f ( x ) − f ⋆ ) , \begin{aligned}
\lVert\nabla f(x)\rVert^2 \le H_1\left(\psi(0)^2-\frac{H_0^2}{H_1^2}\right) = H_1\left(f(x)-f_\star+\frac{H_0}{H_1}\right)^2-\frac{H_0^2}{H_1} \\
&= H_1(f(x)-f_\star)^2+2H_0(f(x)-f_\star),
\end{aligned} ∥ ∇ f ( x ) ∥ 2 ≤ H 1 ( ψ ( 0 ) 2 − H 1 2 H 0 2 ) = H 1 ( f ( x ) − f ⋆ + H 1 H 0 ) 2 − H 1 H 0 2 = H 1 ( f ( x ) − f ⋆ ) 2 + 2 H 0 ( f ( x ) − f ⋆ ) , which is the first claim. For the second, multiply the first claim by H 1 H_1 H 1
H 1 ∥ ∇ f ( x ) ∥ 2 ≤ 2 H 0 H 1 ( f ( x ) − f ⋆ ) + H 1 2 ( f ( x ) − f ⋆ ) 2 ≤ ( H 0 + H 1 ( f ( x ) − f ⋆ ) ) 2 . H_1\lVert\nabla f(x)\rVert^2 \le2H_0H_1(f(x)-f_\star)+H_1^2(f(x)-f_\star)^2 \le\left(H_0+H_1(f(x)-f_\star)\right)^2. H 1 ∥ ∇ f ( x ) ∥ 2 ≤ 2 H 0 H 1 ( f ( x ) − f ⋆ ) + H 1 2 ( f ( x ) − f ⋆ ) 2 ≤ ( H 0 + H 1 ( f ( x ) − f ⋆ ) ) 2 . Lemma B.8. Under (4) , if M H ( x 0 ) = 0 M_H(x_0)=0 M H ( x 0 ) = 0 x 0 ∈ R d x_0\in\mathbb{R}^d x 0 ∈ R d M H ≡ 0 M_H\equiv0 M H ≡ 0 f f f
Proof. M H ( x 0 ) = 0 M_H(x_0)=0 M H ( x 0 ) = 0 H 0 = 0 H_0=0 H 0 = 0 f ( x 0 ) = f ⋆ f(x_0)=f_\star f ( x 0 ) = f ⋆ H 1 = 0 H_1=0 H 1 = 0 ∇ 2 f ≡ 0 \nabla^2f\equiv0 ∇ 2 f ≡ 0 f f f M H ≡ 0 M_H\equiv0 M H ≡ 0 H 1 > 0 H_1>0 H 1 > 0 y ∈ R d y\in\mathbb{R}^d y ∈ R d s ↦ M H ( x 0 + s ( y − x 0 ) ) = H 1 ( f ( x 0 + s ( y − x 0 ) ) − f ⋆ ) s\mapsto M_H(x_0+s(y-x_0))=H_1(f(x_0+s(y-x_0))-f_\star) s ↦ M H ( x 0 + s ( y − x 0 )) = H 1 ( f ( x 0 + s ( y − x 0 )) − f ⋆ ) s = 0 s=0 s = 0 Lemma B.7 its derivative satisfies
d d s M H ( x 0 + s ( y − x 0 ) ) = H 1 ⟨ ∇ f ( x 0 + s ( y − x 0 ) ) , y − x 0 ⟩ \frac{d}{ds}M_H(x_0+s(y-x_0)) = H_1\langle\nabla f(x_0+s(y-x_0)),y-x_0\rangle d s d M H ( x 0 + s ( y − x 0 )) = H 1 ⟨ ∇ f ( x 0 + s ( y − x 0 )) , y − x 0 ⟩ ≤ H 1 M H ( x 0 + s ( y − x 0 ) ) ∥ y − x 0 ∥ . \le\sqrt{H_1}M_H(x_0+s(y-x_0))\lVert y-x_0\rVert. ≤ H 1 M H ( x 0 + s ( y − x 0 )) ∥ y − x 0 ∥ . Lemma B.1 with c = H 1 ∥ y − x 0 ∥ c=\sqrt{H_1}\lVert y-x_0\rVert c = H 1 ∥ y − x 0 ∥ M H ( x 0 + s ( y − x 0 ) ) ≤ M H ( x 0 ) e H 1 s ∥ y − x 0 ∥ = 0 M_H(x_0+s(y-x_0))\le M_H(x_0)e^{\sqrt{H_1}s\lVert y-x_0\rVert}=0 M H ( x 0 + s ( y − x 0 )) ≤ M H ( x 0 ) e H 1 s ∥ y − x 0 ∥ = 0 [ 0 , 1 ] [0,1] [ 0 , 1 ] M H ( y ) = 0 M_H(y)=0 M H ( y ) = 0 f ( y ) = f ⋆ f(y)=f_\star f ( y ) = f ⋆ y y y f f f
We close this section with the elementary sequence lemma that turns a quadratic decrease of the gap into a 1 / T 1/T 1/ T
Lemma B.9. Let ( x t ) t ≥ 0 (x_t)_{t\ge0} ( x t ) t ≥ 0 f ( x t ) − f ⋆ f(x_t)-f_\star f ( x t ) − f ⋆ t t t
f ( x t + 1 ) − f ⋆ ≤ ( f ( x t ) − f ⋆ ) − β ( f ( x t ) − f ⋆ ) 2 for all t ≥ 0 , f(x_{t+1})-f_\star\le(f(x_t)-f_\star)-\beta(f(x_t)-f_\star)^2 \qquad\text{for all }t\ge0, f ( x t + 1 ) − f ⋆ ≤ ( f ( x t ) − f ⋆ ) − β ( f ( x t ) − f ⋆ ) 2 for all t ≥ 0 , where β > 0 \beta>0 β > 0 f ( x T ) − f ⋆ ≤ 1 / ( β T ) f(x_T)-f_\star\le1/(\beta T) f ( x T ) − f ⋆ ≤ 1/ ( β T ) T ≥ 1 T\ge1 T ≥ 1
Proof. If f ( x T ) = f ⋆ f(x_T)=f_\star f ( x T ) = f ⋆ f ( x t ) − f ⋆ ≥ f ( x T ) − f ⋆ > 0 f(x_t)-f_\star\ge f(x_T)-f_\star> 0 f ( x t ) − f ⋆ ≥ f ( x T ) − f ⋆ > 0 t ≤ T t \le T t ≤ T t < T t<T t < T
1 f ( x t + 1 ) − f ⋆ − 1 f ( x t ) − f ⋆ = ( f ( x t ) − f ⋆ ) − ( f ( x t + 1 ) − f ⋆ ) ( f ( x t ) − f ⋆ ) ( f ( x t + 1 ) − f ⋆ ) ≥ β f ( x t ) − f ⋆ f ( x t + 1 ) − f ⋆ ≥ β . \frac{1}{f(x_{t+1})-f_\star}-\frac{1}{f(x_t)-f_\star}=\frac{(f(x_t)-f_\star)-(f(x_{t+1})-f_\star)}{(f(x_t)-f_\star)(f(x_{t+1})-f_\star)}\ge\beta\frac{f(x_t)-f_\star}{f(x_{t+1})-f_\star}\ge\beta. f ( x t + 1 ) − f ⋆ 1 − f ( x t ) − f ⋆ 1 = ( f ( x t ) − f ⋆ ) ( f ( x t + 1 ) − f ⋆ ) ( f ( x t ) − f ⋆ ) − ( f ( x t + 1 ) − f ⋆ ) ≥ β f ( x t + 1 ) − f ⋆ f ( x t ) − f ⋆ ≥ β . Summing over t < T t<T t < T 1 / ( f ( x T ) − f ⋆ ) ≥ 1 / ( f ( x 0 ) − f ⋆ ) + β T ≥ β T 1/(f(x_T)-f_\star)\ge1/(f(x_0)-f_\star)+\beta T\ge\beta T 1/ ( f ( x T ) − f ⋆ ) ≥ 1/ ( f ( x 0 ) − f ⋆ ) + β T ≥ β T
Proofs for Section 2
In this section, we present the proofs of the results of § 2 . We first verify the distortion bounds (6) and (7) for SAM and USAM. We then prove Proposition 2.1 by direct computation on the two one-dimensional examples, Theorem 2.2 by exhibiting two one-dimensional objectives in the class (3) , and Proposition 2.4 using the lemmas of Appendix § 9 . For completeness, we restate each result before its proof.
Verification of (6) and (7) . The displacement is d = r ∇ f ( x ) / ∥ ∇ f ( x ) ∥ d = r \nabla f(x) / \lVert\nabla f(x) \rVert d = r ∇ f ( x ) / ∥ ∇ f ( x )∥ d = ρ ∇ f ( x ) d = \rho\nabla f(x) d = ρ ∇ f ( x ) ∥ d ∥ = r \lVert d \rVert= r ∥ d ∥ = r ∥ d ∥ = ρ ∥ ∇ f ( x ) ∥ \lVert d \rVert= \rho\lVert\nabla f(x) \rVert ∥ d ∥ = ρ ∥ ∇ f ( x )∥ (2) , ∥ ∇ f ( x + d ) − ∇ f ( x ) ∥ ≤ L ∥ d ∥ \lVert\nabla f(x+d) - \nabla f(x) \rVert\le L \lVert d \rVert ∥ ∇ f ( x + d ) − ∇ f ( x )∥ ≤ L ∥ d ∥ ∥ ∇ f ( x ) ∥ \lVert\nabla f(x) \rVert ∥ ∇ f ( x )∥ (6) . Under (3) with L 1 > 0 L_1 > 0 L 1 > 0 M L M_L M L L 1 L_1 L 1 Lemma B.2 gives
∥ ∇ f ( x + d ) − ∇ f ( x ) ∥ ≤ ( L 0 + L 1 ∥ ∇ f ( x ) ∥ ) e L 1 ∥ d ∥ − 1 L 1 . \lVert\nabla f(x+d) - \nabla f(x) \rVert\le(L_0 + L_1 \lVert\nabla f(x) \rVert) \frac{e^{L_1 \lVert d \rVert} - 1}{L_1}. ∥ ∇ f ( x + d ) − ∇ f ( x )∥ ≤ ( L 0 + L 1 ∥ ∇ f ( x )∥) L 1 e L 1 ∥ d ∥ − 1 . Inserting the two values of ∥ d ∥ \lVert d \rVert ∥ d ∥ ∥ ∇ f ( x ) ∥ \lVert\nabla f(x) \rVert ∥ ∇ f ( x )∥ (7) .
Proposition 2.1 (restated).
(i) Let f ( x ) = x 2 / 2 f(x) = x^2/2 f ( x ) = x 2 /2 (2) with L = 1 L = 1 L = 1 r > 0 r > 0 r > 0 η ∈ ( 0 , 2 ) \eta\in(0, 2) η ∈ ( 0 , 2 ) x ≠ 0 x \ne0 x = 0
D S A M ( x ) : = D ( x , r sign ( x ) ) = r ∣ x ∣ , x t + 1 = [ 1 − η ( 1 + D S A M ( x t ) ) ] x t . D_{\mathrm{SAM}}(x) := D(x,r\operatorname{sign}(x)) = \frac{r}{\lvert x\rvert}, \qquad x_{t+1} = [1 - \eta(1 + D_{\mathrm{SAM}}(x_t))]x_t. D SAM ( x ) := D ( x , r sign ( x )) = ∣ x ∣ r , x t + 1 = [ 1 − η ( 1 + D SAM ( x t ))] x t . Let a = η r / ( 2 − η ) a = \eta r/(2-\eta) a = η r / ( 2 − η ) ∣ x t + 1 ∣ < ∣ x t ∣ \lvert x_{t+1}\rvert< \lvert x_t\rvert ∣ x t + 1 ∣ < ∣ x t ∣ ∣ x t ∣ > a \lvert x_t\rvert> a ∣ x t ∣ > a ∣ x t + 1 ∣ > ∣ x t ∣ \lvert x_{t+1}\rvert> \lvert x_t\rvert ∣ x t + 1 ∣ > ∣ x t ∣ 0 < ∣ x t ∣ < a 0 < \lvert x_t\rvert< a 0 < ∣ x t ∣ < a x t + 1 = − x t x_{t+1} = -x_t x t + 1 = − x t ∣ x t ∣ = a \lvert x_t\rvert= a ∣ x t ∣ = a ± a \pm a ± a
(ii) Let f ( x ) = x 4 / 4 f(x) = x^4/4 f ( x ) = x 4 /4 (3) with ( L 0 , L 1 ) = ( 4 , 1 ) (L_0,L_1) = (4,1) ( L 0 , L 1 ) = ( 4 , 1 ) ρ > 0 \rho> 0 ρ > 0 η > 0 \eta> 0 η > 0 x ≠ 0 x \ne0 x = 0
D U S A M ( x ) : = D ( x , ρ x 3 ) = ( 1 + ρ x 2 ) 3 − 1 , x t + 1 = [ 1 − η ( 1 + D U S A M ( x t ) x t 2 ) ] x t . D_{\mathrm{USAM}}(x) := D(x,\rho x^3) = (1+\rho x^2)^3 - 1, \qquad x_{t+1} = [1-\eta(1+D_{\mathrm{USAM}}(x_t)x_t^2)]x_t. D USAM ( x ) := D ( x , ρ x 3 ) = ( 1 + ρ x 2 ) 3 − 1 , x t + 1 = [ 1 − η ( 1 + D USAM ( x t ) x t 2 )] x t . Consequently, if ∣ x 0 ∣ > ( 2 / ( η ρ 3 ) ) 1 / 8 \lvert x_0\rvert> (2/(\eta\rho^3))^{1/8} ∣ x 0 ∣ > ( 2/ ( η ρ 3 ) ) 1/8 x t + 1 x_{t+1} x t + 1 x t x_t x t ∣ x t + 1 ∣ > ∣ x t ∣ \lvert x_{t+1}\rvert> \lvert x_t\rvert ∣ x t + 1 ∣ > ∣ x t ∣ t t t ∣ x t ∣ → ∞ \lvert x_t\rvert\to\infty ∣ x t ∣ → ∞
Proof of Proposition 2.1. (i) Here ∇ f ( x ) = x \nabla f(x) = x ∇ f ( x ) = x x ≠ 0 x \ne0 x = 0 y = x + r sign ( x ) y = x + r\operatorname{sign}(x) y = x + r sign ( x ) r sign ( x ) = ( r / ∣ x ∣ ) x r\operatorname{sign}(x) = (r/\lvert x\rvert)x r sign ( x ) = ( r / ∣ x ∣) x
D S A M ( x ) = ∣ y − x ∣ ∣ x ∣ = r ∣ x ∣ , x + = x − η y = x − η ( 1 + r ∣ x ∣ ) x = [ 1 − η ( 1 + D S A M ( x ) ) ] x . D_{\mathrm{SAM}}(x) = \frac{\lvert y-x\rvert}{\lvert x\rvert} = \frac{r}{\lvert x\rvert}, \qquad x^+ = x-\eta y = x-\eta\left(1+\frac{r}{\lvert x\rvert}\right)x = [1-\eta(1+D_{\mathrm{SAM}}(x))]x. D SAM ( x ) = ∣ x ∣ ∣ y − x ∣ = ∣ x ∣ r , x + = x − η y = x − η ( 1 + ∣ x ∣ r ) x = [ 1 − η ( 1 + D SAM ( x ))] x . Write c ( x ) : = 1 − η − η r / ∣ x ∣ c(x) := 1-\eta-\eta r/\lvert x\rvert c ( x ) := 1 − η − η r / ∣ x ∣ ∣ x + ∣ = ∣ c ( x ) ∣ ∣ x ∣ \lvert x^+\rvert= \lvert c(x)\rvert\lvert x\rvert ∣ x + ∣ = ∣ c ( x )∣ ∣ x ∣ η > 0 \eta> 0 η > 0 c ( x ) < 1 c(x) < 1 c ( x ) < 1 η < 2 \eta< 2 η < 2
c ( x ) > − 1 ⟺ 2 − η > η r ∣ x ∣ ⟺ ∣ x ∣ > η r 2 − η = a . c(x) > -1 \Longleftrightarrow2-\eta> \frac{\eta r}{\lvert x\rvert} \Longleftrightarrow\lvert x\rvert> \frac{\eta r}{2-\eta} = a. c ( x ) > − 1 ⟺ 2 − η > ∣ x ∣ η r ⟺ ∣ x ∣ > 2 − η η r = a . Hence ∣ c ( x ) ∣ < 1 \lvert c(x)\rvert< 1 ∣ c ( x )∣ < 1 ∣ x ∣ > a \lvert x\rvert> a ∣ x ∣ > a ∣ c ( x ) ∣ > 1 \lvert c(x)\rvert> 1 ∣ c ( x )∣ > 1 0 < ∣ x ∣ < a 0 < \lvert x\rvert< a 0 < ∣ x ∣ < a c ( x ) = − 1 c(x) = -1 c ( x ) = − 1 ∣ x ∣ = a \lvert x\rvert= a ∣ x ∣ = a a ↦ − a ↦ a a \mapsto-a \mapsto a a ↦ − a ↦ a ± a \pm a ± a x t ≠ 0 x_t \ne0 x t = 0 t t t x t → 0 x_t \to0 x t → 0 0 < ∣ x t ∣ < a 0 < \lvert x_t\rvert< a 0 < ∣ x t ∣ < a t t t ∣ x t ∣ \lvert x_t\rvert ∣ x t ∣ x t → 0 x_t \to0 x t → 0
(ii) Here f ′ ( x ) = x 3 f'(x) = x^3 f ′ ( x ) = x 3 f ′ ′ ( x ) = 3 x 2 f''(x) = 3x^2 f ′′ ( x ) = 3 x 2 u ≥ 0 u \ge0 u ≥ 0 3 u 2 − u 3 3u^2-u^3 3 u 2 − u 3 4 4 4 u = 2 u=2 u = 2 3 x 2 ≤ 4 + ∣ x ∣ 3 = 4 + ∣ f ′ ( x ) ∣ 3x^2 \le4+\lvert x\rvert^3 = 4+\lvert f'(x)\rvert 3 x 2 ≤ 4 + ∣ x ∣ 3 = 4 + ∣ f ′ ( x )∣ (3) hold with ( L 0 , L 1 ) = ( 4 , 1 ) (L_0,L_1) = (4,1) ( L 0 , L 1 ) = ( 4 , 1 ) y = x + ρ x 3 = x ( 1 + ρ x 2 ) y = x+\rho x^3 = x(1+\rho x^2) y = x + ρ x 3 = x ( 1 + ρ x 2 ) y 3 = ( 1 + ρ x 2 ) 3 x 3 y^3 = (1+\rho x^2)^3x^3 y 3 = ( 1 + ρ x 2 ) 3 x 3 x ≠ 0 x \ne0 x = 0
D U S A M ( x ) = ∣ y 3 − x 3 ∣ ∣ x 3 ∣ = ( 1 + ρ x 2 ) 3 − 1 , x + = x − η y 3 = [ 1 − η ( 1 + D U S A M ( x ) x 2 ) ] x . D_{\mathrm{USAM}}(x) = \frac{\lvert y^3-x^3\rvert}{\lvert x^3\rvert} = (1+\rho x^2)^3-1, \qquad x^+ = x-\eta y^3 = [1-\eta(1+D_{\mathrm{USAM}}(x)x^2)]x. D USAM ( x ) = ∣ x 3 ∣ ∣ y 3 − x 3 ∣ = ( 1 + ρ x 2 ) 3 − 1 , x + = x − η y 3 = [ 1 − η ( 1 + D USAM ( x ) x 2 )] x . If ∣ x ∣ > ( 2 / ( η ρ 3 ) ) 1 / 8 |x| > (2/(\eta\rho^{3}))^{1/8} ∣ x ∣ > ( 2/ ( η ρ 3 ) ) 1/8 η ( 1 + ρ x 2 ) 3 x 2 ≥ η ρ 3 x 8 > 2 \eta(1+\rho x^{2})^{3}x^{2} \ge\eta\rho^{3}x^{8} > 2 η ( 1 + ρ x 2 ) 3 x 2 ≥ η ρ 3 x 8 > 2 − 1 -1 − 1 x + x^{+} x + x x x ∣ x + ∣ > ∣ x ∣ |x^{+}| > |x| ∣ x + ∣ > ∣ x ∣ ∣ x + ∣ > ( 2 / ( η ρ 3 ) ) 1 / 8 |x^{+}| > (2/(\eta\rho^{3}))^{1/8} ∣ x + ∣ > ( 2/ ( η ρ 3 ) ) 1/8 ∣ x t ∣ |x_t| ∣ x t ∣ t t t ∣ x t + 1 ∣ ≥ ( η ρ 3 x t 8 − 1 ) ∣ x t ∣ ≥ ( η ρ 3 x 0 8 − 1 ) ∣ x t ∣ |x_{t+1}| \ge(\eta\rho^{3}x_t^{8}-1)|x_t| \ge(\eta\rho^{3}x_0^{8}-1)|x_t| ∣ x t + 1 ∣ ≥ ( η ρ 3 x t 8 − 1 ) ∣ x t ∣ ≥ ( η ρ 3 x 0 8 − 1 ) ∣ x t ∣ η ρ 3 x 0 8 − 1 > 1 \eta\rho^{3}x_0^{8}-1 > 1 η ρ 3 x 0 8 − 1 > 1 ∣ x t ∣ → ∞ |x_t| \to\infty ∣ x t ∣ → ∞
Theorem 2.2 (restated). Let L 0 > 0 L_0 > 0 L 0 > 0 L 1 > 0 L_1 > 0 L 1 > 0 d ( x ) = α ( ∥ ∇ f ( x ) ∥ ) ∇ f ( x ) d(x)=\alpha(\|\nabla f(x)\|)\nabla f(x) d ( x ) = α ( ∥∇ f ( x ) ∥ ) ∇ f ( x ) (3) and every point with nonzero gradient, D ( x , d ( x ) ) ≤ δ D(x,d(x)) \le\delta D ( x , d ( x )) ≤ δ s > 0 s > 0 s > 0
α ( s ) ≤ min { δ L 0 , log ( 1 + δ ) L 1 s } . (30) \alpha(s) \le\min\left\{\frac{\delta}{L_0},\frac{\log(1+\delta)}{L_1s}\right\}. \tag*{(30)} α ( s ) ≤ min { L 0 δ , L 1 s log ( 1 + δ ) } . (30) Proof of Theorem 2.2. Fix s > 0 s > 0 s > 0 f q ( x ) = L 0 x 2 / 2 f_q(x)=L_0x^2/2 f q ( x ) = L 0 x 2 /2 f q ′ ′ ≡ L 0 ≤ L 0 + L 1 ∣ f q ′ ( x ) ∣ f_q'' \equiv L_0 \le L_0+L_1|f_q'(x)| f q ′′ ≡ L 0 ≤ L 0 + L 1 ∣ f q ′ ( x ) ∣ (3) . At the point x = s / L 0 x=s/L_0 x = s / L 0 f q ′ ( x ) = s f_q'(x)=s f q ′ ( x ) = s d ( x ) = α ( s ) s d(x)=\alpha(s)s d ( x ) = α ( s ) s
D ( x , d ( x ) ) = ∣ f q ′ ( x + d ( x ) ) − f q ′ ( x ) ∣ ∣ f q ′ ( x ) ∣ = L 0 α ( s ) s s = L 0 α ( s ) . D(x,d(x))=\frac{|f_q'(x+d(x))-f_q'(x)|}{|f_q'(x)|}=\frac{L_0\alpha(s)s}{s}=L_0\alpha(s). D ( x , d ( x )) = ∣ f q ′ ( x ) ∣ ∣ f q ′ ( x + d ( x )) − f q ′ ( x ) ∣ = s L 0 α ( s ) s = L 0 α ( s ) . The hypothesis D ( x , d ( x ) ) ≤ δ D(x,d(x)) \le\delta D ( x , d ( x )) ≤ δ α ( s ) ≤ δ / L 0 \alpha(s) \le\delta/L_0 α ( s ) ≤ δ / L 0
Next consider f e ( x ) = e L 1 x / L 2 f_e(x)=e^{L_1x/L_2} f e ( x ) = e L 1 x / L 2 f e ′ ( x ) = e L 1 x / L 1 > 0 f_e'(x)=e^{L_1x}/L_1 > 0 f e ′ ( x ) = e L 1 x / L 1 > 0 f e ′ ′ ( x ) = e L 1 x = L 1 f e ′ ( x ) ≤ L 0 + L 1 ∣ f e ′ ( x ) ∣ f_e''(x)=e^{L_1x}=L_1f_e'(x) \le L_0+L_1|f_e'(x)| f e ′′ ( x ) = e L 1 x = L 1 f e ′ ( x ) ≤ L 0 + L 1 ∣ f e ′ ( x ) ∣ (3) . At the point x = log ( L 1 s ) / L 1 x=\log(L_1s)/L_1 x = log ( L 1 s ) / L 1 f e ′ ( x ) = s f_e'(x)=s f e ′ ( x ) = s d ( x ) = α ( s ) s ≥ 0 d(x)=\alpha(s)s \ge0 d ( x ) = α ( s ) s ≥ 0 f e ′ ( x + d ) = e L 1 d f e ′ ( x ) f_e'(x+d)=e^{L_1d}f_e'(x) f e ′ ( x + d ) = e L 1 d f e ′ ( x )
D ( x , d ( x ) ) = f e ′ ( x + d ( x ) ) − f e ′ ( x ) f e ′ ( x ) = e L 1 α ( s ) s − 1. D(x,d(x))=\frac{f_e'(x+d(x))-f_e'(x)}{f_e'(x)}=e^{L_1\alpha(s)s}-1. D ( x , d ( x )) = f e ′ ( x ) f e ′ ( x + d ( x )) − f e ′ ( x ) = e L 1 α ( s ) s − 1. The hypothesis gives e L 1 α ( s ) s ≤ 1 + δ e^{L_1\alpha(s)s} \le1+\delta e L 1 α ( s ) s ≤ 1 + δ α ( s ) ≤ log ( 1 + δ ) / ( L 1 s ) \alpha(s) \le\log(1+\delta)/(L_1s) α ( s ) ≤ log ( 1 + δ ) / ( L 1 s )
Proposition 2.4 (restated).
(i) Under (2) , the constant scale M ≡ L M \equiv L M ≡ L κ = 0 \kappa=0 κ = 0
(ii) Under (3) , the scale M L M_L M L κ = L 1 \kappa=L_1 κ = L 1
(iii) Under (4) , either M H ≡ 0 M_H \equiv0 M H ≡ 0 f f f M H > 0 M_H > 0 M H > 0 M H M_H M H κ = H 1 \kappa=\sqrt{H_1} κ = H 1
(iv) Under (3) , for every x ∈ R d x \in\mathbb{R}^{d} x ∈ R d
L 0 + L 1 ∥ ∇ f ( x ) ∥ ≤ 3 2 L 0 + 3 L 1 2 2 ( 2 log 2 − 1 ) ( f ( x ) − f ⋆ ) . (31) L_0+L_1\|\nabla f(x)\| \le\frac{3}{2}L_0+\frac{3L_1^2}{2(2\log2-1)}(f(x)-f_\star). \tag*{(31)} L 0 + L 1 ∥∇ f ( x ) ∥ ≤ 2 3 L 0 + 2 ( 2 log 2 − 1 ) 3 L 1 2 ( f ( x ) − f ⋆ ) . (31) In particular, (3) implies (4) with the constants H 0 = 3 L 0 / 2 H_0=3L_0/2 H 0 = 3 L 0 /2 H 1 = 3 L 1 2 / ( 2 ( 2 log 2 − 1 ) ) H_1=3L_1^2/(2(2\log2-1)) H 1 = 3 L 1 2 / ( 2 ( 2 log 2 − 1 ))
Proof of Proposition 2.4. (i) With M ≡ L M \equiv L M ≡ L κ = 0 \kappa=0 κ = 0 (11) read ∥ ∇ 2 f ( x ) ∥ ≤ L \|\nabla^2f(x)\| \le L ∥ ∇ 2 f ( x ) ∥ ≤ L L ≤ L L \le L L ≤ L 0 ≤ L 0 \le L 0 ≤ L
(ii) The first condition is (3) , and the third holds with κ = L 1 \kappa=L_1 κ = L 1 L 1 ∥ ∇ f ( x ) ∥ ≤ L 0 + L 1 ∥ ∇ f ( x ) ∥ L_1\|\nabla f(x)\| \le L_0+L_1\|\nabla f(x)\| L 1 ∥∇ f ( x ) ∥ ≤ L 0 + L 1 ∥∇ f ( x ) ∥ x , y x,y x , y ∇ f \nabla f ∇ f s ↦ M L ( x + s ( y − x ) ) = L 0 + L 1 ∥ ∇ f ( x + s ( y − x ) ) ∥ s \mapsto M_L(x+s(y-x))=L_0+L_1\|\nabla f(x+s(y-x))\| s ↦ M L ( x + s ( y − x )) = L 0 + L 1 ∥∇ f ( x + s ( y − x )) ∥ [ 0 , 1 ] [0,1] [ 0 , 1 ]
d d s M L ( x + s ( y − x ) ) ≤ L 1 ∥ ∇ 2 f ( x + s ( y − x ) ) ( y − x ) ∥ ≤ L 1 ∥ ∇ 2 f ( x + s ( y − x ) ) ∥ ∥ y − x ∥ ≤ L 1 M L ( x + s ( y − x ) ) ∥ y − x ∥ . \begin{aligned}
\frac{d}{ds}M_L(x+s(y-x)) \le L_1\|\nabla^2f(x+s(y-x))(y-x)\| \le L_1\|\nabla^2f(x+s(y-x))\|\|y-x\| \\
&\le L_1M_L(x+s(y-x))\|y-x\|.
\end{aligned} d s d M L ( x + s ( y − x )) ≤ L 1 ∥ ∇ 2 f ( x + s ( y − x )) ( y − x ) ∥ ≤ L 1 ∥ ∇ 2 f ( x + s ( y − x )) ∥∥ y − x ∥ ≤ L 1 M L ( x + s ( y − x )) ∥ y − x ∥. Lemma B.1 with c = L 1 ∥ y − x ∥ c=L_1\lVert y-x\rVert c = L 1 ∥ y − x ∥ M L ( y ) ≤ M L ( x ) e L 1 ∥ y − x ∥ M_L(y)\le M_L(x)e^{L_1\lVert y-x\rVert} M L ( y ) ≤ M L ( x ) e L 1 ∥ y − x ∥
(iii) If M H M_H M H M H ≡ 0 M_H\equiv0 M H ≡ 0 f f f M H > 0 M_H>0 M H > 0 κ = H 1 \kappa=\sqrt{H_1} κ = H 1 Lemma B.7 . For the second, fix x , y x,y x , y Lemma B.7 ,
d d s M H ( x + s ( y − x ) ) = H 1 ⟨ ∇ f ( x + s ( y − x ) ) , y − x ⟩ ≤ H 1 ∥ ∇ f ( x + s ( y − x ) ) ∥ ∥ y − x ∥ ≤ H 1 M H ( x + s ( y − x ) ) ∥ y − x ∥ , \begin{aligned}
\frac{d}{ds}M_H\bigl(x+s(y-x)\bigr)=H_1\left\langle\nabla f\bigl(x+s(y-x)\bigr),y-x\right\rangle\le H_1\left\lVert\nabla f\bigl(x+s(y-x)\bigr)\right\rVert\lVert y-x\rVert\\
&\le\sqrt{H_1}M_H\bigl(x+s(y-x)\bigr)\lVert y-x\rVert,
\end{aligned} d s d M H ( x + s ( y − x ) ) = H 1 ⟨ ∇ f ( x + s ( y − x ) ) , y − x ⟩ ≤ H 1 ∇ f ( x + s ( y − x ) ) ∥ y − x ∥ ≤ H 1 M H ( x + s ( y − x ) ) ∥ y − x ∥ , and Lemma B.1 with c = H 1 ∥ y − x ∥ c=\sqrt{H_1}\lVert y-x\rVert c = H 1 ∥ y − x ∥ M H ( y ) ≤ M H ( x ) e H 1 ∥ y − x ∥ M_H(y)\le M_H(x)e^{\sqrt{H_1}\lVert y-x\rVert} M H ( y ) ≤ M H ( x ) e H 1 ∥ y − x ∥
(iv) By (ii), Lemma B.3 applies to M L M_L M L ( 2 log 2 − 1 ) ∥ ∇ f ( x ) ∥ 2 ≤ ( f ( x ) − f ⋆ ) ( L 0 + L 1 ∥ ∇ f ( x ) ∥ ) (2\log2-1)\lVert\nabla f(x)\rVert^2\le(f(x)-f_\star)(L_0+L_1\lVert\nabla f(x)\rVert) ( 2 log 2 − 1 ) ∥ ∇ f ( x ) ∥ 2 ≤ ( f ( x ) − f ⋆ ) ( L 0 + L 1 ∥ ∇ f ( x )∥)
∥ ∇ f ( x ) ∥ 2 − L 1 ( f ( x ) − f ⋆ ) 2 log 2 − 1 ∥ ∇ f ( x ) ∥ − L 0 ( f ( x ) − f ⋆ ) 2 log 2 − 1 ≤ 0. \lVert\nabla f(x)\rVert^2-\frac{L_1(f(x)-f_\star)}{2\log2-1}\lVert\nabla f(x)\rVert-\frac{L_0(f(x)-f_\star)}{2\log2-1}\le0. ∥ ∇ f ( x ) ∥ 2 − 2 log 2 − 1 L 1 ( f ( x ) − f ⋆ ) ∥ ∇ f ( x )∥ − 2 log 2 − 1 L 0 ( f ( x ) − f ⋆ ) ≤ 0. Since s 2 ≤ A + B s s^2\le A+Bs s 2 ≤ A + B s A , B , s ≥ 0 A,B,s\ge0 A , B , s ≥ 0 s ≤ ( B + B 2 + 4 A ) / 2 ≤ B + A s\le(B+\sqrt{B^2+4A})/2\le B+\sqrt{A} s ≤ ( B + B 2 + 4 A ) /2 ≤ B + A
∥ ∇ f ( x ) ∥ ≤ L 1 ( f ( x ) − f ⋆ ) 2 log 2 − 1 + L 0 ( f ( x ) − f ⋆ ) 2 log 2 − 1 . \lVert\nabla f(x)\rVert\le\frac{L_1(f(x)-f_\star)}{2\log2-1}+\sqrt{\frac{L_0(f(x)-f_\star)}{2\log2-1}}. ∥ ∇ f ( x )∥ ≤ 2 log 2 − 1 L 1 ( f ( x ) − f ⋆ ) + 2 log 2 − 1 L 0 ( f ( x ) − f ⋆ ) . Therefore, using A B ≤ ( A + B ) / 2 \sqrt{AB}\le(A+B)/2 A B ≤ ( A + B ) /2 A = L 0 A=L_0 A = L 0 B = L 1 2 ( f ( x ) − f ⋆ ) / ( 2 log 2 − 1 ) B=L_1^2(f(x)-f_\star)/(2\log2-1) B = L 1 2 ( f ( x ) − f ⋆ ) / ( 2 log 2 − 1 )
L 0 + L 1 ∥ ∇ f ( x ) ∥ ≤ L 0 + L 1 2 ( f ( x ) − f ⋆ ) 2 log 2 − 1 + L 0 ⋅ L 1 2 ( f ( x ) − f ⋆ ) 2 log 2 − 1 ≤ 3 2 L 0 + 3 L 1 2 2 ( 2 log 2 − 1 ) ( f ( x ) − f ⋆ ) , \begin{aligned}
L_0+L_1\lVert\nabla f(x)\rVert\le L_0+\frac{L_1^2(f(x)-f_\star)}{2\log2-1}+\sqrt{L_0\cdot\frac{L_1^2(f(x)-f_\star)}{2\log2-1}} \\
&\le\frac{3}{2}L_0+\frac{3L_1^2}{2(2\log2-1)}(f(x)-f_\star),
\end{aligned} L 0 + L 1 ∥ ∇ f ( x )∥ ≤ L 0 + 2 log 2 − 1 L 1 2 ( f ( x ) − f ⋆ ) + L 0 ⋅ 2 log 2 − 1 L 1 2 ( f ( x ) − f ⋆ ) ≤ 2 3 L 0 + 2 ( 2 log 2 − 1 ) 3 L 1 2 ( f ( x ) − f ⋆ ) , which is (12). Combined with (3), this bounds ∥ ∇ 2 f ( x ) ∥ \lVert\nabla^2f(x)\rVert ∥ ∇ 2 f ( x )∥
Theorem 2.5 (restated). Let M M M κ \kappa κ ρ ≥ 0 \rho\ge0 ρ ≥ 0 γ > 0 \gamma>0 γ > 0 ∇ f ( x t ) ≠ 0 \nabla f(x_t)\ne0 ∇ f ( x t ) = 0
e − ρ M ( x t ) ≤ M ( y t ) ≤ e ρ M ( x t ) , ∥ ∇ f ( y t ) − ∇ f ( x t ) ∥ ∥ ∇ f ( x t ) ∥ ≤ e ρ − 1. e^{-\rho}M(x_t)\le M(y_t)\le e^\rho M(x_t),\qquad\frac{\lVert\nabla f(y_t)-\nabla f(x_t)\rVert}{\lVert\nabla f(x_t)\rVert}\le e^\rho-1. e − ρ M ( x t ) ≤ M ( y t ) ≤ e ρ M ( x t ) , ∥ ∇ f ( x t )∥ ∥ ∇ f ( y t ) − ∇ f ( x t )∥ ≤ e ρ − 1. In particular, D C S - S A M ≤ e ρ − 1 D_{\mathrm{CS\text{-}SAM}}\le e^\rho-1 D CS - SAM ≤ e ρ − 1
Proof of Theorem 2.5. The two claims are the inequalities in (25) of Lemma B.4 , which holds for every κ \kappa κ M M M ρ ≥ 0 \rho\ge0 ρ ≥ 0 ∇ f ( x t ) ≠ 0 \nabla f(x_t)\ne0 ∇ f ( x t ) = 0 ∥ ∇ f ( x t ) ∥ \lVert\nabla f(x_t)\rVert ∥ ∇ f ( x t )∥
Proofs for Section 3
In this section, we present the proofs of Theorem 3.1 in Appendix § 11 .§ 1 and of Theorem 3.2 in Appendix § 11 .§ 2 ; for completeness, each theorem is restated before its proofs.
Proofs for Section 3.1: the (L 0 , L 1 L_0,L_1 L 0 , L 1
Throughout this subsection f f f (3) and M = M L M=M_L M = M L κ = L 1 \kappa=L_1 κ = L 1 Lemmas B.2 to B.6 apply with M ( x t ) = L 0 + L 1 ∥ ∇ f ( x t ) ∥ M(x_t)=L_0+L_1\lVert\nabla f(x_t)\rVert M ( x t ) = L 0 + L 1 ∥ ∇ f ( x t )∥ M ( y t ) = L 0 + L 1 ∥ ∇ f ( y t ) ∥ M(y_t)=L_0+L_1\lVert\nabla f(y_t)\rVert M ( y t ) = L 0 + L 1 ∥ ∇ f ( y t )∥ s ↦ s 2 / ( L 0 + L 1 s ) s\mapsto s^2/(L_0+L_1s) s ↦ s 2 / ( L 0 + L 1 s ) [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) ( 2 L 0 s + L 1 s 2 ) / ( L 0 + L 1 s ) 2 ≥ 0 (2L_0s+L_1s^2)/(L_0+L_1s)^2\ge0 ( 2 L 0 s + L 1 s 2 ) / ( L 0 + L 1 s ) 2 ≥ 0 Lemma B.5 reads
f ( x t + 1 ) − f ⋆ ≤ ( f ( x t ) − f ⋆ ) − γ e − ρ χ ( ρ , γ ) ∥ ∇ f ( x t ) ∥ 2 L 0 + L 1 ∥ ∇ f ( x t ) ∥ . (32) f(x_{t+1})-f_\star\le(f(x_t)-f_\star)-\gamma e^{-\rho}\chi(\rho,\gamma)\frac{\lVert\nabla f(x_t)\rVert^2}{L_0+L_1\lVert\nabla f(x_t)\rVert}. \tag*{(32)} f ( x t + 1 ) − f ⋆ ≤ ( f ( x t ) − f ⋆ ) − γ e − ρ χ ( ρ , γ ) L 0 + L 1 ∥ ∇ f ( x t )∥ ∥ ∇ f ( x t ) ∥ 2 . (32) Theorem 3.1 (restated). Let f f f (3) , let ρ ≥ 0 \rho\ge0 ρ ≥ 0 γ > 0 \gamma>0 γ > 0 χ ( ρ , γ ) > 0 \chi(\rho,\gamma)>0 χ ( ρ , γ ) > 0 ( x t ) t ≥ 0 (x_t)_{t\ge0} ( x t ) t ≥ 0 M = M L M=M_L M = M L T ≥ 1 T\ge1 T ≥ 1
(i) (Nonconvex rate )
min 0 ≤ t < T ∥ ∇ f ( x t ) ∥ 2 ≤ ( e ρ L 0 ( f ( x 0 ) − f ⋆ ) γ χ ( ρ , γ ) T + e ρ L 1 ( f ( x 0 ) − f ⋆ ) γ χ ( ρ , γ ) T ) 2 . (33) \min_{0\le t<T}\lVert\nabla f(x_t)\rVert^2\le\left(\sqrt{\frac{e^{\rho}L_0(f(x_0)-f_\star)}{\gamma\chi(\rho,\gamma)T}}+\frac{e^{\rho}L_1(f(x_0)-f_\star)}{\gamma\chi(\rho,\gamma)T}\right)^2. \tag*{(33)} 0 ≤ t < T min ∥ ∇ f ( x t ) ∥ 2 ≤ ( γ χ ( ρ , γ ) T e ρ L 0 ( f ( x 0 ) − f ⋆ ) + γ χ ( ρ , γ ) T e ρ L 1 ( f ( x 0 ) − f ⋆ ) ) 2 . (33) (ii) (Convex rate ) If in addition f f f x ⋆ x_\star x ⋆ c 0 ≥ 0 c_0\ge0 c 0 ≥ 0
f ( x T ) − f ⋆ ≤ e ρ ( L 0 ∥ x 0 − x ⋆ ∥ 2 + L 1 ∥ x 0 − x ⋆ ∥ ( f ( x 0 ) − f ⋆ ) ) γ χ ( ρ , γ ) T . (34) f(x_T)-f_\star\le\frac{e^{\rho}\left(L_0\lVert x_0-x_\star\rVert^2+L_1\lVert x_0-x_\star\rVert(f(x_0)-f_\star)\right)}{\gamma\chi(\rho,\gamma)T}. \tag*{(34)} f ( x T ) − f ⋆ ≤ γ χ ( ρ , γ ) T e ρ ( L 0 ∥ x 0 − x ⋆ ∥ 2 + L 1 ∥ x 0 − x ⋆ ∥ ( f ( x 0 ) − f ⋆ ) ) . (34) (iii) (PL rate ) If in addition f f f μ \mu μ (15) , then
f ( x T ) − f ⋆ ≤ ( 1 − 2 μ γ e − ρ χ ( ρ , γ ) L 0 + L 1 2 μ ( f ( x 0 ) − f ⋆ ) ) T ( f ( x 0 ) − f ⋆ ) . (35) f(x_T)-f_\star\le\left(1-\frac{2\mu\gamma e^{-\rho}\chi(\rho,\gamma)}{L_0+L_1\sqrt{2\mu(f(x_0)-f_\star)}}\right)^T(f(x_0)-f_\star). \tag*{(35)} f ( x T ) − f ⋆ ≤ ( 1 − L 0 + L 1 2 μ ( f ( x 0 ) − f ⋆ ) 2 μ γ e − ρ χ ( ρ , γ ) ) T ( f ( x 0 ) − f ⋆ ) . (35) Proof of Theorem 3.1. (i) Summing (32) over t < T t<T t < T
γ e − ρ χ ( ρ , γ ) ∑ t < T ∥ ∇ f ( x t ) ∥ 2 L 0 + L 1 ∥ ∇ f ( x t ) ∥ ≤ f ( x 0 ) − f ( x T ) ≤ f ( x 0 ) − f ⋆ . \gamma e^{-\rho}\chi(\rho,\gamma)\sum_{t<T}\frac{\lVert\nabla f(x_t)\rVert^2}{L_0+L_1\lVert\nabla f(x_t)\rVert}\le f(x_0)-f(x_T)\le f(x_0)-f_\star. γ e − ρ χ ( ρ , γ ) t < T ∑ L 0 + L 1 ∥ ∇ f ( x t )∥ ∥ ∇ f ( x t ) ∥ 2 ≤ f ( x 0 ) − f ( x T ) ≤ f ( x 0 ) − f ⋆ . Since the map s ↦ s 2 / ( L 0 + L 1 s ) s\mapsto s^2/(L_0+L_1s) s ↦ s 2 / ( L 0 + L 1 s )
( min t < T ∥ ∇ f ( x t ) ∥ ) 2 ≤ e ρ ( f ( x 0 ) − f ⋆ ) γ χ ( ρ , γ ) T ( L 0 + L 1 min t < T ∥ ∇ f ( x t ) ∥ ) . \left(\min_{t<T}\lVert\nabla f(x_t)\rVert\right)^2\le\frac{e^\rho(f(x_0)-f_\star)}{\gamma\chi(\rho,\gamma)T}\left(L_0+L_1\min_{t<T}\lVert\nabla f(x_t)\rVert\right). ( t < T min ∥ ∇ f ( x t )∥ ) 2 ≤ γ χ ( ρ , γ ) T e ρ ( f ( x 0 ) − f ⋆ ) ( L 0 + L 1 t < T min ∥ ∇ f ( x t )∥ ) . Since s 2 ≤ A + B s s^2\le A+Bs s 2 ≤ A + B s A , B , s ≥ 0 A,B,s\ge0 A , B , s ≥ 0 s ≤ A + B s\le\sqrt{A}+B s ≤ A + B
min t < T ∥ ∇ f ( x t ) ∥ ≤ e ρ L 0 ( f ( x 0 ) − f ⋆ ) γ χ ( ρ , γ ) T + e ρ L 1 ( f ( x 0 ) − f ⋆ ) γ χ ( ρ , γ ) T , \min_{t<T}\lVert\nabla f(x_t)\rVert\le\sqrt{\frac{e^\rho L_0(f(x_0)-f_\star)}{\gamma\chi(\rho,\gamma)T}}+\frac{e^\rho L_1(f(x_0)-f_\star)}{\gamma\chi(\rho,\gamma)T}, t < T min ∥ ∇ f ( x t )∥ ≤ γ χ ( ρ , γ ) T e ρ L 0 ( f ( x 0 ) − f ⋆ ) + γ χ ( ρ , γ ) T e ρ L 1 ( f ( x 0 ) − f ⋆ ) , and squaring gives (16).
(ii) Since c 0 ≥ 0 c_0 \ge0 c 0 ≥ 0 Lemma B.6 gives ∥ x t − x ⋆ ∥ ≤ ∥ x 0 − x ⋆ ∥ \lVert x_t-x_\star\rVert\le\lVert x_0-x_\star\rVert ∥ x t − x ⋆ ∥ ≤ ∥ x 0 − x ⋆ ∥ t t t
f ( x t ) − f ⋆ ≤ ⟨ ∇ f ( x t ) , x t − x ⋆ ⟩ ≤ ∥ ∇ f ( x t ) ∥ ∥ x 0 − x ⋆ ∥ . f(x_t)-f_\star\le\langle\nabla f(x_t),x_t-x_\star\rangle\le\lVert\nabla f(x_t)\rVert\lVert x_0-x_\star\rVert. f ( x t ) − f ⋆ ≤ ⟨ ∇ f ( x t ) , x t − x ⋆ ⟩ ≤ ∥ ∇ f ( x t )∥ ∥ x 0 − x ⋆ ∥ . Since the map s ↦ s 2 / ( L 0 + L 1 s ) s \mapsto s^2/(L_0+L_1s) s ↦ s 2 / ( L 0 + L 1 s ) f ( x t ) − f ⋆ ≤ f ( x 0 ) − f ⋆ f(x_t)-f_\star\le f(x_0)-f_\star f ( x t ) − f ⋆ ≤ f ( x 0 ) − f ⋆
∥ ∇ f ( x t ) ∥ 2 L 0 + L 1 ∥ ∇ f ( x t ) ∥ ≥ ( f ( x t ) − f ⋆ ) 2 L 0 ∥ x 0 − x ⋆ ∥ 2 + L 1 ∥ x 0 − x ⋆ ∥ ( f ( x t ) − f ⋆ ) ≥ ( f ( x t ) − f ⋆ ) 2 L 0 ∥ x 0 − x ⋆ ∥ 2 + L 1 ∥ x 0 − x ⋆ ∥ ( f ( x 0 ) − f ⋆ ) . \begin{aligned}
\frac{\lVert\nabla f(x_t)\rVert^2}{L_0+L_1\lVert\nabla f(x_t)\rVert}
\ge
\frac{(f(x_t)-f_\star)^2}{L_0\lVert x_0-x_\star\rVert^2+L_1\lVert x_0-x_\star\rVert(f(x_t)-f_\star)} \\
&\ge
\frac{(f(x_t)-f_\star)^2}{L_0\lVert x_0-x_\star\rVert^2+L_1\lVert x_0-x_\star\rVert(f(x_0)-f_\star)}.
\end{aligned} L 0 + L 1 ∥ ∇ f ( x t )∥ ∥ ∇ f ( x t ) ∥ 2 ≥ L 0 ∥ x 0 − x ⋆ ∥ 2 + L 1 ∥ x 0 − x ⋆ ∥ ( f ( x t ) − f ⋆ ) ( f ( x t ) − f ⋆ ) 2 ≥ L 0 ∥ x 0 − x ⋆ ∥ 2 + L 1 ∥ x 0 − x ⋆ ∥ ( f ( x 0 ) − f ⋆ ) ( f ( x t ) − f ⋆ ) 2 . Inserting this into (32) gives
f ( x t + 1 ) − f ⋆ ≤ ( f ( x t ) − f ⋆ ) − γ e − ρ χ ( ρ , γ ) L 0 ∥ x 0 − x ⋆ ∥ 2 + L 1 ∥ x 0 − x ⋆ ∥ ( f ( x 0 ) − f ⋆ ) ( f ( x t ) − f ⋆ ) 2 . f(x_{t+1})-f_\star\le(f(x_t)-f_\star)
-\frac{\gamma e^{-\rho}\chi(\rho,\gamma)}
{L_0\lVert x_0-x_\star\rVert^2+L_1\lVert x_0-x_\star\rVert(f(x_0)-f_\star)}
(f(x_t)-f_\star)^2 . f ( x t + 1 ) − f ⋆ ≤ ( f ( x t ) − f ⋆ ) − L 0 ∥ x 0 − x ⋆ ∥ 2 + L 1 ∥ x 0 − x ⋆ ∥ ( f ( x 0 ) − f ⋆ ) γ e − ρ χ ( ρ , γ ) ( f ( x t ) − f ⋆ ) 2 . Since f ( x t ) − f ⋆ f(x_t)-f_\star f ( x t ) − f ⋆ Lemma B.5 , Lemma B.9 applies and gives (17).
(iii) If f ( x 0 ) = f ⋆ f(x_0)=f_\star f ( x 0 ) = f ⋆ f ( x 0 ) > f ⋆ f(x_0)>f_\star f ( x 0 ) > f ⋆ (15) gives ∥ ∇ f ( x t ) ∥ ≥ 2 μ ( f ( x t ) − f ⋆ ) \lVert\nabla f(x_t)\rVert\ge\sqrt{2\mu(f(x_t)-f_\star)} ∥ ∇ f ( x t )∥ ≥ 2 μ ( f ( x t ) − f ⋆ ) s ↦ s 2 / ( L 0 + L 1 s ) s \mapsto s^2/(L_0+L_1s) s ↦ s 2 / ( L 0 + L 1 s ) (32) , and f ( x t ) − f ⋆ ≤ f ( x 0 ) − f ⋆ f(x_t)-f_\star\le f(x_0)-f_\star f ( x t ) − f ⋆ ≤ f ( x 0 ) − f ⋆
f ( x t + 1 ) − f ⋆ ≤ ( f ( x t ) − f ⋆ ) − γ e − ρ χ ( ρ , γ ) 2 μ ( f ( x t ) − f ⋆ ) L 0 + L 1 2 μ ( f ( x t ) − f ⋆ ) ≤ ( 1 − 2 μ γ e − ρ χ ( ρ , γ ) L 0 + L 1 2 μ ( f ( x 0 ) − f ⋆ ) ) ( f ( x t ) − f ⋆ ) . \begin{aligned}
f(x_{t+1})-f_\star\le(f(x_t)-f_\star)-\gamma e^{-\rho}\chi(\rho,\gamma)
\frac{2\mu(f(x_t)-f_\star)}{L_0+L_1\sqrt{2\mu(f(x_t)-f_\star)}} \\
&\le\left(1-\frac{2\mu\gamma e^{-\rho}\chi(\rho,\gamma)}
{L_0+L_1\sqrt{2\mu(f(x_0)-f_\star)}}\right)(f(x_t)-f_\star).
\end{aligned} f ( x t + 1 ) − f ⋆ ≤ ( f ( x t ) − f ⋆ ) − γ e − ρ χ ( ρ , γ ) L 0 + L 1 2 μ ( f ( x t ) − f ⋆ ) 2 μ ( f ( x t ) − f ⋆ ) ≤ ( 1 − L 0 + L 1 2 μ ( f ( x 0 ) − f ⋆ ) 2 μ γ e − ρ χ ( ρ , γ ) ) ( f ( x t ) − f ⋆ ) . Applying this with t = 0 t=0 t = 0 f ( x 1 ) − f ⋆ ≥ 0 f(x_1)-f_\star\ge0 f ( x 1 ) − f ⋆ ≥ 0 f ( x 0 ) − f ⋆ > 0 f(x_0)-f_\star>0 f ( x 0 ) − f ⋆ > 0 μ γ e − ρ χ ( ρ , γ ) > 0 \mu\gamma e^{-\rho}\chi(\rho,\gamma)>0 μ γ e − ρ χ ( ρ , γ ) > 0 t t t
Proofs for Section 3.2: the ( H 0 , H 1 ) (H_0,H_1) ( H 0 , H 1 )
Throughout this subsection f f f (4) , is nonconstant, and M = M H M=M_H M = M H κ = H 1 \kappa=\sqrt{H_1} κ = H 1 Lemmas B.2 to B.6 apply with M ( x t ) = H 0 + H 1 ( f ( x t ) − f ⋆ ) M(x_t)=H_0+H_1(f(x_t)-f_\star) M ( x t ) = H 0 + H 1 ( f ( x t ) − f ⋆ ) M ( y t ) = H 0 + H 1 ( f ( y t ) − f ⋆ ) M(y_t)=H_0+H_1(f(y_t)-f_\star) M ( y t ) = H 0 + H 1 ( f ( y t ) − f ⋆ ) f ( x t ) − f ⋆ f(x_t)-f_\star f ( x t ) − f ⋆ Lemma B.5 , we have M ( x t ) ≤ H 0 + H 1 ( f ( x 0 ) − f ⋆ ) M(x_t)\le H_0+H_1(f(x_0)-f_\star) M ( x t ) ≤ H 0 + H 1 ( f ( x 0 ) − f ⋆ ) t t t Lemma B.5 gives
f ( x t + 1 ) − f ⋆ ≤ ( f ( x t ) − f ⋆ ) − γ e − ρ χ ( ρ , γ ) ∥ ∇ f ( x t ) ∥ 2 H 0 + H 1 ( f ( x t ) − f ⋆ ) ≤ ( f ( x t ) − f ⋆ ) − γ e − ρ χ ( ρ , γ ) ∥ ∇ f ( x t ) ∥ 2 H 0 + H 1 ( f ( x 0 ) − f ⋆ ) . (36) \begin{aligned}
f(x_{t+1})-f_\star
&\le(f(x_t)-f_\star)-\gamma e^{-\rho}\chi(\rho,\gamma)
\frac{\lVert\nabla f(x_t)\rVert^2}{H_0+H_1(f(x_t)-f_\star)}\\
&\le(f(x_t)-f_\star)-\gamma e^{-\rho}\chi(\rho,\gamma)
\frac{\lVert\nabla f(x_t)\rVert^2}{H_0+H_1(f(x_0)-f_\star)}. \tag*{(36)}
\end{aligned} f ( x t + 1 ) − f ⋆ ≤ ( f ( x t ) − f ⋆ ) − γ e − ρ χ ( ρ , γ ) H 0 + H 1 ( f ( x t ) − f ⋆ ) ∥ ∇ f ( x t ) ∥ 2 ≤ ( f ( x t ) − f ⋆ ) − γ e − ρ χ ( ρ , γ ) H 0 + H 1 ( f ( x 0 ) − f ⋆ ) ∥ ∇ f ( x t ) ∥ 2 . (36) Note that the second inequality in (36) has a constant coefficient in front of ∥ ∇ f ( x t ) ∥ 2 \lVert\nabla f(x_t)\rVert^2 ∥ ∇ f ( x t ) ∥ 2 H 1 H_1 H 1
Theorem 3.2 (restated). Let f f f (4) and be nonconstant, let ρ ≥ 0 \rho\ge0 ρ ≥ 0 γ > 0 \gamma>0 γ > 0 χ ( ρ , γ ) > 0 \chi(\rho,\gamma)>0 χ ( ρ , γ ) > 0 ( x t ) t ≥ 0 (x_t)_{t\ge0} ( x t ) t ≥ 0 M = M H M=M_H M = M H T ≥ 1 T\ge1 T ≥ 1
(i) (Nonconvex rate)
min 0 ≤ t < T ∥ ∇ f ( x t ) ∥ 2 ≤ e ρ ( H 0 + H 1 ( f ( x 0 ) − f ⋆ ) ) ( f ( x 0 ) − f ⋆ ) γ χ ( ρ , γ ) T . (37) \min_{0\le t<T}\lVert\nabla f(x_t)\rVert^2
\le\frac{e^\rho\left(H_0+H_1(f(x_0)-f_\star)\right)(f(x_0)-f_\star)}
{\gamma\chi(\rho,\gamma)T}. \tag*{(37)} 0 ≤ t < T min ∥ ∇ f ( x t ) ∥ 2 ≤ γ χ ( ρ , γ ) T e ρ ( H 0 + H 1 ( f ( x 0 ) − f ⋆ ) ) ( f ( x 0 ) − f ⋆ ) . (37) (ii) (Convex rate ) If in addition f f f x ⋆ x_\star x ⋆ c 0 ≥ 0 c_0 \ge0 c 0 ≥ 0
f ( x T ) − f ⋆ ≤ e ρ ( H 0 + H 1 ( f ( x 0 ) − f ⋆ ) ) ∥ x 0 − x ⋆ ∥ 2 γ χ ( ρ , γ ) T . (38) f(x_T) - f_\star\le\frac{e^\rho\left(H_0 + H_1(f(x_0)-f_\star)\right)\lVert x_0-x_\star\rVert^2}{\gamma\chi(\rho,\gamma)T}. \tag*{(38)} f ( x T ) − f ⋆ ≤ γ χ ( ρ , γ ) T e ρ ( H 0 + H 1 ( f ( x 0 ) − f ⋆ ) ) ∥ x 0 − x ⋆ ∥ 2 . (38) (iii) (PL rate ) If in addition f f f μ \mu μ (15) , then
f ( x T ) − f ⋆ ≤ ( 1 − 2 μ γ e − ρ χ ( ρ , γ ) H 0 + H 1 ( f ( x 0 ) − f ⋆ ) ) T ( f ( x 0 ) − f ⋆ ) . (39) f(x_T)-f_\star\le\left(1-\frac{2\mu\gamma e^{-\rho}\chi(\rho,\gamma)}{H_0+H_1(f(x_0)-f_\star)}\right)^T(f(x_0)-f_\star). \tag*{(39)} f ( x T ) − f ⋆ ≤ ( 1 − H 0 + H 1 ( f ( x 0 ) − f ⋆ ) 2 μ γ e − ρ χ ( ρ , γ ) ) T ( f ( x 0 ) − f ⋆ ) . (39) Proof of Theorem 3.2. (i) Summing the second inequality in (36) over t < T t<T t < T
γ e − ρ χ ( ρ , γ ) H 0 + H 1 ( f ( x 0 ) − f ⋆ ) ∑ t < T ∥ ∇ f ( x t ) ∥ 2 ≤ f ( x 0 ) − f ( x T ) ≤ f ( x 0 ) − f ⋆ , \frac{\gamma e^{-\rho}\chi(\rho,\gamma)}{H_0+H_1(f(x_0)-f_\star)}\sum_{t<T}\lVert\nabla f(x_t)\rVert^2 \le f(x_0)-f(x_T) \le f(x_0)-f_\star, H 0 + H 1 ( f ( x 0 ) − f ⋆ ) γ e − ρ χ ( ρ , γ ) t < T ∑ ∥ ∇ f ( x t ) ∥ 2 ≤ f ( x 0 ) − f ( x T ) ≤ f ( x 0 ) − f ⋆ , and the minimum over t < T t<T t < T
(ii) Since c 0 ≥ 0 c_0 \ge0 c 0 ≥ 0 Lemma B.6 gives ∥ x t − x ⋆ ∥ ≤ ∥ x 0 − x ⋆ ∥ \lVert x_t-x_\star\rVert\le\lVert x_0-x_\star\rVert ∥ x t − x ⋆ ∥ ≤ ∥ x 0 − x ⋆ ∥ ∥ ∇ f ( x t ) ∥ ≥ ( f ( x t ) − f ⋆ ) / ∥ x 0 − x ⋆ ∥ \lVert\nabla f(x_t)\rVert\ge(f(x_t)-f_\star)/\lVert x_0-x_\star\rVert ∥ ∇ f ( x t )∥ ≥ ( f ( x t ) − f ⋆ ) / ∥ x 0 − x ⋆ ∥ (36) ,
f ( x t + 1 ) − f ⋆ ≤ ( f ( x t ) − f ⋆ ) − γ e − ρ χ ( ρ , γ ) ∥ x 0 − x ⋆ ∥ 2 ( H 0 + H 1 ( f ( x 0 ) − f ⋆ ) ) ( f ( x t ) − f ⋆ ) 2 , f(x_{t+1})-f_\star\le(f(x_t)-f_\star)-\frac{\gamma e^{-\rho}\chi(\rho,\gamma)}{\lVert x_0-x_\star\rVert^2\left(H_0+H_1(f(x_0)-f_\star)\right)}(f(x_t)-f_\star)^2, f ( x t + 1 ) − f ⋆ ≤ ( f ( x t ) − f ⋆ ) − ∥ x 0 − x ⋆ ∥ 2 ( H 0 + H 1 ( f ( x 0 ) − f ⋆ ) ) γ e − ρ χ ( ρ , γ ) ( f ( x t ) − f ⋆ ) 2 , and Lemma B.9 gives (20).
(iii) Let f ( x 0 ) > f ⋆ f(x_0)>f_\star f ( x 0 ) > f ⋆ (15) and the second inequality in (36) give
f ( x t + 1 ) − f ⋆ ≤ ( 1 − 2 μ γ e − ρ χ ( ρ , γ ) H 0 + H 1 ( f ( x 0 ) − f ⋆ ) ) ( f ( x t ) − f ⋆ ) . f(x_{t+1})-f_\star\le\left(1-\frac{2\mu\gamma e^{-\rho}\chi(\rho,\gamma)}{H_0+H_1(f(x_0)-f_\star)}\right)(f(x_t)-f_\star). f ( x t + 1 ) − f ⋆ ≤ ( 1 − H 0 + H 1 ( f ( x 0 ) − f ⋆ ) 2 μ γ e − ρ χ ( ρ , γ ) ) ( f ( x t ) − f ⋆ ) . As in the proof of Theorem 3.1(iii), the case t = 0 t=0 t = 0 [ 0 , 1 ) [0,1) [ 0 , 1 )
Experimental details
In this section, we give the details needed to reproduce the experiments of § 4 . Appendix § 12 .§ 1 specifies the one-dimensional verification experiments of § 4.1 : the update rules, the curvature scales and the constants that make them valid everywhere, the stopping rules, and the evaluation of the distortion. Appendix § 12 .§ 2 gives, for the deep-network experiments of § 4.2 , the training protocol, the minibatch curvature scales and their fixed coefficients, the tuning campaign with the complete grid of every method, the selection rule, and the selected configuration of every method in every model–dataset setting (Table 4 ).
Table 4. Configurations selected on seed 3107 by the best test accuracy over 200 epochs, for every method and setting of Table 3. For SAM and USAM, η \eta η r r r ρ \rho ρ ρ \rho ρ γ \gamma γ L 0 L_0 L 0 M L M_L M L L 0 + L 1 ∥ ∇ f i ( x ) ∥ L_0 + L_1 \lVert\nabla f_i(x)\rVert L 0 + L 1 ∥ ∇ f i ( x )∥ L 1 = 1 L_1 = 1 L 1 = 1 H 1 H_1 H 1 M H M_H M H H 0 + H 1 [ f i ( x ) − ℓ i ∗ ] + H_0 + H_1[f_i(x) - \ell_i^*]_+ H 0 + H 1 [ f i ( x ) − ℓ i ∗ ] + H 0 = 1 H_0 = 1 H 0 = 1 ℓ i ∗ = 0 \ell_i^* = 0 ℓ i ∗ = 0
The pseudocode for CS-SAM is given in Algorithm 1.
Algorithm 1 Curvature-Scaled SAM (CS-SAM).
Require: starting point x 0 ∈ R d x_0 \in\mathbb{R}^d x 0 ∈ R d ρ ≥ 0 \rho\ge0 ρ ≥ 0 γ > 0 \gamma> 0 γ > 0 M M M Definition 2.3 )
for t = 0 , 1 , … t = 0,1,\ldots t = 0 , 1 , …
if ∇ f ( x t ) = 0 \nabla f(x_t) = 0 ∇ f ( x t ) = 0
return x t x_t x t
end if
y t ← x t + ρ M ( x t ) ∇ f ( x t ) y_t \leftarrow x_t + \frac{\rho}{M(x_t)}\nabla f(x_t) y t ← x t + M ( x t ) ρ ∇ f ( x t )
x t + 1 ← x t − γ M ( y t ) ∇ f ( y t ) x_{t+1} \leftarrow x_t - \frac{\gamma}{M(y_t)}\nabla f(y_t) x t + 1 ← x t − M ( y t ) γ ∇ f ( y t )
end for
Verification experiments of Section 4.1
The experiments of § 4.1 are deterministic and one-dimensional, with analytic function values and gradients, so there are no datasets, minibatches, random seeds, or hyperparameter searches. All computations use double precision.
Update rules and scales. The three methods are run exactly as stated in (SAM), (USAM), and (CS-SAM), with ∇ f = f ′ \nabla f = f' ∇ f = f ′ f ⋆ = 0 f_\star= 0 f ⋆ = 0 x = 0 x = 0 x = 0
M L ( x ) = L 0 + L 1 ∣ f ′ ( x ) ∣ , M H ( x ) = H 0 + H 1 ( f ( x ) − f ⋆ ) . M_L(x) = L_0 + L_1 \lvert f'(x) \rvert,\qquad M_H(x) = H_0 + H_1\left(f(x) - f_\star\right). M L ( x ) = L 0 + L 1 ∣ f ′ ( x )∣ , M H ( x ) = H 0 + H 1 ( f ( x ) − f ⋆ ) . For the quadratic f ( x ) = x 2 / 2 f(x) = x^2/2 f ( x ) = x 2 /2 f ′ ′ ≡ 1 f'' \equiv1 f ′′ ≡ 1 ( L 0 , L 1 ) = ( H 0 , H 1 ) = ( 1 , 0 ) (L_0,L_1) = (H_0,H_1) = (1,0) ( L 0 , L 1 ) = ( H 0 , H 1 ) = ( 1 , 0 ) M L = M H ≡ 1 M_L = M_H \equiv1 M L = M H ≡ 1 f ( x ) = x 4 / 4 f(x) = x^4/4 f ( x ) = x 4 /4 f ′ ′ ( x ) = 3 x 2 f''(x) = 3x^2 f ′′ ( x ) = 3 x 2 ( L 0 , L 1 ) = ( 4 , 1 ) (L_0,L_1) = (4,1) ( L 0 , L 1 ) = ( 4 , 1 ) ( H 0 , H 1 ) = ( 3 , 3 ) (H_0,H_1) = (3,3) ( H 0 , H 1 ) = ( 3 , 3 ) M L ( x ) = 4 + ∣ x ∣ 3 M_L(x) = 4 + \lvert x \rvert^3 M L ( x ) = 4 + ∣ x ∣ 3 M H ( x ) = 3 + 3 x 4 / 4 M_H(x) = 3 + 3x^4/4 M H ( x ) = 3 + 3 x 4 /4
Parameter regime. The common choice ρ = γ = 1 / 8 \rho= \gamma= 1/8 ρ = γ = 1/8 (14) , 2 − e 1 / 8 ≈ 0.867 2 - e^{1/8} \approx0.867 2 − e 1/8 ≈ 0.867 γ ω ( γ ) e 3 ρ = 1 8 ω ( 1 8 ) e 3 / 8 ≈ 0.095 \gamma\omega(\gamma)e^{3\rho} = \frac{1}{8}\omega\left(\frac{1}{8}\right)e^{3/8} \approx0.095 γ ω ( γ ) e 3 ρ = 8 1 ω ( 8 1 ) e 3/8 ≈ 0.095 χ ( 1 / 8 , 1 / 8 ) ≈ 0.772 > 0 \chi(1/8,1/8) \approx0.772 > 0 χ ( 1/8 , 1/8 ) ≈ 0.772 > 0 ρ ( e ρ − 1 ) / ( 2 log 2 − 1 ) ≈ 0.043 \rho(e^\rho- 1)/(2\log2 - 1) \approx0.043 ρ ( e ρ − 1 ) / ( 2 log 2 − 1 ) ≈ 0.043 γ e 3 ρ / ( 2 ( 2 log 2 − 1 ) ) ≈ 0.235 \gamma e^{3\rho}/(2(2\log2 - 1)) \approx0.235 γ e 3 ρ / ( 2 ( 2 log 2 − 1 )) ≈ 0.235 c 0 ≈ 0.722 ≥ 0 c_0 \approx0.722 \ge0 c 0 ≈ 0.722 ≥ 0 x ⋆ = 0 x_\star= 0 x ⋆ = 0 Figure 1 a and Figure 1 b is the one guaranteed by Theorem 3.1(ii) with M = M L M = M_L M = M L M = M H M = M_H M = M H e ρ − 1 e^\rho- 1 e ρ − 1 Figure 1 c and Figure 1 d is that of Theorem 2.5, which holds for every ρ ≥ 0 \rho\ge0 ρ ≥ 0
Two-cycle and divergence (Figures 1a and 1b). A run stops when ∣ f ′ ( x ) ∣ ≤ 10 − 12 \lvert f'(x) \rvert\le10^{-12} ∣ f ′ ( x )∣ ≤ 1 0 − 12 10 12 10^{12} 1 0 12 r = 1 r = 1 r = 1 η = 0.2 \eta= 0.2 η = 0.2 ρ = γ = 1 / 8 \rho= \gamma= 1/8 ρ = γ = 1/8 x 0 = 3 x_0 = 3 x 0 = 3 x t + 1 = 0.8 x t − 0.2 sign ( x t ) x_{t+1} = 0.8x_t - 0.2\operatorname{sign}(x_t) x t + 1 = 0.8 x t − 0.2 sign ( x t ) a = η r / ( 2 − η ) = 1 / 9 a = \eta r/(2-\eta) = 1/9 a = η r / ( 2 − η ) = 1/9 x t + 1 = ( 1 − γ ( 1 + ρ ) ) x t = 55 64 x t x_{t+1} = (1-\gamma(1+\rho))x_t = \frac{55}{64}x_t x t + 1 = ( 1 − γ ( 1 + ρ )) x t = 64 55 x t ρ = 1 / 8 \rho= 1/8 ρ = 1/8 η = 1 / 32 \eta= 1/32 η = 1/32 ρ = γ = 1 / 8 \rho= \gamma= 1/8 ρ = γ = 1/8 x 0 = 4 x_0 = 4 x 0 = 4 y 0 = 4 + 1 8 ⋅ 4 3 = 12 y_0 = 4 + \frac{1}{8}\cdot4^3 = 12 y 0 = 4 + 8 1 ⋅ 4 3 = 12 x 1 = 4 − 1 32 ⋅ 12 3 = − 50 x_1 = 4 - \frac{1}{32}\cdot12^3 = -50 x 1 = 4 − 32 1 ⋅ 1 2 3 = − 50 x 2 ≈ 1.2 × 10 11 x_2 \approx1.2 \times10^{11} x 2 ≈ 1.2 × 1 0 11 Figure 1 b shows ∣ x t ∣ |x_t| ∣ x t ∣ 2 t 2t 2 t ( 2 / ( η ρ 3 ) ) 1 / 8 ≈ 3.67 (2/(\eta\rho^3))^{1/8} \approx3.67 ( 2/ ( η ρ 3 ) ) 1/8 ≈ 3.67 x 0 = 4 x_0 = 4 x 0 = 4
Distortion (Figure 1 c and Figure 1 d). These figures evaluate independent points rather than trajectories. At each nonstationary x x x y y y s = ∣ f ′ ( x ) ∣ s = |f'(x)| s = ∣ f ′ ( x ) ∣ D = ∣ f ′ ( y ) − f ′ ( x ) ∣ / ∣ f ′ ( x ) ∣ D = |f'(y) - f'(x)|/|f'(x)| D = ∣ f ′ ( y ) − f ′ ( x ) ∣/∣ f ′ ( x ) ∣ (5) ; no outer step enters. The perturbations are those of SAM with r = 1 / 8 r = 1/8 r = 1/8 ρ = 1 / 8 \rho= 1/8 ρ = 1/8 ρ = 1 / 8 \rho= 1/8 ρ = 1/8 1 / 8 1/8 1/8 e ρ − 1 = e 1 / 8 − 1 ≈ 0.133 e^\rho- 1 = e^{1/8} - 1 \approx0.133 e ρ − 1 = e 1/8 − 1 ≈ 0.133
Deep-network experiments of Section 4.2
Training protocol. All runs train ResNet-20 or ResNet-32 with batch normalization on CIFAR-10 or CIFAR-100 for 200 epochs with batch size 128 and the cross-entropy loss, with random-crop and horizontal-flip augmentation and no cutout. Momentum and weight decay are zero for every method. The test accuracy is evaluated after every epoch. Every method computes two minibatch gradients per iteration, one at the iterate and one at the perturbed point, so that equal numbers of epochs correspond to equal numbers of gradient evaluations. The runs were performed on four RTX 6000 Ada GPUs.
Learning-rate schedules. The schedule of SAM and USAM acts on the outer step η t \eta_t η t r r r ρ \rho ρ η t ≡ η \eta_t \equiv\eta η t ≡ η η \eta η E = 200 E = 200 E = 200 e ∈ { 0 , … , E − 1 } e \in\{0,\ldots,E-1\} e ∈ { 0 , … , E − 1 }
η t = η 2 ( 1 + cos π e E ) , (40) \eta_t = \frac{\eta}{2}\left(1+\cos\frac{\pi e}{E}\right), \tag*{(40)} η t = 2 η ( 1 + cos E π e ) , (40) so that η t = η \eta_t = \eta η t = η η t ≈ 6 × 10 − 5 η \eta_t \approx6 \times10^{-5}\eta η t ≈ 6 × 1 0 − 5 η [27 ] .
Minibatch curvature scales. As stated in § 4.2 , the M L M_L M L L 0 + L 1 ∥ ∇ f i ( x ) ∥ L_0 + L_1\|\nabla f_i(x)\| L 0 + L 1 ∥∇ f i ( x ) ∥ M H M_H M H H 0 + H 1 [ f i ( x ) − ℓ i ⋆ ] + H_0 + H_1[f_i(x)-\ell_i^\star]_+ H 0 + H 1 [ f i ( x ) − ℓ i ⋆ ] + ℓ i ⋆ = 0 \ell_i^\star= 0 ℓ i ⋆ = 0 f i f_i f i ∇ f i \nabla f_i ∇ f i ( ρ , γ , L 0 , L 1 ) (\rho,\gamma,L_0,L_1) ( ρ , γ , L 0 , L 1 ) ( ρ , γ , H 0 , H 1 ) (\rho,\gamma,H_0,H_1) ( ρ , γ , H 0 , H 1 ) ρ / M ( x t ) \rho/M(x_t) ρ / M ( x t ) γ / M ( y t ) \gamma/M(y_t) γ / M ( y t ) L 1 = 1 L_1 = 1 L 1 = 1 M L M_L M L H 0 = 1 H_0 = 1 H 0 = 1 M H M_H M H ( ρ , γ , L 0 ) (\rho,\gamma,L_0) ( ρ , γ , L 0 ) ( ρ , γ , H 1 ) (\rho,\gamma,H_1) ( ρ , γ , H 1 )
Tuning protocol. The protocol has three stages, each run on all four model–dataset settings.
Baselines. SAM and USAM, each with a constant and with a cosine annealing schedule, are tuned on seed 3107 over a 4 × 4 4 \times4 4 × 4 η ∈ { 0.03 , 0.1 , 0.3 , 1 } \eta\in\{0.03,0.1,0.3,1\} η ∈ { 0.03 , 0.1 , 0.3 , 1 } r ∈ { 0.01 , 0.05 , 0.1 , 0.2 } r \in\{0.01,0.05,0.1,0.2\} r ∈ { 0.01 , 0.05 , 0.1 , 0.2 } ρ ∈ { 0.1 , 0.3 , 1 , 3 } \rho\in\{0.1,0.3,1,3\} ρ ∈ { 0.1 , 0.3 , 1 , 3 } (40) , η \eta η
(ii) CS-SAM. The M L M_L M L ρ ∈ { 0.2 , 0.4 , 0.8 , 1.6 } \rho\in\{0.2, 0.4, 0.8, 1.6\} ρ ∈ { 0.2 , 0.4 , 0.8 , 1.6 } γ ∈ { 0.2 , 0.4 , 0.8 } \gamma\in\{0.2, 0.4, 0.8\} γ ∈ { 0.2 , 0.4 , 0.8 } L 0 ∈ { 0.02 , 0.5 , 2 } L_0 \in\{0.02, 0.5, 2\} L 0 ∈ { 0.02 , 0.5 , 2 } L 1 = 1 L_1 = 1 L 1 = 1 M H M_H M H ρ ∈ { 0.3 , 1 , 3 } \rho\in\{0.3, 1, 3\} ρ ∈ { 0.3 , 1 , 3 } γ ∈ { 0.3 , 1 , 3 } \gamma\in\{0.3, 1, 3\} γ ∈ { 0.3 , 1 , 3 } H 1 ∈ { 1 , 3 , 10 , 30 } H_1 \in\{1, 3, 10, 30\} H 1 ∈ { 1 , 3 , 10 , 30 } H 0 = 1 H_0 = 1 H 0 = 1
(iii) Seeds. For every method and setting, the configuration with the highest best test accuracy over the 200 epochs on seed 3107 is rerun with seeds 3407 and 4096. Table 3 reports the mean and the sample standard deviation over the three seeds of the best test accuracy over epochs.
Selected configurations. Table 4 lists, for every method and setting, the configuration selected in stages (i) and (ii) and rerun in stage (iii); these are the configurations behind the entries of Table 3 .
Table 4 : Configurations selected on seed 3107 by the best test accuracy over 200 epochs, for every method and setting of Table 3 . For SAM and USAM, η \eta η (40) , r r r ρ \rho ρ CS-SAM , ρ \rho ρ γ \gamma γ L 0 L_0 L 0 M L M_L M L L 0 + L 1 ∥ ∇ f i ( x ) ∥ L_0 + L_1 \lVert\nabla f_i(x)\rVert L 0 + L 1 ∥ ∇ f i ( x )∥ L 1 = 1 L_1 = 1 L 1 = 1 H 1 H_1 H 1 M H M_H M H H 0 + H 1 [ f i ( x ) − ℓ i ∗ ] + H_0 + H_1[f_i(x) - \ell_i^*]_+ H 0 + H 1 [ f i ( x ) − ℓ i ∗ ] + H 0 = 1 H_0 = 1 H 0 = 1 ℓ i ∗ = 0 \ell_i^* = 0 ℓ i ∗ = 0
