On the Randomized Complexity of Minimizing a Convex Quadratic Function

By Max Simchowitz. 2018

12 citations recorded by the source corpus.

Minimizing a convex, quadratic objective is a fundamental problem in machine learning and optimization. In this work, we study prove information-theoretic, gradient query complexity lower bounds for minimizing convex quadratic functions, which, unlike prior works, apply even for randomized algorithms. Specifically, we construct a distribution over quadratic functions that witnesses lower bounds which match those known for deterministic algorithms, up to multiplicative constants. The distribution which witnesses our lower bound is in fact quite benign: it is both closed form, and derived from classical ensembles in random matrix theory. We believe that our construction constitutes a plausible "average case" setting, and thus provides compelling evidence that the worst case and average case complexity of convex-quadratic optimization are essentially identical.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Is Local SGD Better than Minibatch SGD? (2020, background): “In addition, Simchowitz (2018) shows that any randomized algorithm that accesses an deterministic ﬁrst order oracle at most T times will have error at least cHB 2 T 2 in the worst case for an H -smooth, convex quadratic objective, for some universal constant c .”