On the Randomized Complexity of Minimizing a Convex Quadratic Function

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.