Abstract
We design and analyze minimax-optimal algorithms for online linear optimization games where the player's choice is unconstrained. The player strives to minimize regret, the difference between his loss and the loss of a post-hoc benchmark strategy. While the standard benchmark is the loss of the best strategy chosen from a bounded comparator set, we consider a very broad range of benchmark functions. The problem is cast as a sequential multi-stage zero-sum game, and we give a thorough analysis of the minimax behavior of the game, providing characterizations for the value of the game, as well as both the player's and the adversary's optimal strategy. We show how these objects can be computed efficiently under certain circumstances, and by selecting an appropriate benchmark, we construct a novel hedging strategy for an unconstrained betting game.
Introduction
In standard online linear optimization, a learner picks a point $x_t$ from a bounded set (such as a unit ball), an adversary picks a gradient $g_t$, and the learner suffers a loss $g_t \cdot x_t$. The goal is to minimize "regret"—the difference between the learner's total loss and the loss of the best fixed strategy in hindsight. However, in many real-world applications—like training neural networks or financial betting—hard constraints on $x_t$ are often arbitrary or difficult to justify.
If one removes these constraints entirely, a clever adversary can make the learner's loss infinite. To address this, this paper explores "unconstrained" games where the benchmark is not just the best point in a set, but a point penalized by a "soft constraint" function. The challenge lies in finding the exact minimax strategy: the move that minimizes the maximum possible regret an adversary can inflict.
Methodology
The author treats the problem as a sequential multi-stage zero-sum game. The search for a minimax strategy is simplified through several key theoretical developments:
- The Rademacher Simplification: For a concave benchmark function, the minimax value of the game is proven to be the expected value of the benchmark loss when the adversary's gradients are chosen randomly and uniformly from $\{-1, 1\}$.
- Conditional Value ($V_t$): By calculating the "value" of the game at any time $t$ given the history, the author derives a "recipe" for the optimal move $x_{t+1}$. This move balances the potential outcomes of the next gradient being $+1$ or $-1$.
- Convex Conjugates: The paper utilizes the relationship between benchmark functions (performance measurement) and penalty functions (penalizing large $x$ values) to bridge the gap between abstract game theory and practical algorithms like Gradient Descent.
Results and Insights
The paper provides exact formulas for the value of the game and optimal update rules across different settings, as summarized in the table below.
Gradient Descent as a Minimax Strategy
One of the most surprising results is that if the benchmark is defined using a quadratic penalty (the "soft feasible set" setting), the minimax-optimal strategy is exactly unprojected Gradient Descent with a constant learning rate. This provides a deep game-theoretic justification for one of the most common algorithms in machine learning.
The Geometry of Dimension
The paper identifies a "phase transition" in the value of these games based on dimensionality. In 1D, the minimax regret approaches $\sqrt{2T/\pi}$. Previous work showed that in 3D and higher, it is $\sqrt{T}$. This suggests the 1D case is inherently "easier" for the learner than higher-dimensional counterparts would suggest.
Bounded-Loss Betting
The author derives a "bounded-loss betting" algorithm using an exponential benchmark. This allows a learner to ensure they never lose more than a fixed constant (e.g., their initial stake), while allowing for exponential rewards if the adversary's gradients are consistently biased in one direction. Equation (15) provides the specific, computable update rule for this scenario.
Discussion and Limitations
While the paper clarifies the 1D case and provides a rigorous foundation for unconstrained optimization, several challenges remain:
- The $n=2$ Mystery: While the 1D and 3D+ cases are understood, the minimax value for the 2-dimensional $L_2$ game remains a conjecture.
- Computational Complexity: Computing exact minimax strategies in high dimensions with complex benchmarks can be computationally expensive, often requiring approximations like the Gaussian approximation.
- Linearity: The current work focuses on linear optimization; extending these exact minimax results to general convex loss functions remains a significant open challenge in the field.
Summary updated