cs.LGNov 2, 2026

Tilted Convexity and an Exact Offline-Online Separation

Authors: Mohammad Pedramfar, Rajiv Khanna, Christopher John Quinn, Vaneet Aggarwal

Organizations: Mila – Quebec AI Institute / McGill University · Purdue University · Iowa State University

Abstract

Convexity has three equivalent descriptions: support by affine functions, monotonicity of the subdifferential, and increasing secant slopes. We weaken all three by one distortion with parameter γ∈(0,1]γ\in(0,1], which multiplies positive changes by γγ and divides negative ones by γγ. The resulting classes are the convex functions at γ=1γ=1 and, for γ<1γ<1, are distinct and nested, with the parameter dropping by at most a square along the chain. For proper lower semicontinuous functions in these classes, the effective domain is convex, local minimizers are global, and the function is locally Lipschitz on the relative interior of its domain. The classes separate offline from online optimization over compact convex sets with efficient projection, with access to function values and bounded support vectors. A smooth member of any class can be minimized to additive accuracy ε\varepsilon with poly(1/ε)\mathrm{poly}(1/\varepsilon) first-order queries and projections. Online, with nonpositive losses and αα-regret measured against αα times the best fixed point, a polynomial-time algorithm achieves γγ-regret O(T)O(\sqrt T) on the largest class. For every fixed, effectively specified γ∈(0,1)γ\in(0,1) and every α∈(γ,1]α\in(γ,1], no randomized polynomial-time algorithm has sublinear expected αα-regret unless NP=RP\mathbf{NP}=\mathbf{RP}, already for smooth concave polynomial losses in the smallest class, each minimized by one linear optimization. Thus, unless NP=RP\mathbf{NP}=\mathbf{RP}, γγ is the exact online coefficient of each class, while the offline coefficient is one.

Figures & tables

Explore similar work

Sep 23, 2026

Sharp Oracle-Regret Tradeoffs for Projection-Free Online Convex Optimization

We characterize the regret attainable in online convex optimization when access to the feasible set is limited to an exact linear optimization oracle. The learner is given an inscribed ball and a diameter bound and must remain feasible on every consistent instance. For convex GG-Lipschitz losses, diameter at most DD, a total allowance of QQ oracle calls, and a strict limit of BB calls per round, the dimension-free minimax expected regret is Θ(GDmax⁡{T,T/(1+min⁡{Q,BT})1/4})Θ(GD\max\{\sqrt T,T/(1+\min\{Q,BT\})^{1/4}\}). The lower bound applies to arbitrary randomized learners. Universal feasibility first forces each action into the hull of the supplied ball and the preceding oracle replies. A fixed-body construction then couples fresh phase directions to a shared simplex, making useful replies costly repeatedly even though all losses have a common minimizer. A counted approximate-gradient method with interleaved blocks attains the matching rate. Total-budget and strict per-round guarantees follow as special cases, including the T3/4T^{3/4} rate with one call per round and the quadratic total budget needed for T\sqrt T regret. For prescribed smoothness ββ, an analytic construction yields a curvature-dependent lower bound and identifies the threshold above which the general characterization remains sharp.
Jan 20, 2026

Small Gradient Norm Regret for Online Convex Optimization

This paper introduces a new problem-dependent regret measure for online convex optimization with smooth losses. The notion, which we call the G⋆G^\star regret, depends on the cumulative squared gradient norm evaluated at the decision in hindsight. We show that the G⋆G^\star regret strictly refines the existing L⋆L^\star (small loss) regret, and that it can be arbitrarily sharper when the losses have vanishing curvature around the hindsight decision. We establish upper and lower bounds on the G⋆G^\star regret and extend our results to dynamic regret and bandit settings. As a byproduct, we refine the existing convergence analysis of stochastic optimization algorithms in the interpolation regime. Some experiments validate our theoretical findings.
Oct 14, 2026

Tracking a Small Set of Experts in Online Convex Optimization

For the fundamental problem of prediction from expert advice, Freund asked whether one could compete with a comparator that switches kk times among only mm experts. For a discrete set of experts, this problem was resolved by Bousquet and Warmuth (2020), who gave an efficient algorithm with optimal regret matching the information-theoretic limit. We study the analogous problem in online convex optimization, where the action space is continuous. An inefficient algorithm can be derived by discretizing the action space and applying the Bousquet--Warmuth algorithm, giving regret of O~(md+k)\widetilde{O}(md+k), while the best known efficient algorithm for this problem has regret O~(dk)\widetilde{O}(dk). We show that this computational inefficiency is inherent, establishing a separation between the information-theoretic and polynomial-time regret achievable for this problem. Specifically, under the hypergraphic planted-clique conjecture, we show that for every polynomial-time algorithm there exist instances for which it incurs at least (kd)1−o(1)(k\sqrt d)^{1-o(1)} regret.