Backprop without Learning Rates Through Coin Betting

Francesco Orabona, Tatiana TommasiarXiv 2017 · arXiv

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.

  1. 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.
  2. 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.
  3. 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.
  4. 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).

Performance comparison on MNIST for Fully Connected and CNN architectures. COCOB (red) matches or exceeds the performance of state-of-the-art optimizers tuned over a grid of learning rates.

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.

The effective learning rate of COCOB over iterations, showing automatic adaptation to the loss landscape.

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

Abstract

Deep learning methods achieve state-of-the-art performance in many application scenarios. Yet, these methods require a significant amount of hyperparameters tuning in order to achieve the best results. In particular, tuning the learning rates in the stochastic optimization process is still one of the main bottlenecks. In this paper, we propose a new stochastic gradient descent procedure for deep networks that does not require any learning rate setting. Contrary to previous methods, we do not adapt the learning rates nor we make use of the assumed curvature of the objective function. Instead, we reduce the optimization process to a game of betting on a coin and propose a learning-rate-free optimal algorithm for this scenario. Theoretical convergence is proven for convex and quasi-convex functions and empirical evidence shows the advantage of our algorithm over popular stochastic gradient algorithms.
BibTeX
@misc{orabona2017backprop,
  author = {Francesco Orabona and Tatiana Tommasi},
  title = {{Backprop without Learning Rates Through Coin Betting}},
  year = {2017},
  eprint = {1705.07795},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1705.07795},
}
Figure