Optimization as a Polynomial Approximation Problem

41 concepts30 papers1 proposal

When we run a first-order optimization algorithm, we are doing more than just shifting points along a gradient; we are implicitly constructing a polynomial. This realization bridges the gap between continuous optimization and classical approximation theory. By viewing iterative updates as polynomial transformations of a problem's underlying spectrum, we can establish fundamental speed limits, design optimal learning rate schedules, and precisely quantify the convergence of complex algebraic relaxations.

The Residual Polynomial Framework

To understand why optimization can be modeled as a polynomial approximation problem, consider minimizing a convex quadratic objective $f(x) = \frac{1}{2} x^T A x$, where $A$ is a symmetric positive-definite Hessian matrix. If we apply vanilla gradient descent with a fixed step size $\eta$, the iterate update is:

$$x_{t+1} = x_t - \eta A x_t = (I - \eta A) x_t$$

If $x^*$ is the true minimizer (where $A x^* = 0$), the error $e_t = x_t - x^*$ evolves according to the linear recurrence $e_{t+1} = (I - \eta A) e_t$. Expanding this recurrence from the initial error $e_0$ yields:

$$e_T = (I - \eta A)^T e_0$$

The operator $(I - \eta A)^T$ is a matrix polynomial of degree $T$. More generally, any first-order method where the next step is a linear combination of past gradients can be expressed as $e_T = P_T(A) e_0$, where $P_T(\lambda)$ is a scalar polynomial of degree $T$. Because an algorithm must achieve zero error if it starts with zero error, this polynomial must satisfy the normalization condition $P_T(0) = 1$. Such polynomials are known as residual polynomials.

The core intuition of this framework is that minimizing the optimization error after $T$ steps is exactly equivalent to finding a residual polynomial $P_T$ that is as close to zero as possible across the entire spectrum (the eigenvalues) of $A$.

As established by Yossi Arjevani et al., this perspective reduces the analysis of iteration complexity to a pure approximation problem. In a companion work, the authors demonstrate that the dimension-free convergence limits of finite-sum optimization algorithms are fundamentally dictated by how well a polynomial of a given degree can fit the inverse of the Hessian's eigenvalues.

This reduction explains the ubiquity of Chebyshev polynomials in acceleration. To minimize the worst-case error over a spectral range $[\mu, L]$, we require a polynomial that oscillates as closely to zero as possible within that interval while maintaining $P_T(0) = 1$. Chebyshev polynomials uniquely satisfy this minimax property.

Leveraging this property, Naman Agarwal et al. demonstrate that vanilla gradient descent can match the accelerated convergence rates of momentum methods simply by scheduling step sizes to match the roots of Chebyshev polynomials. This polynomial alignment is powerful enough to extend beyond standard optimization; Jun-Kun Wang et al. show that varying the integration time of Hamiltonian Monte Carlo according to Chebyshev roots reduces the algorithm's sensitivity to the target distribution's condition number from a linear dependency to a square root.

Complex Spectra and Average-Case Universality

When optimizing non-symmetric systems—such as bilinear games, saddle-point problems, or differentiable multi-agent architectures (e.g., GANs)—the eigenvalues of the governing Jacobian matrix are no longer confined to the real line; they spread into the complex plane.

   Worst-Case (Real Spectrum)           Complex Spectrum (Games)
       [====== Spectrum ======]                 .

*  .
*
  0 ----------- µ ----------- L           0 -------*---*-------
       Minimize max |P(λ)|                      *  .  .

*
                                          Minimize |P(λ)| over 2D shape

In these scenarios, the residual polynomial must suppress eigenvalues over a two-dimensional "spectral shape." Waïss Azizian et al. formalize this by modeling first-order algorithms as polynomial transformations over complex spectral domains, proving that acceleration is achieved by finding polynomials that shrink the entire geometric shape toward the origin.

Using this framework, Guodong Zhang et al. analyze polynomial iterations over complex eigenvalues to demonstrate why negative momentum is inherently suboptimal for minimax optimization, as it fails to compress the complex spectrum as effectively as extragradient methods. Similarly, Junhyung Lyle Kim et al. use polynomial analysis to map out the exact spectral shapes where Momentum Extragradient achieves optimal acceleration.

The polynomial lens also allows us to move from pessimistic worst-case bounds to average-case performance. Instead of minimizing the maximum absolute value of a polynomial over a spectrum, we can minimize its expected value weighted against a specific eigenvalue distribution.

Carles Domingo-Enrich et al. utilize this to design optimal first-order methods for bilinear games by tailoring residual polynomials to the average-case geometry of the optimization landscape. This average-case behavior exhibits a powerful universality in high dimensions. Leonardo Cunha et al. show that average-case convergence is almost entirely determined by the "tails" of the spectral distribution—how eigenvalues concentrate at the extreme edges—and that algorithms can remain robust by approximating the optimal residual polynomial for these edges.

