From smoothed analysis to backward error: The power of adaptive perturbations

Michał Dereziński, Michael W. Mahoney, Raphael A. Meyer, Christopher MuscoarXiv 2026 · arXiv

TL;DR

This paper reveals an exponential gap between "smoothed analysis" (oblivious random perturbations) and "backward error" (adaptive perturbations) for solving linear systems. While oblivious perturbations fail to improve worst-case complexity, adaptive randomized perturbations allow for exponentially faster solvers, though symmetry is required to achieve similar gains deterministically.

What Problem Does This Paper Address?

In theoretical computer science, smoothed analysis is a popular framework for explaining why certain algorithms perform well in practice despite poor worst-case guarantees. The idea is to analyze an algorithm's performance on a problem instance that has been slightly nudged by random noise. In numerical analysis, this is closely related to backward error: instead of solving $Ax=b$ exactly, we find a solution $\tilde{x}$ that exactly solves a nearby problem $(A + \Delta)\tilde{x} = b$.

The central question this paper tackles is: Are these two concepts quantitatively the same?

Specifically, if we want to solve a linear system to a small backward error $\epsilon$, does it matter if the perturbation $\Delta$ is chosen randomly and independently of the input (oblivious), or if it is chosen based on the specific matrix $A$ (adaptive)? Furthermore, is randomness strictly necessary to achieve these computational speedups?

Methods

The authors study these questions within the matrix-vector product (matvec) model. In this model, an algorithm can only interact with the matrix $A$ by computing products $Ax$ or $A^\top x$. This is the standard model for iterative methods like Conjugate Gradient or GMRES.

To prove their results, the authors employ several sophisticated theoretical tools:

  • Hidden Gaussian Theorems: They prove that even after an algorithm performs several matvec queries, a significant portion of a random Gaussian matrix remains "hidden" and unobserved, allowing them to establish information-theoretic lower bounds.
  • Polynomial Approximation Theory: They reduce the problem of achieving small backward error to finding specific polynomials that satisfy conflicting constraints (e.g., being large at one point while small on average elsewhere).
  • Krylov Subspace Analysis: They demonstrate that for deterministic algorithms, the best possible strategy is essentially to search within a Krylov subspace, which allows them to use polynomial lower bounds to bound algorithmic complexity.

Datasets

Not discussed in the paper. This is a theoretical work focused on proving complexity bounds and does not use empirical datasets.

Key Insights and Ideas

  • Adaptivity is the "Secret Sauce": The paper proves that oblivious perturbations (the hallmark of smoothed analysis) cannot beat the trivial $\Omega(n)$ complexity for general linear systems. However, recent work has shown that adaptive perturbations can solve systems in $O(\log n / \epsilon)$ matvecs. This represents an exponential separation between the two frameworks.
  • Randomness is Essential for General Systems: The authors show that no deterministic algorithm can achieve non-trivial backward error for general matrices in fewer than $\Omega(n)$ matvecs. You need both adaptivity and randomness to break the complexity barrier for unstructured matrices.
  • Symmetry Changes the Game: If the matrix $A$ is symmetric, the requirement for randomness vanishes. The authors provide a deterministic algorithm that achieves $\epsilon$ backward error in $O(1/\epsilon)$ matvecs.
  • The Geometry of Hardness: The hardness for general systems stems from the requirement of using "odd" polynomials when solving the normal equations ($A^\top A x = A^\top b$). As shown in Figure 1, forcing an odd polynomial to be small on average while large at a specific point (near the origin) requires a very high degree, which translates to high computational cost.
Figure 1: Illustration of hardness of approximation in backward error with odd polynomials (Theorem 4.6). The requirement that an odd polynomial be simultaneously small on [2ε, 1] and large at 1/κ forces a degree of Ω(log(κ)/ε)

Key Results

  1. Smoothed Analysis Lower Bound: Any algorithm solving a randomly (obliviously) perturbed $n \times n$ system requires $\Omega(n)$ matvecs. This proves that smoothed analysis cannot explain the $O(\log n / \epsilon)$ performance of adaptive solvers.
  2. Deterministic Lower Bound: For general matrices, any deterministic algorithm requires $\Omega(n)$ matvecs to achieve a constant backward error. This is the first formal separation between randomized and deterministic algorithms in this computational model.
  3. Symmetric Upper Bound: For symmetric matrices, a deterministic Krylov-based method achieves $\epsilon$ backward error in $O(1/\epsilon)$ matvecs. This is achieved by using "bump" polynomials that handle cases where the matrix has eigenvalues near zero, as illustrated in Figure 2.
Figure 2: Illustration of the polynomials used in the symmetric upper bound (Theorem 4.7). There are two cases: (a) When µ places little mass near zero, then we use a polynomial that approximates 1/x well far from the origin; (b) When µ places much of its mass near zero, then we use a simple non-negative polynomial that is large near zero.

Limitations and Future Work

  • Condition Number Dependence: While the randomized adaptive solver for general systems is fast, it still possesses a logarithmic dependence on the condition number $\kappa$. The authors show this is unavoidable for deterministic methods, but it remains an open question if a randomized method could remove this dependence entirely.
  • Model Constraints: The results are specific to the matrix-vector product model. While this covers most practical iterative solvers, it does not account for algorithms that can access matrix entries directly (like sparse direct solvers).
  • Extension to Other Problems: The authors suggest that the gap between smoothed analysis and adaptive backward error likely exists in other fundamental problems, such as eigenvector computation or matrix functional approximation, which warrants further investigation.

Summary updated

Abstract

Smoothed analysis has become a central tool in theoretical computer science, often allowing for significant improvements to worst-case running times if we settle for a solution to a small random perturbation of the problem instance. This is closely related to the classical concept of backward error in numerical analysis, which allows an algorithm to return a solution to an arbitrary perturbation of the problem. Despite the qualitative similarity of these concepts, we show that they can exhibit large quantitative differences. Notably, we prove that, while a linear system with any $n \times n$ matrix $A$ can be solved to backward error $ε$ using $O(\log(n) / ε)$ matrix-vector products with $A$, any algorithm that solves a random $ε$-sized perturbation of $A$ requires $Ω(n)$ matrix-vector products. This means that a useful perturbation for solving a linear system in backward error must be adaptive to the input. Interestingly, however, randomness is still essential: we show that any deterministic method that attains small backward error for all linear systems provably requires $Ω(n)$ matrix-vector products, resulting in the first separation between randomized and deterministic algorithms in a natural computational model for solving linear systems. Finally, we show that matrix structure can significantly affect backward error complexity. For example, we show a deterministic $O(1/ε)$ matrix-vector product algorithm for symmetric linear systems.
BibTeX
@misc{derezinski2026from,
  author = {Michał Dereziński and Michael W. Mahoney and Raphael A. Meyer and Christopher Musco},
  title = {{From smoothed analysis to backward error: The power of adaptive perturbations}},
  year = {2026},
  eprint = {2611.18545},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.18545},
}
Figure