3 citations · 3 across the 5 of their papers we have counts for
8 papers · 1 filter
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…
A Unified Characterization of Private Learnability via Graph Theory
Noga Alon, Shay Moran, Hilla Schefler +1
We provide a unified framework for characterizing pure and approximate differentially private (DP) learnability. The framework uses the language of graph theory: for a concept clas…