Source-linked AI summary
A Simple Complexity Lower Bound for Solving $Ax=b$
Ohad Shamir
TL;DR
The note addresses the query complexity of solving linear systems and the need for a simpler proof of an existing randomized lower bound. It gives a short, direct proof strategy and shows that the theorem also yields a lower bound for strongly convex quadratic optimization.
Problem
A fundamental problem in linear algebra already has a randomized worst-case lower bound, but its proof uses sophisticated machinery and imported intermediate results.
Source: §1 · p. 1Method
Results
Theorem 1 establishes a worst-case query lower bound for possibly randomized algorithms, and its reduction gives an Ω(√κ log(1/ε)) gradient/value lower bound for strongly convex quadratics.
Source: §2 · pp. 2–3Takeaways & Limitations
The lower bound holds even for symmetric matrices with the specified spectrum, with D revealed and a more powerful oracle available.
Source: §2 · p. 2The result is an oracle-query bound in a model where algorithms observe b and access A through matrix-vector products.
Source: §2 · p. 2
Abstract
from arXiv · showhide
In this note, we provide a short and direct proof that approximately solving $Ax=b$ to relative error $\varepsilon$, where $A$ has condition number $\kappa$ and unrestricted dimension, requires $\Omega(\kappa\log(1/\varepsilon))$ matrix-vector multiplications in the worst case, even for randomized algorithms. This essentially recovers the lower bound of Derezi\'nski, Epperly and Meyer [2026] for this setting, whose elegant and more general approach inspired us to seek a short direct proof. A straightforward reduction implies the classical $\Omega(\sqrt{\kappa}\log(1/\varepsilon))$ lower bound for optimizing strongly convex quadratic functions, applicable to randomized algorithms.
1 Introduction
The note seeks a short, relatively self-contained proof of a randomized worst-case lower bound for solving linear systems, building on Derezi´nski et al. [2026]. Its proof uses polynomial inapproximability and random orthogonal rotations.
1 Introduction
- Derezi´nski et al. [2026] established an essentially optimal Ω(κ log(1/ε)) worst-case matrix-vector lower bound, including for randomized algorithms.Their bound matches, up to constants, the complexity of conjugate gradient applied to the normal equations.Source: §1 · p. 1
- The earlier lower-bound proof uses sophisticated machinery, including trace-inverse estimation, Wishart matrices, and information inequalities, and relies on intermediate results from other papers.The note describes a simpler proof as useful for this fundamental problem.Source: §1 · p. 1
- The note aims to give a short, mostly self-contained proof using standard approximation theory, elementary probability, and a concentration-of-measure result.The authors do not claim particular novelty and borrow ideas from earlier work.Source: §1 · p. 1
- The proof uses polynomial inapproximability and random orthogonal matrices to encode rotations that limited matrix-vector queries cannot reveal.The authors say their details differ from earlier work, yielding a compact and direct proof.Source: §1 · p. 2
- The author reports that ChatGPT contributed ideas, proof strategies, and drafts, and that the author revised and checked the final write-up.The author takes full responsibility for the final text.Source: §1 · p. 2
2 Setup and Main Result
The section specifies an oracle model and states a lower bound for solving linear systems, with a reduction to strongly convex quadratic optimization. The result holds under additional restrictions on the matrices and oracle.
2 Setup and Main Result
- In the oracle model, the algorithm observes b, adaptively chooses query vectors, and receives (Ax, A⊤x), with unrestricted computation and dimension.Source: §2 · p. 2
- For κ≥C and 0<ε≤c, Theorem 1 requires a worst-case minimum number of oracle queries even for possibly randomized algorithms.The guarantee is required for every b and every A with condition number at most κ.Source: §2 · p. 2
- The lower bound holds for symmetric A with spectrum in [−κ, −1] ∪ [1, κ], even when D is revealed and the algorithm receives a more powerful oracle.The section also says restricting A to symmetric matrices loses nothing for proving a lower bound.Source: §2 · p. 2
- The lower bound already holds in dimension n=Ω(T^2).Source: §2 · p. 2
- The theorem implies an Ω(√κ log(1/ε)) lower bound on gradient/value evaluations for strongly convex quadratic optimization, including randomized algorithms.Here κ is the Hessian condition number.Source: §2 · p. 3
- A first-order gradient/value oracle for the quadratic functions can be simulated using two products with A; for symmetric A, cond(A^2)=cond(A)^2.The function value is obtained from the residual after computing Ax.Source: §2 · p. 3
3 Proof of Thm. 1
The proof combines low-degree polynomial inapproximability with a random orthogonal rotation that hides information from limited oracle queries. It concludes that, under the stated conditions, solving to relative error ε requires a query budget on the order of κ log(1/ε), even for randomized algorithms.
3 Proof of Thm. 1
- The proof uses a randomized construction with a uniform orthogonal U and a fixed diagonal D, then applies Yao’s minimax principle to extend failure against deterministic algorithms to randomized ones.The construction encodes low-degree polynomial inapproximability in D and a hidden rotation in U.Source: §3 · p. 3
3.1 Step 1: Standard Polynomial Inapproximability Results
- Step 1 uses Chebyshev extremality to bound low-degree polynomial approximation and represents the obstruction using at most d+1 weighted spectral points.The weighted formulation captures an inapproximability result for average error as well as maximal error.Source: §3.1 · p. 4
3.2 Step 2: A Random Orthogonal U Hides Information
- Conditioned on how a uniform orthogonal map acts on a subspace, its action on the orthogonal complement remains uniformly random.This lets the proof argue that the oracle responses reveal information about U only on the queried subspace.Source: §3.2 · p. 5
3.3 Step 3: Construction and Proof of Theorem 1
- The hard distribution sets A = UDU^T with U uniform and b an independent standard Gaussian vector.The proof uses chi-square concentration to control projected Gaussian norms with probability at least 0.9.Source: §3.3 · p. 8
- For sufficiently small ε and sufficiently large n, any T ≤ (κ/3) log(1/ε) fails to return an ε-optimal solution with constant probability under the construction.Yao’s minimax principle yields the lower bound for randomized algorithms.Source: §3.3 · p. 9