Learning and Testing Convex Functions

Renato Ferreira Pinto; Cassandra Marcussen; Elchanan Mossel; Shivam Nadimpalli

cs.DSNov 14, 2025

Learning and Testing Convex Functions

Authors: Renato Ferreira Pinto, Cassandra Marcussen, Elchanan Mossel, Shivam Nadimpalli

Organizations: Columbia University · Harvard University · MIT

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.

Explore similar work

May 8, 2026math.FA

Structure-Preserving Reconstruction of Convex Lipschitz Functionals on Hilbert Spaces from Finite Samples

Convex functionals are ubiquitous in applied analysis, appearing as value functions, risk measures, super-hedging prices, and loss functionals in machine learning. In many applications, however, the functional is only observed through finitely many exact pointwise evaluations. We ask whether a convex functional on a separable Hilbert space

H

can be reconstructed, up to arbitrary uniform accuracy, by an explicit formula which preserves convexity and Lipschitz regularity and is finitely computable. We answer this affirmatively. For every compact convex

C\subseteq H

, every

L

-Lipschitz convex functional

ρ:C\to\mathbb{R}

, and every

\varepsilon>0

, we construct an explicit finite-sample reconstruction which is convex,

L

-Lipschitz, and uniformly

\varepsilon

-accurate on

C

. The construction uses only finitely many linear measurements

\langle b,\cdot\rangle_H

, with

b

lying in a finite-dimensional subspace of

H

, and is exactly implementable by a

\operatorname{ReLU}

-MLP. Building on this, we introduce convex neural functionals (CNFs), a structured trainable architecture class containing our reconstruction, whose every admissible parameter configuration is automatically convex and Lipschitz, providing a principled foundation for learning convex functionals from finite data.

Anastasis Kratsios

Lipschitz Constant Kernel Hilbert Spaces Convex Sets Neural-Network Approximation Finite-Sample

Ask PDF

Apr 29, 2026cs.LG

Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals

We study three problems that involve identifying homogeneous halfspaces under Gaussian distributions: agnostic learning, one-sided reliable learning, and fairness auditing. In each of these problems, we are given labeled examples

(\mathbf{x}, \mathrm{y})

drawn from an unknown distribution on

\mathbb{R}^d\times\{-1, +1\}

, whose marginal distribution on

\mathbf{x}

is standard Gaussian and on

\mathrm{y}

is arbitrary. The goal of each problem is to output a homogeneous halfspace that approaches the best-fitting homogeneous halfspace in terms of its corresponding loss measure. We prove near-optimal computational hardness results for these problems under the widely believed hardness assumption of the Learning With Errors (LWE) problem. Prior hardness results for these problems were mostly established for general halfspaces; our findings extend some of these hardness results to homogeneous halfspaces. Remarkably, our lower bound strictly generalizes over prior works and narrows the gap between the upper and lower bounds for agnostically learning homogeneous halfspaces under Gaussian marginals.

Jizhou Huang, Brendan Juba

Optimal Sample Complexity Homomorphic Encryption Np-Hard Lipschitz Constant

Ask PDF

May 26, 2026cs.DS

Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals

We study the problem of computationally efficient proper agnostic learning of multidimensional concept classes under the Gaussian distribution. In this setting, given i.i.d. labeled samples from an unknown distribution over

\mathbb{R}^d \times \{\pm 1\}

whose marginal on

\mathbb{R}^d

is Gaussian, the goal is to output a hypothesis from a target class

\mathcal{F}

whose 0-1 loss is within

ε

of that of the best classifier in

\mathcal{F}

. We give the first efficient proper agnostic learning algorithm for arbitrary Boolean functions of

K

halfspaces under Gaussian marginals. Our algorithm runs in time

d^{O(K^2 \log(1/ε)/ε^2)} + (K/ε)^{O(K^3/ε^{2.5})}

. Prior to our work, the only known algorithm for

K \geq 2

was brute-force search, with run-time exponential in

d

. Moreover, the dependence of our run-time on the dimension

d

matches that of the best known improper learning algorithm, namely

d^{\widetilde{O}(K^2/ε^2)}

. For the special case of a single halfspace (

K=1

), the best previous run-time was

d^{O(1/ε^4)} + (1/ε)^{O(1/ε^6)}

. Our algorithm improves this to

d^{O(1/ε^2)} + (1/ε)^{O(1/ε^{2.5})}

. Once again, the dependence on

d

matches that of the best known improper algorithm, namely

d^{O(1/ε^2)}

. Furthermore, the dependence of our run-time on the dimension

d

is essentially optimal in the statistical query model.

Sergei Tikhonov, Arsen Vasilyan

Optimal Sample Complexity Binary Classification Distributional Learning 3D Gaussian Splatting

Ask PDF