7 papers
Margin in Abstract Spaces
Yair Ashlagi, Roi Livni, Shay Moran +1
Margin-based learning, exemplified by linear and kernel methods, is one of the few classical settings where generalization guarantees are independent of the number of parameters. T…
Optimal Reconstruction from Linear Queries
Yuval Filmus, Shay Moran, Elizaveta Nesterova
We study the problem of reconstructing an unknown point in from approximate linear queries. This setting arises naturally in applications ranging from low-dimensiona…
Uniform Laws of Large Numbers in Product Spaces
Ron Holzman, Shay Moran, Alexander Shlimovich
Uniform laws of large numbers form a cornerstone of Vapnik--Chervonenkis theory, where they are characterized by the finiteness of the VC dimension. In this work, we study uniform…
Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension
Yuval Filmus, Steve Hanneke, Idan Mehalel +1
A classical result in online learning characterizes the optimal mistake bound achievable by deterministic learners using the Littlestone dimension (Littlestone '88). We prove an an…
The Optimal Approximation Factor in Density Estimation
Olivier Bousquet, Daniel Kane, Shay Moran
Consider the following problem: given two arbitrary densities and a sample-access to an unknown target density , find which of the 's is closer to in total va…
The unstable formula theorem revisited via algorithms
Maryanthe Malliaris, Shay Moran
This paper is about the surprising interaction of a foundational result from model theory, about stability of theories, with algorithmic stability in learning. First, in response t…