Convex optimization methods that tune themselves with cone lifting
Conic-Lifting for Learning-rate-free Convex Optimization
Machine Learning
Summary
Finding the best solution in tasks where choices get better over time often needs careful tuning of settings called learning rates. The authors present a way to avoid this tuning by turning the problem into a different shape called a cone, adding a new dimension that helps balance decisions automatically. This approach unifies multiple older methods into one framework that works even when the problem space is not limited or has no set boundaries. Surprisingly, it also matches known successful methods in special cases, showing it captures some fundamental ideas in optimization.
What this means in practice
- •For machine learning engineers: Improve training of online learning models by automatically adjusting optimization steps without manual tuning of learning rates.
- •For financial algorithm developers: Create adaptive trading algorithms that optimize decisions continuously without preset parameters for step sizes, even under changing market conditions.
Authors
Julien Grand-Clément, Joon Kwon, Francesco Orabona
Abstract
A central topic in online and stochastic optimization is to design algorithms that do not require tuning of hyperparameters. Successful strategies in online learning include AdaGrad-style learning rates, Conic Blackwell algorithms, and parameter-free algorithms. However, these classes require different, often difficult, analyses. We develop a unifying family of Online Convex Optimization (OCO) algorithms that require no user-tuned learning rate on convex domains that may be unbounded. The construction lifts the domain to a cone by adding one scalar coordinate, an idea going back to Blackwell (1954). The lifted subgradients are orthogonal to the corresponding lifted decisions, leaving the comparator scale free to optimize in the regret analysis. Applying Follow-the-Regularized-Leader (FTRL) and Online Mirror Descent (OMD) on the cone recovers Conic Blackwell Algorithm (CBA) and Conic Blackwell Algorithm Plus (CBA$^+$) on bounded domains in Hilbert spaces and extends them to finite-dimensional normed spaces with a strongly convex squared norm. For arbitrary nonempty closed convex domains in these spaces, a known gradient bound yields parameter-free regret guarantees. Surprisingly, on an unconstrained Hilbert space, the construction recovers the Krichevsky--Trofimov (KT) coin-betting algorithm exactly. We also give a parameter-free algorithm for unconstrained domains that requires no gradient bound.