Tilted Convexity and an Exact Offline-Online Separation

Mohammad Pedramfar, Rajiv Khanna, Christopher John Quinn, Vaneet AggarwalarXiv 2026 · arXiv

TL;DR

This paper introduces "tilted convexity," a quantitative relaxation of standard convexity that preserves essential properties like global optimality of local minimizers. The authors prove that while these functions are easy to minimize individually (offline), they are fundamentally harder to solve in a sequence (online), establishing the first known class where the "online efficiency" is exactly determined and strictly lower than the "offline efficiency."

What Problem Does This Paper Address?

Convexity is the "gold standard" for optimization because it guarantees that any local minimum is a global one, making it computationally tractable. However, many modern objectives in machine learning, statistics, and control are non-convex. Researchers have long sought "convex-like" relaxations—such as quasiconvexity or pseudoconvexity—that maintain some of convexity's benefits while covering a broader range of functions.

The challenge is that standard relaxations often focus only on the sign of derivatives or changes, ignoring their magnitude. This paper addresses the need for a quantitative relaxation. It asks: if we allow a controlled multiplicative distortion in the basic definitions of convexity, what structural properties remain, and how does this affect our ability to solve these problems efficiently in both static (offline) and sequential (online) settings?

Methods

The authors introduce a distortion parameter $\gamma \in (0, 1]$. They define a "tilt function" $\psi_\gamma(s)$ that multiplies positive values by $\gamma$ and divides negative values by $\gamma$. They then apply this distortion to the three classic, equivalent ways of defining a convex function:

  1. Support by affine functions: The function stays above its tangent line.
  2. Monotonicity of the subdifferential: Gradients "point away" from each other.
  3. Increasing secant slopes: The slope between two points on the graph increases as you move from left to right.

While these three descriptions are identical for standard convex functions ($\gamma = 1$), the authors show that for $\gamma < 1$, they actually define three distinct, nested classes of functions.

To prove the difficulty of the online version, the authors use a reduction from Label Cover, a classic problem in computational complexity. They show that if an algorithm could achieve better-than-$\gamma$ performance in an online setting, it would effectively be solving NP-hard problems in polynomial time.

Datasets

As a theoretical work in optimization and learning theory, this paper does not use standard empirical datasets (like ImageNet). Instead, it relies on constructed mathematical examples to demonstrate the boundaries of these function classes. These include:

  • Concave polynomials and quadratics: Used to show the limits of the classes.
  • Radial functions: Functions like the one shown in Figure 1, which have a single minimizer but regions of negative curvature.
  • Robust regression losses: Such as Cauchy and Geman–McClure losses, which are common in computer vision.

Key Insights and Ideas

  • The Divergence of Definitions: The most striking insight is that the three "faces" of convexity, which we usually treat as one, split apart under relaxation. This creates a hierarchy of function classes (illustrated in Figure 2) that interleave based on the square of the parameter $\gamma$.
The nested hierarchy of tilted convexity classes. As the parameter $\gamma$ decreases, the classes expand toward pseudoconvexity and quasiconvexity.
  • Convex-like Structure: Despite being non-convex, functions in these classes are "well-behaved." Their domains are convex, they are locally Lipschitz (meaning they don't jump around too much), and most importantly, any local minimum is guaranteed to be a global minimum.
  • The Exact Offline-Online Gap: In the offline world, you can minimize these functions to any accuracy $\epsilon$ using a number of queries that scales with $1/\epsilon$. However, in the online world (where functions are revealed one by one), you can only guarantee performance against a benchmark that is "tilted" by $\gamma$. This is the first time such a gap has been calculated exactly for a nested hierarchy of classes.

Key Results

  • Offline Tractability: Smooth functions in any of the three tilted classes can be minimized to additive accuracy $\epsilon$ in polynomial time. Specifically, projected gradient descent requires $O(1/\epsilon)$ queries, and accelerated methods can reach $O(1/\sqrt{\epsilon})$.
  • Online Achievability: The authors provide a polynomial-time algorithm that achieves $O(\sqrt{T})$ "$\gamma$-regret." This means the algorithm performs nearly as well as the best fixed point in hindsight, provided that the benchmark is scaled down by the factor $\gamma$.
  • Computational Hardness: They prove that achieving any "$\alpha$-regret" where $\alpha > \gamma$ is impossible for randomized polynomial-time algorithms unless NP = RP. This establishes $\gamma$ as the fundamental limit for online optimization in these classes.
An example of a tilted convex function (solid) compared to a standard convex function (dashed). The shaded regions show where the function is non-convex, yet it still behaves predictably enough for optimization.

Limitations and Future Work

The authors identify several open questions:

  • Query Efficiency: The current online algorithm requires multiple queries (value and gradient) per round. It remains unknown if the same $\gamma$ coefficient can be achieved using only a single gradient query or just the function value at the current point.
  • Optimality of Rates: While they provide an accelerated rate for offline optimization, it is not yet clear if this rate is the absolute mathematical limit for these specific classes.
  • Bandit Feedback: Extending these results to the "bandit" setting—where the learner only sees the loss value at their chosen point and nothing else—is a significant next step.

Summary updated

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.
BibTeX
@misc{pedramfar2026tilted,
  author = {Mohammad Pedramfar and Rajiv Khanna and Christopher John Quinn and Vaneet Aggarwal},
  title = {{Tilted Convexity and an Exact Offline-Online Separation}},
  year = {2026},
  eprint = {2611.03472},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.03472},
}
Figure