Introduction
Many theoretical results quantifying the behaviour of algorithms for optimization problems are framed as oracle complexity bounds , also frequently referred to as evaluation complexity bounds . This metric quantifies the number of oracle calls , denoted by K ε ( f ) K^\varepsilon(f) K ε ( f ) , required by a given algorithm to converge to an ε \varepsilon ε -optimal point for a problem characterized by a mapping f f f . An oracle call typically refers to a black-box which, given a point, returns pointwise information about the function, but no global information. Such an oracle could, for instance, return function values, gradient evaluations, Hessian-vector products, or combinations thereof. The notion of ε \varepsilon ε -optimality may be defined in several different ways, such as absolute or relative distance to solution, function value accuracy, gradient norm, etc. Even with the oracle and notion of optimality settled, the resulting complexity measure can be measured in different ways, of which we expose three different ones below.
Worst-Case Complexity. Historically, the vast majority of the optimization literature focuses heavily on worst-case oracle complexity guarantees. The goal of such an analysis is to provide a uniform upper bound on the oracle complexity K ε ( f ) K^\varepsilon(f) K ε ( f ) that remains valid uniformly for all instances f ∈ F f \in\mathcal{F} f ∈ F within a specified problem class F \mathcal{F} F [31 , 51 , 34 , 7 , 53 ] .
Even when these upper bounds are tight, meaning there exists a problem within F \mathcal{F} F that attains the upper bound, such instances are often pathological in some way and characterizing the practical performance of the algorithm solely with this worst-case scenario is often overly pessimistic. Such an analysis frequently fails to explain why algorithms perform well on real-world problems that lack this worst-case geometry.
Average-Case Complexity. To address this problem, alternative complexity measures have been proposed. The first is the one of average-case complexity, which computes the expectation of the complexity E f ∼ D [ K ε ( f ) ] \mathbb{E}_{f\sim\mathcal{D}}[K^\varepsilon(f)] E f ∼ D [ K ε ( f )] , where D \mathcal{D} D is a probability distribution over F \mathcal{F} F . By integrating over an entire ensemble of instances, the framework captures the “typical” performance that we can expect to encounter in practice. Presenting an average-case complexity result next to a worst-case complexity result allows to gain an image of the pessimistic and the typical behaviour of the algorithm. Famous examples show that quicksort, despite having worst-case complexity O ( n 2 ) \mathcal{O}(n^2) O ( n 2 ) , has average-case complexity O ( n log n ) \mathcal{O}(n\log n) O ( n log n ) [23 ] , that quickselect has worst-case complexity O ( n 2 ) \mathcal{O}(n^2) O ( n 2 ) yet average-case complexity O ( n ) \mathcal{O}(n) O ( n ) [22 ] , and that the simplex method, which can exhibit exponential-time behaviour, runs in polynomial time in average [4 ] .
Optimization algorithms have recently been studied in an average-case perspective. Due to the complexity of the question “What is a random function?” , most of the works have tackled the study on random quadratic functions. First-order methods have been analyzed in Scieur and Pedregosa [47 ] ; Cunha et al. [13 ] ; Pedregosa and Scieur [42 ] ; Paquette et al. [40 ] , with Benning and Döring [3 ] considering random generalized linear models. Another line of work has considered the study of the average-case behaviour of the Conjugate Gradient Method on various distributions of random quadratics, namely Deift and Trogdon [16 ] ; Ding and Trogdon [17 ] ; Paquette and Trogdon [41 ] . Slightly tangential, but mention-worthy in our opinion, is the line of work in Paquette et al. [38 ] ; Paquette and Paquette [39 ] ; Lee et al. [27 ] ; Marshall et al. [29 ] , who study the high-dimensional limiting dynamics of stochastic methods over a random class of quadratic functions.
However, average-case analyses are hard to carry out in general due to analytical difficulties of probabilistic iterative processes, and to interpret in practice due to their strong dependency on the input distribution, which may poorly reflect instances observed in practice.
Smoothed Complexity. Smoothed analysis aims to bridge the gap between worst-case and typically-observed complexity by studying the expected performance of an algorithm under a small localized perturbation of a worst-case instance. It was first introduced in Spielman and Teng [48 ] , where the authors provided evidence for the simplex algorithm with standard pivoting rules taking polynomial time to run, whereas the worst-case complexity was exponential. This showed that the worst-case instances were rare instances and could be avoided by a small perturbation. A more recent survey on smoothed analysis for linear programming includes Dadush and Huiberts [14 ] and the references therein.
Beyond linear programming, smoothed analysis has been successfully applied across a wide range of algorithmic settings. This includes local-search heuristics for combinatorial problems Manthey [28 ] , size of Pareto sets in multiobjective optimization Röglin [45 ] , analysis of the condition number of structured real polynomial systems Ergür et al. [20 ] , game-theoretic optimization Anagnostides and Sandholm [1 ] , and online metric problems Coester and Umenberger [10 ] , to name a few.
In the same spirit, it was proposed in Menon and Trogdon (2016) to study the smoothed complexity of optimization algorithms, namely of the Conjugate Gradient Method. They study the complexity of a perturbed quadratic function, where the perturbation is itself a quadratic function, and show the expected complexity is much better than the worst-case complexity over the class of quadratic functions.
Contribution and Motivation
In this paper, given a function class F \mathcal{F} F , we consider the smoothed complexity measure
sup f ∈ F E W [ K ε ( f W ) ] \sup_{f\in\mathcal{F}}\mathbb{E}_{W}\left[\mathsf{K}^{\varepsilon}(f_W)\right] f ∈ F sup E W [ K ε ( f W ) ]
of the function class F \mathcal{F} F , where given f : R n → R ∈ F f:\mathbb{R}^{n}\to\mathbb{R}\in\mathcal{F} f : R n → R ∈ F , f W f_W f W denotes a random perturbation of the function f f f . This notion will be formalized in § 3 .
The smoothed complexity count sup f ∈ F E W [ K ε ( f W ) ] \sup_{f\in\mathcal{F}}\mathbb{E}_{W}\left[\mathsf{K}^{\varepsilon}(f_W)\right] sup f ∈ F E W [ K ε ( f W ) ] interpolates between the worst-case and average-case analysis: an adversary first chooses a function f ∈ F f\in\mathcal{F} f ∈ F , and only the perturbation is randomized. This is the optimization analogue of the smoothed analysis in Spielman and Teng [48 ] , inspired by Menon and Trogdon (2016).
Within this framework, we study Gradient Descent (§ 3.1 ), Nesterov Accelerated Gradient Descent (§ 3.3 ), the Conjugate Gradient method (§ 3.4 ), the Cubic Regularized Newton Method (§ 3.5 ), a Hybrid Gradient–Cubic Newton method (§ 3.7 ), and the Gauss–Newton method in the convex and nonconvex settings (§ 3.8 –§ 3.9 and 3.10, respectively). This is by no means an exhaustive list of the algorithms that can be covered in our setting, but they provide, in our opinion, a representative overview of main optimization methods and of our analytical framework.
In all the cases we consider, we show that degenerate problem instances benefit, under any positive perturbation, from the same complexity guarantees as the corresponding non-degenerate class. This therefore explains why algorithms perform well in practice, even in degenerate settings. Specifically we observe the following:
For the standard first-order methods of Gradient Descent (§ 3.1 –§ 3.2 ), Nesterov Accelerated Gradient Descent (§ 3.3 ), and Conjugate Gradient (§ 3.4 ), it is known that convex functions enjoy a non-asymptotic complexity guarantee polynomial in 1 / ε 1/\varepsilon 1/ ε , whereas strongly convex functions improve this to log ( 1 / ε ) \log(1/\varepsilon) log ( 1/ ε ) . The latter comes at the cost of a dependency on the condition number κ \kappa κ , which is infinite in the merely convex case, and can be arbitrarily large for function with a very small strong convexity parameter.
The same holds true in a nonconvex setting, under gradient domination inequalities. We show that the random perturbation of the input does not make the condition number arbitrarily large in expectation, and that the smoothed complexity guarantee for convex functions enjoys a favourable dependency on ε \varepsilon ε without a bad condition number.
For second-order methods, such as Cubic Regularized Newton (§ 3.5 -§ 3.6 ) and a hybrid method between Gradient Descent and Cubic Regularized Newton (§ 3.7 ), classical global rate bounds show a constant number of steps followed by local quadratic convergence on strongly convex functions. We show that convex functions, under an arbitrary positive perturbation, enjoy the same type of non-asymptotic convergence bound, and quantify the size of the quadratic convergence region and the dependence on the problem condition number. We also study a nonconvex setting under gradient domination.
Finally, for Gauss-Newton methods (§ 3.8 -§ 3.10 ), we show that perturbations allow the method to retain linear convergence in the convex case or radially monotone case. We also study an adaptive Armijo line-search variant in the convex case.
Motivation. As a secondary motivation to computing the quantity in Equation (1) , we mention the recent work on differential privacy through additive random quadratics in Cortild and Cartis [11 ] . In this work, it is shown that an additive quadratic perturbation inherently enforces privacy when solving the problem, without loosing too much on the accuracy side. No complexity results were provided, as the study of such complexity notion was out of the scope of the cited paper. The current paper complements that story, by providing the necessary complexity computations.
Notation. We denote by, for any base b > 1 b > 1 b > 1 , log b , + ( x ) = log b ( x ) \log_{b,+}(x) = \log_b(x) log b , + ( x ) = log b ( x ) if x ≥ 1 x \ge1 x ≥ 1 and 0 otherwise. We note that log b , + ( x ) ≤ log b ( 1 + x ) \log_{b,+}(x) \le\log_b(1 + x) log b , + ( x ) ≤ log b ( 1 + x ) for all x ≥ 0 x \ge0 x ≥ 0 .
Random Matrix Theory Preliminaries
Consider a random real n × m n \times m n × m Gaussian matrix G G G (with entries independently following the standard normal distribution), and let W = 1 m G G T W = \frac{1}{m}GG^{T} W = m 1 G G T be a real n × n n \times n n × n Wishart matrix with parameter m m m . We place ourselves in the setting of proportional growth , in which the parameters m m m and n n n grow proportionally with n / m → d ∈ ( 0 , 1 ) n/m \to d \in(0,1) n / m → d ∈ ( 0 , 1 ) . We assume this limit is taking place from the left, so that n / m ≤ d n/m \le d n / m ≤ d holds for all ( n , m ) (n,m) ( n , m ) . We note that this corresponds to the overparametrized model , such that W W W is almost surely nonsingular. For a fixed n n n , as d → 0 d \to0 d → 0 , we must have m → ∞ m \to\infty m → ∞ , corresponding to the infinitely overparametrized setting.
The results in this paper reduce to the study of the extreme eigenvalues of W W W , denoted by λ min ( W ) \lambda_{\min}(W) λ m i n ( W ) and λ max ( W ) \lambda_{\max}(W) λ m a x ( W ) . Equivalently, we study the extreme singular values of G G G , denoted by s min ( G ) s_{\min}(G) s m i n ( G ) and s max ( G ) s_{\max}(G) s m a x ( G ) , linked to the extreme eigenvalues of W W W through the relations
λ min ( W ) = s min ( G ) 2 m and λ max ( W ) = s max ( G ) 2 m . \lambda_{\min}(W) = \frac{s_{\min}(G)^2}{m} \quad\text{and} \quad\lambda_{\max}(W) = \frac{s_{\max}(G)^2}{m}. λ m i n ( W ) = m s m i n ( G ) 2 and λ m a x ( W ) = m s m a x ( G ) 2 .
Wishart matrices and its singular values have been thoroughly studied over the past decades. To mention a few, we refer to Bai and Yin [2 ] ; Davidson and Szarek [15 ] ; Johnstone [25 ] ; Dumitriu and Edelman [18 ] ; Edelman and Sutton [19 ] ; Rudelson and Vershynin [43 , 44 ] ; Chiani [9 ] ; Huang and Tikhomirov [24 ] . For a more recent survey and introduction to the matter we refer to Vershynin [52 ] and the references therein.
We now introduce the main moment bounds used throughout. They can be obtained from, for instance, Sarkar et al. [46 ] , Lemma 2.2, Theorem 2.2. However, the resulting bounds are quite loose, so we reprove them. The proofs and explicit constants are given in Appendix § 6 .
Theorem 2.1 (Moment Bounds of Singular Values). For every q > 0 q > 0 q > 0 , there exists constants C q , d max C^{\max}_{q,d} C q , d m a x and C d , q min C^{\min}_{d,q} C d , q m i n so that, for m , n m,n m , n sufficiently large,
E [ s max ( G ) q m − q / 2 ] ≤ C d , q max and E [ s min ( G ) − q m q / 2 ] ≤ C d , q min . \mathbb{E}\left[s_{\max}(G)^q m^{-q/2}\right] \le C^{\max}_{d,q}
\quad\text{and}\quad
\mathbb{E}\left[s_{\min}(G)^{-q}m^{q/2}\right] \le C^{\min}_{d,q}. E [ s m a x ( G ) q m − q /2 ] ≤ C d , q m a x and E [ s m i n ( G ) − q m q /2 ] ≤ C d , q m i n .
Smoothed Analysis Results
In this paper, we consider the smoothed complexity measure over a function class F \mathcal{F} F given by
sup f ∈ F E W [ K ε ( f W ) ] , where f W ( x ) = f ( x ) + σ 2 2 ( x − x ~ ) T W ( x − x ~ ) , (1) \sup_{f \in\mathcal{F}} \mathbb{E}_{W}[\mathbb{K}^{\varepsilon}(f_{W})], \quad\text{where } f_{W}(x)=f(x)+\frac{\sigma^{2}}{2}(x-\tilde{x})^{T}W(x-\tilde{x}), \tag*{(1)} f ∈ F sup E W [ K ε ( f W )] , where f W ( x ) = f ( x ) + 2 σ 2 ( x − x ~ ) T W ( x − x ~ ) , (1)
where f : R n → R ∈ F f:\mathbb{R}^{n}\to\mathbb{R}\in\mathcal{F} f : R n → R ∈ F is a function belonging to the function class F \mathcal{F} F , and f W f_{W} f W is a perturbation of the function f f f characterized by the scaling parameter σ \sigma σ , a given center x ~ \tilde{x} x ~ and the random Wishart matrix W = 1 m G G T W=\frac{1}{m}GG^{T} W = m 1 G G T .1 The scaling parameter σ \sigma σ plays the role of the variance of the random matrix W W W . We note that σ \sigma σ , x 0 x_{0} x 0 and x ~ \tilde{x} x ~ are fixed before drawing W W W , and are fixed accross the supremum.
All of our guarantees will concern optimization of the perturbed objective f W f_{W} f W . When f f f has a minimizer x ∗ x_{*} x ∗ , guarantees on f W f_{W} f W are linked to guarantees on f f f through
f ( x ) − min f ≤ δ + σ 2 2 ( x ∗ − x ~ ) T W ( x ∗ − x ~ ) , f(x)-\min f\leq\delta+\frac{\sigma^{2}}{2}(x_{*}-\tilde{x})^{T}W(x_{*}-\tilde{x}), f ( x ) − min f ≤ δ + 2 σ 2 ( x ∗ − x ~ ) T W ( x ∗ − x ~ ) ,
where f W ( x ) − min f W ≤ δ f_{W}(x)-\min f_{W}\leq\delta f W ( x ) − min f W ≤ δ . Thus, the improved regularity comes with a perturbation bias.
For convex L L L -smooth f f f , it holds that f W f_{W} f W is μ σ \mu_{\sigma} μ σ -strongly convex and L σ L_{\sigma} L σ -smooth, for
μ σ = σ 2 λ min ( W ) = σ 2 s min ( G ) 2 m and L σ = L + σ 2 λ max ( W ) = L + σ 2 s max ( G ) 2 m . (2) \mu_{\sigma}=\sigma^{2}\lambda_{\min}(W)=\sigma^{2}\frac{s_{\min}(G)^{2}}{m}
\quad\text{and}\quad
L_{\sigma}=L+\sigma^{2}\lambda_{\max}(W)=L+\sigma^{2}\frac{s_{\max}(G)^{2}}{m}. \tag*{(2)} μ σ = σ 2 λ m i n ( W ) = σ 2 m s m i n ( G ) 2 and L σ = L + σ 2 λ m a x ( W ) = L + σ 2 m s m a x ( G ) 2 . (2)
For D 2 = ∥ x 0 − x ~ ∥ 2 D^{2}=\lVert x_{0}-\tilde{x}\rVert^{2} D 2 = ∥ x 0 − x ~ ∥ 2 and Δ = f ( x 0 ) − inf f \Delta=f(x_{0})-\inf f Δ = f ( x 0 ) − inf f ,
f W ( x 0 ) − inf f W ≤ Δ σ = Δ + σ 2 D 2 λ max ( W ) 2 = Δ + σ 2 D 2 s max ( G ) 2 2 m . (3) f_{W}(x_{0})-\inf f_{W}\leq\Delta_{\sigma}=\Delta+\frac{\sigma^{2}D^{2}\lambda_{\max}(W)}{2}
=\Delta+\frac{\sigma^{2}D^{2}s_{\max}(G)^{2}}{2m}. \tag*{(3)} f W ( x 0 ) − inf f W ≤ Δ σ = Δ + 2 σ 2 D 2 λ m a x ( W ) = Δ + 2 m σ 2 D 2 s m a x ( G ) 2 . (3)
Numerical Illustrations. For each method, we compare
the theoretical smoothed complexity bound;
the empirical expectation of the corresponding worst-case bound; and
the empirical iteration count of the algorithm when applied to f W f_{W} f W .
All empirical quantities are computed as an average over 100 samples of the perturbation. The experiments were implemented in Python 3.13 and run on a MacBook Pro with an Apple M5 chip.2 The function used in each experiment is specified in the corresponding section.
Gradient Descent
We begin with the Gradient Descent method (Cauchy, [8 ] ) on the class F μ L \mathcal{F}_{\mu}^{L} F μ L of μ \mu μ -strongly convex and L L L -smooth functions, with the convention that μ = 0 \mu=0 μ = 0 corresponds to the convex bounded-below setting F 0 L ⊃ F μ L \mathcal{F}_{0}^{L}\supset\mathcal{F}_{\mu}^{L} F 0 L ⊃ F μ L . For h ∈ F μ L h\in\mathcal{F}_{\mu}^{L} h ∈ F μ L , we consider, for x 0 ∈ R n x_{0}\in\mathbb{R}^{n} x 0 ∈ R n and k ≥ 0 k\geq0 k ≥ 0 ,
x k + 1 = x k − 1 L ∇ h ( x k ) . x_{k+1}=x_{k}-\frac{1}{L}\nabla h(x_{k}). x k + 1 = x k − L 1 ∇ h ( x k ) .
We measure complexity in terms of relative function value accuracy, namely, for ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) ,
K G D ε ( h ) = min k ≥ 0 { k : h ( x k ) − inf h h ( x 0 ) − inf h ≤ ε } . \mathbb{K}_{\mathrm{GD}}^{\varepsilon}(h)=\min_{k\geq0}\left\{k:\frac{h(x_{k})-\inf h}{h(x_{0})-\inf h}\leq\varepsilon\right\}. K GD ε ( h ) = k ≥ 0 min { k : h ( x 0 ) − inf h h ( x k ) − inf h ≤ ε } .
where K G D ε ( h ) = 0 \mathbb{K}_{\mathrm{GD}}^{\varepsilon}(h)=0 K GD ε ( h ) = 0 if h ( x 0 ) = inf h h(x_{0})=\inf h h ( x 0 ) = inf h .
We first recall the classical worst-case complexity (see, for instance, (Wright and Recht, [53 ] , Equation (3.15))), which will serve as a benchmark for our smoothed complexity guarantees.
Theorem 3.1 (Worst-Case Complexity for (GD) - [53 ] ). Let h ∈ F μ L h \in F_{\mu}^{L} h ∈ F μ L with 0 < μ ≤ L < + ∞ 0 < \mu\le L < +\infty 0 < μ ≤ L < + ∞ , and let ( x k ) (x_k) ( x k ) be the iterates of (GD). Then, for κ = L / μ \kappa= L/\mu κ = L / μ ,
h ( x k ) − inf h h ( x 0 ) − inf h ≤ ( 1 − 1 κ ) k . \frac{h(x_k)-\inf h}{h(x_0)-\inf h} \le\left(1-\frac{1}{\kappa}\right)^k. h ( x 0 ) − inf h h ( x k ) − inf h ≤ ( 1 − κ 1 ) k . Thus the relative accuracy complexity is bounded by
sup h ∈ F μ L K G D ε ( h ) ≤ ⌈ κ log 1 ε ⌉ . \sup_{h\in F_{\mu}^{L}} \mathbb{K}_{\mathrm{GD}}^{\varepsilon}(h) \le\left\lceil\kappa\log\frac{1}{\varepsilon}\right\rceil. h ∈ F μ L sup K GD ε ( h ) ≤ ⌈ κ log ε 1 ⌉ .
Though the above theorem is only valid for μ > 0 \mu> 0 μ > 0 , it is known that Algorithm (GD) converges for μ = 0 \mu= 0 μ = 0 , albeit at a sublinear rate. The below represents our first smoothed complexity bound.
Theorem 3.2 (Smoothed Complexity for (GD)). Let 0 < σ , L < + ∞ 0 < \sigma,L < +\infty 0 < σ , L < + ∞ and ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) . We denote by f W f_W f W a perturbation of f f f , parametrized by σ \sigma σ , as defined in Equation (1) and apply Algorithm (GD) to f W f_W f W . Then, as n → ∞ n \to\infty n → ∞ , the smoothed complexity of Algorithm (GD) over the function class F 0 L F_0^L F 0 L is bounded by
sup f ∈ F 0 L E W [ K G D ε ( f W ) ] ≤ 1 + O d ( ( 1 + σ − 2 L ) log 1 ε ) . \sup_{f\in F_0^L}\mathbb{E}_W[\mathbb{K}_{\mathrm{GD}}^{\varepsilon}(f_W)] \le1+\mathcal{O}_d\left((1+\sigma^{-2}L)\log\frac{1}{\varepsilon}\right). f ∈ F 0 L sup E W [ K GD ε ( f W )] ≤ 1 + O d ( ( 1 + σ − 2 L ) log ε 1 ) .
Proof. Fix any f ∈ F 0 L f \in F_0^L f ∈ F 0 L . By Equation (2) , Cauchy–Schwarz and Theorem 2.1 ,
E W [ κ σ ] = L σ − 2 E W [ m s min ( G ) 2 ] + E W [ s max ( G ) 2 s min ( G ) 2 ] ≤ O d ( 1 + σ − 2 L ) . \mathbb{E}_W[\kappa_\sigma]=L\sigma^{-2}\mathbb{E}_W\left[\frac{m}{s_{\min}(G)^2}\right]+\mathbb{E}_W\left[\frac{s_{\max}(G)^2}{s_{\min}(G)^2}\right]\le\mathcal{O}_d(1+\sigma^{-2}L). E W [ κ σ ] = L σ − 2 E W [ s m i n ( G ) 2 m ] + E W [ s m i n ( G ) 2 s m a x ( G ) 2 ] ≤ O d ( 1 + σ − 2 L ) .
The result follows from Theorem 3.1 applied to h = f W h=f_W h = f W , and where the ensuing step-size in Algorithm (GD) is 1 / L σ 1/L_\sigma 1/ L σ , where L σ L_\sigma L σ is defined in (2) . □
Discussion. The smoothed complexity bound depends only logarithmically on ε \varepsilon ε , even though we are considering the class of merely convex functions, for which we expect an inverse dependency in ε \varepsilon ε . This is due to the perturbation, which renders the objective strongly convex. The strong convexity parameter may however be arbitrarily small, in which case the condition number is arbitrarily large, and the linear bound is worse than the sublinear bound. Given the nature of the perturbation matrix, this occurs with sufficiently small probability, so that, in expectation, we do not observe this. In fact, the expected strong convexity parameter is proportional to the scale of the perturbation, σ 2 \sigma^2 σ 2 , as can be seen in the bound, where σ − 2 L \sigma^{-2}L σ − 2 L acts as a condition number.
Numerical Illustration. We illustrate Theorem 3.2 on a weighted Huber objective, based on the Huber function used to generate bad instances for smooth convex first-order optimization [49 ] ,
f ( x ) = ∑ i = 1 n 2 10 ( i − n / 2 ) / n ϕ ( x i ) , ϕ ( t ) = { 1 2 t 2 , ∣ t ∣ ≤ 1 , ∣ t ∣ − 1 2 , ∣ t ∣ > 1. f(x)=\sum_{i=1}^{n}2^{10(i-n/2)/n}\phi(x_i), \qquad\phi(t)=
\begin{cases}
\frac{1}{2}t^2, & |t|\le1,\\
|t|-\frac{1}{2}, & |t|>1.
\end{cases} f ( x ) = i = 1 ∑ n 2 10 ( i − n /2 ) / n ϕ ( x i ) , ϕ ( t ) = { 2 1 t 2 , ∣ t ∣ − 2 1 , ∣ t ∣ ≤ 1 , ∣ t ∣ > 1.
The weights give L = 2 5 L=2^5 L = 2 5 and a ratio of largest to smallest curvature of 2 10 ( n − 1 ) / n 2^{10(n-1)/n} 2 10 ( n − 1 ) / n in the quadratic region. The results are shown in Figure 1 , including the iteration count of GD applied directly to the unperturbed objective with step-size 1 / L 1/L 1/ L , shown as a dotted line without markers. This additional curve is independent of σ \sigma σ and d d d . We observe that our bounds are very close to the empirical smoothed complexity of the worst-case bound, but that both are overly pessimistic compared to the empirical smoothed complexity of the run algorithm. This highlights the well-known fact that first-order methods can be overly pessimistic in their worst-case behaviour.
Figure 1. Smoothed complexity of Algorithm (GD) under Wishart perturbations.
We additionally consider a degenerate ill-conditioned quadratic, given by
f ( x ) = 1 2 ∑ i = 1 ⌊ n / 2 ⌋ a i x i 2 , a i = 2 10 ( i − n / 2 ) / n . f(x) = \frac{1}{2}\sum_{i=1}^{\lfloor n/2\rfloor} a_i x_i^2,\qquad a_i = 2^{10(i-n/2)/n}. f ( x ) = 2 1 i = 1 ∑ ⌊ n /2 ⌋ a i x i 2 , a i = 2 10 ( i − n /2 ) / n .
It has a large spread in its non-zero eigenvalues, and a large number of zero eigenvalues. The function is therefore not strongly convex. The results are shown in Figure 2 . We see that our results correctly predict the tendency in σ \sigma σ , whereas the dependency in d d d is more pessimistic.
Figure 2. Smoothed complexity of Algorithm (GD) under Wishart perturbations.
Gradient Descent under Radial Monotonicity
We now consider Algorithm (GD) beyond the convex setting. Specifically, we say that a function h ∈ F − ∞ L h \in\mathcal{F}^{L}_{-\infty} h ∈ F − ∞ L , where F − ∞ L \mathcal{F}^{L}_{-\infty} F − ∞ L denotes the class of nonconvex L L L -smooth functions, satisfies gradient domination , also known as the Polyak-Lojasiewicz inequality , with parameter η > 0 \eta> 0 η > 0 if it is bounded below and
∥ ∇ h ( x ) ∥ 2 ≥ 2 η ( h ( x ) − inf h ) for all x ∈ R n . \lVert\nabla h(x)\rVert^2 \ge2\eta(h(x)-\inf h)\quad\text{for all }x\in\mathbb{R}^n. ∥ ∇ h ( x ) ∥ 2 ≥ 2 η ( h ( x ) − inf h ) for all x ∈ R n .
Denote by F P L , η L \mathcal{F}^{L}_{\mathrm{PL},\eta} F PL , η L , the subclass of F − ∞ L \mathcal{F}^{L}_{-\infty} F − ∞ L that satisfies gradient domination with parameter η > 0 \eta> 0 η > 0 . We note that gradient domination implies that all local minimizers are global, and therefore we can measure complexity in terms of relative function value accuracy K G D ε ( h ) K^{\varepsilon}_{\mathrm{GD}}(h) K GD ε ( h ) as done in § 3.1 .
Gradient domination does not require convexity, but still ensures linear convergence of Gradient Descent. We first give the deterministic worst-case complexity under gradient domination, whose proof may be found in [26 Theorem 1] .
Theorem 3.3 (Worst-Case Complexity of (GD) under Gradient Domination - Karimi et al. [26 ] ).
Let h ∈ F P L , η L h \in\mathcal{F}_{\mathrm{PL},\eta}^{L} h ∈ F PL , η L with 0 < η ≤ L < + ∞ 0 < \eta\le L < +\infty 0 < η ≤ L < + ∞ , and let ( x k ) (x_k) ( x k ) be the iterates of (GD). Then,
h ( x k ) − inf h h ( x 0 ) − inf h ≤ ( 1 − η L ) k . \frac{h(x_k)-\inf h}{h(x_0)-\inf h} \le\left(1-\frac{\eta}{L}\right)^k. h ( x 0 ) − inf h h ( x k ) − inf h ≤ ( 1 − L η ) k .
Thus, for ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) , the relative function value accuracy complexity is bounded by
sup h ∈ F P L , η L K G D ε ( h ) ≤ ⌈ L η log 1 ε ⌉ . \sup_{h\in\mathcal{F}_{\mathrm{PL},\eta}^{L}} \mathbb{K}_{\mathrm{GD}}^{\varepsilon}(h) \le\left\lceil\frac{L}{\eta}\log\frac{1}{\varepsilon}\right\rceil. h ∈ F PL , η L sup K GD ε ( h ) ≤ ⌈ η L log ε 1 ⌉ .
We now consider the class of radially monotone functions, denoted by F r a d L ( x ~ ) \mathcal{F}_{\mathrm{rad}}^{L}(\tilde{x}) F rad L ( x ~ ) , within F − ∞ L \mathcal{F}_{-\infty}^{L} F − ∞ L , namely functions for which
f ( x ~ ) = inf f and ( x − x ~ ) T ∇ f ( x ) ≥ 0 for every x ∈ R n . f(\tilde{x})=\inf f \quad\text{and}\quad(x-\tilde{x})^{T}\nabla f(x)\ge0 \quad\text{for every }x\in\mathbb{R}^{n}. f ( x ~ ) = inf f and ( x − x ~ ) T ∇ f ( x ) ≥ 0 for every x ∈ R n .
These functions are nondecreasing along rays to the specified center, which is a minimizer, but could still have negative curvature, and thus need not be convex.
Fixing the center of the perturbation to be the same x ~ \tilde{x} x ~ , we obtain that
( x − x ~ ) T ∇ f W ( x ) = ( x − x ~ ) T ∇ f ( x ) + ( x − x ~ ) T σ 2 W ( x − x ~ ) ≥ σ 2 λ min ( W ) ∥ x − x ~ ∥ 2 . (x-\tilde{x})^{T}\nabla f_{W}(x)=(x-\tilde{x})^{T}\nabla f(x)+(x-\tilde{x})^{T}\sigma^{2}W(x-\tilde{x})\ge\sigma^{2}\lambda_{\min}(W)\lVert x-\tilde{x}\rVert^{2}. ( x − x ~ ) T ∇ f W ( x ) = ( x − x ~ ) T ∇ f ( x ) + ( x − x ~ ) T σ 2 W ( x − x ~ ) ≥ σ 2 λ m i n ( W ) ∥ x − x ~ ∥ 2 .
which implies that
∥ ∇ f W ( x ) ∥ ≥ σ 2 λ min ( W ) ∥ x − x ~ ∥ . \lVert\nabla f_{W}(x)\rVert\ge\sigma^{2}\lambda_{\min}(W)\lVert x-\tilde{x}\rVert. ∥ ∇ f W ( x )∥ ≥ σ 2 λ m i n ( W ) ∥ x − x ~ ∥ .
As f W f_{W} f W is L σ L_{\sigma} L σ -smooth for L σ = L + σ 2 λ max ( W ) L_{\sigma}=L+\sigma^{2}\lambda_{\max}(W) L σ = L + σ 2 λ m a x ( W ) , and x ~ \tilde{x} x ~ is a minimizer of f W f_{W} f W , we get
f W ( x ) − f W ( x ~ ) ≤ L σ 2 ∥ x − x ~ ∥ 2 . f_{W}(x)-f_{W}(\tilde{x})\le\frac{L_{\sigma}}{2}\lVert x-\tilde{x}\rVert^{2}. f W ( x ) − f W ( x ~ ) ≤ 2 L σ ∥ x − x ~ ∥ 2 .
which, combined with the previous point, gives
∥ ∇ f W ( x ) ∥ 2 ≥ σ 4 λ min ( W ) 2 ∥ x − x ~ ∥ 2 ≥ 2 σ 4 λ min ( W ) 2 L σ ( f W ( x ) − inf f W ) . \lVert\nabla f_{W}(x)\rVert^{2}\ge\sigma^{4}\lambda_{\min}(W)^{2}\lVert x-\tilde{x}\rVert^{2}\ge\frac{2\sigma^{4}\lambda_{\min}(W)^{2}}{L_{\sigma}}(f_{W}(x)-\inf f_{W}). ∥ ∇ f W ( x ) ∥ 2 ≥ σ 4 λ m i n ( W ) 2 ∥ x − x ~ ∥ 2 ≥ L σ 2 σ 4 λ m i n ( W ) 2 ( f W ( x ) − inf f W ) .
Specifically, f W ∈ F P L , η σ L σ f_{W}\in\mathcal{F}_{\mathrm{PL},\eta_{\sigma}}^{L_{\sigma}} f W ∈ F PL , η σ L σ , for
L σ = L + σ 2 λ max ( W ) and η σ = σ 4 λ min ( W ) 2 L σ . L_{\sigma}=L+\sigma^{2}\lambda_{\max}(W)\quad\text{and}\quad\eta_{\sigma}=\frac{\sigma^{4}\lambda_{\min}(W)^{2}}{L_{\sigma}}. L σ = L + σ 2 λ m a x ( W ) and η σ = L σ σ 4 λ m i n ( W ) 2 .
We now state the smoothed complexity guarantee.
Theorem 3.4 (Smoothed Complexity of (GD) under Radial Monotonicity). Let 0 < σ , L < + ∞ 0<\sigma,L<+\infty 0 < σ , L < + ∞ , ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) , and x ~ ∈ R n \tilde{x}\in\mathbb{R}^{n} x ~ ∈ R n . We denote by f W f_{W} f W a perturbation of f f f , parametrized by σ \sigma σ , as defined in Equation (1) . Then, as n → ∞ n\to\infty n → ∞ , the smoothed complexity of Algorithm (GD) over the function class F r a d L ( x ~ ) \mathcal{F}_{\mathrm{rad}}^{L}(\tilde{x}) F rad L ( x ~ ) is bounded by
sup f ∈ F r a d L ( x ~ ) E W [ K G D ε ( f W ) ] ≤ 1 + O d ( ( 1 + σ − 2 L ) 2 log 1 ε ) . \sup_{f\in\mathcal{F}_{\mathrm{rad}}^{L}(\tilde{x})}\mathbb{E}_{W}\left[\mathbb{K}_{\mathrm{GD}}^{\varepsilon}(f_{W})\right]\le1+\mathcal{O}_{d}\left((1+\sigma^{-2}L)^{2}\log\frac{1}{\varepsilon}\right). f ∈ F rad L ( x ~ ) sup E W [ K GD ε ( f W ) ] ≤ 1 + O d ( ( 1 + σ − 2 L ) 2 log ε 1 ) .
Proof. Fix any f ∈ F r a d L ( x ~ ) f\in\mathcal{F}_{\mathrm{rad}}^{L}(\tilde{x}) f ∈ F rad L ( x ~ ) , so that f W ∈ F P L , η σ L σ f_{W}\in\mathcal{F}_{\mathrm{PL},\eta_{\sigma}}^{L_{\sigma}} f W ∈ F PL , η σ L σ . Theorem 3.3 and the preceding bounds give
K G D ε ( f W ) ≤ 1 + ( L + σ 2 λ max ( W ) ) 2 σ 4 λ min ( W ) 2 log 1 ε . \mathbb{K}_{\mathrm{GD}}^{\varepsilon}(f_{W})\le1+\frac{(L+\sigma^{2}\lambda_{\max}(W))^{2}}{\sigma^{4}\lambda_{\min}(W)^{2}}\log\frac{1}{\varepsilon}. K GD ε ( f W ) ≤ 1 + σ 4 λ m i n ( W ) 2 ( L + σ 2 λ m a x ( W ) ) 2 log ε 1 .
Expanding the numerator, applying Cauchy-Schwarz to each mixed moment and using Theorem 2.1 proves the result.
Discussion. As in § 3.1 , the smoothed complexity bound depends only logarithmically on ε \varepsilon ε , even though the original objective did not satisfy gradient domination. In contrast to § 3.1 , the dependency in 1 + σ − 2 L 1+\sigma^{-2}L 1 + σ − 2 L is squared. This is explained through the equality L σ η σ = L σ 2 μ σ 2 \frac{L_{\sigma}}{\eta_{\sigma}}=\frac{L_{\sigma}^{2}}{\mu_{\sigma}^{2}} η σ L σ = μ σ 2 L σ 2 , where μ σ = σ 2 λ min ( W ) \mu_{\sigma}=\sigma^{2}\lambda_{\min}(W) μ σ = σ 2 λ m i n ( W ) . This additional factor thus arises naturally in the passage from radial monotonicity to gradient domination.
Numerical Illustration. To illustrate Theorem 3.4 , we consider the objective
f ( x ) = ∑ i = 1 n ( 1 − e − x i 2 / 2 ) , x ~ = 0. f(x)=\sum_{i=1}^{n}\left(1-e^{-x_i^2/2}\right),\qquad\tilde{x}=0. f ( x ) = i = 1 ∑ n ( 1 − e − x i 2 /2 ) , x ~ = 0.
This objective satisfies ( x − x ~ ) T ∇ f ( x ) = ∑ i = 1 n x i 2 e − x i 2 / 2 ≥ 0 (x-\tilde{x})^{T}\nabla f(x)=\sum_{i=1}^{n}x_i^2e^{-x_i^2/2}\ge0 ( x − x ~ ) T ∇ f ( x ) = ∑ i = 1 n x i 2 e − x i 2 /2 ≥ 0 and f ( x ~ ) = min f f(\tilde{x})=\min f f ( x ~ ) = min f , so that f f f is radially monotone. However, f f f is nonconvex, as ∂ i i f ( x ) = ( 1 − x i 2 ) e − x i 2 / 2 \partial_{ii}f(x)=(1-x_i^2)e^{-x_i^2/2} ∂ ii f ( x ) = ( 1 − x i 2 ) e − x i 2 /2 , and does not satisfy a global gradient domination bound, as, for instance, along x = t e 1 x=te_1 x = t e 1 , the function tends to a finite value as t → ∞ t\to\infty t → ∞ . The objective is however globally smooth with L = 1 L=1 L = 1 .
The results are shown in Figure 3 . We note that the growth in d d d and in σ \sigma σ is pessimistic in our bounds, but the growth occurs in the correct trend. However, these results show the applicability of the PL guarantee in our framework.
Figure 3. Smoothed complexity of Algorithm (GD) under Wishart perturbations.
Nesterov Accelerated Gradient Descent
We next consider Nesterov Accelerated Gradient Descent (Nesterov, [32 ] ) on the same class F μ L \mathcal{F}_{\mu}^{L} F μ L . For h ∈ F μ L h\in\mathcal{F}_{\mu}^{L} h ∈ F μ L , initialize y 0 = x 0 y_0=x_0 y 0 = x 0 and consider, for k ≥ 0 k\ge0 k ≥ 0 ,
x k + 1 = y k − 1 L ∇ h ( y k ) , y k + 1 = x k + 1 + L − μ L + μ ( x k + 1 − x k ) . x_{k+1}=y_k-\frac{1}{L}\nabla h(y_k),\qquad y_{k+1}=x_{k+1}+\frac{\sqrt{L}-\sqrt{\mu}}{\sqrt{L}+\sqrt{\mu}}(x_{k+1}-x_k). x k + 1 = y k − L 1 ∇ h ( y k ) , y k + 1 = x k + 1 + L + μ L − μ ( x k + 1 − x k ) .
(NAG)
We again measure complexity in terms of relative function value accuracy, namely, for ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) ,
K N A G ε ( h ) = min { k ≥ 0 : h ( x k ) − inf h h ( x 0 ) − inf h ≤ ε } , \mathsf{K}^{\varepsilon}_{\mathrm{NAG}}(h)=\min\left\{k\ge0:\frac{h(x_k)-\inf h}{h(x_0)-\inf h}\le\varepsilon\right\}, K NAG ε ( h ) = min { k ≥ 0 : h ( x 0 ) − inf h h ( x k ) − inf h ≤ ε } ,
where K N A G ε ( h ) = 0 \mathsf{K}^{\varepsilon}_{\mathrm{NAG}}(h)=0 K NAG ε ( h ) = 0 if h ( x 0 ) = inf h h(x_0)=\inf h h ( x 0 ) = inf h .
We first recall the classical accelerated worst-case complexity; see, for instance, (Nesterov, [34 ] ). The bound is accelerated in the sense that it depends on κ \sqrt{\kappa} κ rather than κ \kappa κ , as in § 3.1 .
Theorem 3.5 (Worst-Case Complexity for (NAG) - Nesterov [34 ] ). Let h ∈ F μ L h\in\mathcal{F}_{\mu}^{L} h ∈ F μ L with 0 < μ ≤ L < + ∞ 0<\mu\le L<+\infty 0 < μ ≤ L < + ∞ , and let ( x k ) (x_k) ( x k ) be the iterates of (NAG). Then, for κ = L / μ \kappa=L/\mu κ = L / μ ,
h ( x k ) − inf h h ( x 0 ) − inf h ≤ 2 ( 1 − 1 κ ) k . \frac{h(x_k)-\inf h}{h(x_0)-\inf h}\le2\left(1-\frac{1}{\sqrt{\kappa}}\right)^k. h ( x 0 ) − inf h h ( x k ) − inf h ≤ 2 ( 1 − κ 1 ) k . Thus the relative accuracy complexity is bounded by
sup h ∈ F μ L K N A G ε ( h ) ≤ ⌈ κ log 2 ε ⌉ . \sup_{h\in\mathcal{F}_{\mu}^{L}}\mathsf{K}^{\varepsilon}_{\mathrm{NAG}}(h)\le\left\lceil\sqrt{\kappa}\log\frac{2}{\varepsilon}\right\rceil. h ∈ F μ L sup K NAG ε ( h ) ≤ ⌈ κ log ε 2 ⌉ .
We provide our smoothed complexity guarantee for Algorithm (NAG), which also shows the acceleration behaviour.
Theorem 3.6 (Smoothed Complexity for (N A G \mathrm{NAG} NAG )). Let 0 < σ , L < + ∞ 0 < \sigma, L < +\infty 0 < σ , L < + ∞ and ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) . We denote by f W f_W f W a perturbation of f f f , parametrized by σ \sigma σ , as defined in Equation (1) . Then, as n → ∞ n \to\infty n → ∞ , the smoothed complexity of Algorithm (N A G \mathrm{NAG} NAG ) over the function class F 0 L \mathcal{F}_0^L F 0 L is bounded by
sup f ∈ F 0 L E W [ K N A G ε ( f W ) ] ≤ 1 + O d ( ( 1 + σ − 1 L ) log 2 ε ) . \sup_{f\in\mathcal{F}_0^L}\mathbb{E}_W\left[\mathbb{K}_{\mathrm{NAG}}^\varepsilon(f_W)\right] \le1 + \mathcal{O}_d\left(\left(1+\sigma^{-1}\sqrt{L}\right)\log\frac{2}{\varepsilon}\right). f ∈ F 0 L sup E W [ K NAG ε ( f W ) ] ≤ 1 + O d ( ( 1 + σ − 1 L ) log ε 2 ) .
Proof. Fix any f ∈ F 0 L f \in\mathcal{F}_0^L f ∈ F 0 L . By Equation (2) , subadditivity of the square root, Cauchy–Schwarz and Theorem 2.1 ,
E W [ κ σ ] ≤ σ − 1 L E W [ m s min ( G ) ] + E W [ s max ( G ) s min ( G ) ] ≤ O d ( 1 + σ − 1 L ) . \mathbb{E}_W\left[\sqrt{\kappa_\sigma}\right] \le\sigma^{-1}\sqrt{L}\mathbb{E}_W\left[\frac{\sqrt{m}}{s_{\min}(G)}\right] + \mathbb{E}_W\left[\frac{s_{\max}(G)}{s_{\min}(G)}\right] \le\mathcal{O}_d\left(1+\sigma^{-1}\sqrt{L}\right). E W [ κ σ ] ≤ σ − 1 L E W [ s m i n ( G ) m ] + E W [ s m i n ( G ) s m a x ( G ) ] ≤ O d ( 1 + σ − 1 L ) .
The result follows from Theorem 3.5 . □
Discussion. As in § 3.1 , the smoothed complexity bound depends logarithmically on ε \varepsilon ε , due to the perturbation inducing strong convexity. Moreover, σ − 2 L \sigma^{-2}L σ − 2 L acts as a condition number, so that the smoothed complexity bound depends on the square root of the condition number.
Numerical Illustration. We use the same weighted Huber objective as for Gradient Descent (§ 3.1 ),
f ( x ) = ∑ i = 1 n 2 10 ( i − n / 2 ) / n ϕ ( x i ) , ϕ ( t ) = { 1 2 t 2 , ∣ t ∣ ≤ 1 , ∣ t ∣ − 1 2 , ∣ t ∣ > 1. f(x)=\sum_{i=1}^{n}2^{10(i-n/2)/n}\phi(x_i),\qquad\phi(t)=\begin{cases}\frac{1}{2}t^2, & |t|\le1,\\ |t|-\frac{1}{2}, & |t|>1.\end{cases} f ( x ) = i = 1 ∑ n 2 10 ( i − n /2 ) / n ϕ ( x i ) , ϕ ( t ) = { 2 1 t 2 , ∣ t ∣ − 2 1 , ∣ t ∣ ≤ 1 , ∣ t ∣ > 1.
The results are shown in Figure 4 . We observe that the theoretical bound and the empirical expectation of the worst-case bound exhibit the same dependencies, up to constants.
Figure 4. Smoothed complexity of Algorithm (N A G \mathrm{NAG} NAG ) under Wishart perturbations.
We additionally consider the degenerate ill-conditioned quadratic from § 3.1 , given by
f ( x ) = 1 2 ∑ i = 1 ⌊ n / 2 ⌋ a i x i 2 , a i = 2 10 ( i − n / 2 ) / n . f(x)=\frac{1}{2}\sum_{i=1}^{\lfloor n/2\rfloor}a_i x_i^2,\qquad a_i=2^{10(i-n/2)/n}. f ( x ) = 2 1 i = 1 ∑ ⌊ n /2 ⌋ a i x i 2 , a i = 2 10 ( i − n /2 ) / n .
The results are shown in Figure 5 . We note that our results correctly predict the dependencies in the shown variables, up to constant factors.
Figure 5. Smoothed complexity of Algorithm (NAG) under Wishart perturbations.
Conjugate Gradient
We next turn to the Conjugate Gradient method Hestenes et al., [21 ] , which exploits the quadratic structure of the objective. Let Q μ L ⊂ F μ L \mathcal{Q}_{\mu}^{L} \subset\mathcal{F}_{\mu}^{L} Q μ L ⊂ F μ L denote the class of μ \mu μ -strongly convex quadratic functions h ( x ) = 1 2 x T A x − b T x + c h(x) = \frac{1}{2}x^{T}Ax - b^{T}x + c h ( x ) = 2 1 x T A x − b T x + c with $0 \preceq \mu I \preceq A \preceq LI$. For h ∈ Q μ L h \in\mathcal{Q}_{\mu}^{L} h ∈ Q μ L , Conjugate Gradient generates, where r k = b − A x k r_k = b - Ax_k r k = b − A x k and p 0 = r 0 p_0 = r_0 p 0 = r 0 , for x 0 ∈ R n x_0 \in\mathbb{R}^{n} x 0 ∈ R n and k ≥ 0 k \ge0 k ≥ 0 ,
α k = r k T r k p k T A p k , x k + 1 = x k + α k p k , r k + 1 = r k − α k A p k , p k + 1 = r k + 1 + r k + 1 T r k + 1 r k T r k p k . \alpha_k = \frac{r_k^{T}r_k}{p_k^{T}Ap_k}, \qquad x_{k+1} = x_k + \alpha_k p_k, \qquad r_{k+1} = r_k - \alpha_k Ap_k, \qquad p_{k+1} = r_{k+1} + \frac{r_{k+1}^{T}r_{k+1}}{r_k^{T}r_k}p_k. α k = p k T A p k r k T r k , x k + 1 = x k + α k p k , r k + 1 = r k − α k A p k , p k + 1 = r k + 1 + r k T r k r k + 1 T r k + 1 p k .
where we terminate on r k = 0 r_k = 0 r k = 0 .
As previously, we measure complexity in terms of relative function value accuracy, namely, for ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) ,
K C G ε ( h ) = min k ≥ 0 { k : h ( x k ) − inf h h ( x 0 ) − inf h ≤ ε } , \mathsf{K}_{\mathrm{CG}}^{\varepsilon}(h) = \min_{k \ge0}\left\{k: \frac{h(x_k)-\inf h}{h(x_0)-\inf h} \le\varepsilon\right\}, K CG ε ( h ) = k ≥ 0 min { k : h ( x 0 ) − inf h h ( x k ) − inf h ≤ ε } ,
where K C G ε ( h ) = 0 \mathsf{K}_{\mathrm{CG}}^{\varepsilon}(h) = 0 K CG ε ( h ) = 0 if h ( x 0 ) = inf h h(x_0) = \inf h h ( x 0 ) = inf h .
We first recall a classic worst-case complexity result (see, for instance, Trefethen and Bau, [50 ] ). The rate corresponds to an accelerated rate, as presented in § 3.3 , in the sense that it depends on κ \sqrt{\kappa} κ rather than κ \kappa κ .
Theorem 3.7 (Worst-Case Complexity of (CG) - Trefethen and Bau [50 ] ). Let h ∈ Q μ L h \in\mathcal{Q}_{\mu}^{L} h ∈ Q μ L with 0 < μ ≤ L < + ∞ 0 < \mu\le L < +\infty 0 < μ ≤ L < + ∞ , and let ( x k ) (x_k) ( x k ) be the iterates of (CG). Then, for κ = L μ \kappa= \frac{L}{\mu} κ = μ L ,
h ( x k ) − inf h h ( x 0 ) − inf h = ∥ x k − x ∗ ∥ ∇ 2 h 2 ∥ x 0 − x ∗ ∥ ∇ 2 h 2 ≤ 4 ( κ − 1 κ + 1 ) 2 k . \frac{h(x_k)-\inf h}{h(x_0)-\inf h} = \frac{\lVert x_k-x_\ast\rVert_{\nabla^{2}h}^{2}}{\lVert x_0-x_\ast\rVert_{\nabla^{2}h}^{2}} \le4\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{2k}. h ( x 0 ) − inf h h ( x k ) − inf h = ∥ x 0 − x ∗ ∥ ∇ 2 h 2 ∥ x k − x ∗ ∥ ∇ 2 h 2 ≤ 4 ( κ + 1 κ − 1 ) 2 k . Therefore, the relative accuracy complexity is bounded by
sup h ∈ Q μ L K C G ε ( h ) ≤ ⌈ κ 2 log 4 ε ⌉ . \sup_{h\in\mathcal{Q}_{\mu}^{L}}\mathsf{K}_{\mathrm{CG}}^{\varepsilon}(h) \le\left\lceil\frac{\sqrt{\kappa}}{2}\log\frac{4}{\varepsilon}\right\rceil. h ∈ Q μ L sup K CG ε ( h ) ≤ ⌈ 2 κ log ε 4 ⌉ .
We now provide a smoothed complexity bound for this method.
Theorem 3.8 (Smoothed Complexity of (CG)). Let 0 < σ , L < + ∞ 0 < \sigma,L < +\infty 0 < σ , L < + ∞ and ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) . We denote by f W f_W f W a perturbation of f f f , parametrized by σ \sigma σ , as defined in Equation (1) . Then, as n → ∞ n \to\infty n → ∞ , the smoothed complexity of Algorithm (CG) over the function class Q 0 L \mathcal{Q}_{0}^{L} Q 0 L is bounded by
sup f ∈ Q 0 L E W [ K C G ε ( f W ) ] ≤ 1 + O d ( ( 1 + σ − 1 L ) log 4 ε ) . \sup_{f\in\mathcal{Q}_{0}^{L}}\mathbb{E}_{W}\left[\mathsf{K}_{\mathrm{CG}}^{\varepsilon}(f_W)\right] \le1 + O_d\left(\left(1+\sigma^{-1}\sqrt{L}\right)\log\frac{4}{\varepsilon}\right). f ∈ Q 0 L sup E W [ K CG ε ( f W ) ] ≤ 1 + O d ( ( 1 + σ − 1 L ) log ε 4 ) .
Proof. Fix any f ∈ Q 0 L f \in\mathcal{Q}^{L}_{0} f ∈ Q 0 L . As for Gradient Descent, it holds that
κ σ = L m + σ 2 s max ( G ) 2 σ 2 s min ( G ) 2 . \kappa_{\sigma} = \frac{Lm+\sigma^{2}s_{\max}(G)^{2}}{\sigma^{2}s_{\min}(G)^{2}}. κ σ = σ 2 s m i n ( G ) 2 L m + σ 2 s m a x ( G ) 2 .
Using the fact that ( a + b ) 1 / 2 ≤ a 1 / 2 + b 1 / 2 (a+b)^{1/2} \le a^{1/2}+b^{1/2} ( a + b ) 1/2 ≤ a 1/2 + b 1/2 , Cauchy-Schwarz and Theorem 2.1 , we obtain
E W [ K C G ε ( f W ) ] ≤ 1 + E W [ ( L m σ 2 s min ( G ) 2 + s max ( G ) 2 s min ( G ) 2 ) 1 / 2 log ( 4 / ε ) 2 ] ≤ 1 + O d ( ( 1 + σ − 1 L ) log 4 ε ) . \mathbb{E}_{W}\left[\mathbb{K}^{\varepsilon}_{\mathrm{CG}}(f_{W})\right] \le1+\mathbb{E}_{W}\left[\left(\frac{Lm}{\sigma^{2}s_{\min}(G)^{2}}+\frac{s_{\max}(G)^{2}}{s_{\min}(G)^{2}}\right)^{1/2}\frac{\log(4/\varepsilon)}{2}\right] \le1+\mathcal{O}_{d}\left(\left(1+\sigma^{-1}\sqrt{L}\right)\log\frac{4}{\varepsilon}\right). E W [ K CG ε ( f W ) ] ≤ 1 + E W [ ( σ 2 s m i n ( G ) 2 L m + s m i n ( G ) 2 s m a x ( G ) 2 ) 1/2 2 log ( 4/ ε ) ] ≤ 1 + O d ( ( 1 + σ − 1 L ) log ε 4 ) .
Remark 3.9. Smoothed analysis of Conjugate Gradient was previously studied in Menon and Trogdon (2016), who study linear systems under random matrix perturbations, or equivalently, quadratic objectives under random quadratic perturbations. Their analysis heavily relies on spectral bounds, whereas ours is derived from moment bounds. This highlights a difference in the motivations: we aim to derive simple bounds directly from moment bounds, applicable across different optimization papers in a unified manner. Although the random matrix ensemble differs, we highlight that our complexity estimate is dimension-free, unlike theirs.
Discussion. We again observe a logarithmic dependency in ε \varepsilon ε , arising due to the perturbation, and a dependency in σ − 1 L \sigma^{-1}\sqrt{L} σ − 1 L , corresponding to the square root of the condition number.
Numerical Illustration. We illustrate Theorem 3.8 on the degenerate convex quadratic
f ( x ) = 1 2 ∑ i = 1 ⌊ n / 2 ⌋ a i x i 2 , a i = 2 10 ( i − n / 2 ) / n . f(x)=\frac{1}{2}\sum_{i=1}^{\lfloor n/2\rfloor}a_i x_i^2,\qquad a_i=2^{10(i-n/2)/n}. f ( x ) = 2 1 i = 1 ∑ ⌊ n /2 ⌋ a i x i 2 , a i = 2 10 ( i − n /2 ) / n .
The positive eigenvalues range from 2 10 ( 1 − n / 2 ) / n 2^{10(1-n/2)/n} 2 10 ( 1 − n /2 ) / n to L = 2 10 ( ⌊ n / 2 ⌋ − n / 2 ) / n L=2^{10(\lfloor n/2\rfloor-n/2)/n} L = 2 10 (⌊ n /2 ⌋ − n /2 ) / n , while the remaining eigenvalues are zero. The results are shown in Figure 6 . The dotted line without markers shows CG applied directly to the unperturbed quadratic. This baseline is independent of σ \sigma σ and d d d . Similarly to the previous section, we observe that the smoothed complexity bound is close to the empirical smoothed complexity of the worst-case bound, but very pessimistic compared to the empirical smoothed complexity of the run algorithm.
Figure 6. Smoothed complexity of Algorithm (CG) under Wishart perturbations.
Cubic Regularized Newton Method
We next turn to the Cubic Regularized Newton Method (CNM) (Nesterov and Polyak [35 ] ) on the class F μ L H ( Δ ) \mathcal{F}^{L_H}_{\mu}(\Delta) F μ L H ( Δ ) of μ \mu μ -strongly convex functions with L H L_H L H -Lipschitz continuous Hessian and initialization bounded by Δ \Delta Δ , with the convention that μ = 0 \mu=0 μ = 0 corresponds to the merely convex bounded-below setting. For h ∈ F μ L H ( Δ ) h \in\mathcal{F}^{L_H}_{\mu}(\Delta) h ∈ F μ L H ( Δ ) , we consider, given x 0 ∈ R n x_0 \in\mathbb{R}^{n} x 0 ∈ R n and k ≥ 0 k \ge0 k ≥ 0 ,
s k ∈ arg min s { m x k ( s ) = h ( x k ) + ∇ h ( x k ) T s + 1 2 s T ∇ 2 h ( x k ) s + L H 6 ∥ s ∥ 3 } , x k + 1 = x k + s k . s_k \in\mathop{\arg\min}_{s}\left\{m_{x_k}(s)=h(x_k)+\nabla h(x_k)^{T}s+\frac{1}{2}s^{T}\nabla^{2}h(x_k)s+\frac{L_H}{6}\lVert s\rVert^{3}\right\},\qquad x_{k+1}=x_k+s_k. s k ∈ arg min s { m x k ( s ) = h ( x k ) + ∇ h ( x k ) T s + 2 1 s T ∇ 2 h ( x k ) s + 6 L H ∥ s ∥ 3 } , x k + 1 = x k + s k .
We now measure complexity in terms of absolute function value accuracy, namely, for ε > 0 \varepsilon>0 ε > 0 ,
K C N M ε ( h ) = min k ≥ 0 { k : h ( x k ) − inf h ≤ ε } . \mathbb{K}^{\varepsilon}_{\mathrm{CNM}}(h)=\min_{k\ge0}\{k:h(x_k)-\inf h\le\varepsilon\}. K CNM ε ( h ) = k ≥ 0 min { k : h ( x k ) − inf h ≤ ε } .
We first recall a worst-case complexity result, combining the slow phase from [35 Theorem 5] with the fast phase from [36 Section 6] . This result is of the classical form C + log log ( 1 / ε ) C+\log\log(1/\varepsilon) C + log log ( 1/ ε ) .
Theorem 3.10 (Worst-Case Complexity for (CNM) - [35 , 36 ] ). Let h ∈ F μ L H ( Δ ) h \in\mathcal{F}_{\mu}^{L_H}(\Delta) h ∈ F μ L H ( Δ ) for 0 < μ , L H < + ∞ 0 < \mu,L_H < +\infty 0 < μ , L H < + ∞ and 0 ≤ Δ < + ∞ 0 \le\Delta< +\infty 0 ≤ Δ < + ∞ , and let ( x k ) (x_k) ( x k ) be the iterates of (CNM). Then, the absolute accuracy complexity is bounded by, for ε > 0 \varepsilon> 0 ε > 0 ,
sup h ∈ F μ L H ( Δ ) K C N M ε ( h ) ≤ K s l o w ( μ , Δ ) + K f a s t ε ( μ ) , \sup_{h\in\mathcal{F}_{\mu}^{L_H}(\Delta)} \mathsf{K}_{\mathrm{CNM}}^{\varepsilon}(h) \le\mathsf{K}_{\mathrm{slow}}(\mu,\Delta)+\mathsf{K}_{\mathrm{fast}}^{\varepsilon}(\mu), h ∈ F μ L H ( Δ ) sup K CNM ε ( h ) ≤ K slow ( μ , Δ ) + K fast ε ( μ ) , where
K s l o w ( μ , Δ ) = ⌈ 6.25 ⋅ 2 3 / 4 ⋅ ( Δ L H 2 μ 3 ) 1 / 4 ⌉ , K f a s t ε ( μ ) = ⌈ log 2 , + log 2 , + ( μ 3 2 L H 2 ε ) ⌉ . \mathsf{K}_{\mathrm{slow}}(\mu,\Delta)=\left\lceil6.25\cdot2^{3/4}\cdot\left(\frac{\Delta L_H^2}{\mu^3}\right)^{1/4}\right\rceil,\qquad
\mathsf{K}_{\mathrm{fast}}^{\varepsilon}(\mu)=\left\lceil\log_{2,+}\log_{2,+}\left(\frac{\mu^3}{2L_H^2\varepsilon}\right)\right\rceil. K slow ( μ , Δ ) = ⌈ 6.25 ⋅ 2 3/4 ⋅ ( μ 3 Δ L H 2 ) 1/4 ⌉ , K fast ε ( μ ) = ⌈ log 2 , + log 2 , + ( 2 L H 2 ε μ 3 ) ⌉ .
Stronger results, although with more complicated dependencies on the variables and more delicate assumptions, exist, and we purposefully do not make use of them here due to the additional complication. We refer the reader to Cartis et al. [5 ] for an initial overview, and to Cartis et al. [7 ] for a comprehensive survey.
As before, the worst-case bound is unbounded in the merely convex setting, whereas the random quadratic regularization makes the bound finite in expectation. This yields the following smoothed complexity guarantee.
Theorem 3.11 (Smoothed Complexity for (CNM)). Let 0 ≤ Δ < + ∞ 0 \le\Delta< +\infty 0 ≤ Δ < + ∞ and 0 < σ , ε , L H < + ∞ 0 < \sigma,\varepsilon,L_H < +\infty 0 < σ , ε , L H < + ∞ . We denote by f W f_W f W a perturbation of f f f , parametrized by σ \sigma σ , as defined in Equation (1) . Then, as n → ∞ n\to\infty n → ∞ , the smoothed complexity of Algorithm (CNM) over the function class F 0 L H ( Δ ) \mathcal{F}_{0}^{L_H}(\Delta) F 0 L H ( Δ ) is bounded by
sup f ∈ F 0 L H ( Δ ) E W [ K C N M ε ( f W ) ] ≤ 2 + O d ( L H 1 / 2 ( σ − 3 / 2 Δ 1 / 4 + D 1 / 2 σ − 1 ) + log 2 ( 1 + log 2 ( 1 + σ 6 L H 2 ε ) ) ) , \sup_{f\in\mathcal{F}_{0}^{L_H}(\Delta)}\mathbb{E}_W\left[\mathsf{K}_{\mathrm{CNM}}^{\varepsilon}(f_W)\right]\le2+O_d\left(L_H^{1/2}\left(\sigma^{-3/2}\Delta^{1/4}+D^{1/2}\sigma^{-1}\right)+\log_2\left(1+\log_2\left(1+\frac{\sigma^6}{L_H^2\varepsilon}\right)\right)\right), f ∈ F 0 L H ( Δ ) sup E W [ K CNM ε ( f W ) ] ≤ 2 + O d ( L H 1/2 ( σ − 3/2 Δ 1/4 + D 1/2 σ − 1 ) + log 2 ( 1 + log 2 ( 1 + L H 2 ε σ 6 ) ) ) , where ∥ x 0 − x ~ ∥ ≤ D \lVert x_0-\widetilde{x}\rVert\le D ∥ x 0 − x ∥ ≤ D .
Proof. Fix any f ∈ F 0 L H ( Δ ) f\in\mathcal{F}_{0}^{L_H}(\Delta) f ∈ F 0 L H ( Δ ) . We consider the fast and slow phases separately:
Slow Phase. Using ( a + b ) 1 / 4 ≤ a 1 / 4 + b 1 / 4 (a+b)^{1/4}\le a^{1/4}+b^{1/4} ( a + b ) 1/4 ≤ a 1/4 + b 1/4 , Equations (2) and (3) , Cauchy-Schwarz and Theorem 2.1 ,
E [ K s l o w ( μ σ , Δ σ ) ] ≤ 1 + E [ 6.25 ⋅ 2 3 / 4 ⋅ ( Δ + σ 2 D 2 s max ( G ) 2 2 m ) 1 / 4 L H 1 / 2 σ − 3 / 2 s min ( G ) − 3 / 2 m 3 / 4 ] \mathbb{E}[\mathsf{K}_{\mathrm{slow}}(\mu_\sigma,\Delta_\sigma)]\le1+\mathbb{E}\left[6.25\cdot2^{3/4}\cdot\left(\Delta+\sigma^2D^2\frac{s_{\max}(G)^2}{2m}\right)^{1/4}L_H^{1/2}\sigma^{-3/2}s_{\min}(G)^{-3/2}m^{3/4}\right] E [ K slow ( μ σ , Δ σ )] ≤ 1 + E [ 6.25 ⋅ 2 3/4 ⋅ ( Δ + σ 2 D 2 2 m s m a x ( G ) 2 ) 1/4 L H 1/2 σ − 3/2 s m i n ( G ) − 3/2 m 3/4 ]
≤ 1 + O ( Δ 1 / 4 L H 1 / 2 σ − 3 / 2 E [ m 3 / 4 s min ( G ) − 3 / 2 ] + σ − 1 D 1 / 2 L H 1 / 2 E [ s max ( G ) 1 / 2 s min ( G ) − 3 / 2 m 1 / 4 ] ) \le1+O\left(\Delta^{1/4}L_H^{1/2}\sigma^{-3/2}\mathbb{E}\left[m^{3/4}s_{\min}(G)^{-3/2}\right]+\sigma^{-1}D^{1/2}L_H^{1/2}\mathbb{E}\left[\frac{s_{\max}(G)^{1/2}s_{\min}(G)^{-3/2}}{m^{1/4}}\right]\right) ≤ 1 + O ( Δ 1/4 L H 1/2 σ − 3/2 E [ m 3/4 s m i n ( G ) − 3/2 ] + σ − 1 D 1/2 L H 1/2 E [ m 1/4 s m a x ( G ) 1/2 s m i n ( G ) − 3/2 ] )
≤ 1 + O d ( Δ 1 / 4 L H 1 / 2 σ − 3 / 2 + σ − 1 D 1 / 2 L H 1 / 2 ) . \le1+O_d\left(\Delta^{1/4}L_H^{1/2}\sigma^{-3/2}+\sigma^{-1}D^{1/2}L_H^{1/2}\right). ≤ 1 + O d ( Δ 1/4 L H 1/2 σ − 3/2 + σ − 1 D 1/2 L H 1/2 ) .
E [ K f a s t ε ( μ σ ) ] ≤ 1 + E [ log 2 ( 1 + log 2 ( 1 + σ 6 s min ( G ) 6 2 L H 2 ε m 3 ) ) ] ≤ 1 + log 2 ( 1 + log 2 ( 1 + σ 6 2 L H 2 ε E [ s max ( G ) 6 m 3 ] ) ) . \mathbb{E}[\mathsf{K}_{\mathrm{fast}}^{\varepsilon}(\mu_\sigma)]\le1+\mathbb{E}\left[\log_2\left(1+\log_2\left(1+\frac{\sigma^6s_{\min}(G)^6}{2L_H^2\varepsilon m^3}\right)\right)\right]\le1+\log_2\left(1+\log_2\left(1+\frac{\sigma^6}{2L_H^2\varepsilon}\mathbb{E}\left[\frac{s_{\max}(G)^6}{m^3}\right]\right)\right). E [ K fast ε ( μ σ )] ≤ 1 + E [ log 2 ( 1 + log 2 ( 1 + 2 L H 2 ε m 3 σ 6 s m i n ( G ) 6 ) ) ] ≤ 1 + log 2 ( 1 + log 2 ( 1 + 2 L H 2 ε σ 6 E [ m 3 s m a x ( G ) 6 ] ) ) .
We conclude by Theorem 2.1 . □
Discussion. We observe that the smoothed complexity bound takes the form C σ + log log ( 1 / ε ) C_\sigma+\log\log(1/\varepsilon) C σ + log log ( 1/ ε ) , where the constant C σ C_\sigma C σ absorbs L H L_H L H , Δ \Delta Δ , D D D , σ \sigma σ , with C σ C_\sigma C σ acting like σ − 3 / 2 \sigma^{-3/2} σ − 3/2 . The quadratic phase is only valid for ε \varepsilon ε sufficiently small.
Numerical Illustration. We illustrate Theorem 3.11 on the logistic regression objective, for r ≥ 2 r\ge2 r ≥ 2 ,
f ( x ) = 1 r ∑ i = 1 r ( log ( 1 + e b i T x ) − 3 4 b i T x ) . f(x)=\frac{1}{r}\sum_{i=1}^{r}\left(\log\left(1+e^{b_i^{T}x}\right)-\frac{3}{4}b_i^{T}x\right). f ( x ) = r 1 i = 1 ∑ r ( log ( 1 + e b i T x ) − 4 3 b i T x ) .
This is the mean binary logistic loss for 4 r 4r 4 r observations, where each feature vector b i b_i b i occurs four times, with three labels equal to one and one equal to zero. We define B = ( b 1 , … , b r ) T = diag ( s i ) Q T B=(b_1,\ldots,b_r)^T=\operatorname{diag}(s_i)Q^T B = ( b 1 , … , b r ) T = diag ( s i ) Q T , where Q ∈ R n × r Q\in\mathbb{R}^{n\times r} Q ∈ R n × r has orthonormal columns obtained through a QR factorization of a standard Gaussian matrix, and s i = 2 3 ( i − 1 ) r − 1 − 2 s_i = 2^{\frac{3(i-1)}{r-1}-2} s i = 2 r − 1 3 ( i − 1 ) − 2 . A minimizer and minimal value is given by
x ∗ = Q diag ( s i − 1 ) log 3 ⋅ 1 and min f = − 3 4 log 3 4 − 1 4 log 1 4 . x_\ast= Q\operatorname{diag}(s_i^{-1})\log3 \cdot\mathbf{1}
\quad\text{and}\quad
\min f = -\frac{3}{4}\log\frac{3}{4}-\frac{1}{4}\log\frac{1}{4}. x ∗ = Q diag ( s i − 1 ) log 3 ⋅ 1 and min f = − 4 3 log 4 3 − 4 1 log 4 1 .
We easily see ∇ 2 f \nabla^2 f ∇ 2 f is positive semidefinite and rank-deficient, making f f f convex but not strongly convex. Moreover, we note that f f f is L G L_G L G -smooth and has L H L_H L H -Lipschitz Hessian, for
L G = 1 r and L H = 4 3 3 r . L_G = \frac{1}{r}
\quad\text{and}\quad
L_H = \frac{4}{3\sqrt{3}r}. L G = r 1 and L H = 3 3 r 4 .
The results are shown in Figure 7 . We note that, unlike in previous experiments, the Lipschitz constants L G L_G L G and L H L_H L H depend on the dimension of the problem n = 4 r n = 4r n = 4 r , and therefore the curves are not constant in n n n , although the upper bounds are dimension-independent. The dependency in d d d is pessimistic but with the correct trends, and the dependency in σ \sigma σ matches up to constants.
Figure 7. Smoothed complexity of Algorithm (CNM) under Wishart perturbations.
Cubic Regularized Newton Method under Radial Monotonicity
We now consider Algorithm (CNM) beyond convexity, as in § 3.2 . We denote by F P L , η L H ( Δ ) F_{\mathrm{PL},\eta}^{L_H}(\Delta) F PL , η L H ( Δ ) the class of twice continuously differentiable functions with L H L_H L H -Lipschitz continuous Hessian, bounded below, satisfying gradient domination with parameter η \eta η , and with initialization bounded by h ( x 0 ) − min h ≤ Δ h(x_0) - \min h \le\Delta h ( x 0 ) − min h ≤ Δ . We use the absolute function value accuracy complexity K C N M ε ( h ) K_{\mathrm{CNM}}^\varepsilon(h) K CNM ε ( h ) , as in § 3.5 . As for Gradient Descent, gradient domination is sufficient to retain linear convergence beyond convexity. This is formalized through the result of (Nesterov and Polyak, [35 ] , Theorem 7).
Theorem 3.12 (Worst-Case Complexity of (CNM) under Gradient Domination - Nesterov and Polyak [35 ] ). Let h ∈ F P L , η L H ( Δ ) h \in F_{\mathrm{PL},\eta}^{L_H}(\Delta) h ∈ F PL , η L H ( Δ ) with 0 < η , L H < + ∞ 0 < \eta, L_H < +\infty 0 < η , L H < + ∞ and 0 ≤ Δ < + ∞ 0 \le\Delta< +\infty 0 ≤ Δ < + ∞ , and let ( x k ) (x_k) ( x k ) be the iterates of (CNM). Then, the absolute function value accuracy complexity, for every ε > 0 \varepsilon> 0 ε > 0 , is bounded by
sup h ∈ F P L , η L H ( Δ ) K C N M ε ( h ) ≤ K s l o w ( η , Δ ) + K f a s t ε ( η ) , \sup_{h \in F_{\mathrm{PL},\eta}^{L_H}(\Delta)} K_{\mathrm{CNM}}^\varepsilon(h) \le K_{\mathrm{slow}}(\eta,\Delta) + K_{\mathrm{fast}}^\varepsilon(\eta), h ∈ F PL , η L H ( Δ ) sup K CNM ε ( h ) ≤ K slow ( η , Δ ) + K fast ε ( η ) , where
K s l o w ( η , Δ ) = ⌈ 8 ( Δ ω ) 1 / 4 ⌉ , K f a s t ε ( η ) = ⌈ log 4 / 3 , + log 2 , + ( ω ε ) ⌉ and ω = η 3 2592 L H 2 . K_{\mathrm{slow}}(\eta,\Delta) = \left\lceil8\left(\frac{\Delta}{\omega}\right)^{1/4}\right\rceil,\qquad
K_{\mathrm{fast}}^\varepsilon(\eta) = \left\lceil\log_{4/3,+}\log_{2,+}\left(\frac{\omega}{\varepsilon}\right)\right\rceil
\quad\text{and}\quad
\omega= \frac{\eta^3}{2592L_H^2}. K slow ( η , Δ ) = ⌈ 8 ( ω Δ ) 1/4 ⌉ , K fast ε ( η ) = ⌈ log 4/3 , + log 2 , + ( ε ω ) ⌉ and ω = 2592 L H 2 η 3 .
We denote by F r a d L G , L H ( Δ , D ; x ~ ) F_{\mathrm{rad}}^{L_G,L_H}(\Delta,D;\tilde{x}) F rad L G , L H ( Δ , D ; x ~ ) the subclass of F r a d L G ( x ~ ) F_{\mathrm{rad}}^{L_G}(\tilde{x}) F rad L G ( x ~ ) from § 3.2 that is also twice continuously differentiable with L H L_H L H -Lipschitz Hessian and bounded initialization f ( x 0 ) − min f ≤ Δ f(x_0) - \min f \le\Delta f ( x 0 ) − min f ≤ Δ and ∥ x 0 − x ~ ∥ ≤ D \lVert x_0 - \tilde{x}\rVert\le D ∥ x 0 − x ~ ∥ ≤ D . The quadratic perturbation preserves the Lipschitz constant of the Hessian L H L_H L H , and the arguments in § 3.2 yield
μ σ = σ 2 λ min ( W ) , L G , σ = L G + σ 2 λ max ( W ) , η σ = μ σ 2 L G , σ . (4) \mu_\sigma= \sigma^2\lambda_{\min}(W),\qquad
L_{G,\sigma} = L_G + \sigma^2\lambda_{\max}(W),\qquad
\eta_\sigma= \frac{\mu_\sigma^2}{L_{G,\sigma}}. \tag*{(4)} μ σ = σ 2 λ m i n ( W ) , L G , σ = L G + σ 2 λ m a x ( W ) , η σ = L G , σ μ σ 2 . (4)
In particular, f W ∈ F P L , η σ L H ( Δ σ ) f_W \in\mathcal{F}_{\mathrm{PL},\eta\sigma}^{L_H}(\Delta_\sigma) f W ∈ F PL , η σ L H ( Δ σ ) . This allows us to establish the following smoothed complexity guarantee.
Theorem 3.13 (Smoothed Complexity of (CNM) under Radial Monotonicity). Let 0 ≤ Δ , D < + ∞ 0 \le\Delta, D < +\infty 0 ≤ Δ , D < + ∞ , 0 < σ , L G , L H , ε < + ∞ 0 < \sigma, L_G, L_H, \varepsilon< +\infty 0 < σ , L G , L H , ε < + ∞ and x ~ ∈ R n \tilde{x} \in\mathbb{R}^n x ~ ∈ R n . We denote by f W f_W f W a perturbation of f f f , parametrized by σ \sigma σ , as defined in Equation (1) . Then, as n → ∞ n \to\infty n → ∞ , the smoothed complexity of Algorithm (CNM) over the function class F r a d L G , L H ( Δ , D ; x ~ ) \mathcal{F}_{\mathrm{rad}}^{L_G,L_H}(\Delta,D;\tilde{x}) F rad L G , L H ( Δ , D ; x ~ ) is bounded by
sup f ∈ F r a d L G , L H ( Δ , D ; x ~ ) E W [ K C N M ε ( f W ) ] ≤ 2 + O d ( L H 1 / 2 ( 1 + σ − 2 L G ) 3 / 4 ( σ − 3 / 2 Δ 1 / 4 + σ − 1 D 1 / 2 ) + log 4 / 3 ( 1 + log 2 ( 1 + σ 6 L H 2 ε ) ) ) . \sup_{f \in\mathcal{F}_{\mathrm{rad}}^{L_G,L_H}(\Delta,D;\tilde{x})} \mathbb{E}_W[\mathcal{K}_{\mathrm{CNM}}^\varepsilon(f_W)] \le2 + \mathcal{O}_d\left(L_H^{1/2}(1+\sigma^{-2}L_G)^{3/4}(\sigma^{-3/2}\Delta^{1/4}+\sigma^{-1}D^{1/2}) + \log_{4/3}\left(1+\log_2\left(1+\frac{\sigma^6}{L_H^2\varepsilon}\right)\right)\right). f ∈ F rad L G , L H ( Δ , D ; x ~ ) sup E W [ K CNM ε ( f W )] ≤ 2 + O d ( L H 1/2 ( 1 + σ − 2 L G ) 3/4 ( σ − 3/2 Δ 1/4 + σ − 1 D 1/2 ) + log 4/3 ( 1 + log 2 ( 1 + L H 2 ε σ 6 ) ) ) .
Proof. Fix any f ∈ F r a d L G , L H ( Δ , D ; x ~ ) f \in\mathcal{F}_{\mathrm{rad}}^{L_G,L_H}(\Delta,D;\tilde{x}) f ∈ F rad L G , L H ( Δ , D ; x ~ ) . We consider the slow and the fast phase separately.
E [ K s l o w ( η σ , Δ σ ) ] ≤ 1 + E W [ 8 ( Δ σ ω σ ) 1 / 4 ] = 1 + O d ( E W [ Δ σ 1 / 4 η σ − 3 / 4 L H 1 / 2 ] ) = 1 + O d ( E W [ Δ σ 1 / 4 μ σ − 3 / 2 L G , σ 3 / 4 L H 1 / 2 ] ) . \mathbb{E}[\mathcal{K}_{\mathrm{slow}}(\eta_\sigma,\Delta_\sigma)] \le1+\mathbb{E}_W\left[8\left(\frac{\Delta_\sigma}{\omega_\sigma}\right)^{1/4}\right] = 1+\mathcal{O}_d\left(\mathbb{E}_W\left[\Delta_\sigma^{1/4}\eta_\sigma^{-3/4}L_H^{1/2}\right]\right) = 1+\mathcal{O}_d\left(\mathbb{E}_W\left[\Delta_\sigma^{1/4}\mu_\sigma^{-3/2}L_{G,\sigma}^{3/4}L_H^{1/2}\right]\right). E [ K slow ( η σ , Δ σ )] ≤ 1 + E W [ 8 ( ω σ Δ σ ) 1/4 ] = 1 + O d ( E W [ Δ σ 1/4 η σ − 3/4 L H 1/2 ] ) = 1 + O d ( E W [ Δ σ 1/4 μ σ − 3/2 L G , σ 3/4 L H 1/2 ] ) .
Using subadditivity of powers < 1 <1 < 1 , we get
E [ K s l o w ( η σ , Δ σ ) ] ≤ 1 + O d ( E W [ ( Δ + σ 2 D 2 λ max ( W ) ) 1 / 4 σ − 3 λ min ( W ) − 3 / 2 ( L G + σ 2 λ max ( W ) ) 3 / 4 L H 1 / 2 ] ) \mathbb{E}[\mathcal{K}_{\mathrm{slow}}(\eta_\sigma,\Delta_\sigma)] \le1+\mathcal{O}_d\left(\mathbb{E}_W\left[(\Delta+\sigma^2D^2\lambda_{\max}(W))^{1/4}\sigma^{-3}\lambda_{\min}(W)^{-3/2}(L_G+\sigma^2\lambda_{\max}(W))^{3/4}L_H^{1/2}\right]\right) E [ K slow ( η σ , Δ σ )] ≤ 1 + O d ( E W [ ( Δ + σ 2 D 2 λ m a x ( W ) ) 1/4 σ − 3 λ m i n ( W ) − 3/2 ( L G + σ 2 λ m a x ( W ) ) 3/4 L H 1/2 ] )
≤ 1 + O d ( E W [ σ − 3 / 2 Δ 1 / 4 + σ − 1 D 1 / 2 λ max ( W ) 1 / 4 λ min ( W ) 3 / 4 ( σ − 2 L G + λ max ( W ) ) 3 / 4 λ min ( W ) 3 / 4 L H 1 / 2 ] ) . \le1+\mathcal{O}_d\left(\mathbb{E}_W\left[\frac{\sigma^{-3/2}\Delta^{1/4}+\sigma^{-1}D^{1/2}\lambda_{\max}(W)^{1/4}}{\lambda_{\min}(W)^{3/4}}\frac{(\sigma^{-2}L_G+\lambda_{\max}(W))^{3/4}}{\lambda_{\min}(W)^{3/4}}L_H^{1/2}\right]\right). ≤ 1 + O d ( E W [ λ m i n ( W ) 3/4 σ − 3/2 Δ 1/4 + σ − 1 D 1/2 λ m a x ( W ) 1/4 λ m i n ( W ) 3/4 ( σ − 2 L G + λ m a x ( W ) ) 3/4 L H 1/2 ] ) .
We conclude by Cauchy-Schwarz and Theorem 2.1 .
E [ K f a s t ε ( η σ ) ] ≤ 1 + E [ log 4 / 3 ( 1 + log 2 ( 1 + ω σ ε ) ) ] ≤ 1 + log 4 / 3 ( 1 + log 2 ( 1 + E [ ω σ ] ε ) ) . \mathbb{E}[\mathcal{K}_{\mathrm{fast}}^\varepsilon(\eta_\sigma)] \le1+\mathbb{E}\left[\log_{4/3}\left(1+\log_2\left(1+\frac{\omega_\sigma}{\varepsilon}\right)\right)\right] \le1+\log_{4/3}\left(1+\log_2\left(1+\frac{\mathbb{E}[\omega_\sigma]}{\varepsilon}\right)\right). E [ K fast ε ( η σ )] ≤ 1 + E [ log 4/3 ( 1 + log 2 ( 1 + ε ω σ ) ) ] ≤ 1 + log 4/3 ( 1 + log 2 ( 1 + ε E [ ω σ ] ) ) .
Since
E [ ω σ ] = O d ( E [ η σ 3 L H 2 ] ) = O d ( L H − 2 E [ μ σ 6 L G , σ − 3 ] ) = O d ( L H − 2 E [ σ 12 λ min ( W ) 6 ( L G + σ 2 λ max ( W ) ) 3 ] ) , \mathbb{E}[\omega_\sigma] = \mathcal{O}_d\left(\mathbb{E}\left[\frac{\eta_\sigma^3}{L_H^2}\right]\right) = \mathcal{O}_d\left(L_H^{-2}\mathbb{E}\left[\mu_\sigma^6L_{G,\sigma}^{-3}\right]\right) = \mathcal{O}_d\left(L_H^{-2}\mathbb{E}\left[\frac{\sigma^{12}\lambda_{\min}(W)^6}{(L_G+\sigma^2\lambda_{\max}(W))^3}\right]\right), E [ ω σ ] = O d ( E [ L H 2 η σ 3 ] ) = O d ( L H − 2 E [ μ σ 6 L G , σ − 3 ] ) = O d ( L H − 2 E [ ( L G + σ 2 λ m a x ( W ) ) 3 σ 12 λ m i n ( W ) 6 ] ) ,
which implies
E [ ω σ ] ≤ O d ( L H − 2 σ 6 E [ λ min ( W ) 6 λ max ( W ) 3 ] ) ≤ O d ( L H − 2 σ 6 E [ λ max ( W ) 3 ] ) = O d ( σ 6 L H 2 ) , \mathbb{E}[\omega_\sigma] \le\mathcal{O}_d\left(L_H^{-2}\sigma^6\mathbb{E}\left[\frac{\lambda_{\min}(W)^6}{\lambda_{\max}(W)^3}\right]\right) \le\mathcal{O}_d\left(L_H^{-2}\sigma^6\mathbb{E}\left[\lambda_{\max}(W)^3\right]\right) = \mathcal{O}_d\left(\frac{\sigma^6}{L_H^2}\right), E [ ω σ ] ≤ O d ( L H − 2 σ 6 E [ λ m a x ( W ) 3 λ m i n ( W ) 6 ] ) ≤ O d ( L H − 2 σ 6 E [ λ m a x ( W ) 3 ] ) = O d ( L H 2 σ 6 ) ,
we get the wanted bound. □ \square □
Discussion. Theorem 3.13 is very closely related to Theorem 3.11, whose upper bound only differs in a factor ( 1 + σ − 2 L G ) 3 / 4 (1+\sigma^{-2}L_G)^{3/4} ( 1 + σ − 2 L G ) 3/4 . This is comparable to the PL extension of Theorem 3.2, provided in Theorem 3.4, which also only differed in one additional factor.
Numerical Illustration. We consider the same radially monotone function as in § 3.2 , namely
f ( x ) = ∑ i = 1 n ( 1 − e − x i 2 / 2 ) , x ~ = 0. f(x)=\sum_{i=1}^{n}\left(1-e^{-x_i^2/2}\right), \qquad\tilde{x}=0. f ( x ) = i = 1 ∑ n ( 1 − e − x i 2 /2 ) , x ~ = 0.
The results are shown in Figure 8 . As in § 3.2 , we observe that the PL extension of our result is less tight in the dependencies than the convex counterpart. However, we still observe similar dependencies in all plotted variables. We note that the theoretical upper bounds are worse than the ones presented in § 3.2 by a constant factor.
Figure 8. Smoothed complexity of Algorithm (CNM) under Wishart perturbations.
Hybrid Gradient–Cubic Newton Method
We combine Gradient Descent and the Cubic Regularized Newton Method on the class F μ L G , L H ( Δ ) \mathcal{F}_{\mu}^{L_G,L_H}(\Delta) F μ L G , L H ( Δ ) of bounded-below μ \mu μ -strongly convex, L G L_G L G -smooth functions with L H L_H L H -Lipschitz continuous Hessian and initializations bounded by h ( x 0 ) − inf h ≤ Δ h(x_0)-\inf h\leq\Delta h ( x 0 ) − inf h ≤ Δ . For h ∈ F μ L G , L H ( Δ ) h\in\mathcal{F}_{\mu}^{L_G,L_H}(\Delta) h ∈ F μ L G , L H ( Δ ) , we run Algorithm (GD) with step-size 1 / L G 1/L_G 1/ L G until
∥ ∇ h ( x k ) ∥ 2 ≤ μ 4 2 L H 2 . \lVert\nabla h(x_k)\rVert^2\leq\frac{\mu^4}{2L_H^2}. ∥ ∇ h ( x k ) ∥ 2 ≤ 2 L H 2 μ 4 .
after which we run Algorithm (CNM). By strong convexity, the switching criterion implies h ( x k ) − min h ≤ μ 3 4 L H 2 h(x_k)-\min h\leq\frac{\mu^3}{4L_H^2} h ( x k ) − min h ≤ 4 L H 2 μ 3 , so that the method enters the fast phase of Theorem 3.10 . We still measure complexity in terms of absolute function value accuracy, namely
K H y b ε ( h ) = min k ≥ 0 { k : h ( x k ) − inf h ≤ ε } . \mathbb{K}_{\mathrm{Hyb}}^\varepsilon(h)=\min_{k\geq0}\{k:h(x_k)-\inf h\leq\varepsilon\}. K Hyb ε ( h ) = k ≥ 0 min { k : h ( x k ) − inf h ≤ ε } .
This improves the rate of the previous section to a rate of the form log ( C ) + log log ( 1 / ε ) \log(C)+\log\log(1/\varepsilon) log ( C ) + log log ( 1/ ε ) .
Theorem 3.14 (Worst-Case Complexity of Hybrid Method). Let h ∈ F μ L G , L H ( Δ ) h\in\mathcal{F}_{\mu}^{L_G,L_H}(\Delta) h ∈ F μ L G , L H ( Δ ) with 0 < μ ≤ L G < + ∞ 0<\mu\leq L_G<+\infty 0 < μ ≤ L G < + ∞ , 0 < L H < + ∞ 0<L_H<+\infty 0 < L H < + ∞ , 0 ≤ Δ < + ∞ 0\leq\Delta<+\infty 0 ≤ Δ < + ∞ . Then, the absolute accuracy complexity is bounded by, for ε > 0 \varepsilon>0 ε > 0 ,
sup h ∈ F μ L G , L H ( Δ ) K H y b ε ( h ) ≤ K s l o w ( μ , L G , Δ ) + K f a s t ε ( μ ) , \sup_{h\in\mathcal{F}_{\mu}^{L_G,L_H}(\Delta)}\mathbb{K}_{\mathrm{Hyb}}^\varepsilon(h)\leq\mathbb{K}_{\mathrm{slow}}(\mu,L_G,\Delta)+\mathbb{K}_{\mathrm{fast}}^\varepsilon(\mu), h ∈ F μ L G , L H ( Δ ) sup K Hyb ε ( h ) ≤ K slow ( μ , L G , Δ ) + K fast ε ( μ ) , where
K s l o w ( μ , L G , Δ ) = ⌈ L G μ log + 4 L G L H 2 Δ μ 4 ⌉ , K f a s t ε ( μ ) = ⌈ log 2 , + log 2 , + μ 3 2 L H 2 ε ⌉ . \mathbb{K}_{\mathrm{slow}}(\mu,L_G,\Delta)=\left\lceil\frac{L_G}{\mu}\log_+\frac{4L_GL_H^2\Delta}{\mu^4}\right\rceil,\qquad
\mathbb{K}_{\mathrm{fast}}^\varepsilon(\mu)=\left\lceil\log_{2,+}\log_{2,+}\frac{\mu^3}{2L_H^2\varepsilon}\right\rceil. K slow ( μ , L G , Δ ) = ⌈ μ L G log + μ 4 4 L G L H 2 Δ ⌉ , K fast ε ( μ ) = ⌈ log 2 , + log 2 , + 2 L H 2 ε μ 3 ⌉ .
Proof. Let κ = L G / μ \kappa=L_G/\mu κ = L G / μ . By L G L_G L G -smoothness, ∥ ∇ h ( x k ) ∥ 2 ≤ 2 L G ( h ( x k ) − min h ) \lVert\nabla h(x_k)\rVert^2\leq2L_G(h(x_k)-\min h) ∥ ∇ h ( x k ) ∥ 2 ≤ 2 L G ( h ( x k ) − min h ) , so the switching criterion is guaranteed once
h ( x k ) − inf h h ( x 0 ) − inf h ≤ μ 3 4 κ L H 2 Δ . \frac{h(x_k)-\inf h}{h(x_0)-\inf h}\leq\frac{\mu^3}{4\kappa L_H^2\Delta}. h ( x 0 ) − inf h h ( x k ) − inf h ≤ 4 κ L H 2 Δ μ 3 .
Theorem 3.1 shows that this takes at most
K s l o w ( μ , L G , Δ ) = ⌈ κ log + 4 κ L H 2 Δ μ 3 ⌉ = ⌈ L G μ log + 4 L G L H 2 Δ μ 4 ⌉ . \mathbb{K}_{\mathrm{slow}}(\mu,L_G,\Delta)=\left\lceil\kappa\log_+\frac{4\kappa L_H^2\Delta}{\mu^3}\right\rceil=\left\lceil\frac{L_G}{\mu}\log_+\frac{4L_GL_H^2\Delta}{\mu^4}\right\rceil. K slow ( μ , L G , Δ ) = ⌈ κ log + μ 3 4 κ L H 2 Δ ⌉ = ⌈ μ L G log + μ 4 4 L G L H 2 Δ ⌉ .
iterations. Once the switching criterion holds, strong convexity gives h ( x k ) − min h ≤ μ 3 4 L H 2 h(x_k)-\min h\leq\frac{\mu^3}{4L_H^2} h ( x k ) − min h ≤ 4 L H 2 μ 3 . The fast phase therefore follows from Theorem 3.10 . □
Theorem 3.15 (Smoothed Complexity of Hybrid Method). Let 0 ≤ Δ < + ∞ 0\leq\Delta<+\infty 0 ≤ Δ < + ∞ and 0 < σ , ε , L G , L H < + ∞ 0<\sigma,\varepsilon,L_G,L_H<+\infty 0 < σ , ε , L G , L H < + ∞ . We denote by f W f_W f W a perturbation of f f f , parametrized by σ \sigma σ , as
defined in Equation (1) . Then, as n → ∞ n \to\infty n → ∞ , the smoothed complexity of the hybrid algorithm over the function class F 0 L G , L H ( Δ , D ) \mathcal{F}^{L_G,L_H}_0(\Delta,D) F 0 L G , L H ( Δ , D ) is bounded by
sup f ∈ F 0 L G , L H ( Δ ) E W [ K H y b ε ( f W ) ] ≤ 2 + O d ( ( 1 + σ − 2 L G ) log ( 2 + L H 2 ( 1 + σ − 2 L G ) ( Δ σ − 6 + D 2 σ − 4 ) ) + log 2 ( 1 + log 2 ( 1 + σ 6 L H 2 ε ) ) ) \sup_{f \in\mathcal{F}^{L_G,L_H}_0(\Delta)} \mathbb{E}_W[\mathbb{K}^{\varepsilon}_{\mathrm{Hyb}}(f_W)] \le2 + \mathcal{O}_d\left((1+\sigma^{-2}L_G)\log\left(2+L_H^2(1+\sigma^{-2}L_G)(\Delta\sigma^{-6}+D^2\sigma^{-4})\right)
+ \log_2\left(1+\log_2\left(1+\frac{\sigma^6}{L_H^2\varepsilon}\right)\right)\right) f ∈ F 0 L G , L H ( Δ ) sup E W [ K Hyb ε ( f W )] ≤ 2 + O d ( ( 1 + σ − 2 L G ) log ( 2 + L H 2 ( 1 + σ − 2 L G ) ( Δ σ − 6 + D 2 σ − 4 ) ) + log 2 ( 1 + log 2 ( 1 + L H 2 ε σ 6 ) ) )
where ∥ x 0 − x ~ ∥ ≤ D \lVert x_0-\widetilde{x}\rVert\le D ∥ x 0 − x ∥ ≤ D .
Proof. Fix any f ∈ F 0 L G , L H ( Δ , D ) f \in\mathcal{F}^{L_G,L_H}_0(\Delta,D) f ∈ F 0 L G , L H ( Δ , D ) . We consider the slow and fast phases separately:
E [ K s l o w , σ ] ≤ 1 + E [ κ σ log ( 1 + 2 κ σ L H 2 m 2 ( 2 m Δ + σ 2 D 2 s max ( G ) 2 ) σ 6 s min ( G ) 6 ) ] = 1 + E [ κ σ log ( 1 + 2 A σ ) ] . \mathbb{E}[\mathbb{K}_{\mathrm{slow},\sigma}] \le1+\mathbb{E}\left[\kappa_\sigma\log\left(1+\frac{2\kappa_\sigma L_H^2m^2(2m\Delta+\sigma^2D^2s_{\max}(G)^2)}{\sigma^6s_{\min}(G)^6}\right)\right]=1+\mathbb{E}[\kappa_\sigma\log(1+2A_\sigma)]. E [ K slow , σ ] ≤ 1 + E [ κ σ log ( 1 + σ 6 s m i n ( G ) 6 2 κ σ L H 2 m 2 ( 2 m Δ + σ 2 D 2 s m a x ( G ) 2 ) ) ] = 1 + E [ κ σ log ( 1 + 2 A σ )] .
where
A σ = κ σ L H 2 m 2 ( 2 m Δ + σ 2 D 2 s max ( G ) 2 ) σ 6 s min ( G ) 6 . A_\sigma=\frac{\kappa_\sigma L_H^2m^2(2m\Delta+\sigma^2D^2s_{\max}(G)^2)}{\sigma^6s_{\min}(G)^6}. A σ = σ 6 s m i n ( G ) 6 κ σ L H 2 m 2 ( 2 m Δ + σ 2 D 2 s m a x ( G ) 2 ) .
Here we used log + ( x ) ≤ log ( 1 + x ) \log_+(x)\le\log(1+x) log + ( x ) ≤ log ( 1 + x ) . Since log ( 1 + 2 x ) ≤ log ( 1 + α ) + x α \log(1+2x)\le\log(1+\alpha)+\frac{x}{\alpha} log ( 1 + 2 x ) ≤ log ( 1 + α ) + α x for any α > 0 \alpha>0 α > 0 , setting α = E [ A σ 2 ] \alpha=\sqrt{\mathbb{E}[A_\sigma^2]} α = E [ A σ 2 ] yields
E [ K s l o w , σ ] ≤ 1 + E [ κ σ ] log ( 1 + E [ A σ 2 ] ) + E [ κ σ A σ ] E [ A σ 2 ] . \mathbb{E}[\mathbb{K}_{\mathrm{slow},\sigma}] \le1+\mathbb{E}[\kappa_\sigma]\log(1+\sqrt{\mathbb{E}[A_\sigma^2]})+\frac{\mathbb{E}[\kappa_\sigma A_\sigma]}{\sqrt{\mathbb{E}[A_\sigma^2]}}. E [ K slow , σ ] ≤ 1 + E [ κ σ ] log ( 1 + E [ A σ 2 ] ) + E [ A σ 2 ] E [ κ σ A σ ] .
By Cauchy-Schwarz,
E [ K s l o w , σ ] ≤ 1 + E [ κ σ 2 ] ( log ( 1 + E [ A σ 2 ] ) + 1 ) . \mathbb{E}[\mathbb{K}_{\mathrm{slow},\sigma}] \le1+\sqrt{\mathbb{E}[\kappa_\sigma^2]}\left(\log(1+\sqrt{\mathbb{E}[A_\sigma^2]})+1\right). E [ K slow , σ ] ≤ 1 + E [ κ σ 2 ] ( log ( 1 + E [ A σ 2 ] ) + 1 ) .
It holds that
E W [ κ σ 2 ] ≤ 2 L G 2 σ − 4 E W [ m 2 s min ( G ) 4 ] + 2 E W [ s max ( G ) 4 s min ( G ) 4 ] ≤ O d ( 1 + σ − 4 L G 2 ) , \mathbb{E}_W[\kappa_\sigma^2]\le2L_G^2\sigma^{-4}\mathbb{E}_W\left[\frac{m^2}{s_{\min}(G)^4}\right]+2\mathbb{E}_W\left[\frac{s_{\max}(G)^4}{s_{\min}(G)^4}\right]\le\mathcal{O}_d(1+\sigma^{-4}L_G^2), E W [ κ σ 2 ] ≤ 2 L G 2 σ − 4 E W [ s m i n ( G ) 4 m 2 ] + 2 E W [ s m i n ( G ) 4 s m a x ( G ) 4 ] ≤ O d ( 1 + σ − 4 L G 2 ) ,
and, since
A σ = L H 2 m 2 ( L G m + σ 2 s max ( G ) 2 ) ( 2 m Δ + σ 2 D 2 s max ( G ) 2 ) σ 8 s min ( G ) 8 = L H 2 ( 2 m 4 L G Δ σ 8 s min ( G ) 8 + 2 m 3 Δ s max ( G ) 2 σ 6 s min ( G ) 8 + L G m 3 D 2 s max ( G ) 2 σ 6 s min ( G ) 8 + m 2 s max ( G ) 4 D 2 σ 4 s min ( G ) 8 ) , \begin{aligned}
A_\sigma=L_H^2\frac{m^2(L_Gm+\sigma^2s_{\max}(G)^2)(2m\Delta+\sigma^2D^2s_{\max}(G)^2)}{\sigma^8s_{\min}(G)^8} \\
&=L_H^2\left(\frac{2m^4L_G\Delta}{\sigma^8s_{\min}(G)^8}+\frac{2m^3\Delta s_{\max}(G)^2}{\sigma^6s_{\min}(G)^8}+\frac{L_Gm^3D^2s_{\max}(G)^2}{\sigma^6s_{\min}(G)^8}+\frac{m^2s_{\max}(G)^4D^2}{\sigma^4s_{\min}(G)^8}\right),
\end{aligned} A σ = L H 2 σ 8 s m i n ( G ) 8 m 2 ( L G m + σ 2 s m a x ( G ) 2 ) ( 2 m Δ + σ 2 D 2 s m a x ( G ) 2 ) = L H 2 ( σ 8 s m i n ( G ) 8 2 m 4 L G Δ + σ 6 s m i n ( G ) 8 2 m 3 Δ s m a x ( G ) 2 + σ 6 s m i n ( G ) 8 L G m 3 D 2 s m a x ( G ) 2 + σ 4 s m i n ( G ) 8 m 2 s m a x ( G ) 4 D 2 ) ,
it holds, by Cauchy-Schwarz and Theorem 2.1 ,
E [ A σ 2 ] ≤ O d ( L H 4 ( L G 2 Δ 2 σ − 16 + Δ 2 σ − 12 + L G 2 D 4 σ − 12 + D 4 σ − 8 ) ) = O d ( L H 4 ( 1 + σ − 2 L G ) 2 ( Δ 2 σ − 12 + D 4 σ − 8 ) ) . \begin{aligned}
\mathbb{E}[A_\sigma^2]\le\mathcal{O}_d\left(L_H^4\left(L_G^2\Delta^2\sigma^{-16}+\Delta^2\sigma^{-12}+L_G^2D^4\sigma^{-12}+D^4\sigma^{-8}\right)\right) \\
&=\mathcal{O}_d\left(L_H^4(1+\sigma^{-2}L_G)^2(\Delta^2\sigma^{-12}+D^4\sigma^{-8})\right).
\end{aligned} E [ A σ 2 ] ≤ O d ( L H 4 ( L G 2 Δ 2 σ − 16 + Δ 2 σ − 12 + L G 2 D 4 σ − 12 + D 4 σ − 8 ) ) = O d ( L H 4 ( 1 + σ − 2 L G ) 2 ( Δ 2 σ − 12 + D 4 σ − 8 ) ) .
Therefore,
E [ K s l o w , σ ] ≤ 1 + O d ( ( 1 + σ − 2 L G ) ( log ( 1 + L H 2 ( 1 + σ − 2 L G ) ( Δ σ − 6 + D 2 σ − 4 ) ) + 1 ) ) . \mathbb{E}[\mathbb{K}_{\mathrm{slow},\sigma}]\le1+\mathcal{O}_d\left((1+\sigma^{-2}L_G)\left(\log(1+L_H^2(1+\sigma^{-2}L_G)(\Delta\sigma^{-6}+D^2\sigma^{-4}))+1\right)\right). E [ K slow , σ ] ≤ 1 + O d ( ( 1 + σ − 2 L G ) ( log ( 1 + L H 2 ( 1 + σ − 2 L G ) ( Δ σ − 6 + D 2 σ − 4 )) + 1 ) ) .
Discussion. As expected, most of the terms that were part of the constant in Section 3.5 are now under the logarithm. Specifically, the only dependency that is not under a logarithm is σ − 2 L G \sigma^{-2}L_G σ − 2 L G , which acts as a condition number, and was also outside of the logarithm in Theorem 3.10 . The quadratic convergence part remains the same, which is to be expected, as the algorithm is identical once the quadratic convergence region is attained.
Numerical Illustration. We illustrate Theorem 3.15 on the convex function
f ( x ) = ∑ i = 1 n ( 1 + x i 2 − 1 ) f(x)=\sum_{i=1}^{n}\left(\sqrt{1+x_i^2}-1\right) f ( x ) = i = 1 ∑ n ( 1 + x i 2 − 1 )
whose gradient is 1-Lipschitz and whose Hessian is 1-Lipschitz. The results are shown in Figure 9 . We observe that our bounds do not capture the tendency in the empirical iteration counters with σ \sigma σ or d d d , but that they agree on the dimension-independence.
Figure 9. Smoothed complexity of the Hybrid Gradient–Cubic Newton method under Wishart perturbations.
Gauss-Newton Method - Convex Case
We next consider Nonlinear Least Squares problems h ( x ) = 1 2 ∥ r ( x ) ∥ 2 h(x) = \frac{1}{2}\lVert r(x)\rVert^{2} h ( x ) = 2 1 ∥ r ( x ) ∥ 2 , and write J ( x ) = ∇ r ( x ) J(x) = \nabla r(x) J ( x ) = ∇ r ( x ) . Let F μ , γ L , γ ˉ \mathcal{F}_{\mu,\gamma}^{L,\bar{\gamma}} F μ , γ L , γ ˉ denote the class for which f f f is μ \mu μ -strongly convex and L L L -smooth, while γ 2 I ⪯ J ( x ) T J ( x ) ⪯ γ ˉ 2 I \gamma^{2} I \preceq J(x)^{T}J(x) \preceq\bar{\gamma}^{2} I γ 2 I ⪯ J ( x ) T J ( x ) ⪯ γ ˉ 2 I for every x x x . As before, μ = γ = 0 \mu= \gamma= 0 μ = γ = 0 denotes the merely convex, possibly rank-deficient setting. For f ∈ F μ , γ L , γ ˉ f \in\mathcal{F}_{\mu,\gamma}^{L,\bar{\gamma}} f ∈ F μ , γ L , γ ˉ , we consider, for x 0 ∈ R n x_{0} \in\mathbb{R}^{n} x 0 ∈ R n and k ≥ 0 k \ge0 k ≥ 0 ,
J k = J ( x k ) , g k = ∇ f ( x k ) , ( J k T J k ) s k = − g k , x k + 1 = x k + γ 2 L s k . J_{k} = J(x_{k}), \quad g_{k} = \nabla f(x_{k}), \quad(J_{k}^{T}J_{k})s_{k} = -g_{k}, \quad x_{k+1} = x_{k} + \frac{\gamma^{2}}{L}s_{k}. J k = J ( x k ) , g k = ∇ f ( x k ) , ( J k T J k ) s k = − g k , x k + 1 = x k + L γ 2 s k .
We measure complexity in terms of relative function value accuracy, namely, for ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) ,
K G N C o n v e x ϵ ( h ) = min k ≥ 0 { k : h ( x k ) − inf h h ( x 0 ) − inf h ≤ ϵ } . K_{\mathrm{GNConvex}}^{\epsilon}(h) = \min_{k \ge0}\left\{k : \frac{h(x_{k})-\inf h}{h(x_{0})-\inf h} \le\epsilon\right\}. K GNConvex ϵ ( h ) = k ≥ 0 min { k : h ( x 0 ) − inf h h ( x k ) − inf h ≤ ϵ } .
where K G N C o n v e x ϵ ( h ) = 0 K_{\mathrm{GNConvex}}^{\epsilon}(h) = 0 K GNConvex ϵ ( h ) = 0 if h ( x 0 ) = inf h h(x_{0}) = \inf h h ( x 0 ) = inf h . Though we do not write it, for least squares problems with r r r let the residual r r r be part of the instance.
We first recall the corresponding worst-case complexity. The proof, which follows the standard descent argument underlying Gauss–Newton analyses ([37 , 6 , 33 ] ), is included in Appendix § 5 .§ 1 .
Theorem 3.16 (Worst-Case Complexity of (GN)). Let h ∈ F μ , γ L , γ ˉ h \in\mathcal{F}_{\mu,\gamma}^{L,\bar{\gamma}} h ∈ F μ , γ L , γ ˉ for 0 < μ ≤ L < + ∞ 0 < \mu\le L < +\infty 0 < μ ≤ L < + ∞ , 0 < γ ≤ γ ˉ < + ∞ 0 < \gamma\le\bar{\gamma} < +\infty 0 < γ ≤ γ ˉ < + ∞ , and let ( x k ) (x_{k}) ( x k ) be the iterates of (GN). Then,
h ( x k ) − inf h h ( x 0 ) − inf h ≤ ( 1 − μ γ 2 L γ ˉ 2 ) k . \frac{h(x_{k})-\inf h}{h(x_{0})-\inf h} \le\left(1-\frac{\mu\gamma^{2}}{L\bar{\gamma}^{2}}\right)^{k}. h ( x 0 ) − inf h h ( x k ) − inf h ≤ ( 1 − L γ ˉ 2 μ γ 2 ) k . In particular, for M = max { L , γ ˉ 2 } M = \max\{L,\bar{\gamma}^{2}\} M = max { L , γ ˉ 2 } , ℓ = min { μ , γ 2 } \ell= \min\{\mu,\gamma^{2}\} ℓ = min { μ , γ 2 } and R = M / ℓ R = M/\ell R = M / ℓ , the relative accuracy complexity is bounded by, for ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) ,
sup h ∈ F μ , γ L , γ ˉ K G N C o n v e x ϵ ( h ) ≤ ⌈ L γ ˉ 2 μ γ 2 log ( 1 / ϵ ) ⌉ ≤ ⌈ R 2 log ( 1 / ϵ ) ⌉ . \sup_{h\in\mathcal{F}_{\mu,\gamma}^{L,\bar{\gamma}}} K_{\mathrm{GNConvex}}^{\epsilon}(h) \le\left\lceil\frac{L\bar{\gamma}^{2}}{\mu\gamma^{2}}\log(1/\epsilon)\right\rceil\le\left\lceil R^{2}\log(1/\epsilon)\right\rceil. h ∈ F μ , γ L , γ ˉ sup K GNConvex ϵ ( h ) ≤ ⌈ μ γ 2 L γ ˉ 2 log ( 1/ ϵ ) ⌉ ≤ ⌈ R 2 log ( 1/ ϵ ) ⌉ .
In the merely convex setting, both the curvature of f f f and the smallest singular value of J J J may vanish. For the perturbed problem, the quadratic regularization can be written as an augmentation of the residual,
r σ ( x ) = ( r ( x ) σ W 1 / 2 ( x − x ~ ) ) , J σ ( x ) = ( J ( x ) σ W 1 / 2 ) . r_{\sigma}(x) =
\begin{pmatrix}
r(x)\\
\sigma W^{1/2}(x-\widetilde{x})
\end{pmatrix},
\qquad
J_{\sigma}(x) =
\begin{pmatrix}
J(x)\\
\sigma W^{1/2}
\end{pmatrix}. r σ ( x ) = ( r ( x ) σ W 1/2 ( x − x ) ) , J σ ( x ) = ( J ( x ) σ W 1/2 ) .
Consequently,
L σ γ ˉ 2 μ τ σ γ 2 ≤ ( L + σ 2 λ max ( W ) ) ( γ ˉ 2 + σ 2 λ max ( W ) ) σ 4 λ min ( W ) 2 . (5) \frac{L_{\sigma}\bar{\gamma}^{2}}{\mu_{\tau}\sigma_{\gamma}^{2}} \le\frac{\left(L+\sigma^{2}\lambda_{\max}(W)\right)\left(\bar{\gamma}^{2}+\sigma^{2}\lambda_{\max}(W)\right)}{\sigma^{4}\lambda_{\min}(W)^{2}}. \tag*{(5)} μ τ σ γ 2 L σ γ ˉ 2 ≤ σ 4 λ m i n ( W ) 2 ( L + σ 2 λ m a x ( W ) ) ( γ ˉ 2 + σ 2 λ m a x ( W ) ) . (5)
This yields the following smoothed complexity guarantee.
Theorem 3.17 (Smoothed Complexity of (GN)). Let 0 < σ , L , γ ˉ < + ∞ 0 < \sigma, L, \bar{\gamma} < +\infty 0 < σ , L , γ ˉ < + ∞ and ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) . We denote by f W f_W f W a perturbation of f f f , parametrized by σ \sigma σ , as defined in Equation (1) . Then, as n → ∞ n \to\infty n → ∞ , the smoothed complexity of the Algorithm (GN) over the function class F 0 , 0 L , γ ˉ F^{L,\bar{\gamma}}_{0,0} F 0 , 0 L , γ ˉ is bounded by
sup f ∈ F 0 , 0 L , γ ˉ E W [ K G N C o n v e x ε ( f W ) ] ≤ 1 + O d ( ( 1 + σ − 2 L ) ( 1 + σ − 2 γ ˉ 2 ) log 1 ε ) . \sup_{f \in F^{L,\bar{\gamma}}_{0,0}} \mathbb{E}_W\left[K^\varepsilon_{\mathrm{GNConvex}}(f_W)\right] \le1 + O_d\left(\left(1+\sigma^{-2}L\right)\left(1+\sigma^{-2}\bar{\gamma}^{2}\right)\log\frac{1}{\varepsilon}\right). f ∈ F 0 , 0 L , γ ˉ sup E W [ K GNConvex ε ( f W ) ] ≤ 1 + O d ( ( 1 + σ − 2 L ) ( 1 + σ − 2 γ ˉ 2 ) log ε 1 ) .
Proof. Fix any f ∈ F 0 , 0 L , γ ˉ f \in F^{L,\bar{\gamma}}_{0,0} f ∈ F 0 , 0 L , γ ˉ . Theorem 3.16 and the perturbed parameters in Equation (5) give
K G N C o n v e x ε ( f W ) ≤ 1 + ( L + σ 2 λ max ( W ) ) ( γ ˉ 2 + σ 2 λ max ( W ) ) σ 4 λ min ( W ) 2 log 1 ε . K^\varepsilon_{\mathrm{GNConvex}}(f_W) \le1 + \frac{\left(L+\sigma^{2}\lambda_{\max}(W)\right)\left(\bar{\gamma}^{2}+\sigma^{2}\lambda_{\max}(W)\right)}{\sigma^{4}\lambda_{\min}(W)^{2}}\log\frac{1}{\varepsilon}. K GNConvex ε ( f W ) ≤ 1 + σ 4 λ m i n ( W ) 2 ( L + σ 2 λ m a x ( W ) ) ( γ ˉ 2 + σ 2 λ m a x ( W ) ) log ε 1 .
Expanding the numerator, applying Cauchy–Schwarz to the mixed moments and using Theorem 2.1 gives the result. □
Discussion. The quantities σ − 2 L \sigma^{-2}L σ − 2 L and σ − 2 γ ˉ 2 \sigma^{-2}\bar{\gamma}^{2} σ − 2 γ ˉ 2 both describe the conditioning scales. We therefore observe a dependency in the square condition number in the smoothed bound. The perturbation allows to recover linear convergence, meaning the upper bound scales logarithmically with ε \varepsilon ε , even though the degenerate setting only enjoys a sublinear convergence rate.
Numerical Illustration. We illustrate Theorem 3.17 on the rank-one nonlinear least-squares objective
f ( x ) = 1 2 ( t ( x ) 2 + 1 4 sin 2 ( t ( x ) ) ) , t ( x ) = 1 n ∑ i = 1 n x i . f(x)=\frac{1}{2}\left(t(x)^{2}+\frac{1}{4}\sin^{2}(t(x))\right), \qquad t(x)=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}x_i. f ( x ) = 2 1 ( t ( x ) 2 + 4 1 sin 2 ( t ( x )) ) , t ( x ) = n 1 i = 1 ∑ n x i .
Indeed, f f f is convex since its second derivative along t t t is 1 + 1 4 cos ( 2 t ) ≥ 3 4 1+\frac{1}{4}\cos(2t)\ge\frac{3}{4} 1 + 4 1 cos ( 2 t ) ≥ 4 3 , while the residual Jacobian has rank one. The results are shown in Figure 10 . We observe that the bounds and the empirical iteration count increase with d d d and exhibit a similar dependency in ε \varepsilon ε , up to constants. This again shows an agreement between the empirical and theoretical observations about the highly overparametrized perturbation model being favourable. However, the empirical iteration count decreases more slowly with σ \sigma σ than the bounds for small perturbations, so that the theoretical dependency in σ \sigma σ is pessimistic on this example.
Figure 10. Smoothed complexity of Algorithm (GN) under Wishart perturbations.
Gauss-Newton Method - Convex Case with Armijo Line Search
We consider the same class F μ , γ L , γ ˉ F^{L,\bar{\gamma}}_{\mu,\gamma} F μ , γ L , γ ˉ as in § 3.8 , replacing the fixed step-size in Algorithm (GN) by an Armijo line search. Specifically, given the Armijo parameters β , τ ∈ ( 0 , 1 ) \beta,\tau\in(0,1) β , τ ∈ ( 0 , 1 ) , for h ∈ F μ , γ L , γ ˉ h \in F^{L,\bar{\gamma}}_{\mu,\gamma} h ∈ F μ , γ L , γ ˉ , consider, for x 0 ∈ R n x_0 \in\mathbb{R}^n x 0 ∈ R n and k ≥ 0 k \ge0 k ≥ 0 ,
J k = J ( x k ) , g k = ∇ h ( x k ) , ( J k T J k ) s k = − g k , x k + 1 = x k + α k s k . (6) J_k=J(x_k), \qquad g_k=\nabla h(x_k), \qquad(J_k^{T}J_k)s_k=-g_k, \qquad x_{k+1}=x_k+\alpha_k s_k. \tag*{(6)} J k = J ( x k ) , g k = ∇ h ( x k ) , ( J k T J k ) s k = − g k , x k + 1 = x k + α k s k . (6)
where α k \alpha_k α k is the largest value in 1 , τ , τ 2 , … 1,\tau,\tau^2,\ldots 1 , τ , τ 2 , … satisfying
h ( x k + α k s k ) ≤ h ( x k ) + β α k g k T s k . h(x_k+\alpha_k s_k)\le h(x_k)+\beta\alpha_k g_k^{T}s_k. h ( x k + α k s k ) ≤ h ( x k ) + β α k g k T s k .
We again measure complexity in terms of relative function value accuracy, namely, for ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) ,
K G N C o n v e x A r m i j o ϵ ( h ) = min k ≥ 0 { k : h ( x k ) − inf h h ( x 0 ) − inf h ≤ ϵ } . K^\epsilon_{\mathrm{GNConvexArmijo}}(h)=\min_{k\geq0}\left\{k:\frac{h(x_k)-\inf h}{h(x_0)-\inf h}\leq\epsilon\right\}. K GNConvexArmijo ϵ ( h ) = k ≥ 0 min { k : h ( x 0 ) − inf h h ( x k ) − inf h ≤ ϵ } .
and only count outer iterations, where K G N C o n v e x A r m i j o ϵ ( h ) = 0 K^\epsilon_{\mathrm{GNConvexArmijo}}(h)=0 K GNConvexArmijo ϵ ( h ) = 0 if h ( x 0 ) = inf h h(x_0)=\inf h h ( x 0 ) = inf h .
The following result follows from the standard Armijo descent argument (Nocedal and Wright, [37 ] ); its proof is included in Appendix § 5 .§ 2 .
Theorem 3.18 (Worst-Case Complexity of (GNArmijo)). Let h ∈ F μ , γ L , γ ˉ h\in\mathcal{F}^{L,\bar{\gamma}}_{\mu,\gamma} h ∈ F μ , γ L , γ ˉ with 0 < μ ≤ L < + ∞ 0<\mu\leq L<+\infty 0 < μ ≤ L < + ∞ and 0 < γ ≤ γ ˉ < + ∞ 0<\gamma\leq\bar{\gamma}<+\infty 0 < γ ≤ γ ˉ < + ∞ , and let ( x k ) (x_k) ( x k ) be the iterates of (GNArmijo) with β , τ ∈ ( 0 , 1 ) \beta,\tau\in(0,1) β , τ ∈ ( 0 , 1 ) . Then, for α ˉ = τ min { 1 , 2 ( 1 − β ) γ 2 / L } \bar{\alpha}=\tau\min\{1,2(1-\beta)\gamma^2/L\} α ˉ = τ min { 1 , 2 ( 1 − β ) γ 2 / L } ,
h ( x k ) − inf h h ( x 0 ) − inf h ≤ ( 1 − 2 μ β α ˉ γ ˉ 2 ) k . \frac{h(x_k)-\inf h}{h(x_0)-\inf h}\leq\left(1-\frac{2\mu\beta\bar{\alpha}}{\bar{\gamma}^2}\right)^k. h ( x 0 ) − inf h h ( x k ) − inf h ≤ ( 1 − γ ˉ 2 2 μ β α ˉ ) k . Thus the relative accuracy complexity is bounded by, for ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) ,
sup h ∈ F μ , γ L , γ ˉ K G N C o n v e x A r m i j o ϵ ( h ) ≤ ⌈ γ ˉ 2 2 μ β α ˉ log 1 ϵ ⌉ . \sup_{h\in\mathcal{F}^{L,\bar{\gamma}}_{\mu,\gamma}}K^\epsilon_{\mathrm{GNConvexArmijo}}(h)\leq\left\lceil\frac{\bar{\gamma}^2}{2\mu\beta\bar{\alpha}}\log\frac{1}{\epsilon}\right\rceil. h ∈ F μ , γ L , γ ˉ sup K GNConvexArmijo ϵ ( h ) ≤ ⌈ 2 μ β α ˉ γ ˉ 2 log ϵ 1 ⌉ .
The line search does not require knowledge of the values of L L L and γ \gamma γ , and instead adapts to them, thus preserving linear convergence. For fixed Armijo parameters, the smoothed complexity order of the fixed-step method is preserved.
Theorem 3.19 (Smoothed Complexity of (GNArmijo)). Let 0 < σ , L , γ ˉ < + ∞ 0<\sigma,L,\bar{\gamma}<+\infty 0 < σ , L , γ ˉ < + ∞ and ϵ , β , τ ∈ ( 0 , 1 ) \epsilon,\beta,\tau\in(0,1) ϵ , β , τ ∈ ( 0 , 1 ) . We denote by f W f_W f W a perturbation of f f f , parametrized by σ \sigma σ , as defined in Equation (1) . Then, as n → ∞ n\to\infty n → ∞ , the smoothed complexity of Algorithm (GNArmijo) over the function class F 0 , 0 L , γ ˉ \mathcal{F}^{L,\bar{\gamma}}_{0,0} F 0 , 0 L , γ ˉ is bounded by
sup f ∈ F 0 , 0 L , γ ˉ E W [ K G N C o n v e x A r m i j o ϵ ( f W ) ] ≤ 1 + O d , β , τ ( ( 1 + σ − 2 L ) ( 1 + σ − 2 γ ˉ 2 ) log 1 ϵ ) . \sup_{f\in\mathcal{F}^{L,\bar{\gamma}}_{0,0}}\mathbb{E}_W\left[K^\epsilon_{\mathrm{GNConvexArmijo}}(f_W)\right]\leq1+O_{d,\beta,\tau}\left((1+\sigma^{-2}L)(1+\sigma^{-2}\bar{\gamma}^2)\log\frac{1}{\epsilon}\right). f ∈ F 0 , 0 L , γ ˉ sup E W [ K GNConvexArmijo ϵ ( f W ) ] ≤ 1 + O d , β , τ ( ( 1 + σ − 2 L ) ( 1 + σ − 2 γ ˉ 2 ) log ϵ 1 ) .
Proof. Fix any f ∈ F 0 , 0 L , γ ˉ f\in\mathcal{F}^{L,\bar{\gamma}}_{0,0} f ∈ F 0 , 0 L , γ ˉ . By Theorem 3.18 ,
K G N C o n v e x A r m i j o ϵ ( f W ) ≤ 1 + 1 2 β τ ( γ ˉ 2 μ σ + L σ γ ˉ σ 2 2 ( 1 − β ) μ σ γ σ 2 ) log 1 ϵ . K^\epsilon_{\mathrm{GNConvexArmijo}}(f_W)\leq1+\frac{1}{2\beta\tau}\left(\frac{\bar{\gamma}^2}{\mu_\sigma}+\frac{L_\sigma\bar{\gamma}_\sigma^2}{2(1-\beta)\mu_\sigma\gamma_\sigma^2}\right)\log\frac{1}{\epsilon}. K GNConvexArmijo ϵ ( f W ) ≤ 1 + 2 β τ 1 ( μ σ γ ˉ 2 + 2 ( 1 − β ) μ σ γ σ 2 L σ γ ˉ σ 2 ) log ϵ 1 .
The expectation of the first term is bounded by O d ( 1 + σ − 2 γ ˉ 2 ) O_d(1+\sigma^{-2}\bar{\gamma}^2) O d ( 1 + σ − 2 γ ˉ 2 ) , as in the proof of Theorem 3.2 , by
E [ γ ˉ σ 2 μ σ ] ≤ E [ γ ˉ 2 + σ 2 s max ( G ) 2 m σ 2 s min ( G ) 2 m ] = E [ m σ − 2 γ ˉ 2 + s max ( G ) 2 s min ( G ) 2 ] ≤ O d ( 1 + σ − 2 γ ˉ 2 ) . \mathbb{E}\left[\frac{\bar{\gamma}_\sigma^2}{\mu_\sigma}\right]\leq\mathbb{E}\left[\frac{\bar{\gamma}^2+\frac{\sigma^2s_{\max}(G)^2}{m}}{\frac{\sigma^2s_{\min}(G)^2}{m}}\right]=\mathbb{E}\left[\frac{m\sigma^{-2}\bar{\gamma}^2+s_{\max}(G)^2}{s_{\min}(G)^2}\right]\leq O_d(1+\sigma^{-2}\bar{\gamma}^2). E [ μ σ γ ˉ σ 2 ] ≤ E [ m σ 2 s m i n ( G ) 2 γ ˉ 2 + m σ 2 s m a x ( G ) 2 ] = E [ s m i n ( G ) 2 m σ − 2 γ ˉ 2 + s m a x ( G ) 2 ] ≤ O d ( 1 + σ − 2 γ ˉ 2 ) .
The expectation of the second term is bounded as in the proof of Theorem 3.17 . □
Discussion. As in § 3.8 , the smoothed complexity bound depends logarithmically on ϵ \epsilon ϵ , thus providing a linear convergence rate rather than a sublinear rate as expected for merely convex functions. The dependency in the condition number remains square, as in § 3.8 .
Numerical Illustration. We use the same rank-one nonlinear least-squares objective as in § 3.8 , namely
f ( x ) = 1 2 ( t ( x ) 2 + 1 4 sin 2 ( t ( x ) ) ) , t ( x ) = 1 n ∑ i = 1 n x i . f(x)=\frac{1}{2}\left(t(x)^2+\frac{1}{4}\sin^2(t(x))\right),\qquad t(x)=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}x_i. f ( x ) = 2 1 ( t ( x ) 2 + 4 1 sin 2 ( t ( x )) ) , t ( x ) = n 1 i = 1 ∑ n x i .
with the Armijo parameters β = τ = 1 / 2 \beta= \tau= 1/2 β = τ = 1/2 . The results are shown in Figure 11 . We note that our theory is overly pessimistic in this setting, where the empirical iteration count is always small, and our theory predicts a large value. This arises from the pessimistic worst-case bound in Theorem 3.18 .
Figure 11. Smoothed complexity of Algorithm (GNArmijo) under Wishart perturbations.
Gauss-Newton Method - Nonconvex Case with Radial Monotonicity
We now consider the nonconvex Nonlinear Least Squares problem with Algorithm (GN), and further assume gradient domination , as in § 3.2 . Specifically, we denote by F P L , η , γ L , γ ˉ \mathcal{F}^{L,\bar{\gamma}}_{\mathrm{PL},\eta,\gamma} F PL , η , γ L , γ ˉ the subclass of F − ∞ , γ L , γ ˉ \mathcal{F}^{L,\bar{\gamma}}_{-\infty,\gamma} F − ∞ , γ L , γ ˉ that satisfies gradient domination with parameter η > 0 \eta> 0 η > 0 , where F − ∞ , γ L , γ ˉ \mathcal{F}^{L,\bar{\gamma}}_{-\infty,\gamma} F − ∞ , γ L , γ ˉ denotes the class of nonconvex L L L -smooth functions satisfying γ 2 I ⪯ J ( x ) T J ( x ) ⪯ γ ˉ 2 I \gamma^2 I \preceq J(x)^T J(x) \preceq\bar{\gamma}^2 I γ 2 I ⪯ J ( x ) T J ( x ) ⪯ γ ˉ 2 I for all x x x . We note that gradient domination implies that all local minimizers are global, and therefore we can measure complexity in terms of relative function value accuracy, namely, for ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) ,
K G N , r a d ε ( h ) = min k ≥ 0 { k : h ( x k ) − inf h h ( x 0 ) − inf h ≤ ε } . \mathsf{K}^{\varepsilon}_{\mathrm{GN,rad}}(h) = \min_{k \ge0} \left\{ k: \frac{h(x_k)-\inf h}{h(x_0)-\inf h} \le\varepsilon\right\}. K GN , rad ε ( h ) = k ≥ 0 min { k : h ( x 0 ) − inf h h ( x k ) − inf h ≤ ε } .
where K G N , r a d ε ( h ) = 0 \mathsf{K}^{\varepsilon}_{\mathrm{GN,rad}}(h)=0 K GN , rad ε ( h ) = 0 if h ( x 0 ) = inf h h(x_0)=\inf h h ( x 0 ) = inf h .
We first give the deterministic worst-case complexity under gradient domination, whose proof is postponed to Appendix § 5 .§ 3 .
Theorem 3.20 (Worst-Case Complexity of (GN) under Gradient Domination). Let h ∈ F P L , η , γ L , γ ˉ h \in\mathcal{F}^{L,\bar{\gamma}}_{\mathrm{PL},\eta,\gamma} h ∈ F PL , η , γ L , γ ˉ with 0 < L , η < + ∞ 0 < L,\eta< +\infty 0 < L , η < + ∞ and 0 < γ ≤ γ ˉ < + ∞ 0 < \gamma\le\bar{\gamma} < +\infty 0 < γ ≤ γ ˉ < + ∞ , and let ( x k ) (x_k) ( x k ) be the iterates of (GN). Then,
h ( x k ) − inf h h ( x 0 ) − inf h ≤ ( 1 − η γ 2 L γ ˉ 2 ) k . \frac{h(x_k)-\inf h}{h(x_0)-\inf h} \le\left(1-\frac{\eta\gamma^2}{L\bar{\gamma}^2}\right)^k. h ( x 0 ) − inf h h ( x k ) − inf h ≤ ( 1 − L γ ˉ 2 η γ 2 ) k . Thus, the relative function value accuracy complexity is bounded by, for ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) ,
sup h ∈ F P L , η , γ L , γ ˉ K G N , r a d ε ( h ) ≤ ⌈ L γ ˉ 2 η γ 2 log 1 ε ⌉ . \sup_{h \in\mathcal{F}^{L,\bar{\gamma}}_{\mathrm{PL},\eta,\gamma}} \mathsf{K}^{\varepsilon}_{\mathrm{GN,rad}}(h) \le\left\lceil\frac{L\bar{\gamma}^2}{\eta\gamma^2}\log\frac{1}{\varepsilon} \right\rceil. h ∈ F PL , η , γ L , γ ˉ sup K GN , rad ε ( h ) ≤ ⌈ η γ 2 L γ ˉ 2 log ε 1 ⌉ .
As in § 3.2 and § 3.6 , gradient domination may be covered through perturbation of radially monotone functions. We denote by F r a d L , γ ˉ ( x ~ ) \mathcal{F}^{L,\bar{\gamma}}_{\mathrm{rad}}(\tilde{x}) F rad L , γ ˉ ( x ~ ) the subclass of F − ∞ , 0 L , γ ˉ \mathcal{F}^{L,\bar{\gamma}}_{-\infty,0} F − ∞ , 0 L , γ ˉ that satisfies radial monotonicity. We now state the smoothed complexity guarantee.
Theorem 3.21 (Smoothed Complexity of (GN) under Radial Monotonicity). Let 0 < σ , L , γ ˉ < + ∞ 0 < \sigma,L,\bar{\gamma} < +\infty 0 < σ , L , γ ˉ < + ∞ , ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) , and let x ~ ∈ R n \tilde{x} \in\mathbb{R}^n x ~ ∈ R n . We denote by f W f_W f W a perturbation of f f f , parametrized by σ \sigma σ , as defined in Equation (1) . Then, as n → ∞ n \to\infty n → ∞ , the smoothed complexity of Algorithm (GN) over the function class
F r a d L , γ ˉ ( x ~ ) \mathcal{F}_{\mathrm{rad}}^{L,\bar{\gamma}}(\tilde{x}) F rad L , γ ˉ ( x ~ ) is bounded by
sup f ∈ F r a d L , γ ˉ ( x ~ ) E W [ K G N , r a d ε ( f W ) ] ≤ 1 + O d ( ( 1 + σ − 2 L ) 2 ( 1 + σ − 2 γ ˉ 2 ) log 1 ε ) . \sup_{f\in\mathcal{F}_{\mathrm{rad}}^{L,\bar{\gamma}}(\tilde{x})}\mathbb{E}_{W}\left[\mathsf{K}_{\mathrm{GN},\mathrm{rad}}^{\varepsilon}(f_{W})\right]\leq1+\mathcal{O}_{d}\left((1+\sigma^{-2}L)^{2}(1+\sigma^{-2}\bar{\gamma}^{2})\log\frac{1}{\varepsilon}\right). f ∈ F rad L , γ ˉ ( x ~ ) sup E W [ K GN , rad ε ( f W ) ] ≤ 1 + O d ( ( 1 + σ − 2 L ) 2 ( 1 + σ − 2 γ ˉ 2 ) log ε 1 ) .
Proof. Fix any f ∈ F r a d L , γ ˉ ( x ~ ) f\in\mathcal{F}_{\mathrm{rad}}^{L,\bar{\gamma}}(\tilde{x}) f ∈ F rad L , γ ˉ ( x ~ ) . Theorem 3.20 and the preceding bounds give
K G N , r a d ε ( f W ) ≤ 1 + ( L + σ 2 λ max ( W ) ) 2 ( γ ˉ 2 + σ 2 λ max ( W ) ) σ 6 λ min ( W ) 3 log 1 ε . \mathsf{K}_{\mathrm{GN},\mathrm{rad}}^{\varepsilon}(f_{W})\leq1+\frac{(L+\sigma^{2}\lambda_{\max}(W))^{2}(\bar{\gamma}^{2}+\sigma^{2}\lambda_{\max}(W))}{\sigma^{6}\lambda_{\min}(W)^{3}}\log\frac{1}{\varepsilon}. K GN , rad ε ( f W ) ≤ 1 + σ 6 λ m i n ( W ) 3 ( L + σ 2 λ m a x ( W ) ) 2 ( γ ˉ 2 + σ 2 λ m a x ( W )) log ε 1 .
Expanding the numerator, applying Cauchy-Schwarz to each mixed moment and using Theorem 2.1 proves the result.
Discussion. We note that, akin to Gradient Descent in § 3.2 , the radial monotonicity setting adds a factor 1 + σ − 2 L 1+\sigma^{-2}L 1 + σ − 2 L to the smoothed bound, compared to the convex case in § 3.8 .
Numerical Illustration. We consider the following nonlinear least squares problem
f ( x ) = 1 2 ∥ r ( x ) ∥ 2 = 1 2 ∑ i = 1 ⌊ n / 2 ⌋ r i ( x ) 2 , r i ( x ) = x i 1 + x i 2 for i = 1 , … , ⌊ n / 2 ⌋ , x ~ = 0. f(x)=\frac{1}{2}\lVert r(x)\rVert^{2}=\frac{1}{2}\sum_{i=1}^{\lfloor n/2\rfloor}r_i(x)^2,\qquad r_i(x)=\frac{x_i}{\sqrt{1+x_i^2}}\quad\text{for }i=1,\ldots,\lfloor n/2\rfloor,\qquad\tilde{x}=0. f ( x ) = 2 1 ∥ r ( x ) ∥ 2 = 2 1 i = 1 ∑ ⌊ n /2 ⌋ r i ( x ) 2 , r i ( x ) = 1 + x i 2 x i for i = 1 , … , ⌊ n /2 ⌋ , x ~ = 0.
We note that ( x − x ~ ) T ∇ f ( x ) = ∑ i x i 2 / ( 1 + x i 2 ) 2 ≥ 0 (x-\tilde{x})^{\mathsf{T}}\nabla f(x)=\sum_i x_i^2/(1+x_i^2)^2\geq0 ( x − x ~ ) T ∇ f ( x ) = ∑ i x i 2 / ( 1 + x i 2 ) 2 ≥ 0 and f ( x ~ ) = min f f(\tilde{x})=\min f f ( x ~ ) = min f , so that the function is radially monotone. We compute that
∂ i i f ( x ) = 1 − 3 x i 2 ( 1 + x i 2 ) 3 and J i i ( x ) = ( 1 + x i 2 ) − 3 / 2 , \partial_{ii}f(x)=\frac{1-3x_i^2}{(1+x_i^2)^3}\qquad\text{and}\qquad J_{ii}(x)=(1+x_i^2)^{-3/2}, ∂ ii f ( x ) = ( 1 + x i 2 ) 3 1 − 3 x i 2 and J ii ( x ) = ( 1 + x i 2 ) − 3/2 ,
so that the objective is nonconvex, globally smooth with L = 1 L=1 L = 1 and has Jacobian singular values bounded by γ ˉ = 1 \bar{\gamma}=1 γ ˉ = 1 . The Jacobian is rank-deficient at every x x x , as the sum only spans the first ⌊ n / 2 ⌋ \lfloor n/2\rfloor ⌊ n /2 ⌋ coordinates, and does not satisfy gradient domination as, for instance, along x = t e 1 x=te_1 x = t e 1 , the objective tends to a finite constant as $t\to\infty.
The results are shown in Figure 12 . As in § 3.2 and § 3.6 , we observe that our bounds are more pessimistic in its dependencies that in the convex counterparts, but that the trends are correct.
Figure 12. Smoothed complexity of Algorithm (GN) under Wishart perturbations.
Conclusion
In this paper, we developed a smoothed analysis framework for a range of classical algorithms in continuous optimization, showing that small random perturbations can lead to substantially sharper complexity guarantees than those suggested by a worst-case analysis. Specifically, we apply methods suited for non-degenerate functions to small perturbations of degenerate functions, and recover the faster best-known rates for the non-degenerate class. The resulting bounds obtained in the framework help explain why algorithms that may exhibit poor worst-case guarantees nevertheless can perform well on nearby instances.
Outlook. Our results suggest that smoothed analysis can provide a useful intermediate perspective between worst-case and average-case analysis for continuous optimization methods. Several questions however remain open. Firstly, the current analysis heavily relies on worst-case results, which inevitably weakens the smoothed complexity results obtained. Secondly, it would be interesting to extend the framework to more nonconvex settings, beyond the radial monotonicity setting in § 3.2 , § 3.6 and § 3.10 . Finally, all algorithms in the present work are deterministic. An open question remains how to tackle stochastic algorithms, and specifically the algorithm of [12 Section 3.3] , which was one motivation of this work.
Acknowledgments. Daniel Cortild acknowledges the support of the Clarendon Funds Scholarships. Coralia Cartis’ work was supported by the Hong Kong Innovation and Technology Commission (InnoHK Project CIMDA) and by the EPSRC grant EP/Y028872/1, Mathematical Foundations of Intelligence: An “Erlangen Programme” for AI.
Proofs
Proof of Theorem 3.16
Let B k = J k T J k B_k = J_k^T J_k B k = J k T J k . Since γ ‾ 2 I ⪯ B k ⪯ γ ‾ 2 I \underline{\gamma}^2 I \preceq B_k \preceq\overline{\gamma}^2 I γ 2 I ⪯ B k ⪯ γ 2 I ,
g k T s k = − g k T B k − 1 g k ≤ − γ ‾ − 2 ∥ g k ∥ 2 , ∥ s k ∥ 2 = g k T B k − 2 g k ≤ − γ ‾ − 2 g k T s k . g_k^T s_k = -g_k^T B_k^{-1}g_k \leq-\overline{\gamma}^{-2}\lVert g_k\rVert^2,\qquad\lVert s_k\rVert^2 = g_k^T B_k^{-2}g_k \leq-\underline{\gamma}^{-2}g_k^T s_k. g k T s k = − g k T B k − 1 g k ≤ − γ − 2 ∥ g k ∥ 2 , ∥ s k ∥ 2 = g k T B k − 2 g k ≤ − γ − 2 g k T s k .
By L L L -smoothness, for any α > 0 \alpha> 0 α > 0 ,
h ( x k + α s k ) ≤ h ( x k ) + α g k T s k + L α 2 2 ∥ s k ∥ 2 ≤ h ( x k ) + α ( 1 − L α 2 γ ‾ 2 ) g k T s k . (7) h(x_k+\alpha s_k) \leq h(x_k)+\alpha g_k^T s_k+\frac{L\alpha^2}{2}\lVert s_k\rVert^2 \leq h(x_k)+\alpha\left(1-\frac{L\alpha}{2\underline{\gamma}^2}\right)g_k^T s_k. \tag*{(7)} h ( x k + α s k ) ≤ h ( x k ) + α g k T s k + 2 L α 2 ∥ s k ∥ 2 ≤ h ( x k ) + α ( 1 − 2 γ 2 Lα ) g k T s k . (7)
The guaranteed decrease is maximized by the fixed step size α = γ ‾ 2 / L \alpha=\underline{\gamma}^2/L α = γ 2 / L . Hence,
h ( x k + 1 ) − min h ≤ h ( x k ) − min h − γ ‾ 2 2 L γ ‾ 2 ∥ g k ∥ 2 ≤ ( 1 − μ γ ‾ 2 L γ ‾ 2 ) ( h ( x k ) − min h ) , h(x_{k+1})-\min h \leq h(x_k)-\min h-\frac{\underline{\gamma}^2}{2L\overline{\gamma}^2}\lVert g_k\rVert^2 \leq\left(1-\frac{\mu\underline{\gamma}^2}{L\overline{\gamma}^2}\right)(h(x_k)-\min h), h ( x k + 1 ) − min h ≤ h ( x k ) − min h − 2 L γ 2 γ 2 ∥ g k ∥ 2 ≤ ( 1 − L γ 2 μ γ 2 ) ( h ( x k ) − min h ) ,
where the last inequality uses ∥ g k ∥ 2 ≥ 2 μ ( h ( x k ) − min h ) \lVert g_k\rVert^2 \geq2\mu(h(x_k)-\min h) ∥ g k ∥ 2 ≥ 2 μ ( h ( x k ) − min h ) . Iterating proves the claim.
Proof of Theorem 3.18
Let B k = J k T J k B_k = J_k^T J_k B k = J k T J k . As in Appendix § 5 .§ 1 ,
g k T s k ≤ − γ ‾ − 2 ∥ g k ∥ 2 , ∥ s k ∥ 2 ≤ − γ ‾ − 2 g k T s k . g_k^T s_k \leq-\overline{\gamma}^{-2}\lVert g_k\rVert^2,\qquad\lVert s_k\rVert^2 \leq-\underline{\gamma}^{-2}g_k^T s_k. g k T s k ≤ − γ − 2 ∥ g k ∥ 2 , ∥ s k ∥ 2 ≤ − γ − 2 g k T s k .
By Equation (7) , Armijo’s condition is satisfied whenever α ≤ 2 ( 1 − β ) γ ‾ 2 / L \alpha\leq2(1-\beta)\underline{\gamma}^2/L α ≤ 2 ( 1 − β ) γ 2 / L . Therefore, α k ≥ α ‾ = τ min { 1 , 2 ( 1 − β ) γ ‾ 2 / L } \alpha_k \geq\overline{\alpha}=\tau\min\{1,2(1-\beta)\underline{\gamma}^2/L\} α k ≥ α = τ min { 1 , 2 ( 1 − β ) γ 2 / L } . By strong convexity,
h ( x k + 1 ) − min h ≤ h ( x k ) − min h + β α k g k T s k ≤ h ( x k ) − min h − β α ‾ γ ‾ − 2 ∥ g k ∥ 2 ≤ ( 1 − 2 μ β α ‾ γ ‾ 2 ) ( h ( x k ) − min h ) . h(x_{k+1})-\min h \leq h(x_k)-\min h+\beta\alpha_k g_k^T s_k \leq h(x_k)-\min h-\beta\overline{\alpha}\overline{\gamma}^{-2}\lVert g_k\rVert^2 \leq\left(1-\frac{2\mu\beta\overline{\alpha}}{\overline{\gamma}^2}\right)(h(x_k)-\min h). h ( x k + 1 ) − min h ≤ h ( x k ) − min h + β α k g k T s k ≤ h ( x k ) − min h − β α γ − 2 ∥ g k ∥ 2 ≤ ( 1 − γ 2 2 μ β α ) ( h ( x k ) − min h ) .
Iterating and using 1 − t ≤ e − t 1-t\leq e^{-t} 1 − t ≤ e − t proves the two claims.
Proof of Theorem 3.20
Taking α = γ ‾ 2 / L \alpha=\underline{\gamma}^2/L α = γ 2 / L in Equation (7) gives
h ( x k + 1 ) ≤ h ( x k ) − γ ‾ 2 2 L γ ‾ 2 ∥ g k ∥ 2 . h(x_{k+1})\leq h(x_k)-\frac{\underline{\gamma}^2}{2L\overline{\gamma}^2}\lVert g_k\rVert^2. h ( x k + 1 ) ≤ h ( x k ) − 2 L γ 2 γ 2 ∥ g k ∥ 2 .
By gradient domination, we obtain
h ( x k + 1 ) − inf h ≤ h ( x k ) − inf h − γ ‾ 2 2 L γ ‾ 2 ∥ g k ∥ 2 ≤ h ( x k ) − inf h − η γ ‾ 2 L γ ‾ 2 ( h ( x k ) − inf h ) , h(x_{k+1})-\inf h\leq h(x_k)-\inf h-\frac{\underline{\gamma}^2}{2L\overline{\gamma}^2}\lVert g_k\rVert^2\leq h(x_k)-\inf h-\frac{\eta\underline{\gamma}^2}{L\overline{\gamma}^2}(h(x_k)-\inf h), h ( x k + 1 ) − inf h ≤ h ( x k ) − inf h − 2 L γ 2 γ 2 ∥ g k ∥ 2 ≤ h ( x k ) − inf h − L γ 2 η γ 2 ( h ( x k ) − inf h ) ,
which proves the first inequality.
Explicit Constants
We sharpen both moment constants in Theorem 2.1 . This does not affect any of the results in the main body, which only require bounds uniform in m m m and n n n .
Proposition B.1 (Positive Moments of the Largest Singular Value). Let q > 0 q>0 q > 0 . If q ≥ 1 q\geq1 q ≥ 1 , then
E [ m − q / 2 s max ( G ) q ] ≤ ( 1 + n m + c q m ) q , c q = ( q 2 q / 2 Γ ( q / 2 ) ) 1 / q . \mathbb{E}\left[m^{-q/2}s_{\max}(G)^q\right]\leq\left(1+\sqrt{\frac{n}{m}}+\frac{c_q}{\sqrt{m}}\right)^q,\qquad c_q=\left(q2^{q/2}\Gamma(q/2)\right)^{1/q}. E [ m − q /2 s m a x ( G ) q ] ≤ ( 1 + m n + m c q ) q , c q = ( q 2 q /2 Γ ( q /2 ) ) 1/ q .
If 0 < q < 1 0<q<1 0 < q < 1 , the same conclusion holds with c q = 2 π c_q=\sqrt{2\pi} c q = 2 π . In particular, whenever n / m ≤ d < 1 n/m\le d<1 n / m ≤ d < 1 ,
C n , m , q max = ( 1 + n m + c q m ) q ≤ C d , q max = ( 1 + d + c q ) q . C^{\max}_{n,m,q}=\left(1+\sqrt{\frac{n}{m}}+\frac{c_q}{\sqrt{m}}\right)^q\le C^{\max}_{d,q}=\left(1+\sqrt{d}+c_q\right)^q. C n , m , q m a x = ( 1 + m n + m c q ) q ≤ C d , q m a x = ( 1 + d + c q ) q .
Proof. Let
Z + = [ s max ( G ) − m − n ] + . Z_+ = [s_{\max}(G)-\sqrt{m}-\sqrt{n}]_+. Z + = [ s m a x ( G ) − m − n ] + .
The Gaussian tail bound [44 Equation (2.3] gives P ( Z + ≥ t ) ≤ 2 e − t 2 / 2 \mathbb{P}(Z_+\ge t)\le2e^{-t^2/2} P ( Z + ≥ t ) ≤ 2 e − t 2 /2 for every t ≥ 0 t\ge0 t ≥ 0 . Hence, for any q > 0 q>0 q > 0 ,
E [ Z + q ] = q ∫ 0 ∞ t q − 1 P ( Z + ≥ t ) d t ≤ 2 q ∫ 0 ∞ t q − 1 e − t 2 / 2 d t = q 2 q / 2 Γ ( q / 2 ) . \mathbb{E}[Z_+^q]=q\int_0^\infty t^{q-1}\mathbb{P}(Z_+\ge t)\,dt\le2q\int_0^\infty t^{q-1}e^{-t^2/2}\,dt=q2^{q/2}\Gamma(q/2). E [ Z + q ] = q ∫ 0 ∞ t q − 1 P ( Z + ≥ t ) d t ≤ 2 q ∫ 0 ∞ t q − 1 e − t 2 /2 d t = q 2 q /2 Γ ( q /2 ) .
For q ≥ 1 q\ge1 q ≥ 1 , Minkowski’s inequality therefore yields
∥ m − 1 / 2 s max ( G ) ∥ q ≤ 1 + n m + ∥ Z + ∥ q m ≤ 1 + n m + c q m . \left\|m^{-1/2}s_{\max}(G)\right\|_q\le1+\sqrt{\frac{n}{m}}+\frac{\left\|Z_+\right\|_q}{\sqrt{m}}\le1+\sqrt{\frac{n}{m}}+\frac{c_q}{\sqrt{m}}. m − 1/2 s m a x ( G ) q ≤ 1 + m n + m ∥ Z + ∥ q ≤ 1 + m n + m c q .
For 0 < q < 1 0<q<1 0 < q < 1 , Jensen’s inequality reduces the claim to the case q = 1 q=1 q = 1 , for which c 1 = 2 π c_1=\sqrt{2\pi} c 1 = 2 π .
Proposition B.2 (Negative Moments of the Smallest Singular Value). Let p = ( m − n + 1 ) / 2 p=(m-n+1)/2 p = ( m − n + 1 ) /2 and 0 < q < 2 p 0<q<2p 0 < q < 2 p , and define
a n , m = n 2 − p Γ ( 3 / 2 ) Γ ( m / 2 + 1 / 2 ) p Γ ( n / 2 + 1 ) Γ ( p ) Γ ( p + 1 / 2 ) . a_{n,m}=\frac{n2^{-p}\Gamma(3/2)\Gamma(m/2+1/2)}{p\Gamma(n/2+1)\Gamma(p)\Gamma(p+1/2)}. a n , m = p Γ ( n /2 + 1 ) Γ ( p ) Γ ( p + 1/2 ) n 2 − p Γ ( 3/2 ) Γ ( m /2 + 1/2 ) . Then
E [ m q / 2 s min ( G ) − q ] ≤ C n , m , q min = 2 p 2 p − q ( m a n , m 1 / p ) q / 2 . \mathbb{E}\left[m^{q/2}s_{\min}(G)^{-q}\right]\le C^{\min}_{n,m,q}=\frac{2p}{2p-q}\left(ma_{n,m}^{1/p}\right)^{q/2}. E [ m q /2 s m i n ( G ) − q ] ≤ C n , m , q m i n = 2 p − q 2 p ( m a n , m 1/ p ) q /2 . Moreover, if n / m ≤ d < 1 n/m\le d<1 n / m ≤ d < 1 and m , n → ∞ m,n\to\infty m , n → ∞ proportionally, then, for all sufficiently large n n n ,
C n , m , q min ≤ C d , q min = 2 K d q , K d = ( e d 1 − 1 / ( 1 − d ) ( 1 − d ) 2 ) 1 / 2 . C^{\min}_{n,m,q}\le C^{\min}_{d,q}=2K_d^q,\qquad K_d=\left(\frac{ed^{1-1/(1-d)}}{(1-d)^2}\right)^{1/2}. C n , m , q m i n ≤ C d , q m i n = 2 K d q , K d = ( ( 1 − d ) 2 e d 1 − 1/ ( 1 − d ) ) 1/2 .
Proof. Let 0 ≤ λ 1 ≤ ⋯ ≤ λ n 0\le\lambda_1\le\cdots\le\lambda_n 0 ≤ λ 1 ≤ ⋯ ≤ λ n be the ordered eigenvalues of G G T GG^T G G T . From their joint density (Dumitriu and Edelman, [18 ] ), for c n , m c_{n,m} c n , m the ordered-density constant,
P ( λ 1 ≤ s ) ≤ c n , m c n − 1 , m + 1 ∫ 0 s λ p − 1 d λ = a n , m s p , \mathbb{P}(\lambda_1\le s)\le\frac{c_{n,m}}{c_{n-1,m+1}}\int_0^s\lambda^{p-1}\,d\lambda=a_{n,m}s^p, P ( λ 1 ≤ s ) ≤ c n − 1 , m + 1 c n , m ∫ 0 s λ p − 1 d λ = a n , m s p ,
where the displayed expression for a n , m a_{n,m} a n , m follows by simplifying the ratio of normalizing constants. Hence,
E [ λ 1 − q / 2 ] = q 2 ∫ 0 ∞ t q / 2 − 1 P ( λ 1 ≤ t − 1 ) d t ≤ q 2 ∫ 0 a n , m 1 / p t q / 2 − 1 d t + q 2 a n , m ∫ a n , m 1 / p ∞ t q / 2 − p − 1 d t = 2 p 2 p − q a n , m q / ( 2 p ) . \mathbb{E}\left[\lambda_1^{-q/2}\right]=\frac{q}{2}\int_0^\infty t^{q/2-1}\mathbb{P}(\lambda_1\le t^{-1})\,dt\le\frac{q}{2}\int_0^{a_{n,m}^{1/p}}t^{q/2-1}\,dt+\frac{q}{2}a_{n,m}\int_{a_{n,m}^{1/p}}^\infty t^{q/2-p-1}\,dt=\frac{2p}{2p-q}a_{n,m}^{q/(2p)}. E [ λ 1 − q /2 ] = 2 q ∫ 0 ∞ t q /2 − 1 P ( λ 1 ≤ t − 1 ) d t ≤ 2 q ∫ 0 a n , m 1/ p t q /2 − 1 d t + 2 q a n , m ∫ a n , m 1/ p ∞ t q /2 − p − 1 d t = 2 p − q 2 p a n , m q / ( 2 p ) .
Since s min ( G ) 2 = λ 1 s_{\min}(G)^2=\lambda_1 s m i n ( G ) 2 = λ 1 , multiplying by m q / 2 m^{q/2} m q /2 proves the first claim. Finally, the Stirling bounds for the Gamma function give
a n , m ≤ ( K d 2 m ) p n 1 / 2 p − 1 ⟹ C n , m , q min ≤ 2 p 2 p − q K d q , a_{n,m}\le\left(\frac{K_d^2}{m}\right)^p n^{1/2}p^{-1}\Longrightarrow C^{\min}_{n,m,q}\le\frac{2p}{2p-q}K_d^q, a n , m ≤ ( m K d 2 ) p n 1/2 p − 1 ⟹ C n , m , q m i n ≤ 2 p − q 2 p K d q ,
where the implications holds once p ≥ n p\ge\sqrt{n} p ≥ n , and the stated uniform constant follows once p ≥ q p\ge q p ≥ q .
From Theorem 2.1 . Propositions B.1 and B.2 give the constants
C n , m , q max = ( 1 + n m + c q m ) q ≤ C d , q max = ( 1 + d + c q ) q , c q = { ( q 2 q / 2 Γ ( q / 2 ) ) 1 / q , q ≥ 1 , 2 π , 0 < q < 1 , C^{\max}_{n,m,q}=\left(1+\sqrt{\frac{n}{m}}+\frac{c_q}{\sqrt{m}}\right)^q\le C^{\max}_{d,q}=(1+\sqrt{d}+c_q)^q,\qquad
c_q=
\begin{cases}
\left(q2^{q/2}\Gamma(q/2)\right)^{1/q}, & q\ge1,\\
\sqrt{2\pi}, & 0<q<1,
\end{cases} C n , m , q m a x = ( 1 + m n + m c q ) q ≤ C d , q m a x = ( 1 + d + c q ) q , c q = { ( q 2 q /2 Γ ( q /2 ) ) 1/ q , 2 π , q ≥ 1 , 0 < q < 1 ,
C n , m , q min = 2 p 2 p − q ( m a n , m 1 / p ) q / 2 ≤ C d , q min = 2 ( e d 1 − 1 / ( 1 − d ) ( 1 − d ) 2 ) q / 2 . C^{\min}_{n,m,q}=\frac{2p}{2p-q}\left(ma_{n,m}^{1/p}\right)^{q/2}\le C^{\min}_{d,q}=2\left(\frac{ed^{1-1/(1-d)}}{(1-d)^2}\right)^{q/2}. C n , m , q m i n = 2 p − q 2 p ( m a n , m 1/ p ) q /2 ≤ C d , q m i n = 2 ( ( 1 − d ) 2 e d 1 − 1/ ( 1 − d ) ) q /2 .
From Smoothed Complexity Theorems. For u , v > 0 u,v>0 u , v > 0 , t ≥ 0 t\ge0 t ≥ 0 , and r > 1 r>1 r > 1 , define
p = m − n + 1 2 n m ≤ d < 1 , M u , v = C d , 4 u max C d , 4 v min , Φ r ( t ) = log r ( 1 + log 2 ( 1 + t ) ) . p=\frac{m-n+1}{2}\qquad\frac{n}{m}\le d<1,\qquad M_{u,v}=\sqrt{C_{d,4u}^{\max}C_{d,4v}^{\min}},\qquad\Phi_r(t)=\log_r(1+\log_2(1+t)). p = 2 m − n + 1 m n ≤ d < 1 , M u , v = C d , 4 u m a x C d , 4 v m i n , Φ r ( t ) = log r ( 1 + log 2 ( 1 + t )) .
Define the auxiliary constants
C G D = σ − 2 L C d , 2 min + M 1 , 1 , C G D , r a d = σ − 4 L 2 C d , 4 min + 2 σ − 2 L M 1 , 2 + M 2 , 2 , C a c c = σ − 1 L C d , 1 min + M 1 / 2 , 1 / 2 , C C N M = 6.25 ⋅ 2 3 / 4 L H 1 / 2 ( Δ 1 / 4 σ − 3 / 2 C d , 3 / 2 min + 2 − 1 / 4 D 1 / 2 σ − 1 M 1 / 4 , 3 / 4 ) , C C N M , r a d = 8 ⋅ 2592 1 / 4 L H 1 / 2 [ Δ 1 / 4 σ − 3 / 2 ( σ − 3 / 2 L G 3 / 4 C d , 3 / 4 min + M 3 / 4 , 3 / 2 ) + 2 − 1 / 4 D 1 / 2 σ − 1 ( σ − 3 / 2 L G 3 / 4 M 1 / 4 , 3 / 2 + M 1 , 3 / 2 ) ] , C H y b , A = 2 L H 2 ( 4 L G 2 Δ 2 σ − 16 C d , 16 min + ( 4 Δ 2 + L G 2 D 4 ) σ − 12 M 2 , 8 + D 4 σ − 8 M 4 , 8 ) 1 / 2 , C H y b = ( 2 L G 2 σ − 4 C d , 4 min + 2 M 2 , 2 ) 1 / 2 ( log ( 1 + C H y b , A ) + 1 ) , C G N = σ − 4 L γ ˉ 2 C d , 4 min + σ − 2 ( L + γ ˉ 2 ) M 1 , 2 + M 2 , 2 , C G N , A r m i j o = 1 2 β π ( σ − 2 γ ˉ 2 C d , 2 min + M 1 , 1 + C G N 2 ( 1 − β ) ) , C G N , r a d = σ − 4 L 2 σ − 2 γ ˉ 2 C d , 4 min + σ − 4 ( L 2 + 2 L γ ˉ 2 ) M 1 , 3 + σ − 2 ( 2 L + γ ˉ 2 ) M 2 , 3 + M 3 , 3 . \begin{aligned}
C_{\mathrm{GD}}&=\sigma^{-2}LC_{d,2}^{\min}+M_{1,1},\\
C_{\mathrm{GD,rad}}&=\sigma^{-4}L^2C_{d,4}^{\min}+2\sigma^{-2}LM_{1,2}+M_{2,2},\\
C_{\mathrm{acc}}&=\sigma^{-1}\sqrt{L}C_{d,1}^{\min}+M_{1/2,1/2},\\
C_{\mathrm{CNM}}&=6.25\cdot2^{3/4}L_H^{1/2}\left(\Delta^{1/4}\sigma^{-3/2}C_{d,3/2}^{\min}+2^{-1/4}D^{1/2}\sigma^{-1}M_{1/4,3/4}\right),\\
C_{\mathrm{CNM,rad}}&=8\cdot2592^{1/4}L_H^{1/2}\left[\Delta^{1/4}\sigma^{-3/2}\left(\sigma^{-3/2}L_G^{3/4}C_{d,3/4}^{\min}+M_{3/4,3/2}\right)+2^{-1/4}D^{1/2}\sigma^{-1}\left(\sigma^{-3/2}L_G^{3/4}M_{1/4,3/2}+M_{1,3/2}\right)\right],\\
C_{\mathrm{Hyb,A}}&=2L_H^2\left(4L_G^2\Delta^2\sigma^{-16}C_{d,16}^{\min}+(4\Delta^2+L_G^2D^4)\sigma^{-12}M_{2,8}+D^4\sigma^{-8}M_{4,8}\right)^{1/2},\\
C_{\mathrm{Hyb}}&=\left(2L_G^2\sigma^{-4}C_{d,4}^{\min}+2M_{2,2}\right)^{1/2}\left(\log(1+C_{\mathrm{Hyb,A}})+1\right),\\
C_{\mathrm{GN}}&=\sigma^{-4}L\bar{\gamma}^2C_{d,4}^{\min}+\sigma^{-2}(L+\bar{\gamma}^2)M_{1,2}+M_{2,2},\\
C_{\mathrm{GN,Armijo}}&=\frac{1}{2\beta\pi}\left(\sigma^{-2}\bar{\gamma}^2C_{d,2}^{\min}+M_{1,1}+\frac{C_{\mathrm{GN}}}{2(1-\beta)}\right),\\
C_{\mathrm{GN,rad}}&=\sigma^{-4}L^2\sigma^{-2}\bar{\gamma}^2C_{d,4}^{\min}+\sigma^{-4}(L^2+2L\bar{\gamma}^2)M_{1,3}+\sigma^{-2}(2L+\bar{\gamma}^2)M_{2,3}+M_{3,3}.
\end{aligned} C GD C GD , rad C acc C CNM C CNM , rad C Hyb , A C Hyb C GN C GN , Armijo C GN , rad = σ − 2 L C d , 2 m i n + M 1 , 1 , = σ − 4 L 2 C d , 4 m i n + 2 σ − 2 L M 1 , 2 + M 2 , 2 , = σ − 1 L C d , 1 m i n + M 1/2 , 1/2 , = 6.25 ⋅ 2 3/4 L H 1/2 ( Δ 1/4 σ − 3/2 C d , 3/2 m i n + 2 − 1/4 D 1/2 σ − 1 M 1/4 , 3/4 ) , = 8 ⋅ 259 2 1/4 L H 1/2 [ Δ 1/4 σ − 3/2 ( σ − 3/2 L G 3/4 C d , 3/4 m i n + M 3/4 , 3/2 ) + 2 − 1/4 D 1/2 σ − 1 ( σ − 3/2 L G 3/4 M 1/4 , 3/2 + M 1 , 3/2 ) ] , = 2 L H 2 ( 4 L G 2 Δ 2 σ − 16 C d , 16 m i n + ( 4 Δ 2 + L G 2 D 4 ) σ − 12 M 2 , 8 + D 4 σ − 8 M 4 , 8 ) 1/2 , = ( 2 L G 2 σ − 4 C d , 4 m i n + 2 M 2 , 2 ) 1/2 ( log ( 1 + C Hyb , A ) + 1 ) , = σ − 4 L γ ˉ 2 C d , 4 m i n + σ − 2 ( L + γ ˉ 2 ) M 1 , 2 + M 2 , 2 , = 2 β π 1 ( σ − 2 γ ˉ 2 C d , 2 m i n + M 1 , 1 + 2 ( 1 − β ) C GN ) , = σ − 4 L 2 σ − 2 γ ˉ 2 C d , 4 m i n + σ − 4 ( L 2 + 2 L γ ˉ 2 ) M 1 , 3 + σ − 2 ( 2 L + γ ˉ 2 ) M 2 , 3 + M 3 , 3 .
The explicit bounds are given by
E [ K G D ε ( f W ) ] ≤ 1 + C G D log 1 ε , for p ≥ max { n , 4 } , E [ K G D , r a d ε ( f W ) ] ≤ 1 + C G D , r a d log 1 ε , for p ≥ max { n , 8 } , E [ K N A G ε ( f W ) ] ≤ 1 + C a c c log 2 ε , for p ≥ max { n , 2 } , E [ K C G ε ( f W ) ] ≤ 1 + C a c c 2 log 4 ε , for p ≥ max { n , 2 } , E [ K C N M ε ( f W ) ] ≤ 2 + C C N M + Φ 2 ( C d , 6 max σ 6 2 L H 2 ε ) , for p ≥ max { n , 3 } , E [ K C N M , r a d ε ( f W ) ] ≤ 2 + C C N M , r a d + Φ 4 / 3 ( C d , 6 max σ 6 2592 L H 2 ε ) , for p ≥ max { n , 6 } , E [ K H y b ε ( f W ) ] ≤ 3 + C H y b + Φ 2 ( C d , 6 max σ 6 2 L H 2 ε ) , for p ≥ max { n , 32 } , E [ K G N C o n v e x ε ( f W ) ] ≤ 1 + C G N log 1 ε , for p ≥ max { n , 8 } , E [ K G N C o n v e x A r m i j o ε ( f W ) ] ≤ 1 + C G N , A r m i j o log 1 ε , for p ≥ max { n , 8 } , E [ K G N , r a d ε ( f W ) ] ≤ 1 + C G N , r a d log 1 ε , for p ≥ max { n , 12 } . \begin{aligned}
\mathbb{E}\left[\mathrm{K}^{\varepsilon}_{\mathrm{GD}}(f_W)\right]&\le1+C_{\mathrm{GD}}\log\frac{1}{\varepsilon}, &&\text{for }p\ge\max\{\sqrt{n},4\},\\
\mathbb{E}\left[\mathrm{K}^{\varepsilon}_{\mathrm{GD,rad}}(f_W)\right]&\le1+C_{\mathrm{GD,rad}}\log\frac{1}{\varepsilon}, &&\text{for }p\ge\max\{\sqrt{n},8\},\\
\mathbb{E}\left[\mathrm{K}^{\varepsilon}_{\mathrm{NAG}}(f_W)\right]&\le1+C_{\mathrm{acc}}\log\frac{2}{\varepsilon}, &&\text{for }p\ge\max\{\sqrt{n},2\},\\
\mathbb{E}\left[\mathrm{K}^{\varepsilon}_{\mathrm{CG}}(f_W)\right]&\le1+\frac{C_{\mathrm{acc}}}{2}\log\frac{4}{\varepsilon}, &&\text{for }p\ge\max\{\sqrt{n},2\},\\
\mathbb{E}\left[\mathrm{K}^{\varepsilon}_{\mathrm{CNM}}(f_W)\right]&\le2+C_{\mathrm{CNM}}+\Phi_2\left(\frac{C_{d,6}^{\max}\sigma^6}{2L_H^2\varepsilon}\right), &&\text{for }p\ge\max\{\sqrt{n},3\},\\
\mathbb{E}\left[\mathrm{K}^{\varepsilon}_{\mathrm{CNM,rad}}(f_W)\right]&\le2+C_{\mathrm{CNM,rad}}+\Phi_{4/3}\left(\frac{C_{d,6}^{\max}\sigma^6}{2592L_H^2\varepsilon}\right), &&\text{for }p\ge\max\{\sqrt{n},6\},\\
\mathbb{E}\left[\mathrm{K}^{\varepsilon}_{\mathrm{Hyb}}(f_W)\right]&\le3+C_{\mathrm{Hyb}}+\Phi_2\left(\frac{C_{d,6}^{\max}\sigma^6}{2L_H^2\varepsilon}\right), &&\text{for }p\ge\max\{\sqrt{n},32\},\\
\mathbb{E}\left[\mathrm{K}^{\varepsilon}_{\mathrm{GNConvex}}(f_W)\right]&\le1+C_{\mathrm{GN}}\log\frac{1}{\varepsilon}, &&\text{for }p\ge\max\{\sqrt{n},8\},\\
\mathbb{E}\left[\mathrm{K}^{\varepsilon}_{\mathrm{GNConvexArmijo}}(f_W)\right]&\le1+C_{\mathrm{GN,Armijo}}\log\frac{1}{\varepsilon}, &&\text{for }p\ge\max\{\sqrt{n},8\},\\
\mathbb{E}\left[\mathrm{K}^{\varepsilon}_{\mathrm{GN,rad}}(f_W)\right]&\le1+C_{\mathrm{GN,rad}}\log\frac{1}{\varepsilon}, &&\text{for }p\ge\max\{\sqrt{n},12\}.
\end{aligned} E [ K GD ε ( f W ) ] E [ K GD , rad ε ( f W ) ] E [ K NAG ε ( f W ) ] E [ K CG ε ( f W ) ] E [ K CNM ε ( f W ) ] E [ K CNM , rad ε ( f W ) ] E [ K Hyb ε ( f W ) ] E [ K GNConvex ε ( f W ) ] E [ K GNConvexArmijo ε ( f W ) ] E [ K GN , rad ε ( f W ) ] ≤ 1 + C GD log ε 1 , ≤ 1 + C GD , rad log ε 1 , ≤ 1 + C acc log ε 2 , ≤ 1 + 2 C acc log ε 4 , ≤ 2 + C CNM + Φ 2 ( 2 L H 2 ε C d , 6 m a x σ 6 ) , ≤ 2 + C CNM , rad + Φ 4/3 ( 2592 L H 2 ε C d , 6 m a x σ 6 ) , ≤ 3 + C Hyb + Φ 2 ( 2 L H 2 ε C d , 6 m a x σ 6 ) , ≤ 1 + C GN log ε 1 , ≤ 1 + C GN , Armijo log ε 1 , ≤ 1 + C GN , rad log ε 1 , for p ≥ max { n , 4 } , for p ≥ max { n , 8 } , for p ≥ max { n , 2 } , for p ≥ max { n , 2 } , for p ≥ max { n , 3 } , for p ≥ max { n , 6 } , for p ≥ max { n , 32 } , for p ≥ max { n , 8 } , for p ≥ max { n , 8 } , for p ≥ max { n , 12 } .