Introduction
In online learning, an algorithm makes a sequence of predictions as data arrives, aiming to minimize cumulative loss. Traditionally, performance is measured through static regret, which compares the algorithm's performance against the single best fixed decision made in hindsight. While this metric is effective for stable environments, it fails to account for non-stationary settings—such as stock markets or drifting sensors—where the optimal decision changes over time.
To address this, researchers use dynamic regret, which compares performance against a sequence of decisions that can evolve. However, a fundamental tension exists: algorithms optimized for static regret often react too slowly to environmental shifts, while those optimized for dynamic regret may overfit to noise in stable periods. This paper provides a rigorous theoretical foundation for the "forgetting factor" heuristic commonly used in signal processing, demonstrating how it can be tuned to balance these two competing objectives.
Theoretical Framework: Discounted Online Newton
The authors bridge the gap between engineering heuristics and learning theory by analyzing the Discounted Online Newton (DON) algorithm. This framework generalizes the standard Online Newton Step by incorporating a discount factor ((\gamma)) that weights recent losses more heavily than past ones.
A key contribution of this work is the proof that the classic Recursive Least-Squares (RLS) algorithm with a forgetting factor is a specific instance of DON. This provides a long-sought regret-theoretical justification for a tool that has been ubiquitous in engineering for decades.
Quantifying the Regret Trade-off
The paper introduces a parameter (\beta \in (0, 1)) that serves as a "knob" for practitioners to explicitly trade off performance based on their environment's stability. By tuning (\beta), the proposed methods achieve:
- Static Regret: (O(T^{1-\beta}))
- Dynamic Regret: (O(T^\beta V^*))
Where (V^) represents the "path length" or the total amount the environment changes. This allows for a flexible middle ground. Furthermore, by exploiting exp-concavity*—a mathematical property between general convexity and strong convexity—the authors achieve tighter bounds than previous state-of-the-art methods.
Computational Efficiency and Gradient Descent
While second-order methods like DON offer superior regret bounds, they are computationally expensive due to (O(n^3)) matrix inversions. To solve this, the authors derived a specific step-size rule for standard Online Gradient Descent (OGD). This rule allows a first-order method to recover the same dynamic regret bounds as the Newton method, providing a computationally efficient alternative for high-dimensional practical applications.
Handling Unknown Non-Stationarity
Optimal tuning of the discount factor typically requires knowing the path length ((V)) in advance, which is rarely possible. To circumvent this, the authors propose a Meta-Algorithm. This approach runs multiple versions of the algorithm with different discount factors in parallel, using an "experts" framework to aggregate their predictions. This allows the system to adapt to the environment's volatility dynamically without prior knowledge of the total change budget.
Key Results and Convergence
The theoretical analysis yields several significant results:
- Optimal Dynamic Regret: For exp-concave and strongly convex functions, the algorithms achieve a dynamic regret of (\max{O(\log T), O(\sqrt{TV})}).
- Stationary Performance: Unlike previous dynamic regret algorithms that suffered (O(\sqrt{T})) static regret, this method maintains (O(\log T)) static regret when the environment is stationary ((V=0)).
- Lower Bounds: The authors establish a lower bound of (O((VT)^{\gamma_0/2})), proving that their upper bounds are nearly optimal for specific ranges of environmental change.
Conclusion
This work provides a unifying theory for online least-squares, justifying the use of forgetting factors through the lens of regret minimization. By offering a clear mechanism to trade off static and dynamic regret, it provides both a theoretical breakthrough and a practical guide for designing adaptive online learning systems.
Summary updated