conftrace_

2026 COLT COLT 2026

How fast can you find a good hypothesis?

Abstract

Hypothesis selection asks for a distribution close to an unknown $P$, given samples from $P$ and access to $n$ candidate hypotheses. We study the computational complexity of achieving statistically optimal sample complexity and approximation constants.

❓ The Questioner

Authors

Anders Aamand, Maryam Aliakbarpour, Justin Y. Chen, Sandeep Silwal

Topics

Machine Learning > Optimization & Theory > Learning Theory Machine Learning > Optimization & Theory > Statistical Learning

Keywords

sample complexity computational complexity hypothesis selection

More from COLT 2026

All COLT 2026 papers →

On efficient robust regression with subquadratic samples

Quiet Planting for k-SAT, Multiple Solutions of Arbitrary Geometry

Optimal Prediction-Augmented Algorithms for Testing Independence of Distributions

Query Efficient Structured Matrix Learning

Swap Regret Minimization Through Response-Based Approachability

Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures