On the Randomized Complexity of Minimizing a Convex Quadratic Function

Abstract

Minimizing a convex, quadratic objective of the form $f_{\mathbf{A},\mathbf{b}}(x):=\frac{1}{2}{x}^{\top }\mathbf{A}x-⟨\mathbf{b},x⟩$ for $\mathbf{A}\succ 0$ is a fundamental problem in machine learning and optimization. In this work, we prove gradient-query complexity lower bounds for minimizing convex quadratic functions which apply to both deterministic and \emph{randomized} algorithms. Specifically, for $\kappa >1$, we exhibit a distribution over $(\mathbf{A},\mathbf{b})$ with condition number $\mathrm{cond}(\mathbf{A})\le \kappa$, such that any \emph{randomized} algorithm requires $\Omega (\sqrt{\kappa })$ gradient queries to find a solution $\hat{x}$ for which $\Vert \hat{x}-{\mathbf{x}}_{\star }\Vert \le {\epsilon }_0\Vert {\mathbf{x}}_{\star }\Vert$, where ${\mathbf{x}}_{\star }={\mathbf{A}}^{-1}\mathbf{b}$ is the optimal solution, and ${\epsilon }_0$ a small constant. Setting $\kappa =1/\epsilon$, this lower bound implies the minimax rate of $T=\Omega ({\lambda }_1(\mathbf{A})\Vert {\mathbf{x}}_{\star }{\Vert }^2/\sqrt{\epsilon })$ queries required to minimize an arbitrary convex quadratic function up to error $f(\hat{x})-f({\mathbf{x}}_{\star })\le \epsilon$. Our lower bound holds for a distribution derived from classical ensembles in random matrix theory, and relies on a careful reduction from adaptively estimating a planted vector $\mathbf{u}$ in a deformed Wigner model. A key step in deriving sharp lower bounds is demonstrating that the optimization error ${\mathbf{x}}_{\star }-\hat{x}$ cannot align too closely with $\mathbf{u}$. To this end, we prove an upper bound on the cosine between ${\mathbf{x}}_{\star }-\hat{x}$ and $\mathbf{u}$ in terms of the MMSE of estimating the plant $\mathbf{u}$ in a deformed Wigner model. We then bound the MMSE by carefully modifying a result due to Lelarge and Miolane 2016, which rigorously establishes a general replica-symmetric formula for planted matrix models.

References in corpus (7)

• The largest eigenvalue of rank one deformation of large Wigner matrices
• MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel
• Mutual Information in Rank-One Matrix Estimation
• Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation
• First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate
• Lower Bounds for Higher-Order Convex Optimization
• Optimal lower bounds for universal relation, samplers, and finding duplicates

Cited by in corpus (8)

• Is Local SGD Better than Minibatch SGD?
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
• Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex Functions?
• The gradient complexity of linear regression
• Oracle Complexity in Nonsmooth Nonconvex Optimization
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
• The Minimax Complexity of Distributed Optimization
• Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales