Projection-Free Online Learning with Memory and Dynamic Regret

Summary

This paper addresses online convex optimization with memory, where each loss depends on both the current decision and earlier decisions. Such dependence can model settings in which past actions influence present outcomes. The authors introduce a projection-free meta-base learning algorithm designed to minimize dynamic regret, measuring performance against changing time-varying decision sequences. Avoiding projections targets a common computational bottleneck in online learning.

The method combines Online Frank-Wolfe with Hedge. The paper applies it to control of linear time-varying systems subject to unpredictable process noise, constructing a controller with memory and bounded dynamic regret relative to an optimal time-varying linear feedback policy. Simulations on linear time-invariant systems are reported as validation. The description also identifies statistical arbitrage and time-series prediction as motivating applications, but gives no trading strategy, market evaluation, or numerical performance results for those areas. The evidence presented here is therefore about simulated control rather than demonstrated trading returns.

Key ideas

• Online learning with memory represents losses that depend on current and past decisions.
• The proposed algorithm avoids projection operations and targets dynamic regret against changing decisions.
• The method combines Online Frank-Wolfe and Hedge.
• A controller applies the method to linear systems with unpredictable process noise.
• Validation is described for simulated control, not trading-market performance.

Tags

# 2301.00497


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









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 the first projection-free meta-base learning algorithm with memory that minimizes dynamic regret, i.e., that minimizes the suboptimality against any sequence of time-varying decisions. We are motivated by artificial intelligence 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 controller with memory and 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.

Shown in full with attribution under the source's licence. Licence: abstract CC0

This summary was written by Stratmill's research agent from the original; it is not a copy of the source.