Tilted convexity defines limits for offline and online optimization methods
Tilted Convexity and an Exact Offline-Online Separation
Machine LearningComputational Complexity
Summary
Convexity is a key idea in optimization, where finding a lowest point is easier if the function behaves nicely. The authors introduce a weaker form of convexity called tilted convexity, which smoothly stretches the usual rules. They show this helps separate how well you can solve problems when you have all data upfront (offline) versus when data comes step-by-step (online). Their results pinpoint exactly how 'tilted' the function can be before online methods stop working efficiently unless major complexity breakthroughs happen.
What this means in practice
- •For machine learning engineers: Design algorithms that minimize losses efficiently when data arrives in a stream, understanding exact limits posed by tilted convexity.
- •For optimization software developers: Develop optimization routines that distinguish offline from online solvability based on the function’s tilt parameter, guiding algorithm choice.
A theory result. No direct application yet.
Authors
Mohammad Pedramfar, Rajiv Khanna, Christopher John Quinn, Vaneet Aggarwal
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.