Convexity is a fundamental property in mathematical optimization, statistics, and machine learning. While the properties of convex functions are well-documented, the "meta-problems"—learning a convex function from samples or testing if an unknown function is convex—have historically been confined to discrete settings or low-dimensional cases. This research establishes the first rigorous framework for these tasks in high-dimensional Euclidean space ($\mathbb{R}^n$) under the standard Gaussian measure.
The Challenge of High Dimensions
In high dimensions, convexity is surprisingly fragile. Without regularity assumptions, convexity cannot be reliably inferred from finite samples; a single undetected "spike" could violate convexity. To address this, the authors assume functions are Lipschitz continuous, a standard regularity condition that makes the problem well-defined in Gaussian space.
Methods for Learning and Testing
The paper introduces several novel techniques to bridge the gap between functional analysis and computational learning theory.
Agnostic Proper Learning
The learning algorithm follows a two-step process:
- Hermite Approximation: The authors demonstrate that Lipschitz functions over Gaussian space are "approximately low-degree" in the Hermite basis. They learn a low-degree Hermite polynomial via regression.
- Convexification: This polynomial is then projected onto the space of convex Lipschitz functions using a quadratically constrained convex program over a discretized grid.
Testing-via-Learning and the Empirical Envelope
For two-sided (tolerant) testing, the authors use the agnostic learner to estimate the distance of a function to the nearest convex one.
For one-sided testing, which must never reject a truly convex function, they construct an "empirical convex envelope"—the functional equivalent of a convex hull. By checking if the function values at sampled points match this envelope, the algorithm can detect non-convexity.
Key Results and Complexity Gaps
The research reveals a significant disparity between different testing and learning objectives:
- Agnostic Learning & Two-Sided Testing: These tasks achieve an error $\epsilon$ with a sample complexity of $n^{O(L^2/\epsilon^2)}$. While polynomial in the dimension $n$, the runtime remains exponential.
- One-Sided Testing: This is significantly harder, requiring $O(\sqrt{n}L/\epsilon)^n$ samples. This suggests that "never being wrong" about convexity is exponentially more difficult than being "mostly right."
- Fundamental Barriers: Using the Correlational Statistical Query (CSQ) model, the authors prove that the $n^{poly(1/\epsilon)}$ complexity is a fundamental barrier for many common algorithmic classes, including those based on gradient descent.
Insights and Future Directions
A key takeaway is that Lipschitzness is a mandatory requirement for meaningful inference of convexity from finite data. The "Hermite Connection" provides a powerful tool for approximating these functions.
Future work remains in closing the "sample-runtime gap" for learning and extending lower bounds to the full Statistical Query (SQ) model. Additionally, the authors pose a provocative question: can a function's global distance to convexity be bounded by local curvature data, such as the negative part of its Hessian? This would further link local properties to global structural inference.
Summary updated