Publications (78)
Near-Polynomially Competitive Active Logistic Regression
Yihan Zhou, Eric Price, Trung Nguyen
We address the problem of active logistic regression in the realizable setting. It is well known that active learning can require exponentially fewer label queries compared to pass…
Lower Bounds for Sparse Recovery
Khanh Do Ba, Piotr Indyk, Eric Price +1
We consider the following k-sparse recovery problem: design an m x n matrix A, such that for any signal x, given Ax we can efficiently recover x' satisfying ||x-x'||_1 <= C min_{k-…
Nearly Optimal Sparse Fourier Transform
Haitham Hassanieh, Piotr Indyk, Dina Katabi +1
We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. We show: * An O(k log n)-time randomized algorithm for…
Fourier-sparse interpolation without a frequency gap
Xue Chen, Daniel M. Kane, Eric Price +1
We consider the problem of estimating a Fourier-sparse signal from noisy samples, where the sampling is done over some interval and the frequencies can be "off-grid". Prev…
BirdRecorder's AI on Sky: Safeguarding birds of prey by detection and classification of tiny objects around wind turbines
Nico Klar, Nizam Gifary, Felix P. G. Ziegler +4
The urgent need for renewable energy expansion, particularly wind power, is hindered by conflicts with wildlife conservation. To address this, we developed BirdRecorder, an advance…
Separations and Equivalences between Turnstile Streaming and Linear Sketching
John Kallaugher, Eric Price
A longstanding observation, which was partially proven in \cite{LNW14,AHLW16}, is that any turnstile streaming algorithm can be implemented as a linear sketch (the reverse is trivi…
A Fast Binary Splitting Approach to Non-Adaptive Group Testing
Eric Price, Jonathan Scarlett
In this paper, we consider the problem of noiseless non-adaptive group testing under the for-each recovery guarantee, also known as probabilistic group testing. In the case of …
Phi-4 Technical Report
Marah Abdin, Jyoti Aneja, Harkirat Behl +24
We present phi-4, a 14-billion parameter language model developed with a training recipe that is centrally focused on data quality. Unlike most language models, where pre-training…
Compressed Sensing using Generative Models
Ashish Bora, Ajil Jalal, Eric Price +1
The goal of compressed sensing is to estimate a vector from an underdetermined system of noisy linear measurements, by making use of prior knowledge on the structure of vectors in…
Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu
Arnab Bhattacharyya, Sutanu Gayen, Eric Price +1
We provide finite sample guarantees for the classical Chow-Liu algorithm (IEEE Trans.~Inform.~Theory, 1968) to learn a tree-structured graphical model of a distribution. For a dist…
The Sketching Complexity of Graph and Hypergraph Counting
John Kallaugher, Michael Kapralov, Eric Price
Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database pr…
Sharp Noisy Binary Search with Monotonic Probabilities
Lucas Gretta, Eric Price
We revisit the noisy binary search model of Karp and Kleinberg, in which we have coins with unknown probabilities that we can flip. The coins are sorted by increasing $p_…
Robust polynomial regression up to the information theoretic limit
Daniel Kane, Sushrut Karmalkar, Eric Price
We consider the problem of robust polynomial regression, where one receives samples that are usually within of a polynomial , but have a chance of…
Improved Concentration Bounds for Count-Sketch
Gregory T. Minton, Eric Price
We present a refined analysis of the classic Count-Sketch streaming heavy hitters algorithm [CCF02]. Count-Sketch uses O(k log n) linear measurements of a vector x in R^n to give a…
Fairness for Image Generation with Uncertain Sensitive Attributes
Ajil Jalal, Sushrut Karmalkar, Jessica Hoffmann +2
This work tackles the issue of fairness in the context of generative procedures, such as image super-resolution, which entail different definitions from the standard classification…
Linear Bandit Algorithms with Sublinear Time Complexity
Shuo Yang, Tongzheng Ren, Sanjay Shakkottai +3
We propose two linear bandits algorithms with per-step complexity sublinear in the number of arms . The algorithms are designed for applications where the arm set is extremely l…
Autonomous Blimp Control using Deep Reinforcement Learning
Yu Tang Liu, Eric Price, Pascal Goldschmid +2
Aerial robot solutions are becoming ubiquitous for an increasing number of tasks. Among the various types of aerial robots, blimps are very well suited to perform long-duration tas…
A Hybrid Sampling Scheme for Triangle Counting
John Kallaugher, Eric Price
We study the problem of estimating the number of triangles in a graph stream. No streaming algorithm can get sublinear space on all graphs, so methods in this area bound the space…
Active Regression via Linear-Sample Sparsification
Xue Chen, Eric Price
We present an approach that improves the sample complexity for a variety of curve fitting problems, including active learning for linear regression, polynomial regression, and cont…
Adversarial examples from computational constraints
Sébastien Bubeck, Eric Price, Ilya Razenshteyn
Why are classifiers in high dimension vulnerable to "adversarial" perturbations? We show that it is likely not due to information theoretic limitations, but rather it could be due…
Adversarial Examples from Cryptographic Pseudo-Random Generators
Sébastien Bubeck, Yin Tat Lee, Eric Price +1
In our recent work (Bubeck, Price, Razenshteyn, arXiv:1805.10204) we argued that adversarial examples in machine learning might be due to an inherent computational hardness of the…
Efficient Sketches for the Set Query Problem
Eric Price
We develop an algorithm for estimating the values of a vector x in R^n over a support S of size k from a randomized sparse binary linear sketch Ax of size O(k). Given Ax and S, we…
Diffusion Posterior Sampling is Computationally Intractable
Shivam Gupta, Ajil Jalal, Aditya Parulekar +2
Diffusion models are a remarkably effective way of learning and sampling from a distribution . In posterior sampling, one is also given a measurement model and…
Tight bounds for learning a mixture of two gaussians
Moritz Hardt, Eric Price
We consider the problem of identifying the parameters of an unknown mixture of two arbitrary -dimensional gaussians from a sequence of independent random samples. Our main resul…
Nearly-optimal bounds for sparse recovery in generic norms, with applications to -median sketching
Arturs Backurs, Piotr Indyk, Eric Price +2
We initiate the study of trade-offs between sparsity and the number of measurements in sparse recovery schemes for generic norms. Specifically, for a norm , sparsity par…
K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance
Piotr Indyk, Eric Price
We initiate the study of sparse recovery problems under the Earth-Mover Distance (EMD). Specifically, we design a distribution over m x n matrices A such that for any x, given Ax,…
Lower Bounds for Compressed Sensing with Generative Models
Akshay Kamath, Sushrut Karmalkar, Eric Price
The goal of compressed sensing is to learn a structured signal from a limited number of noisy linear measurements . In traditional compressed sensing, "structure"…
Sharp Constants in Uniformity Testing via the Huber Statistic
Shivam Gupta, Eric Price
Uniformity testing is one of the most well-studied problems in property testing, with many known test statistics, including ones based on counting collisions, singletons, and the e…
AirPose: Multi-View Fusion Network for Aerial 3D Human Pose and Shape Estimation
Nitin Saini, Elia Bonetto, Eric Price +2
In this letter, we present a novel markerless 3D human motion capture (MoCap) system for unstructured, outdoor environments that uses a team of autonomous unmanned aerial vehicles…
Improved Sample Complexity Bounds for Diffusion Model Training
Shivam Gupta, Aditya Parulekar, Eric Price +1
Diffusion models have become the most popular approach to deep generative modeling of images, largely due to their empirical performance and reliability. From a theoretical standpo…
Compressed Sensing with Deep Image Prior and Learned Regularization
Dave Van Veen, Ajil Jalal, Mahdi Soltanolkotabi +3
We propose a novel method for compressed sensing recovery using untrained deep generative models. Our method is based on the recently proposed Deep Image Prior (DIP), wherein the c…
New constructions of RIP matrices with fast multiplication and fewer rows
Jelani Nelson, Eric Price, Mary Wootters
In compressed sensing, the "restricted isometry property" (RIP) is a sufficient condition for the efficient reconstruction of a nearly k-sparse vector x in C^d from m linear measur…
Extensions and Limitations of the Neural GPU
Eric Price, Wojciech Zaremba, Ilya Sutskever
The Neural GPU is a recent model that can learn algorithms such as multi-digit binary addition and binary multiplication in a way that generalizes to inputs of arbitrary length. We…
Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions
Badih Ghazi, Haitham Hassanieh, Piotr Indyk +3
We present the first sample-optimal sublinear time algorithms for the sparse Discrete Fourier Transform over a two-dimensional sqrt{n} x sqrt{n} grid. Our algorithms are analyzed f…
Binary Embedding: Fundamental Limits and Fast Algorithm
Xinyang Yi, Constantine Caramanis, Eric Price
Binary embedding is a nonlinear dimension reduction methodology where high dimensional data are embedded into the Hamming cube while preserving the structure of the original space.…
A Competitive Algorithm for Agnostic Active Learning
Eric Price, Yihan Zhou
For some hypothesis classes and input distributions, active agnostic learning needs exponentially fewer samples than passive learning; for other classes and distributions, it offer…
Total Variation Distance Estimation in Autoregressive Models
Eric Price, Kevin Tian, Zhiyang Xun +1
Modern LLM deployments use a number of implementation choices and inference optimizations (e.g., batching, custom kernels, and quantization) on top of fixed weights, so two engines…
Optimal Identity Testing with High Probability
Ilias Diakonikolas, Themis Gouleakis, John Peebles +1
We study the problem of testing identity against a given distribution with a focus on the high confidence regime. More precisely, given samples from an unknown distribution ove…
A Robust Sparse Fourier Transform in the Continuous Setting
Eric Price, Zhao Song
In recent years, a number of works have studied methods for computing the Fourier transform in sublinear time if the output is sparse. Most of these have focused on the discrete se…
Stochastic Multi-armed Bandits in Constant Space
David Liau, Eric Price, Zhao Song +1
We consider the stochastic bandit problem in the sublinear space setting, where one cannot record the win-loss record for all arms. We give an algorithm using words of s…
Accelerated Video Annotation driven by Deep Detector and Tracker
Eric Price, Aamir Ahmad
Annotating object ground truth in videos is vital for several downstream tasks in robot perception and machine learning, such as for evaluating the performance of an object tracker…
Query Lower Bounds for Diffusion Sampling
Zhiyang Xun, Eric Price
Diffusion models generate samples by iteratively querying learned score estimates. A rapidly growing literature focuses on accelerating sampling by minimizing the number of score e…
Fast Regression with an Guarantee
Eric Price, Zhao Song, David P. Woodruff
Sketching has emerged as a powerful technique for speeding up problems in numerical linear algebra, such as regression. In the overconstrained regression problem, one is given an $…
Compressive Sensing with Local Geometric Features
Rishi Gupta, Piotr Indyk, Eric Price +1
We propose a framework for compressive sensing of images with local distinguishable objects, such as stars, and apply it to solve a problem in celestial navigation. Specifically, l…
Optimal Non-Adaptive Probabilistic Group Testing in General Sparsity Regimes
Wei Heng Bay, Eric Price, Jonathan Scarlett
In this paper, we consider the problem of noiseless non-adaptive probabilistic group testing, in which the goal is high-probability recovery of the defective set. We show that in t…
Fast Splitting Algorithms for Sparsity-Constrained and Noisy Group Testing
Eric Price, Jonathan Scarlett, Nelvin Tan
In group testing, the goal is to identify a subset of defective items within a larger set of items based on tests whose outcomes indicate whether at least one defective item is pre…
Active Perception based Formation Control for Multiple Aerial Vehicles
Rahul Tallamraju, Eric Price, Roman Ludwig +4
Autonomous motion capture (mocap) systems for outdoor scenarios involving flying or mobile cameras rely on i) a robotic front-end to track and follow a human subject in real-time w…
Robust Compressed Sensing MRI with Deep Generative Priors
Ajil Jalal, Marius Arvinte, Giannis Daras +3
The CSGM framework (Bora-Jalal-Price-Dimakis'17) has shown that deep generative priors can be powerful tools for solving inverse problems. However, to date this framework has been…
The Noisy Power Method: A Meta Algorithm with Applications
Moritz Hardt, Eric Price
We provide a new robust convergence analysis of the well-known power method for computing the dominant singular vectors of a matrix that we call the noisy power method. Our result…
Coresets for Data Discretization and Sine Wave Fitting
Alaa Maalouf, Murad Tukan, Eric Price +2
In the \emph{monitoring} problem, the input is an unbounded stream of integers in , that are obtained from a sensor (such as GPS or heart b…
Compressed Sensing with Adversarial Sparse Noise via L1 Regression
Sushrut Karmalkar, Eric Price
We present a simple and effective algorithm for the problem of \emph{sparse robust linear regression}. In this problem, one would like to estimate a sparse vector $w^* \in \mathbb{…
Finite-Sample Symmetric Mean Estimation with Fisher Information Rate
Shivam Gupta, Jasper C. H. Lee, Eric Price
The mean of an unknown variance- distribution can be estimated from samples with variance and nearly corresponding subgaussian rate. When is know…
Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering
Ilias Diakonikolas, Sushrut Karmalkar, Daniel Kane +2
We study high-dimensional sparse estimation tasks in a robust setting where a constant fraction of the dataset is adversarially corrupted. Specifically, we focus on the fundamental…
Finite-Sample Maximum Likelihood Estimation of Location
Shivam Gupta, Jasper C. H. Lee, Eric Price +1
We consider 1-dimensional location estimation, where we estimate a parameter from samples , with each drawn i.i.d. from a known distribution . For fixe…
Equality of Opportunity in Supervised Learning
Moritz Hardt, Eric Price, Nathan Srebro
We propose a criterion for discrimination against a specified sensitive attribute in supervised learning, where the goal is to predict some target based on available features. Assu…
On the Power of Adaptivity in Sparse Recovery
Piotr Indyk, Eric Price, David P. Woodruff
The goal of (stable) sparse recovery is to recover a -sparse approximation of a vector from linear measurements of . Specifically, the goal is to recover such t…
Simulating Random Walks in Random Streams
John Kallaugher, Michael Kapralov, Eric Price
The random order graph streaming model has received significant attention recently, with problems such as matching size estimation, component counting, and the evaluation of bounde…
Optimal Testing of Discrete Distributions with High Probability
Ilias Diakonikolas, Themis Gouleakis, Daniel M. Kane +2
We study the problem of testing discrete distributions with a focus on the high probability regime. Specifically, given samples from one or more discrete distributions, a property…
Simulation and Control of Deformable Autonomous Airships in Turbulent Wind
Eric Price, Yu Tang Liu, Michael J. Black +1
Abstract. Fixed wing and multirotor UAVs are common in the field of robotics. Solutions for simulation and control of these vehicles are ubiquitous. This is not the case for airshi…
Beyond Catoni: Sharper Rates for Heavy-Tailed and Robust Mean Estimation
Shivam Gupta, Samuel B. Hopkins, Eric Price
We study the fundamental problem of estimating the mean of a -dimensional distribution with covariance given samples. When , \cite{catoni} s…
Factorial Lower Bounds for (Almost) Random Order Streams
Ashish Chiplunkar, John Kallaugher, Michael Kapralov +1
In this paper we introduce and study the \textsc{StreamingCycles} problem, a random order streaming version of the Boolean Hidden Hypermatching problem that has been instrumental i…
Lower Bounds for Adaptive Sparse Recovery
Eric Price, David P. Woodruff
We give lower bounds for the problem of stable sparse recovery from /adaptive/ linear measurements. In this problem, one would like to estimate a vector from linea…
Instance-Optimal Compressed Sensing via Posterior Sampling
Ajil Jalal, Sushrut Karmalkar, Alexandros G. Dimakis +1
We characterize the measurement complexity of compressed sensing of signals drawn from a known prior distribution, even when the support of the prior is the entire space (rather th…
Viewpoint-driven Formation Control of Airships for Cooperative Target Tracking
Eric Price, Michael J. Black, Aamir Ahmad
For tracking and motion capture (MoCap) of animals in their natural habitat, a formation of safe and silent aerial platforms, such as airships with on-board cameras, is well suited…
Batch Sparse Recovery, or How to Leverage the Average Sparsity
Alexandr Andoni, Lior Kamma, Robert Krauthgamer +1
We introduce a \emph{batch} version of sparse recovery, where the goal is to report a sequence of vectors that estimate unknown signals $A_1,\ld…
Estimating the Frequency of a Clustered Signal
Xue Chen, Eric Price
We consider the problem of locating a signal whose frequencies are "off grid" and clustered in a narrow band. Given noisy sample access to a function with Fourier spectrum i…
Airship Formations for Animal Motion Capture and Behavior Analysis
Eric Price, Aamir Ahmad
Using UAVs for wildlife observation and motion capture offers manifold advantages for studying animals in the wild, especially grazing herds in open terrain. The aerial perspective…
A Simple Proof of a New Set Disjointness with Applications to Data Streams
Akshay Kamath, Eric Price, David P. Woodruff
The multiplayer promise set disjointness is one of the most widely used problems from communication complexity in applications. In this problem there are players with subsets $…
Deep Residual Reinforcement Learning based Autonomous Blimp Control
Yu Tang Liu, Eric Price, Michael J. Black +1
Blimps are well suited to perform long-duration aerial tasks as they are energy efficient, relatively silent and safe. To address the blimp navigation and control task, in previous…
Spectral Guarantees for Adversarial Streaming PCA
Eric Price, Zhiyang Xun
In streaming PCA, we see a stream of vectors and want to estimate the top eigenvector of their covariance matrix. This is easier if the spectral…
L1 Regression with Lewis Weights Subsampling
Aditya Parulekar, Advait Parulekar, Eric Price
We consider the problem of finding an approximate solution to regression while only observing a small number of labels. Given an unlabeled data matrix , we…
Collision-based Testers are Optimal for Uniformity and Closeness
Ilias Diakonikolas, Themis Gouleakis, John Peebles +1
We study the fundamental problems of (i) uniformity testing of a discrete distribution, and (ii) closeness testing between two discrete distributions with bounded -norm. Th…
Deep Neural Network-based Cooperative Visual Tracking through Multiple Micro Aerial Vehicles
Eric Price, Guilherme Lawless, Heinrich H. Bülthoff +2
Multi-camera full-body pose capture of humans and animals in outdoor environments is a highly challenging problem. Our approach to it involves a team of cooperating micro aerial ve…
High-dimensional Location Estimation via Norm Concentration for Subgamma Vectors
Shivam Gupta, Jasper C. H. Lee, Eric Price
In location estimation, we are given samples from a known distribution shifted by an unknown translation , and want to estimate as precisely as possible. Asymptoti…
Hardness and Algorithms for Robust and Sparse Optimization
Eric Price, Sandeep Silwal, Samson Zhou
We explore algorithms and limitations for sparse optimization problems such as sparse linear regression and robust linear regression. The goal of the sparse linear regression probl…
(1+eps)-approximate Sparse Recovery
Eric Price, David P. Woodruff
The problem central to sparse recovery and compressive sensing is that of stable sparse recovery: we want a distribution of matrices A in R^{m\times n} such that, for any x \in R^n…
Posterior Sampling by Combining Diffusion Models with Annealed Langevin Dynamics
Zhiyang Xun, Shivam Gupta, Eric Price
Given a noisy linear measurement of a distribution , and a good approximation to the prior , when can we sample from the posterior ? Posterio…
Optimal Lower Bound for Itemset Frequency Indicator Sketches
Eric Price
Given a database, a common problem is to find the pairs or -tuples of items that frequently co-occur. One specific problem is to create a small space "sketch" of the data that r…