In the classical theory of online learning, we often measure success through regret: the difference between the total loss an algorithm incurs and the loss it would have incurred had it known the best fixed strategy in hindsight. For years, a standard result was that regret grows with the dimensionality $d$ of the problem—often linearly ($O(d)$) or as a high-degree polynomial.
In modern machine learning, where $d$ can represent millions of features or thousands of products, a linear dependence on dimension is a death sentence for performance. Recent research has focused on "breaking the curse of dimensionality" by developing algorithms whose regret scales logarithmically with $d$, depends only on the intrinsic rank of the problem, or is entirely dimension-free.
The Geometry of the Search Space
The way an algorithm explores a high-dimensional space is dictated by its regularizer or barrier function. If the regularizer doesn't "fit" the geometry of the feasible set, the algorithm wastes time exploring corners of the space that are unlikely to be optimal.
Sebastien Bubeck and Ronen Eldan addressed this in The entropic barrier: a simple and optimal universal self-concordant barrier. They showed that by using an "entropic barrier," one can achieve optimal self-concordance parameters that scale linearly with dimension, closing a gap in Interior Point Methods that previously led to sub-optimal regret.
However, the "optimal" strategy often changes depending on how much time you have. Emmeran Johnson and Ciara Pike-Burke demonstrate in On the necessity of adaptive regularisation: Optimal anytime online learning on ℓp-balls that there is a fundamental transition: in low-dimensional regimes ($d \le T$), regret scales with $d$, but in high-dimensional regimes ($d > T$), it can become independent of $d$ if the algorithm adaptively changes its regularization.
Exploiting Hidden Structure
When the ambient dimension is high, we often hope the problem is secretly "simple." This simplicity usually takes two forms: sparsity or low-rank structure.
- Sparsity: In Sparsity Regret Bounds for Individual Sequences in Online Linear Regression, Sébastien Gerchinovitz shows that if only a few features are actually relevant, we can achieve regret bounds that scale with the number of relevant features rather than the total number of dimensions.
- Low-Rank: For large-scale problems like dynamic pricing for thousands of items, Jonas Mueller 0001 and Vasilis Syrgkanis utilize low-rank assumptions in Low-Rank Bandit Methods for High-Dimensional Dynamic Pricing. By assuming demand is driven by a small number of latent features, their algorithms (OPOK and OPOL) avoid the $O(d)$ scaling that makes traditional bandits fail in retail settings.
The Price of Adaptivity
We often want "parameter-free" algorithms that don't require us to tune learning rates. However, this convenience often comes at a cost. Ashok Cutkosky and Francesco Orabona noted in Black-Box Reductions for Parameter-free Online Learning in Banach Spaces that many parameter-free reductions inadvertently re-introduce a linear dependence on $d$ into the regret bound.
Similarly, Guanghui Wang and Lijun Zhang found that universal algorithms—those that adapt to whether a function is convex or strongly convex—often suffer from a "price of adaptivity" where the regret scales with dimension even when specialized algorithms could achieve dimension-independent bounds (Adaptivity and Optimality: A Universal Algorithm for Online Convex Optimization).
Dimension-Free Chasing
In some problems, like Convex Function Chasing (CFC), the goal is to move to a new point to minimize a hitting cost while also minimizing the movement cost. Traditional competitive ratios for CFC scaled with the ambient dimension $d$.
Anupam Gupta and C. J. Argue broke this barrier in Dimension-Free Bounds on Chasing Convex Functions. They proved that if the functions are well-conditioned or restricted to a low-dimensional subspace, the competitive ratio can be made entirely independent of the ambient dimension. This allows for efficient decision-making in virtually infinite-dimensional spaces, provided the "active" part of the problem remains manageable.
Closing the Gap in Bandit Optimization
Bandit settings are notoriously difficult because the learner only sees the reward for the action they took, not the full loss function. Early bounds for Bandit Convex Optimization (BCO) had staggering polynomial dependencies on dimension, such as $O(d^{9.5})$.
Tor Lattimore significantly tightened this in Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation, bringing the dependence down to $O(d^{2.5})$ by exploiting the geometry of level sets. While a gap still exists between these upper bounds and the theoretical lower bounds (which Shinsaku Sakaue and others have shown must scale at least linearly with $d$ in certain inverse optimization tasks), the trend is toward making high-dimensional learning practical by refining how algorithms explore the underlying geometry.