Tilted Convexity and an Exact Offline-Online Separation

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 $γ\in(0,1]$, which multiplies positive changes by $γ$ and divides negative ones by $γ$. The resulting classes are the convex functions at $γ=1$ and, for $γ<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 $\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(\sqrt T)$ on the largest class. For every fixed, effectively specified $γ\in(0,1)$ and every $α\in(γ,1]$, no randomized polynomial-time algorithm has sublinear expected $α$-regret unless $\mathbf{NP}=\mathbf{RP}$, already for smooth concave polynomial losses in the smallest class, each minimized by one linear optimization. Thus, unless $\mathbf{NP}=\mathbf{RP}$, $γ$ is the exact online coefficient of each class, while the offline coefficient is one.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Machine Learning

• arXiv preprint · 2 November 2026

  Efficient Proper Agnostic Learning of Halfspaces

  Anindya De, Elchanan Mossel, Shivam Nadimpalli and 1 other
• arXiv preprint · 3 November 2026

  Semidirect sums of tensors and the matrix multiplication exponent

  Baitian Li
• arXiv preprint · 2 November 2026

  State Synthesis with an NP oracle

  Aniruddha Sen
• arXiv preprint · 3 November 2026

  State Evolution and Universality of Iterated Linear Programs for the Binary Perceptron

  Jianan Zhang and Shuangping Li
• arXiv preprint · 2 November 2026

  Circuit Lower Bounds for Extended Gate Bases from Subexponential Counting

  Mengyang Wu and Minghao Wang

All new papers in Machine Learning