Efficient Online Learning with Memory via Frank-Wolfe Optimization: Algorithms with Bounded Dynamic Regret and Applications to Control

Hongyu Zhou, Zirui Xu, Vasileios Tzoumas

Abstract

This paper introduces Meta-OFW, the first "projection-free" algorithm for Online Convex Optimization with Memory (OCO-M) that provides a guaranteed bound on dynamic regret. By replacing computationally expensive quadratic projections with efficient linear optimization via the Frank-Wolfe method, the proposed framework enables real-time control for high-dimensional systems. We demonstrate that Meta-OFW is significantly faster than previous state-of-the-art methods—up to 52x in specific scenarios—while effectively handling time-varying environments and unpredictable noise.

Introduction

In the field of autonomous control and online learning, agents must make sequential decisions in real-time. However, three major hurdles often impede performance: the projection bottleneck, memory effects, and dynamic environments. Standard algorithms like Online Gradient Descent require solving a quadratic program at every time step to project decisions back into a feasible set, which is computationally prohibitive for high-dimensional robotics. Furthermore, real-world systems often exhibit memory, where current states depend on a history of past actions. Finally, most algorithms focus on static regret, whereas non-stationary environments require minimizing dynamic regret—the difference between the algorithm's performance and the best sequence of time-varying decisions.

Methods

The authors propose a hierarchical framework called Meta-OFW to address these challenges simultaneously.

Hierarchical Framework

  • Base Learners (Online Frank-Wolfe): The system runs multiple base learners using the Online Frank-Wolfe (OFW) method. Unlike gradient-based methods, OFW finds a descent direction by solving a simple linear program, which is significantly faster than quadratic projection. Each base learner employs a different step size to hedge against varying levels of environmental volatility.
  • Meta-Learner (Hedge): A master algorithm (Hedge) observes the performance of all base learners, assigning weights to their suggestions and combining them into a final decision. This ensemble approach allows the system to adapt even when environmental variation is unknown.

Control Reduction

To apply this to robotics, the authors utilize a Disturbance-Action Control (DAC) policy. They provide a mathematical proof that DAC can approximate any optimal time-varying linear feedback policy, effectively reducing complex control problems into an OCO-M framework.

Comparison of Meta-OFW with existing online learning algorithms.

Experimental Evaluation

The researchers evaluated Meta-OFW using simulated linear dynamical systems under various conditions:

  • Noise Profiles: The algorithm was tested against six noise distributions (Gaussian, Uniform, Gamma, Beta, Exponential, and Weibull) to ensure robustness against non-stochastic or adversarial noise.
  • Loss Functions: Quadratic loss functions were used, with weights varying over time in either sinusoidal (smooth) or step (sudden) patterns.

Key Results

  • Computational Efficiency: Meta-OFW was observed to be 3 times faster than the previous state-of-the-art OCO-M algorithm (Scream) as system dimensions increased. Compared to standard projection-based methods, the Frank-Wolfe variants achieved up to a 20x speedup.
  • Performance: In simulations featuring exponential noise and step-changing weights, Meta-OFW achieved a cumulative loss 52 times lower than the Scream algorithm.
  • Theoretical Contributions: The authors proved a dynamic regret bound of $O(\sqrt{T(1 + V_T + \bar{D}_T + C_T)})$, where $V_T$ and $D_T$ represent environmental and gradient changes over time. As shown in the comparison table above, this is the first such bound for a projection-free algorithm that accounts for memory.

Conclusion and Future Work

Meta-OFW demonstrates that for real-time control, sacrificing the precision of quadratic projections for the speed of linear sub-problems (Frank-Wolfe) does not necessitate losing theoretical safety or performance bounds. While the current work focuses on linear systems with known matrices, future research aims to extend these projection-free methods to fully non-linear dynamics and integrate online system identification to learn environmental physics during control.

Summary updated

Abstract

Projection operations are a typical computation bottleneck in online learning. In this paper, we enable projection-free online learning within the framework of Online Convex Optimization with Memory (OCO-M)-OCO-M captures how the history of decisions affects the current outcome by allowing the online learning loss functions to depend on both current and past decisions. Particularly, we introduce a projection-free meta-base learning algorithm with memory that minimizes dynamic regret, i.e., that minimizes the sub optimality against any sequence of time-varying decisions. We are motivated by applications where autonomous agents need to adapt to time-varying environments in real-time, accounting for how past decisions affect the present. Examples of such applications are: online control of dynamical systems; statistical arbitrage; and time series prediction. The algorithm builds on the Online Frank-Wolfe (OFW) and Hedge algorithms. We demonstrate how our algorithm can be applied to the online control of linear time-varying systems in the presence of unpredictable process noise. To this end, we develop a projection-free OCO-M controller with bounded dynamic regret against any optimal time-varying linear feedback control policy. We validate our algorithm in simulated scenarios of online control of linear time-invariant systems.
BibTeX
@inproceedings{zhou2023efficient,
  author = {Hongyu Zhou and Zirui Xu and Vasileios Tzoumas},
  title = {{Efficient Online Learning with Memory via Frank-Wolfe Optimization: Algorithms with Bounded Dynamic Regret and Applications to Control}},
  booktitle = {CDC},
  year = {2023},
  url = {https://openreview.net/forum?id=cgRbJ4jGZ8},
}

Loading related content...

Figure