Metraipolis › archive › dc_98fc0ed31800
Tilted Convexity and an Exact Offline-Online Separation — arXiv:2611.03472
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.03472
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T11:23:18.905Z
- SHA-256 of the archived text
23f3d64346c24776f974bfcd71257d47c7571ca91bc6aad9c8439c66195a965d- Stable URL of this page
https://metraipolis.com/documento/dc_98fc0ed31800
How to cite
Tilted Convexity and an Exact Offline-Online Separation — arXiv:2611.03472 — arXiv (en), https://arxiv.org/abs/2611.03472 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_98fc0ed31800 (Metraipolis archive dc_98fc0ed31800, sha256 23f3d64346c24776f974bfcd71257d47c7571ca91bc6aad9c8439c66195a965d)
BibTeX
@misc{dc98fc0ed31800,
title = {Tilted Convexity and an Exact Offline-Online Separation — arXiv:2611.03472},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.03472},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_98fc0ed31800; sha256 23f3d64346c24776f974bfcd71257d47c7571ca91bc6aad9c8439c66195a965d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03472. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\gamma\in(0,1]$, which multiplies positive changes by $\gamma$ and divides negative ones by $\gamma$. The resulting classes are the convex functions at $\gamma=1$ and, for $\gamma<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 $\alpha$-regret measured against $\alpha$ times the best fixed point, a polynomial-time algorithm achieves $\gamma$-regret $O(\sqrt T)$ on the largest class. For every fixed, effectively specified $\gamma\in(0,1)$ and every $\alpha\in(\gamma,1]$, no randomized polynomial-time algorithm has sublinear expected $\alpha$-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}$, $\gamma$ is the exact online coefficient of each class, while the offline coefficient is one.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Computational Complexity (cs.CC); Optimization and Control (math.OC); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2611.03472 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:02:37.712Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).