Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity

Haitong Liu; Deepak Narayanan Sridharan; David Steurer; Manuel Wiedmer

cs.DSJun 25, 2026

Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity

Authors: Haitong Liu, Deepak Narayanan Sridharan, David Steurer, Manuel Wiedmer

Organizations: ETH Zurich

Abstract

We study the fundamental problem of learning a high-dimensional Gaussian truncated to an unknown halfspace. Lee, Mehrotra and Zampetakis (FOCS'24) recently obtained the first polynomial time algorithm for this problem, but their resulting sample and time complexity bounds are not optimal. Under non-trivial truncation, for any target accuracy $\varepsilon > 0$ and dimension $d$ we give an efficient algorithm that uses $n = \tilde{O}(d^2/\varepsilon^2)$ samples and learns the underlying Gaussian to error $\varepsilon$ in total variation distance. Our algorithm is also fast: its runtime is dominated by the cost of computing the empirical covariance matrix. Both our sample and time complexity are optimal in terms of $d$ and $\varepsilon$ even without truncation: in this regard, we can learn a Gaussian under halfspace truncation for free. The key ingredient behind our result is a novel reinterpretation of the low-degree moments of the truncated Gaussian in terms of a relative truncation parameter. This relative truncation parameter uniquely determines the parameters of the untruncated Gaussian and enables direct parameter recovery. This reinterpretation allows us to circumvent the time intensive projected stochastic gradient descent procedure that is widely used in learning under truncation.

Explore similar work

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

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 2, 2026stat.ML

Mean Testing under Truncation beyond Gaussian

We characterize the fundamental limits of high-dimensional mean testing under arbitrary truncation, where samples are drawn from the conditional distribution

P(\cdot \mid S)

for an unknown truncation set

S

that may hide up to an

\varepsilon

-fraction of the probability mass. For distributions with

p

-th directional moments of magnitude at most

ν_{P,p}

, truncation induces a bias of order

O(ν_{P,p}\varepsilon^{1-1/p})

. This bias creates a sharp information-theoretic detectability floor: when the signal

α

falls below this threshold, the null and alternative hypotheses are indistinguishable even with infinite data. Above this floor, we prove that a simple second-order test achieving near-optimal sample complexity

n = O\!\left(\frac{\|Σ_P\|}{(α-4ν_{P,p}\varepsilon^{1-1/p})^2}\sqrt{d}\right)

. We further identify a structural escape from this finite-moment bias barrier. Under a directional median regularity assumption, truncation bias improves to linear order

O(\varepsilon)

. This reveals an intermediate regime in which estimation requires

Θ(d)

samples for uniform recovery, while testing recovers the classical

Θ(\sqrt d)

rate once truncation bias is eliminated. Together, our results provide a unified framework for mean testing under truncation, connecting finite-moment, sub-Gaussian, and median-regular structural regimes.

Yuhao Wang, Roberto Imbuzeiro Oliveira, Themis Gouleakis

Truncation Regularity 3D Gaussian Splatting Implicit Bias

Ask PDF