As models grow larger, this interaction becomes highly predictable; Courtney Paquette et al. demonstrate that the halting time of large-scale models becomes deterministic because the residual polynomial effectively integrates over a universal, predictable eigenvalue distribution. The utility of these minimax-optimal polynomials extends to matrix-level operations as well; Noah Amsel et al. optimize iterative matrix sign computations by employing sequences of minimax polynomials that adaptively compress the singular value range at each step.

Orthogonal Polynomials in Relaxation Hierarchies

The deep symmetry between optimization and polynomial approximation operates in reverse when the objective function itself is a polynomial. To find the global minimum of a multivariate polynomial over a constrained domain like a hypercube, direct optimization is often non-convex and intractable. Instead, researchers use algebraic relaxation hierarchies—such as Sum-of-Squares (SOS), Putinar, or Schmüdgen representations—to transform the problem into a sequence of convex semidefinite programs (SDPs).

As synthesized by Jean B. Lasserre et al., these hierarchies provide a sequence of increasingly accurate lower bounds that are guaranteed to converge to the true global minimum. Remarkably, the rate of this convergence is governed by the exact same mathematical machinery found in first-order acceleration: the structural properties and roots of orthogonal polynomials.

To bound the error of a measure-based polynomial optimization hierarchy, researchers must determine how well a polynomial of a given degree $r$ can approximate an indicator or step function over the domain. Lucas Slot et al. prove that univariate measure-based hierarchies achieve a near-optimal convergence rate of $O(\log^2 r / r^2)$ by directly mapping the hierarchy's bounds to the smallest roots of Jacobi-type orthogonal polynomials. When certifying that a polynomial is strictly positive over a hypercube, Monique Laurent et al. show that establishing tight degree bounds is the primary bottleneck to making these algebraic certificates computationally practical.

For binary polynomial optimization (where variables are restricted to $\{-1, 1\}^n$), the underlying domain is discrete, meaning the continuous Jacobi polynomials no longer apply. Instead, Lucas Slot et al. establish that the approximation error of SOS hierarchies is explicitly bounded by the extremal roots of Krawtchouk polynomials—the orthogonal polynomials associated with discrete binomial measures. This connection reveals a crucial structural property: the constant factor in the error bound depends entirely on the degree of the objective polynomial rather than the number of variables $n$, ensuring that the relaxation remains stable as the problem scales.

Optimization Domain    Characteristic Orthogonal Polynomial    Governing Error Metric
--------------------------------------------------------------------------------------
Continuous Hypercube   Jacobi / Chebyshev Polynomials          Smallest Roots -> O(1/r²)
Discrete Hypercube     Krawtchouk Polynomials                  Least Root -> Dimension-Free Bounds

To refine these algebraic guarantees, Lorenzo Baldi et al. analyze Putinar's Positivstellensatz on the hypercube, demonstrating that the degree required for a valid sum-of-squares certificate scales linearly with the ratio of the function's maximum to minimum values.

The choice of polynomial basis can radically alter these convergence behaviors. For instance, Morteza Lahijanian et al. compare Bernstein polynomial bases against SOS relaxations for constructing stochastic barrier functions, noting that while Bernstein approximations theoretically offer linear convergence compared to the logarithmic convergence of SOS, a practical gap remains due to dimensional scaling in higher dimensions.

Ultimately, bridging the gap between abstract algebraic representations and concrete convergence rates relies on classical approximation theorems. Milan Korda et al. apply Jackson-type theorems to smooth functions to derive explicit convergence rates for moment-SOS hierarchies within optimal control problems, while Victor Magron utilizes Bernstein polynomial approximations to refine the lower bounds of Putinar-type representations over hypercubes.

Whether we are designing a faster gradient descent schedule or bounding the precision of a semidefinite relaxation, the underlying mechanism remains identical: we are leveraging the mathematical limits of polynomial approximation to reshape and control the spectrum of our optimization problem.

Key Foundational Work

Dimension-Free Iteration Complexity of Finite Sum Optimization Problems (2016) — contributed 2 concept elements to this direction.
On Lower and Upper Bounds in Smooth and Strongly Convex Optimization (2016) — contributed 2 concept elements to this direction.
On the Iteration Complexity of Oblivious First-Order Optimization Algorithms (2016) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_residual_polynomial_optimization_ccbad271,
  title = {residual polynomial optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/residual-polynomial-optimization/rdr_ccbad27153764576968533a059e7c677},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_residual_polynomial_optimization_ccbad271_v1,
  title = {residual polynomial optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/residual-polynomial-optimization/rdr_ccbad27153764576968533a059e7c677/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake