Online Convex Optimization (OCO) algorithms often struggle with poorly conditioned data—situations where data is stretched out in one dimension and squashed in another. Standard methods like Online Gradient Descent (OGD) are highly sensitive to this scaling. While preconditioning can correct this, it typically requires prior knowledge of the data's geometry.
This paper tackles a specific instance of this challenge: the Low-rank Experts Problem. Imagine receiving advice from $N$ experts, but their advice is highly redundant, meaning their losses reside in a low-dimensional subspace of rank $r \ll N$. Traditional algorithms yield regret that scales with the total number of experts $N$. The authors' goal is to design an algorithm whose regret depends only on the intrinsic rank $r$, without knowing $r$ or the subspace beforehand.
The Core Innovation: Online Lazy Newton (OLN)
To solve this, the authors introduce Online Lazy Newton (OLN), an affine-invariant algorithm that automatically adapts to the intrinsic dimensionality of a problem. OLN is a sophisticated evolution of the classic Online Newton Step (ONS), modified with two critical changes to achieve affine invariance:
- Lazy Projections: Standard ONS projects the solution back into the feasible set at every single step (a "greedy" approach). OLN, instead, maintains an unconstrained running sum of gradients and only projects when it needs to make a prediction. This is reminiscent of dual averaging methods.
- Zero Initialization: Instead of initializing the covariance matrix (the preconditioner) with $\epsilon I$—which introduces a "preferred" coordinate system and breaks affine invariance—OLN starts at zero ($A_0 = 0$) and uses a Moore-Penrose pseudo-inverse.
Because OLN is affine-invariant, running it on a skewed dataset is mathematically identical to running it on a perfectly "whitened" version of that same data. It essentially learns the optimal preconditioner on the fly.
Key Insights and Theoretical Contributions
- Intrinsic vs. Ambient Dimension: The core insight is that regret should not be a tax on the number of dimensions available (the ambient dimension $d$), but on the number of dimensions the data actually uses (the intrinsic rank $r$).
- Loss-Based Bounds: Instead of assuming separate bounds on domain size and function steepness, the authors assume a bound $C$ on the magnitude of the losses themselves ($|g_t^\top x| \leq C$). This naturally fits problems like "Expert Advice," where losses are typically bounded between 0 and 1.
- Decoupling Past and Future: Lazy projections decouple the conditioning learned from past gradients from the constraints of the feasible set, allowing more aggressive adaptation to the data's geometry.
Results: Solving the Low-Rank Experts Problem
As a purely theoretical paper, the results are mathematical proofs demonstrating optimal performance across any data sequence satisfying structural properties like low rank.
- Optimal Regret: OLN achieves a regret bound of $O(C\sqrt{rT} \log T)$ for the low-rank experts problem. This matches the known lower bound of $\Omega(\sqrt{rT})$ up to a small logarithmic factor.
- Significant Improvement: Previous state-of-the-art algorithms achieved $O(r\sqrt{T})$. By moving $r$ inside the square root, OLN provides a massive improvement for problems with large ranks.
- Dimension Independence: The regret is completely independent of the ambient dimension $d$ and the total number of experts $N$.
Limitations and Future Directions
While OLN resolves a major open problem, several challenges remain:
- The Logarithmic Gap: A $\sqrt{\log T}$ gap remains between the proven upper bound and the theoretical lower bound. Closing this gap is an open mathematical challenge.
- Computational Complexity: Maintaining and inverting the matrix $A_t$ requires $O(d^2)$ space and $O(d^2)$ time per step (using rank-1 updates). For extremely high-dimensional problems, this remains expensive. "Sketching" (matrix compression) is a potential fix, but full affine-invariant analysis for sketched versions is left for future work.
- Full Information Only: The analysis assumes the learner sees the entire loss vector at each step. Extending these affine-invariant benefits to the Bandit setting (where only the loss of the chosen action is observed) is a major open direction.
Summary updated