908 citations · 1.7k across the 21 of their papers we have counts for
23 papers
Automatic Prompt Optimization with "Gradient Descent" and Beam Search
Reid Pryzant, Dan Iter, Jerry Li +3
Large Language Models (LLMs) have shown impressive performance as general purpose agents, but their abilities remain highly dependent on prompts which are hand written with onerous…
Query lower bounds for log-concave sampling
Sinho Chewi, Jaume de Dios Pont, Jerry Li +2
Log-concave sampling has witnessed remarkable algorithmic advances in recent years, but the corresponding problem of proving lower bounds for this task has remained elusive, with l…
REAP: A Large-Scale Realistic Adversarial Patch Benchmark
Nabeel Hingun, Chawin Sitawarin, Jerry Li +1
Machine learning models are known to be susceptible to adversarial perturbation. One famous attack is the adversarial patch, a sticker with a particularly crafted pattern that make…
Efficient Algorithms for Multidimensional Segmented Regression
Ilias Diakonikolas, Jerry Li, Anastasia Voloshinov
We study the fundamental problem of fixed design {\em multidimensional segmented regression}: Given noisy samples from a function , promised to be piecewise linear on an unknown…
Sample Efficient Toeplitz Covariance Estimation
Yonina C. Eldar, Jerry Li, Cameron Musco +1
We study the sample complexity of estimating the covariance matrix of a distribution over -dimensional vectors, under the assumption that is Toeplitz. This…
How Hard Is Robust Mean Estimation?
Samuel B. Hopkins, Jerry Li
Robust mean estimation is the problem of estimating the mean of a -dimensional distribution from a list of independent samples, an -fraction of which…
Spectral Signatures in Backdoor Attacks
Brandon Tran, Jerry Li, Aleksander Madry
A recent line of work has uncovered a new form of data poisoning: so-called \emph{backdoor} attacks. These attacks are particularly dangerous because they do not affect a network's…
Privately Learning High-Dimensional Distributions
Gautam Kamath, Jerry Li, Vikrant Singhal +1
We present novel, computationally efficient, and differentially private algorithms for two fundamental high-dimensional learning problems: learning a multivariate Gaussian and lear…
Sever: A Robust Meta-Algorithm for Stochastic Optimization
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane +3
In high dimensions, most machine learning methods are brittle to even a small fraction of structured outliers. To address this, we introduce a new meta-algorithm that can take in a…
Fast and Sample Near-Optimal Algorithms for Learning Multidimensional Histograms
Ilias Diakonikolas, Jerry Li, Ludwig Schmidt
We study the problem of robustly learning multi-dimensional histograms. A -dimensional function is called a -histogram if there exists a partiti…
Mixture Models, Robustness, and Sum of Squares Proofs
Samuel B. Hopkins, Jerry Li
We use the Sum of Squares method to develop new efficient algorithms for learning well-separated mixtures of Gaussians and robust mean estimation, both in high dimensions, that sub…
The Power of Choice in Priority Scheduling
Dan Alistarh, Justin Kopinsky, Jerry Li +1
Consider the following random process: we are given queues, into which elements of increasing labels are inserted uniformly at random. To remove an element, we pick two queues…
On the Limitations of First-Order Approximation in GAN Dynamics
Jerry Li, Aleksander Madry, John Peebles +1
While Generative Adversarial Networks (GANs) have demonstrated promising performance on multiple vision tasks, their learning dynamics are not yet well understood, both in theory a…
Robustly Learning a Gaussian: Getting Optimal Error, Efficiently
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane +3
We study the fundamental problem of learning the parameters of a high-dimensional Gaussian in the presence of noise -- where an -fraction of our samples were chosen by…
Being Robust (in High Dimensions) Can Be Practical
Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane +3
Robust estimation is much more challenging in high dimensions than it is in one dimension: Most techniques either lead to intractable optimization problems or estimators that can t…
Robust Sparse Estimation Tasks in High Dimensions
Jerry Li
In this paper we initiate the study of whether or not sparse estimation tasks can be performed efficiently in high dimensions, in the robust setting where an $\eps$-fraction of sam…
The ZipML Framework for Training Models with End-to-End Low Precision: The Cans, the Cannots, and a Little Bit of Deep Learning
Hantian Zhang, Jerry Li, Kaan Kara +3
Recently there has been significant interest in training machine-learning models at low precision: by reducing precision, one can reduce computation and communication by one order…
QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding
Dan Alistarh, Demjan Grubic, Jerry Li +2
Parallel implementations of stochastic gradient descent (SGD) have received significant research attention, thanks to excellent scalability properties of this algorithm, and to its…
Fast Algorithms for Segmented Regression
Jayadev Acharya, Ilias Diakonikolas, Jerry Li +1
We study the fixed design segmented regression problem: Given noisy samples from a piecewise linear function , we want to recover up to a desired accuracy in mean-squared er…
On the Importance of Registers for Computability
Rati Gelashvili, Mohsen Ghaffari, Jerry Li +1
All consensus hierarchies in the literature assume that we have, in addition to copies of a given object, an unbounded number of registers. But why do we really need these register…
Replacing Mark Bits with Randomness in Fibonacci Heaps
Jerry Li, John Peebles
A Fibonacci heap is a deterministic data structure implementing a priority queue with optimal amortized operation costs. An unfortunate aspect of Fibonacci heaps is that they must…
Model Counting of Query Expressions: Limitations of Propositional Methods
Paul Beame, Jerry Li, Sudeepa Roy +1
Query evaluation in tuple-independent probabilistic databases is the problem of computing the probability of an answer to a query given independent probabilities of the individual…
Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases
Paul Beame, Jerry Li, Sudeepa Roy +1
The best current methods for exactly computing the number of satisfying assignments, or the satisfying probability, of Boolean formulas can be seen, either directly or indirectly,…