Learning and Testing Convex Functions

Renato Ferreira Pinto Jr., Cassandra Marcussen, Elchanan Mossel, Shivam NadimpalliarXiv 2025 · DOI · arXiv

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:

  1. 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.
  2. 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.

Figure 2: (a) A convex function and its piecewise linear approximation. (b) A non-convex function where the empirical convex envelope (red dashed line) deviates from the function values, enabling detection.

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

Abstract

We consider the problems of \emph{learning} and \emph{testing} real-valued convex functions over Gaussian space. Despite the extensive study of function convexity across mathematics, statistics, and computer science, its learnability and testability have largely been examined only in discrete or restricted settings -- typically with respect to the Hamming distance, which is ill-suited for real-valued functions. In contrast, we study these problems in high dimensions under the standard Gaussian measure, assuming sample access to the function and a mild smoothness condition, namely Lipschitzness. A smoothness assumption is natural and, in fact, necessary even in one dimension: without it, convexity cannot be inferred from finitely many samples. As our main results, we give: - Learning Convex Functions: An agnostic proper learning algorithm for Lipschitz convex functions that achieves error $\varepsilon$ using $n^{O(1/\varepsilon^2)}$ samples, together with a complementary lower bound of $n^{\mathrm{poly}(1/\varepsilon)}$ samples in the \emph{correlational statistical query (CSQ)} model. - Testing Convex Functions: A tolerant (two-sided) tester for convexity of Lipschitz functions with the same sample complexity (as a corollary of our learning result), and a one-sided tester (which never rejects convex functions) using $O(\sqrt{n}/\varepsilon)^n$ samples.
BibTeX
@misc{jr2025learning,
  author = {Renato Ferreira Pinto Jr. and Cassandra Marcussen and Elchanan Mossel and Shivam Nadimpalli},
  title = {{Learning and Testing Convex Functions}},
  year = {2025},
  eprint = {2511.11498},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.11498},
}
Figure