25 citations · 76 across the 24 of their papers we have counts for
10 papers · 1 filter
Learning Correlated Reward Models: Statistical Barriers and Opportunities
Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Gabriele Farina +1
Random Utility Models (RUMs) are a classical framework for modeling user preferences and play a key role in reward modeling for Reinforcement Learning from Human Feedback (RLHF). H…
The Space Complexity of Learning-Unlearning Algorithms
Yeshwanth Cherapanamjeri, Sumegha Garg, Nived Rajaraman +2
We study the memory complexity of machine unlearning algorithms that provide strong data deletion guarantees to the users. Formally, consider an algorithm for a particular learning…
How much is a noisy image worth? Data Scaling Laws for Ambient Diffusion
Giannis Daras, Yeshwanth Cherapanamjeri, Constantinos Daskalakis
The quality of generative models depends on the quality of the data they are trained on. Creating large-scale, high-quality datasets is often expensive and sometimes impossible, e.…
Optimal PAC Bounds Without Uniform Convergence
Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty +1
In statistical learning theory, determining the sample complexity of realizable binary classification for VC classes was a long-standing open problem. The results of Simon and Hann…
The One-Inclusion Graph Algorithm is not Always Optimal
Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty +1
The one-inclusion graph algorithm of Haussler, Littlestone, and Warmuth achieves an optimal in-expectation risk bound in the standard PAC classification setup. In one of the first…
Uniform Approximations for Randomized Hadamard Transforms with Applications
Yeshwanth Cherapanamjeri, Jelani Nelson
Randomized Hadamard Transforms (RHTs) have emerged as a computationally efficient alternative to the use of dense unstructured random matrices across a range of domains in computer…
Adversarial Examples in Multi-Layer Random ReLU Networks
Peter L. Bartlett, Sébastien Bubeck, Yeshwanth Cherapanamjeri
We consider the phenomenon of adversarial examples in ReLU networks with independent gaussian parameters. For networks of constant depth and with a large range of widths (for insta…
A single gradient step finds adversarial examples on random two-layers neural networks
Sébastien Bubeck, Yeshwanth Cherapanamjeri, Gauthier Gidel +1
Daniely and Schacham recently showed that gradient descent finds adversarial examples on random undercomplete two-layers ReLU neural networks. The term "undercomplete" refers to th…
Thresholding based Efficient Outlier Robust PCA
Yeshwanth Cherapanamjeri, Prateek Jain, Praneeth Netrapalli
We consider the problem of outlier robust PCA (OR-PCA) where the goal is to recover principal directions despite the presence of outlier data points. That is, given a data matrix $…
Nearly-optimal Robust Matrix Completion
Yeshwanth Cherapanamjeri, Kartik Gupta, Prateek Jain
In this paper, we consider the problem of Robust Matrix Completion (RMC) where the goal is to recover a low-rank matrix by observing a small number of its entries out of which a fe…