15 citations · 82 across the 26 of their papers we have counts for
32 papers · 1 filter
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…
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…
Local Borsuk-Ulam, Stability, and Replicability
Zachary Chase, Bogdan Chornomaz, Shay Moran +1
We use and adapt the Borsuk-Ulam Theorem from topology to derive limitations on list-replicable and globally stable learning algorithms. We further demonstrate the applicability of…
Universal Rates for Multiclass Learning
Steve Hanneke, Shay Moran, Qian Zhang
We study universal rates for multiclass classification, establishing the optimal rates (up to log factors) for all hypothesis classes. This generalizes previous results on binary c…
Multiclass Boosting: Simple and Intuitive Weak Learning Criteria
Nataly Brukhim, Amit Daniely, Yishay Mansour +1
We study a generalization of boosting to the multiclass setting. We introduce a weak learning condition for multiclass classification that captures the original notion of weak lear…