# Learning and Testing Convex Functions

arXiv: https://arxiv.org/abs/2511.11498 · HTML: https://mlsanity.com/paper/2511.11498/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 80 references that are in the map.
- First posted on arXiv 14 Nov 2025.

## Builds on (most cited first, 24 of 24)

- [Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent](https://mlsanity.com/paper/2006.12011/) (2020)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [Statistical-Query Lower Bounds via Functional Gradients](https://mlsanity.com/paper/2006.15812/) (2020)
- [Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2006.12476/) (2020)
- [On the Approximation Power of Two-Layer Networks of Random ReLUs](https://mlsanity.com/paper/2102.02336/) (2021)
- [Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks](https://mlsanity.com/paper/2202.05258/) (2022)
- [Agnostic Proper Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2102.05629/) (2021)
- [A Practical Guide to Robust Optimization](https://mlsanity.com/paper/1501.02634/) (2015)
- [A Computational Framework for Multivariate Convex Regression and its Variants](https://mlsanity.com/paper/1509.08165/) (2015)
- [Nonparametric Shape-restricted Regression](https://mlsanity.com/paper/1709.05707/) (2017)
- [Testing Convex Truncation](https://mlsanity.com/paper/2305.03146/) (2023)
- [Properly learning monotone functions via local reconstruction](https://mlsanity.com/paper/2204.11894/) (2022)
- [Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals](https://mlsanity.com/paper/2411.14349/) (2024)
- [Robust testing of low-dimensional functions](https://mlsanity.com/paper/2004.11642/) (2020)
- [Agnostic proper learning of monotone functions: beyond the black-box correction barrier](https://mlsanity.com/paper/2304.02700/) (2023)
- [Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions](https://mlsanity.com/paper/2310.12375/) (2023)
- [A o(n) monotonicity tester for Boolean functions over the hypercube](https://mlsanity.com/paper/1302.4536/) (2013)
- [Testing and Learning Convex Sets in the Ternary Hypercube](https://mlsanity.com/paper/2305.03194/) (2023)
- [Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach](https://mlsanity.com/paper/2404.17882/) (2024)
- [Lower Bounds for Convexity Testing](https://mlsanity.com/paper/2410.17958/) (2024)
- [Robust learning of halfspaces under log-concave marginals](https://mlsanity.com/paper/2505.13708/) (2025)
- [Testing local properties of arrays](https://mlsanity.com/paper/1811.07448/) (2018)
- [Parameterized Convexity Testing](https://mlsanity.com/paper/2110.13012/) (2021)
- [Local Lipschitz Filters for Bounded-Range Functions with Applications to Arbitrary Real-Valued Functions](https://mlsanity.com/paper/2308.14716/) (2023)

## Built on by (most cited first, 2 of 2)

- [Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2602.24178/) (2026)
- [Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2605.27594/) (2026)

## Abstract (arXiv)

We consider the problems of learning and 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 nO(1/varepsilon2) samples, together with a complementary lower bound of npoly(1/varepsilon) samples in the 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(√n/varepsilon)n samples.