# On the Randomized Complexity of Minimizing a Convex Quadratic Function

arXiv: https://arxiv.org/abs/1807.09386 · HTML: https://mlsanity.com/paper/1807.09386/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jul 2018.

## Built on by (most cited first, 5 of 5)

- [Oracle Complexity in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2104.06763/) (2021)
- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (2022)
- [The Minimax Complexity of Distributed Optimization](https://mlsanity.com/paper/2109.00534/) (2021)
- [Accelerated Gradient Algorithms with Adaptive Subspace Search for Instance-Faster Optimization](https://mlsanity.com/paper/2312.03218/) (2023)

## Abstract (arXiv)

Minimizing a convex, quadratic objective of the form fA,b(x) := frac12x^top A x - langle b, x rangle for 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 randomized algorithms. Specifically, for kappa > 1, we exhibit a distribution over (A,b) with condition number cond(A) ≤ kappa, such that any randomized algorithm requires Omega(√kappa) gradient queries to find a solution hat x for which |hat x - mathbf x_star| ≤ ε0|xstar|, where mathbf xstar = A-1b is the optimal solution, and ε0 a small constant. Setting kappa =1/ε, this lower bound implies the minimax rate of T = Omega(λ1(A)|mathbf x_star|2/√ε) queries required to minimize an arbitrary convex quadratic function up to error f(hatx) - f(mathbf x_star) ≤ ε. 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 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.