betaFeedback

WorksMathematics

From Worst-Case to Smoothed Complexity in Continuous Optimization

Abstract

Worst-case complexity bounds often fail to reflect the practical performance of optimization algorithms, while average-case complexity heavily relies on the distribution of the input. In this work, we develop a smoothed-analysis framework for classical continuous optimization algorithms by studying their behaviour on random perturbations of arbitrary functions. Our main contribution is to apply methods suited for non-degenerate functions to perturbations of degenerate functions, thereby recovering the faster best-known rates for the non-degenerate class. We derive smoothed complexity guarantees for several standard methods, including (Accelerated) Gradient Descent, Conjugate Gradient, and Newton-type methods, under various settings including nonconvex ones, and show that these bounds can substantially improve upon their worst-case guarantees, bringing them closer to the practical behaviour of the respective methods.

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), required by a given algorithm to converge to an ε\varepsilon-optimal point for a problem characterized by a mapping ff. 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) that remains valid uniformly for all instances f∈Ff \in\mathcal{F} within a specified problem class F\mathcal{F} [31, 51, 34, 7, 53].

Even when these upper bounds are tight, meaning there exists a problem within F\mathcal{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 Ef∼D[Kε(f)]\mathbb{E}_{f\sim\mathcal{D}}[K^\varepsilon(f)], where D\mathcal{D} is a probability distribution over F\mathcal{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(n2)\mathcal{O}(n^2), has average-case complexity O(nlog⁡n)\mathcal{O}(n\log n) [23], that quickselect has worst-case complexity O(n2)\mathcal{O}(n^2) yet average-case complexity O(n)\mathcal{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}, we consider the smoothed complexity measure

sup⁡f∈FEW[Kε(fW)]\sup_{f\in\mathcal{F}}\mathbb{E}_{W}\left[\mathsf{K}^{\varepsilon}(f_W)\right]

of the function class F\mathcal{F}, where given f:Rn→R∈Ff:\mathbb{R}^{n}\to\mathbb{R}\in\mathcal{F}, fWf_W denotes a random perturbation of the function ff. This notion will be formalized in § 3.

The smoothed complexity count sup⁡f∈FEW[Kε(fW)]\sup_{f\in\mathcal{F}}\mathbb{E}_{W}\left[\mathsf{K}^{\varepsilon}(f_W)\right] interpolates between the worst-case and average-case analysis: an adversary first chooses a function f∈Ff\in\mathcal{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, whereas strongly convex functions improve this to log⁡(1/ε)\log(1/\varepsilon). 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>1b > 1, log⁡b,+(x)=log⁡b(x)\log_{b,+}(x) = \log_b(x) if x≥1x \ge1 and 0 otherwise. We note that log⁡b,+(x)≤log⁡b(1+x)\log_{b,+}(x) \le\log_b(1 + x) for all x≥0x \ge0.

Random Matrix Theory Preliminaries

Consider a random real n×mn \times m Gaussian matrix GG (with entries independently following the standard normal distribution), and let W=1mGGTW = \frac{1}{m}GG^{T} be a real n×nn \times n Wishart matrix with parameter mm. We place ourselves in the setting of proportional growth, in which the parameters mm and nn grow proportionally with n/m→d∈(0,1)n/m \to d \in(0,1). We assume this limit is taking place from the left, so that n/m≤dn/m \le d holds for all (n,m)(n,m). We note that this corresponds to the overparametrized model, such that WW is almost surely nonsingular. For a fixed nn, as d→0d \to0, we must have m→∞m \to\infty, corresponding to the infinitely overparametrized setting.

The results in this paper reduce to the study of the extreme eigenvalues of WW, denoted by λmin⁡(W)\lambda_{\min}(W) and λmax⁡(W)\lambda_{\max}(W). Equivalently, we study the extreme singular values of GG, denoted by smin⁡(G)s_{\min}(G) and smax⁡(G)s_{\max}(G), linked to the extreme eigenvalues of WW through the relations

λmin⁡(W)=smin⁡(G)2mandλmax⁡(W)=smax⁡(G)2m.\lambda_{\min}(W) = \frac{s_{\min}(G)^2}{m} \quad\text{and} \quad\lambda_{\max}(W) = \frac{s_{\max}(G)^2}{m}.

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>0q > 0, there exists constants Cq,dmax⁡C^{\max}_{q,d} and Cd,qmin⁡C^{\min}_{d,q} so that, for m,nm,n sufficiently large,

E[smax⁡(G)qm−q/2]≤Cd,qmax⁡andE[smin⁡(G)−qmq/2]≤Cd,qmin⁡.\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}.

Smoothed Analysis Results

In this paper, we consider the smoothed complexity measure over a function class F\mathcal{F} given by

sup⁡f∈FEW[Kε(fW)],where fW(x)=f(x)+σ22(x−x~)TW(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)}

where f:Rn→R∈Ff:\mathbb{R}^{n}\to\mathbb{R}\in\mathcal{F} is a function belonging to the function class F\mathcal{F}, and fWf_{W} is a perturbation of the function ff characterized by the scaling parameter σ\sigma, a given center x~\tilde{x} and the random Wishart matrix W=1mGGTW=\frac{1}{m}GG^{T}.1 The scaling parameter σ\sigma plays the role of the variance of the random matrix WW. We note that σ\sigma, x0x_{0} and x~\tilde{x} are fixed before drawing WW, and are fixed accross the supremum.

All of our guarantees will concern optimization of the perturbed objective fWf_{W}. When ff has a minimizer x∗x_{*}, guarantees on fWf_{W} are linked to guarantees on ff through

f(x)−min⁡f≤δ+σ22(x∗−x~)TW(x∗−x~),f(x)-\min f\leq\delta+\frac{\sigma^{2}}{2}(x_{*}-\tilde{x})^{T}W(x_{*}-\tilde{x}),

where fW(x)−min⁡fW≤δf_{W}(x)-\min f_{W}\leq\delta. Thus, the improved regularity comes with a perturbation bias.

For convex LL-smooth ff, it holds that fWf_{W} is μσ\mu_{\sigma}-strongly convex and LσL_{\sigma}-smooth, for

μσ=σ2λmin⁡(W)=σ2smin⁡(G)2mandLσ=L+σ2λmax⁡(W)=L+σ2smax⁡(G)2m.(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)}

For D2=∥x0−x~∥2D^{2}=\lVert x_{0}-\tilde{x}\rVert^{2} and Δ=f(x0)−inf⁡f\Delta=f(x_{0})-\inf f,

fW(x0)−inf⁡fW≤Δσ=Δ+σ2D2λmax⁡(W)2=Δ+σ2D2smax⁡(G)22m.(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)}

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 fWf_{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} of μ\mu-strongly convex and LL-smooth functions, with the convention that μ=0\mu=0 corresponds to the convex bounded-below setting F0L⊃FμL\mathcal{F}_{0}^{L}\supset\mathcal{F}_{\mu}^{L}. For h∈FμLh\in\mathcal{F}_{\mu}^{L}, we consider, for x0∈Rnx_{0}\in\mathbb{R}^{n} and k≥0k\geq0,

xk+1=xk−1L∇h(xk).x_{k+1}=x_{k}-\frac{1}{L}\nabla h(x_{k}).

We measure complexity in terms of relative function value accuracy, namely, for ε∈(0,1)\varepsilon\in(0,1),

References

  1. [1]Anagnostides, I. and Sandholm, T. (2024). Convergence of $\text{log}(1/\epsilon)$ for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis. In The Thirty-Eighth Annual Conference on Neural Information Processing Systems.arxiv.org/abs/2410.21636
  2. [2]Bai, Z. D. and Yin, Y. Q. (1993). Limit of the Smallest Eigenvalue of a Large Dimensional Sample Covariance Matrix. The Annals of Probability, 21(3):1275–1294.
  3. [3]Benning, P. and Döring, L. (2024). Gradient Span Algorithms Make Predictable Progress in High Dimension. arXiv preprint arXiv:2410.09973.arxiv.org/abs/2410.09973
  4. [4]Borgwardt, K.-H. (1982). Some Distribution-Independent Results about the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method. Mathematics of Operations Research, 7(3):441–462.DOI
  5. [5]Cartis, C., Gould, N. I. M., and Toint, P. L. (2011). Adaptive cubic regularisation methods for unconstrained optimization. Part I: Motivation, convergence and numerical results. Mathematical Programming, 127(2):245–295.
  6. [6]Cartis, C., Gould, N. I. M., and Toint, P. L. (2013). On the Evaluation Complexity of Cubic Regularization Methods for Potentially Rank-Deficient Nonlinear Least-Squares Problems and Its Relevance to Constrained Nonlinear Optimization. SIAM Journal on Optimization, 23(3):1553–1574.DOI
  7. [7]Cartis, C., Gould, N. I. M., and Toint, P. L. (2022). Evaluation Complexity of Algorithms for Nonconvex Optimization: Theory, Computation and Perspectives. MOS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics.DOI
  8. [8]Cauchy, A. (1847). Méthode générale pour la résolution des systemes d’équations simultanées. Comp. Rend. Sci. Paris, 25(1847):536–538.
  9. [9]Chiani, M. (2014). Distribution of the largest eigenvalue for real Wishart and Gaussian random matrices and a simple approximation for the Tracy–Widom distribution. Journal of Multivariate Analysis, 129:69–81.DOI
  10. [10]Coester, C. and Umenberger, J. (2025). Smoothed Analysis of Online Metric Problems. arXiv preprint arXiv:2507.17834.arxiv.org/abs/2507.17834
  11. [11]Cortild, D. and Cartis, C. (2026). Quadratic Objective Perturbation: Curvature-Based Differential Privacy. arXiv preprint arXiv:2605.05905.arxiv.org/abs/2605.05905
  12. [12]Cortild, D., Cartis, C., and Peypouquet, J. (2026). Stochastic Krasnoselskii-Mann Iterations: Convergence without Uniformly Bounded Variance. arXiv preprint arXiv:2604.22581.arxiv.org/abs/2604.22581
  13. [13]Cunha, L., Gidel, G., Pedregosa, F., Scieur, D., and Paquette, C. (2022). Only tails matter: Average-Case Universality and Robustness in the Convex Regime. In Proceedings of the 39th International Conference on Machine Learning, pages 4474–4491. PMLR.arxiv.org/abs/2206.09901
  14. [14]Dadush, D. and Huiberts, S. (2020). A Friendly Smoothed Analysis of the Simplex Method. SIAM Journal on Computing, 49(5):STOC18–449–STOC18–499.
  15. [15]Davidson, K. R. and Szarek, S. J. (2001). Local Operator Theory, Random Matrices and Banach Spaces. In Handbook of the Geometry of Banach Spaces, volume 1, pages 317–366. Elsevier Science B.V.DOI
  16. [16]Deift, P. and Trogdon, T. (2021). The conjugate gradient algorithm on well-conditioned Wishart matrices is almost deterministic. Quarterly of Applied Mathematics, 79(1):125–161.arxiv.org/abs/1901.09007
  17. [17]Ding, X. and Trogdon, T. (2021). The conjugate gradient algorithm on a general class of spiked covariance matrices. Quarterly of Applied Mathematics, 80(1):99–155.arxiv.org/abs/2106.13902
  18. [18]Dumitriu, I. and Edelman, A. (2002). Matrix models for beta ensembles. Journal of Mathematical Physics, 43(11):5830–5847.
  19. [19]Edelman, A. and Sutton, B. D. (2005). Tails of Condition Number Distributions. SIAM Journal on Matrix Analysis and Applications, 27(2):547–560.DOI
  20. [20]Ergür, A. A., Paouris, G., and Rojas, J. M. (2019). Probabilistic Condition Number Estimates for Real Polynomial Systems I: A Broader Family of Distributions. Found. Comput. Math., 19(1):131–157.DOI
  21. [21]Hestenes, M. R., Stiefel, E., et al. (1952). Methods of conjugate gradients for solving linear systems. Journal of research of the National Bureau of Standards, 49(6):409–436.DOI
  22. [22]Hoare, C. A. R. (1961). Algorithm 65: Find. Communications of the ACM, 4(7):321–322.DOI
  23. [23]Hoare, C. A. R. (1962). Quicksort. The Computer Journal, 5(1):10–16.DOI
  24. [24]Huang, H. and Tikhomirov, K. (2020). A remark on the smallest singular value of powers of Gaussian matrices. arXiv preprint arXiv:1910.03702.arxiv.org/abs/1910.03702
  25. [25]Johnstone, I. M. (2001). On the distribution of the largest eigenvalue in principal components analysis. The Annals of Statistics, 29(2):295–327.DOI
  26. [26]Karimi, H., Nutini, J., and Schmidt, M. (2020). Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition. arXiv preprint arXiv:1608.04636.
  27. [27]Lee, K., Cheng, A. N., Paquette, E., and Paquette, C. (2022). Trajectory of Mini-Batch Momentum: Batch Size Saturation and Convergence in High Dimensions. In Advances in Neural Information Processing Systems.arxiv.org/abs/2206.01029
  28. [28]Manthey, B. (2020). Smoothed Analysis of Local Search. In Roughgarden, T., editor, Beyond the Worst-Case Analysis of Algorithms, pages 285–308. Cambridge University Press, 1 edition.DOI
  29. [29]Marshall, N., Xiao, K. L., Paquette, E., and Agarwala, A. (2025). To Clip or not to Clip: The Dynamics of SGD with Gradient Clipping in High-Dimensions. In International Conference on Learning Representations.arxiv.org/abs/2406.11733
  30. [31]Nemirovsky, A. S. and Yudin, D. B. (1983). Problem Complexity and Method Efficiency in Optimization. Wiley.DOI
  31. [32]Nesterov, Y. (1983). A method for solving the convex programming problem with convergence rate O(1/k²). Soviet Mathematics Doklady, 269:543.
  32. [33]Nesterov, Y. (2003). Modified Gauss-Newton Scheme with Worst-Case Guarantees for its Global Performance.
  33. [34]Nesterov, Y. (2018). Lectures on Convex Optimization, volume 137 of Springer Optimization and Its Applications. Springer International Publishing.DOI
  34. [35]Nesterov, Y. and Polyak, B. (2006). Cubic regularization of Newton method and its global performance. Mathematical Programming, 108(1):177–205.DOI
  35. [36]Nesterov, Yu. (2008). Accelerating the cubic regularization of Newton’s method on convex problems. Mathematical Programming, 112(1):159–181.DOI
  36. [37]Nocedal, J. and Wright, S. J. (2006). Numerical Optimization. Springer Series in Operations Research. Springer.
  37. [38]Paquette, C., Lee, K., Pedregosa, F., and Paquette, E. (2021). SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality. In Proceedings of Thirty Fourth Conference on Learning Theory, pages 3548–3626. PMLR.arxiv.org/abs/2102.04396
  38. [39]Paquette, C. and Paquette, E. (2021). Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models. In Advances in Neural Information Processing Systems, volume 34, pages 9229–9240. Curran Associates, Inc.arxiv.org/abs/2106.03696
  39. [40]Paquette, C., van Merriënboer, B., Paquette, E., and Pedregosa, F. (2023). Halting Time is Predictable for Large Models: A University Property and Average-Case Analysis. Foundations of Computational Mathematics, 23(2):597–673.arxiv.org/abs/2006.04299
  40. [41]Paquette, E. and Trogdon, T. (2023). Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices. Communications on Pure and Applied Mathematics, 76(5):1085–1136.arxiv.org/abs/2007.00640
  41. [42]Pedregosa, F. and Scieur, D. (2020). Average-Case Acceleration Through Spectral Density Estimation. In Proceedings of the 37th International Conference on Machine Learning, pages 7553–7562. PMLR.arxiv.org/abs/2002.04756
  42. [43]Rudelson, M. and Vershynin, R. (2009). The smallest singular value of a random rectangular matrix. arXiv preprint arXiv:0802.3956.arxiv.org/abs/0802.3956
  43. [44]Rudelson, M. and Vershynin, R. (2010). Non-asymptotic theory of random matrices: Extreme singular values. arXiv preprint arXiv:1003.2990.arxiv.org/abs/1003.2990
  44. [45]Röglin, H. (2020). Smoothed Analysis of Pareto Curves in Multiobjective Optimization. In Roughgarden, T., editor, Beyond the Worst-Case Analysis of Algorithms, pages 334–358. Cambridge University Press, 1 edition.arxiv.org/abs/2010.11064
  45. [46]Sarkar, P., Khare, K., and Srivastava, S. (2026). Moment bounds for condition numbers and singular values of high-dimensional Gaussian random matrices: Applications and limitations. arXiv preprint arXiv:2602.21487.arxiv.org/abs/2602.21487
  46. [47]Scieur, D. and Pedregosa, F. (2020). Universal Average-Case Optimality of Polyak Momentum. In Proceedings of the 37th International Conference on Machine Learning, pages 8565–8572. PMLR.arxiv.org/abs/2002.04664
  47. [48]Spielman, D. A. and Teng, S.-H. (2004). Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3):385–463.
  48. [49]Taylor, A. B., Hendrickx, J. M., and Glineur, F. (2017). Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods. Mathematical Programming, 161(1):307–345.arxiv.org/abs/1502.05666
  49. [50]Trefethen, L. N. and Bau, Iii, D. (1997). Numerical Linear Algebra. Society for Industrial and Applied Mathematics.
  50. [51]Vavasis, S. A. (1991). Nonlinear Optimization: Complexity Issues. Oxford University Press, Inc.
  51. [52]Vershynin, R. (2018). High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press.
  52. [53]Wright, S. J. and Recht, B. (2022). Optimization for Data Analysis. Cambridge University Press, 1 edition.DOI

Paper details

vlnc:W_ea455ke2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents