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.
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