Introduction
In the realm of deep learning, the learning rate is often considered the most critical hyperparameter. A poorly chosen rate can lead to slow convergence or complete divergence. While adaptive optimizers like Adam and AdaGrad have mitigated this by adjusting rates per-parameter, they still rely on a user-defined initial global learning rate. Tuning this value typically involves exhaustive grid searches and significant computational overhead.
This paper introduces COCOB (COntinuous COin Betting), a novel optimization algorithm that eliminates the need for manual learning rate tuning. By reframing stochastic gradient descent (SGD) as a game of betting on coin flips, the authors develop a parameter-free method that matches the performance of perfectly tuned state-of-the-art optimizers.
The Coin Betting Framework
The core innovation of COCOB is the reduction of the optimization problem to a gambling scenario.
- The Betting Metaphor: Imagine a gambler betting on the outcome of adversarial coin flips, represented by gradients ($g_t$). An optimal betting strategy aims to maximize wealth, which grows exponentially with successful bets.
- The Reduction: The authors demonstrate that if negative gradients are treated as coin flip outcomes, the "bet" amount corresponds to the parameter update. Maximizing wealth in this game naturally leads the average of the bets to converge to the minimum of the loss function.
- COCOB Algorithm: Unlike previous theoretical coin-betting models that were too conservative for practical use, COCOB employs a data-dependent strategy. It tracks the sum of gradients and the sum of their absolute values to dynamically determine the "bet" size for each coordinate.
- COCOB-Backprop: To handle the complexities of deep neural networks, such as vanishing or exploding gradients, the authors proposed a practical variant that dynamically updates the scale of the bets.
Experimental Evaluation
The authors evaluated COCOB against popular optimizers including Adam, AdaGrad, RMSProp, and Adadelta across standard benchmarks such as MNIST (MLP and CNN), CIFAR-10, and Penn Tree Bank (PTB).
On MNIST and CIFAR-10, COCOB's training cost decreased at a rate comparable to—or faster than—the best-tuned versions of Adam and RMSProp. Notably, while baseline optimizers required multiple runs across a fine grid of learning rates to find their peak performance, COCOB achieved competitive results in a single run with default settings.
Insights into Adaptive Step Sizes
A key feature of COCOB is its scale-invariance; multiplying the loss function or gradients by a constant does not change the sequence of parameter updates. Furthermore, the algorithm implicitly manages an "effective" learning rate.
As shown in the visualization of this effective rate, COCOB does not use a constant or strictly decreasing step size. Instead, it maintains a large rate when far from the optimum and automatically shrinks it as it approaches the minimum, providing a natural form of annealing.
Conclusion
COCOB represents a significant step toward truly "plug-and-play" deep learning. By removing the learning rate bottleneck, it reduces the computational cost of model development. While theoretical guarantees for non-convex deep networks remain an area for future research, its empirical success across various architectures demonstrates its robustness. Future work may explore extending these betting strategies to second-order optimization methods.
Summary updated