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 γ∈(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 ε with poly(1/ε) 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) on the largest class. For every fixed, effectively specified γ∈(0,1) and every α∈(γ,1], no randomized polynomial-time algorithm has sublinear expected α-regret unless NP=RP, already for smooth concave polynomial losses in the smallest class, each minimized by one linear optimization. Thus, unless NP=RP, γ is the exact online coefficient of each class, while the offline coefficient is one.
Related
- Accelerating posterior sampling in Bayesian inverse problems with diffusion models: an online-offline perspective
- Adapting offline models to a streaming context for music source separation
- Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor
- Poisson Exchange Beyond Submodularity: Effective Approximation Algorithms for Offline and Online Subset Selection over Matroids
- Offline–Online Decoupled Architecture for Projected Microsecond-Latency and near Machine-Precision Caputo Fractional Derivative Evaluation, with an Edge-Computing Feasibility Study
BibTeX
@misc{pedramfar2026tilted,
title = {{Tilted Convexity and an Exact Offline-Online Separation}},
author = {Mohammad Pedramfar and Rajiv Khanna and Christopher John Quinn and Vaneet Aggarwal},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03472},
eprint = {2611.03472},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03472},
}
RIS
TY - UNPB
TI - Tilted Convexity and an Exact Offline-Online Separation
AU - Mohammad Pedramfar
AU - Rajiv Khanna
AU - Christopher John Quinn
AU - Vaneet Aggarwal
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03472
UR - https://arxiv.org/abs/2611.03472
AB - 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], 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 ε with poly(1/ε) 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) on the largest class. For every fixed, effectively specified γ∈(0,1) and every α∈(γ,1], no randomized polynomial-time algorithm has sublinear expected α-regret unless NP=RP, already for smooth concave polynomial losses in the smallest class, each minimized by one linear optimization. Thus, unless NP=RP, γ is the exact online coefficient of each class, while the offline coefficient is one.
ER -