Resource-Aware Discretization of Accelerated Optimization Flows

Miguel Vaquero, Pol Mestres, Jorge CortésarXiv 2020 · DOI · arXiv

Abstract

This paper tackles the problem of discretizing accelerated optimization flows while retaining their convergence properties. Inspired by the success of resource-aware control in developing efficient closed-loop feedback implementations on digital systems, we view the last sampled state of the system as the resource to be aware of. The resulting variable-stepsize discrete-time algorithms retain by design the desired decrease of the Lyapunov certificate of their continuous-time counterparts. Our algorithm design employs various concepts and techniques from resource-aware control that, in the present context, have interesting parallelisms with the discrete-time implementation of optimization algorithms. These include derivative- and performance-based triggers to monitor the evolution of the Lyapunov function as a way of determining the algorithm stepsize, exploiting sampled information to enhance algorithm performance, and employing high-order holds using more accurate integrators of the original dynamics. Throughout the paper, we illustrate our approach on a newly introduced continuous-time dynamics termed heavy-ball dynamics with displaced gradient, but the ideas proposed here have broad applicability to other globally asymptotically stable flows endowed with a Lyapunov certificate.

Introduction: The Discretization Gap

In recent years, the optimization community has increasingly turned to continuous-time models, specifically Ordinary Differential Equations (ODEs), to analyze accelerated methods like Nesterov’s or Polyak’s Heavy-Ball method. These smooth models allow for elegant analysis using Lyapunov stability theory. However, a significant "discretization gap" persists. When these continuous flows are converted into discrete steps for digital implementation—often via simple schemes like Forward Euler—the theoretical acceleration properties frequently vanish, or the algorithm becomes numerically unstable.

This paper addresses the challenge of finding a principled discretization framework that ensures the resulting discrete-time algorithm inherits the convergence guarantees of its continuous-time progenitor.

Methodology: Resource-Aware Optimization

The authors propose a framework inspired by resource-aware control, a field typically used to manage communication and computation in digital control systems. In this context, the "resource" is the sampled state of the optimizer. The goal is to re-sample (i.e., compute a new gradient) only when the current information is no longer sufficient to guarantee a specific rate of progress along a Lyapunov "energy" function.

Heavy-Ball with Displaced Gradient

A key innovation is the introduction of a generalized continuous-time model: heavy-ball dynamics with a displaced gradient. By evaluating the gradient at a "displaced" position ($x + av$), the authors introduce a design parameter ($a$) that provides additional flexibility for stabilization during discretization. This displacement acts as a "look-ahead" mechanism, stabilizing the discrete-time implementation even with larger steps.

Triggered Stepsizes and Algorithm Design

Instead of a fixed stepsize, the framework employs "triggers" to determine the next iteration point.

  • Derivative-based triggers monitor the instantaneous rate of change of the Lyapunov function.
  • Performance-based triggers monitor the accumulated decay over time, often allowing for larger, more efficient steps.

The general structure of this approach is formalized in Algorithm 1, which integrates these design choices into a cohesive iterative process.

Algorithm 1: Displaced-Gradient Algorithm

High-Order Hold (HOH)

To further improve accuracy, the authors employ a High-Order Hold discretization. This technique splits the dynamics into a linear part (solved exactly) and a nonlinear gradient part (held constant between samples), leading to trajectories that more closely follow the continuous flow than standard first-order methods.

Experimental Evaluation

The proposed algorithms were evaluated on two primary benchmarks: an ill-conditioned quadratic objective and a regularized logistic regression problem. These tests represent classic challenges for optimization, ranging from curvature disparities to non-quadratic, strongly convex landscapes.

Key Results

  • Adaptive Efficiency: In ill-conditioned scenarios, the HOH algorithms automatically tuned their stepsizes to near-optimal values, eventually outperforming Nesterov’s accelerated gradient method.
  • Stability by Design: Unlike explicit schemes that can diverge, the resource-aware approach maintains stability by construction, strictly following the Lyapunov certificate.
  • Convergence Rates: The algorithms successfully matched the $O(e^{-\sqrt{\mu}/4 \cdot t})$ exponential convergence rate of the continuous heavy-ball flow.
  • Qualitative Behavior: The HOH methods exhibited a "leap-frog" behavior, jumping over the oscillations typical of momentum methods and finding a smoother path to the minimizer.

Conclusion and Future Directions

While the resource-aware approach offers significant advantages in stability and adaptive stepsize selection, it introduces some computational overhead per iteration due to trigger calculations. However, this is often offset by a reduction in the total number of iterations required. Future work includes extending these theoretical guarantees to general convex or non-convex landscapes and exploring "restart schemes" as a type of triggering condition.

Summary updated

Abstract

This paper tackles the problem of discretizing accelerated optimization flows while retaining their convergence properties. Inspired by the success of resource-aware control in developing efficient closed-loop feedback implementations on digital systems, we view the last sampled state of the system as the resource to be aware of. The resulting variable-stepsize discrete-time algorithms retain by design the desired decrease of the Lyapunov certificate of their continuous-time counterparts. Our algorithm design employs various concepts and techniques from resource-aware control that, in the present context, have interesting parallelisms with the discrete-time implementation of optimization algorithms. These include derivative- and performance-based triggers to monitor the evolution of the Lyapunov function as a way of determining the algorithm stepsize, exploiting sampled information to enhance algorithm performance, and employing high-order holds using more accurate integrators of the original dynamics. Throughout the paper, we illustrate our approach on a newly introduced continuous-time dynamics termed heavy-ball dynamics with displaced gradient, but the ideas proposed here have broad applicability to other globally asymptotically stable flows endowed with a Lyapunov certificate.
BibTeX
@misc{vaquero2020resource,
  author = {Miguel Vaquero and Pol Mestres and Jorge Cortés},
  title = {{Resource-Aware Discretization of Accelerated Optimization Flows}},
  year = {2020},
  eprint = {2009.09135},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2009.09135},
}
Figure