In online convex optimization, a learner repeatedly makes decisions, observes loss vectors, and aims to minimize regret—the difference between their cumulative loss and the loss of the best fixed decision in hindsight.
To achieve optimal regret, classical algorithms like Online Gradient Descent require careful tuning of a learning rate hyperparameter. Crucially, the optimal learning rate depends on two oracle constants: the norm of the best decision vector ($\|w^*\|$) and the maximum magnitude of the incoming gradients ($G$).
In real-world streaming environments, we rarely know either value in advance. If we choose a learning rate that is too aggressive, the algorithm may diverge; if we choose one that is too conservative, it learns too slowly. The field of parameter-free and scale-free online learning aims to eliminate this manual tuning entirely, designing algorithms that automatically adapt to both the unknown scale of the optimal solution and the unknown magnitude of the data.
The Two Dimensions of Adaptivity
To make an online learning algorithm truly autonomous, it must solve two distinct problems:
- Parameter-Free Adaptivity: The algorithm must adapt to the unknown norm of the optimal competitor, $\|w^*\|$, without requiring a pre-defined bounded decision set or a manually tuned learning rate.
- Scale-Free Adaptivity: The algorithm's decisions must be invariant to constant scaling of the loss vectors, meaning it automatically adjusts to the unknown gradient magnitude $G$.
Without these properties, practitioners are forced to rely on heuristics like the "doubling trick," which restarts the algorithm with a larger parameter guess whenever a bound is violated. However, the doubling trick is computationally inefficient and fails to provide smooth, continuous adaptation.
Parameter-Free Adaptivity via Time-Varying Regularization
The first breakthrough in removing oracle knowledge focused on adapting to the scale of the competitor. In standard Online Mirror Descent or Follow-the-Regularized-Leader (FTRL), the regularizer is static. To adapt to an unconstrained space where the optimal competitor could be anywhere, the regularizer must evolve dynamically over time.
Matthew J. Streeter et al. demonstrated in No-Regret Algorithms for Unconstrained Online Convex Optimization that near-optimal regret can be achieved in unconstrained spaces by adaptively tuning the learning rate based on accumulated rewards. This allowed the algorithm to perform nearly as well as an oracle that knew the optimal solution's norm in advance.
To achieve this in arbitrary dimensions, Francesco Orabona proposed a solution in Dimension-Free Exponentiated Gradient by introducing a time-varying regularizer based on the norm of the weight vector itself. By dynamically adjusting the regularizer's parameters according to the cumulative norm of observed gradients, the algorithm self-tunes its effective step size. This implicitly estimates the scale of the optimal competitor, yielding dimension-free regret bounds without prior parameter knowledge.
Scale-Free Optimization: Resisting Magnitude Shifts
Even if an algorithm can adapt to the size of the optimal weight vector, it can still be derailed if the magnitude of the incoming data changes unexpectedly. If an adversary suddenly multiplies all loss vectors by a factor of 1,000, a standard algorithm's behavior will change drastically unless its learning rate is divided by 1,000. Scale-free algorithms ensure that decision-making remains consistent regardless of such constant scaling factors.
Francesco Orabona et al. expanded this concept in Scale-Free Algorithms for Online Linear Optimization, introducing algorithms like AdaFTRL and SOLO FTRL. These methods achieve optimal regret bounds in unbounded decision spaces without requiring prior knowledge of loss vector norms. They accomplish this by ensuring the regret bound adapts directly to the observed variance or cumulative squared norm of the data, effectively automating hyperparameter tuning for data magnitude.
This scale-free mechanism has since been integrated into broader frameworks. For instance, the authors of Improved Online Conformal Prediction via Strongly Adaptive Online Learning utilized scale-free online gradient descent as a base learner. This allowed their system to maintain robust uncertainty estimation and valid coverage under streaming data without needing pre-tuned learning rates or prior knowledge of data volatility.
The Coin Betting Paradigm
One of the most elegant and intuitive frameworks for parameter-free learning shifts the perspective from geometric optimization to financial gambling.
Imagine an agent betting on the outcome of a series of coin flips, where the "coin flips" correspond to the signs or directions of incoming gradients. Instead of maintaining a weight vector and taking gradient steps, the algorithm tracks its total accumulated wealth. Each round, the agent bets a fraction of its current wealth on the direction of the next gradient. If the agent bets correctly (i.e., aligns with the negative gradient), its wealth grows exponentially.
We can map the agent's wealth back to an optimization setting by setting the decision weight $w_t$ proportional to the current wealth multiplied by the betting fraction. Because wealth grows multiplicatively when predictions are correct, the effective learning rate automatically scales up when the algorithm is performing well and scales down when it encounters losses.
As explored by Giulia Denevi et al. in Online Parameter-Free Learning of Multiple Low Variance Tasks, coin betting algorithms completely eliminate the need for manually tuned learning rates or regularization constants while maintaining rigorous performance guarantees. Furthermore, in Parameter-Free Online Linear Optimization with Side Information via Universal Coin Betting, the authors demonstrated that this paradigm can be combined with information-theoretic compression techniques to automatically exploit structured side information with zero manual tuning.
Potential Functions and Drifting Games
Another powerful lens for parameter-free learning comes from minimax analysis and potential functions, often framed as "drifting games." Here, the goal is to ensure that a potential function tracking the algorithm's regret never exceeds a certain threshold, regardless of the adversary's actions.
Kamalika Chaudhuri et al. introduced a foundational approach in A Parameter-free Hedging Algorithm called NormalHedge. This algorithm eliminates the learning rate parameter entirely by using a potential function that dynamically balances the weights of different actions based on their historical performance relative to the average.
Subsequently, Haipeng Luo et al. formalized this perspective in A Drifting-Games Analysis for Online Learning and Applications to Boosting. By treating online learning as a drifting game and applying clever convex relaxations, the authors constructed adaptive algorithms that eliminate the need for a fixed time horizon or manual learning rate schedules. The resulting potential functions allow the algorithm to self-regulate and adapt automatically to the cumulative loss and duration of the learning task.
The Grand Challenge: Unifying Parameter-Free and Scale-Free Bounds
While algorithms have been developed to tackle parameter adaptivity and scale adaptivity independently, combining both properties into a single, unified framework remains a core challenge.
In Open Problem: Parameter-Free and Scale-Free Online Algorithms, Francesco Orabona et al. pointed out that online linear optimization historically lacked a unified method that is simultaneously parameter-free and scale-free without incurring sub-optimal regret. This gap prevents a single algorithm from seamlessly adapting to both an unknown optimal solution norm and an unknown data magnitude simultaneously.
This challenge becomes even more pronounced in non-stationary environments where the optimal decision changes over time. As noted by Yawei Zhao et al. in Understand Dynamic Regret with Switching Cost for Online Decision Making, traditional theoretical bounds for dynamic regret depend heavily on knowing the "budget of dynamics" (the total path length of the changing target) to tune the learning rate.
To address this, Ali Jadbabaie et al. designed a fully adaptive algorithm in Online Optimization : Competing with Dynamic Comparators. By utilizing a novel doubling trick on non-monotone quantities, the authors provided a regret bound that automatically scales with the complexity of both the environment and the sequence of optimal actions. This eliminates the need to pre-tune learning rates based on unknown regularity parameters, moving the field closer to truly autonomous online optimization.