5 papers
Actively Learning Halfspaces without Synthetic Data
Hadley Black, Kasper Green Larsen, Arya Mazumdar +2
In the classic point location problem, one is given an arbitrary dataset of points with query access to an unknown halfspace $f : \mathbb{R}^d \to \{0,…
Learning with Monotone Adversarial Corruptions
Kasper Green Larsen, Chirag Pabbaraju, Abhishek Shetty
We study the extent to which standard machine learning algorithms rely on exchangeability and independence of data by introducing a monotone adversarial corruption model. In this m…
The Interplay Between Interpolation and Aggregation in Regression: Optimal Sample Complexity
Mikael Møller Høgsgaard, Kasper Green Larsen, Liang-Yu Zou
This work investigates theoretically the interplay between interpolation and aggregation in regression. We establish that the -graph dimension characterizes learnability for a…
A Fine-Grained Understanding of Uniform Convergence for Halfspaces
Aryeh Kontorovich, Kasper Green Larsen
We study the fine-grained uniform convergence behavior of halfspaces beyond worst-case VC bounds. For inhomogeneous halfspaces in with , we show that standar…
The Sample Complexity of Replicable Realizable PAC Learning
Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju +1
In this paper, we consider the problem of replicable realizable PAC learning. We construct a particularly hard learning problem and show a sample complexity lower bound with a clos…