Convex optimization is the gold standard of algorithmic optimization because it guarantees that any local minimum is also a global minimum. However, real-world optimization landscapes are rarely perfectly smooth bowls. In practice, objective functions are frequently corrupted by inherent noise, rounding errors, or fractal-like micro-oscillations.
If you zoom out from these landscapes, they exhibit a clear, global convex trend. But if you zoom in, they reveal a jagged terrain of local minima that instantly trap traditional gradient descent algorithms.
To bridge this gap, a powerful research direction has emerged around approximately convex functions. By formalizing what it means for a function to be "nearly" convex, researchers have mapped out the exact theoretical boundaries and algorithmic strategies required to optimize bumpy, non-convex landscapes in polynomial time.
Formalizing the Bumps: Functional Foundations
To analyze a function that is almost convex, mathematicians must first relax the classical definition of convexity. Standard midpoint convexity requires that the function value of a midpoint never exceeds the average of its endpoints:
$$f\left(\frac{x+y}{2}\right) \le \frac{f(x)+f(y)}{2}$$
To model real-world imperfections, this inequality can be modified with a controlled error term. Józef Tabor et al. generalized this framework by incorporating a flexible, distance-dependent error function $\alpha$. They proved that classical regularity properties—such as local boundedness and continuity—still hold even when strict convexity is replaced by this error-tolerant inequality.
However, optimization problems often occur on non-convex or discrete domains (like digital grids), where midpoints might not even exist within the set. To address this, Jacek Tabor et al. introduced a computer-assisted method using interval arithmetic to rigorously calculate the maximum possible deviation of functions satisfying relaxed midconvexity on non-convex sets.
Complementing this, Jacek Chudziak et al. extended the classical maximum principle to "conditionally $\delta$-midconvex" functions. They demonstrated that if a function is only approximately convex within specific subsets of its domain, its global maximum can still be tightly bounded by the values at its extremal vertices plus an error term proportional to the approximation factor $\delta$.
Strict Convexity: \___/ (Single global minimum)
Approximate Convexity: \_/\_/\_/ (Global trend is convex, but full of local traps)
The Fundamental Limits of Noise
Can we efficiently optimize any non-convex function that stays close to a convex baseline? The short answer is no. The feasibility of finding a global minimum depends heavily on a delicate balance between the noise level, the desired accuracy, and the dimensionality of the problem.
Andrej Risteski et al. established the fundamental information-theoretic limits of approximately convex optimization. They proved that if a non-convex function deviates from a true convex baseline by at most a noise factor $\Delta$, polynomial-time optimization to an accuracy of $\epsilon$ is possible if and only if:
$$\Delta \approx \frac{\epsilon^2}{\sqrt{d}}$$
where $d$ is the dimension of the space.
This bound reveals an intuitive but severe curse of dimensionality. In high-dimensional spaces, even a tiny additive perturbation can create an exponential number of local "pockets" that can trap an optimization algorithm. If the noise $\Delta$ exceeds this threshold, the problem becomes fundamentally intractable, requiring exponential time for any algorithm to guarantee an accurate minimum.
Escaping Local Minima via Global Sampling
Because gradient-based methods look only at local derivatives, they are fundamentally unsuited for approximately convex functions; they immediately get stuck in the nearest micro-oscillation. To bypass these local traps, algorithms must replace local steps with global stochastic exploration.
Alexandre Belloni et al. provided a theoretical breakthrough by combining the Hit-and-Run sampling algorithm with Simulated Annealing. Instead of following a gradient, their algorithm treats the objective function as an energy landscape and draws samples from a probability distribution proportional to $\exp(-f(x)/T)$. By starting at a high temperature $T$ and slowly cooling it, the distribution gradually concentrates around the global minimum.
Why does this work? The Hit-and-Run algorithm generates random lines through the search space and takes large, global steps along them. Because these steps are macroscopic rather than infinitesimal, the algorithm routinely "jumps over" the local non-convex bumps, guided entirely by the broader, global convex trend of the landscape.
Gradient Descent: [x] -> Trapped in local dip
Hit-and-Run Step: [x] --------=========>>>> [x] (Jumps over the local dip)
This paradigm was expanded by Oren Mangoubi et al. to handle situations where the noise is not bounded by a constant but scales with the function's value (unbounded oracle noise). By pairing Simulated Annealing with Stochastic Gradient Langevin Dynamics (SGLD), the authors proved that polynomial-time convergence is still guaranteed, provided that the noise coefficients scale inversely with the problem dimension.
Alternative Paradigms: Envelopes and Quantum Speedups
Beyond stochastic sampling, researchers have approached approximately convex optimization from two other distinct angles: surrogate modeling and quantum acceleration.
Learning the Envelope
Rather than navigating a bumpy landscape directly, an alternative strategy is to smooth it out. Eva L. Dyer et al. introduced a framework called Convex Relaxation Regression (CoRR). CoRR takes random samples of a complex, non-convex function and uses them to learn its underlying convex envelope. By fitting a provably convex surrogate to the data, CoRR transforms a needle-in-a-haystack global search into a clean, efficient convex optimization problem, achieving a polynomial error rate relative to the number of samples.
Quantum Acceleration
To push past the query-complexity limits faced by classical algorithms in high dimensions, Tongyang Li et al. introduced a quantum algorithm for optimizing approximately convex functions. By leveraging quantum superposition to evaluate the objective function across multiple states simultaneously, their method achieves a polynomial speedup over classical sampling. When applied to stochastic convex bandit problems, this quantum framework yields logarithmic regret, representing an exponential improvement over the fundamental limits of classical bandit algorithms.
Key Foundational Work
Strict verification of approximate midconvexity on non-convex sets (2013) — contributed 3 concept elements to this direction.
Approximately convex functions on topological vector spaces (2010) — contributed 3 concept elements to this direction.