Approaching Quartic Convergence Rates for Quasi-Stochastic Approximation with Application to Gradient-Free Optimization

Caio Kalil Lauand, Sean P. MeynNeurIPS 2022

TL;DR

This paper shatters the long-held belief that Quasi-Stochastic Approximation (QSA) is limited to a convergence rate of $O(n^{-2})$. By leveraging tools from number theory and introducing a novel "forward-backward" filtering technique, the authors demonstrate that it is possible to achieve near-quartic convergence rates ($O(n^{-4+\delta})$), offering a massive speedup for gradient-free optimization and reinforcement learning.

What Problem Does This Paper Address?

Stochastic Approximation (SA) is the mathematical backbone of many machine learning algorithms, used to find roots of functions when only noisy observations are available. However, SA is notoriously slow; its mean square error typically vanishes at a rate of $O(n^{-1})$.

In many applications, such as reinforcement learning or gradient-free optimization (GFO), the "noise" in the system isn't actually random—it’s a "probing signal" designed by the engineer. This leads to Quasi-Stochastic Approximation (QSA), where deterministic signals (like sinusoids) replace random variables. While QSA was known to be faster than SA, the research community generally assumed its "speed limit" was $O(n^{-2})$. This paper addresses the challenge of breaking through that $O(n^{-2})$ ceiling to reach even faster convergence.

Methods

The authors move the analysis into continuous time using Ordinary Differential Equations (ODEs) to simplify the math before translating it back to discrete algorithms. Their approach relies on three pillars:

  1. Perturbative Mean Flow (p-mean flow): They introduce a new mathematical representation of the QSA ODE that accounts for higher-order "noise" terms. This allows them to see exactly how the probing signal interacts with the algorithm's trajectory.
  2. Probing Signal Design: They use mixtures of sinusoids as probing signals. By applying results from number theory (specifically regarding the irrationality of frequencies), they ensure that the "noise" cancels out much faster than random noise ever could.
  3. Forward-Backward (FB) Filtering: This is a novel algorithmic contribution. Standard Polyak-Ruppert averaging can be biased if the probing signal isn't perfectly designed. The FB algorithm runs a pair of ODEs—one forward and one effectively "backward" in time—to cancel out these biases, achieving near-quartic rates even under less-than-ideal conditions.

Datasets

The paper evaluates its theoretical claims using standard, high-dimensional optimization benchmarks rather than traditional image or text datasets. These include:

  • Rastrigin Function: A non-convex function with many local minima, used to test global optimization.
  • Ackley Function: A standard benchmark characterized by a nearly flat outer region and a very large hole at the center.
  • Three-Hump Camel Function: Another classic global optimization test case.

Key Insights and Ideas

  • Design Beats Randomness: The core "aha moment" is that if you can design the noise, you can make it "orthogonal" to the error. By choosing frequencies that are "linearly independent over the rationals," the authors ensure that the error terms vanish at an accelerated rate.
  • The $O(n^{-2})$ Limit was a Fallacy: The authors show that the previous limit was not a fundamental mathematical wall, but rather a result of using analysis tools that weren't sharp enough to capture the benefits of sophisticated signal design.
  • Hidden Geometry: The paper highlights a "hidden geometry" where certain classes of functions are orthogonal to the solutions of Poisson’s equation. Exploiting this orthogonality is what allows the error to drop so precipitously.

Key Results

  • Theoretical Breakthrough: The authors prove that for any $\delta > 0$, an MSE rate of $O(T^{-4+\delta})$ is achievable through careful design.
  • Empirical Validation: In tests on the Rastrigin and Ackley functions, the proposed algorithms (1qSGD and 2qSGD) maintained stable "scaled root-MSE" values, confirming that the actual error was decreasing at the predicted $O(T^{-2\rho})$ rate (where $\rho$ is a gain parameter).
  • FB Filtering Superiority: The Forward-Backward algorithm successfully achieved these fast rates even in scenarios where standard Polyak-Ruppert averaging failed due to frequency interference.

Limitations and Future Work

  • The Curse of Dimensionality: While the theory holds for any dimension $d$, the authors note that the impact of high dimensionality on the constant factors of the convergence rate is not yet fully understood for QSA.
  • The "True" Speed Limit: While they reached $O(n^{-4})$, the authors haven't ruled out the possibility of even faster rates (e.g., $O(n^{-10})$). The fundamental lower bound for QSA remains an open question.
  • Gain Constraints: Current theory requires the gain parameter $\rho > 1/2$. Experimental data suggests this might be an artifact of the analysis rather than a hard requirement, suggesting a path for further theoretical refinement.

Summary updated

BibTeX
@inproceedings{lauand2022approaching,
  author = {Caio Kalil Lauand and Sean P. Meyn},
  title = {{Approaching Quartic Convergence Rates for Quasi-Stochastic Approximation with Application to Gradient-Free Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
}

Loading related content...

Figure