25 citations · 76 across the 24 of their papers we have counts for
25 papers
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…
Heavy-tailed Contamination is Easier than Adversarial Contamination
Yeshwanth Cherapanamjeri, Daniel Lee
A large body of work in the statistics and computer science communities dating back to Huber (Huber, 1960) has led to statistically and computationally efficient outlier-robust est…
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.…
Efficient Automated Circuit Discovery in Transformers using Contextual Decomposition
Aliyah R. Hsu, Georgia Zhou, Yeshwanth Cherapanamjeri +4
Automated mechanistic interpretation research has attracted great interest due to its potential to scale explanations of neural network internals to large models. Existing automate…
Statistical Barriers to Affine-equivariant Estimation
Zihao Chen, Yeshwanth Cherapanamjeri
We investigate the quantitative performance of affine-equivariant estimators for robust mean estimation. As a natural stability requirement, the construction of such affine-equivar…
Diagnosing Transformers: Illuminating Feature Spaces for Clinical Decision-Making
Aliyah R. Hsu, Yeshwanth Cherapanamjeri, Briton Park +3
Pre-trained transformers are often fine-tuned to aid clinical decision-making using limited clinical notes. Model interpretability is crucial, especially in high-stakes domains lik…
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…
Robust Algorithms on Adaptive Inputs from Bounded Adversaries
Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff +3
We study dynamic algorithms robust to adaptive input generated from sources with bounded capabilities, such as sparsity or limited interaction. For example, we consider robust line…
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…
Estimation of Standard Auction Models
Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Andrew Ilyas +1
We provide efficient estimation methods for first- and second-price auctions under independent (asymmetric) private values and partial observability. Given a finite set of observat…
What Makes A Good Fisherman? Linear Regression under Self-Selection Bias
Yeshwanth Cherapanamjeri, Constantinos Daskalakis, Andrew Ilyas +1
In the classical setting of self-selection, the goal is to learn models, simultaneously from observations where is the output of one of under…
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…
Terminal Embeddings in Sublinear Time
Yeshwanth Cherapanamjeri, Jelani Nelson
Recently (Elkin, Filtser, Neiman 2017) introduced the concept of a {\it terminal embedding} from one metric space to another with a set of designated terminals…
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…
Optimal Mean Estimation without a Variance
Yeshwanth Cherapanamjeri, Nilesh Tripuraneni, Peter L. Bartlett +1
We study the problem of heavy-tailed mean estimation in settings where the variance of the data-generating distribution does not exist. Concretely, given a sample $\mathbf{X} = \{X…
On Adaptive Distance Estimation
Yeshwanth Cherapanamjeri, Jelani Nelson
We provide a static data structure for distance estimation which supports {\it adaptive} queries. Concretely, given a dataset of points in $\mathbb{R}^d…
Optimal Robust Linear Regression in Nearly Linear Time
Yeshwanth Cherapanamjeri, Efe Aras, Nilesh Tripuraneni +3
We study the problem of high-dimensional robust linear regression where a learner is given access to samples from the generative model (with $X…
List Decodable Mean Estimation in Nearly Linear Time
Yeshwanth Cherapanamjeri, Sidhanth Mohanty, Morris Yau
Learning from data in the presence of outliers is a fundamental problem in statistics. Until recently, no computationally efficient algorithms were known to compute the mean of a h…
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond
Yeshwanth Cherapanamjeri, Samuel B. Hopkins, Tarun Kathuria +2
We study efficient algorithms for linear regression and covariance estimation in the absence of Gaussian assumptions on the underlying distributions of samples, making assumptions…
Testing Markov Chains without Hitting
Yeshwanth Cherapanamjeri, Peter L. Bartlett
We study the problem of identity testing of markov chains. In this setting, we are given access to a single trajectory from a markov chain with unknown transition matrix and th…
Fast Mean Estimation with Sub-Gaussian Rates
Yeshwanth Cherapanamjeri, Nicolas Flammarion, Peter L. Bartlett
We propose an estimator for the mean of a random vector in that can be computed in time for i.i.d.~samples and that has error bounds matching the s…
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 $…