Conic-Lifting for Learning-rate-free Convex Optimization

Julien Grand-Clément; Joon Kwon; Francesco Orabona

math.OCOct 29, 2026

Conic-Lifting for Learning-rate-free Convex Optimization

Authors: Julien Grand-Clément, Joon Kwon, Francesco Orabona

Organizations: ISOM Department, HEC Paris, 78350, Jouy-en-Josas, France · INRAE & Université Paris–Saclay, 91120, Palaiseau, France · King Abdullah University of Science and Technology (KAUST), 23955–6900, Thuwal, Kingdom of Saudi Arabia

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.

Figures & tables

Panel of Figure 1 — Figure 1. Conic lifting of a bounded closed convex set $\mathcal{V}\subseteq\mathbb{R}^{2}$ . The slice at $\bar{y}=1$ is $\mathcal{V}\times\{1\}$ . Every positive multiple $\widecheck{\boldsymbol{y}}=\bar{y}(\boldsymbol{x},1)$ on the highlighted ray decodes to the same decision $\boldsymbol{x}=\boldsymbol{y}/\bar{y}$ . The cone continues along the indicated rays beyond the displayed portion.

Papers / algorithms	Decision set $\mathcal{V}$	Lifting	Cone (possibly truncated)	Role of the conic construction
RM / RM+	Simplex	$\times$	$\{\lambda x:x\in\Delta^{d},\ \lambda\geqslant 0\}=\mathbb{R}_{+}^{d}$	Homogeneity and normalization yield learning-rate-free regret bounds.
COFTRL	Simplex	$\times$	$\{\lambda x:x\in\Delta^{d},\ 0<\lambda\leqslant 1\}$	Lifted regret = positive part of maximum linearized regret.
HOOD	Simplex	$\times$	$\{\lambda x:x\in\Delta^{d},\ 0\leqslant\lambda\leqslant 1\}$	Lifted regret = positive part of maximum linearized regret.
ECHO-OFTRL	Simplex	$\checkmark$	$\{\lambda(x,1):x\in\Delta^{d},\ 0\leqslant\lambda\leqslant 1\}$	Lifted regret = positive part of maximum linearized regret.
LRL-OFTRL	Compact convex	$\checkmark$	$\{\lambda(x,1):x\in\mathcal{V},\ 0\leqslant\lambda\leqslant 1\}$	Lifted regret = positive part of maximum linearized regret.
Lee et al. (2020) ; Luo et al. (2022)	Compact convex	$\checkmark$	$\{\lambda(x,1):x\in\mathcal{V},\ \lambda\geqslant 0\}$	A logarithmically homogeneous barrier controls stability as learning rates change.

Table 1. Uses of conic reformulations in online learning. Lifting means appending a coordinate,

x\mapsto(x,1)

. RM and RM+ are from Hart and Mas-Colell (2000) ; Tammelin et al. (2015) . HOOD is from Abbadi et al. (2026) . ECHO-OFTRL is from Liu et al. (2026) . Lagrangian Hedging is from Gordon (2005) ; Gordon (2006) , and CBA / CBA+ are from Grand-Clément and Kroer (2021) ; Grand-Clément and Kroer (2024) . LRL-OFTRL is from Farina et al. (2022) , and COFTRL is from Soleymani et al. (2025) , who also treat compact convex domains using the lifted cone

\mathcal{C}_{\mathcal{V}}

. For truncated domains, the regret identities use the closed comparator set, including zero.

Online Convex Optimization

Online Convex Optimization studies sequential decisions under changing convex losses, seeking low regret with limited feedback and constraints.

See all 66 papers

Parameter-Free Dynamic Regret under Heavy-Tailed Noise
Jul 29, 2026Vaneet AggarwalOnline Convex Optimization Dynamic Regret Minimization
Purdue University
Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets
Aug 29, 2026Dhruv Sarkar, Aprameyo ChakrabarttyOnline Convex Optimization
Massachusetts Institute of Technology, Cambridge, MA · Purdue University, West Lafayette, IN
Gradient-Variation Regret Bounds for Unconstrained Online Learning
Apr 13, 2026Yuheng Zhao, Andrew Jacobsen, Nicolò Cesa-Bianchi +1Online Convex Optimization Dynamic Regret Minimization
Università degli Studi di Milano & Politecnico di Milano

Jul 29, 2026J/K move · Enter open · S save

Parameter-Free Dynamic Regret under Heavy-Tailed Noise

Vaneet Aggarwal

Purdue University

Online Convex Optimization Dynamic Regret Minimization Minimax Regret Heavy-Tailed Noise Adaptive Gradient Methods Heavy-Tailed Stochastic Optimization

Open paper AskPDF arXiv

We study online convex optimization with one unbiased stochastic subgradient per round and noise having a finite

p

-th central moment, where

p\in(1,2]

is unknown. For a bounded convex domain of diameter

D

, subgradients bounded by

G

, noise scale

σ

, and comparator path length

P_T

, let

Λ_T=1+P_T/D

. A single algorithm, using none of

G,σ,p,P_T

, attains expected dynamic regret

O_p\left(\min\{GD\sqrt{TΛ_T}+σDT^{1/p}Λ_T^{(p-1)/p},\,GDT\}\right)

against every fixed comparator sequence. Restarted AdaGrad experts produce the noise-path exponent

(p-1)/p

, and a prior favoring longer restart intervals removes horizon-dependent logarithmic overhead. We give an explicit bound uniform in

p

; its logarithm-free form has noise coefficient

O(1+\log(p/(p-1)))

, while the static-regret constant is universal. The analysis requires only marginal noise moments and permits dependent errors. Complete pathwise proofs retain both the expert-loss range and the gradient energies preceding comparator movement. Matching lower bounds hold on every bounded convex domain of positive diameter, under the same gradient-only information model. Together with a path-budget-tuned upper bound, they characterize the minimax rate with universal constants, including its linear-regret saturation.

Abstract

Online Convex Optimization

Explore similar work

Parameter-Free Dynamic Regret under Heavy-Tailed Noise

Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets

Gradient-Variation Regret Bounds for Unconstrained Online Learning