# Minimax Optimal Algorithms for Unconstrained Linear Optimization

arXiv: https://arxiv.org/abs/1302.2176 · HTML: https://mlsanity.com/paper/1302.2176/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2013.

## Built on by (most cited first, 12 of 12)

- [Parameter-free Stochastic Optimization of Variationally Coherent Functions](https://mlsanity.com/paper/2102.00236/) (2021)
- [PDE-Based Optimal Strategy for Unconstrained Online Learning](https://mlsanity.com/paper/2201.07877/) (2022)
- [Mechanic: A Learning Rate Tuner](https://mlsanity.com/paper/2306.00144/) (2023)
- [Dealing with unbounded gradients in stochastic saddle-point optimization](https://mlsanity.com/paper/2402.13903/) (2024)
- [Pareto Optimal Model Selection in Linear Bandits](https://mlsanity.com/paper/2102.06593/) (2021)
- [Scale-free Unconstrained Online Learning for Curved Losses](https://mlsanity.com/paper/2202.05630/) (2022)
- [Unconstrained Dynamic Regret via Sparse Coding](https://mlsanity.com/paper/2301.13349/) (2023)
- [Model Selection for Generic Contextual Bandits](https://mlsanity.com/paper/2107.03455/) (2021)
- [Parameter-Free Dynamic Regret for Unconstrained Linear Bandits](https://mlsanity.com/paper/2603.25916/) (2026)
- [Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications](https://mlsanity.com/paper/2509.08911/) (2025)
- [Parameter-free Online Linear Optimization with Side Information via Universal Coin Betting](https://mlsanity.com/paper/2202.02406/) (2022)
- [Solving Robust MDPs through No-Regret Dynamics](https://mlsanity.com/paper/2305.19035/) (2023)

## Abstract (arXiv)

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. The standard benchmark is the loss of the best strategy chosen from a bounded comparator set. When the the comparison set and the adversary's gradients satisfy L_infinity bounds, we give the value of the game in closed form and prove it approaches sqrt(2T/pi) as T -> infinity. Interesting algorithms result when we consider soft constraints on the comparator, rather than restricting it to a bounded set. As a warmup, we analyze the game with a quadratic penalty. The value of this game is exactly T/2, and this value is achieved by perhaps the simplest online algorithm of all: unprojected gradient descent with a constant learning rate. We then derive a minimax-optimal algorithm for a much softer penalty function. This algorithm achieves good bounds under the standard notion of regret for any comparator point, without needing to specify the comparator set in advance. The value of this game converges to sqrt{e} as T ->infinity; we give a closed-form for the exact value as a function of T. The resulting algorithm is natural in unconstrained investment or betting scenarios, since it guarantees at worst constant loss, while allowing for exponential reward against an "easy" adversary.