Publications (113)
Decomposition Methods for Large Scale LP Decoding
Siddharth Barman, Xishuo Liu, Stark C. Draper +1
When binary linear error-correcting codes are used over symmetric channels, a relaxed version of the maximum likelihood decoding problem can be stated as a linear program (LP). Thi…
K-Planes: Explicit Radiance Fields in Space, Time, and Appearance
Sara Fridovich-Keil, Giacomo Meanti, Frederik Warburg +2
We introduce k-planes, a white-box model for radiance fields in arbitrary dimensions. Our model uses d choose 2 planes to represent a d-dimensional scene, providing a seamless way…
Active Learning for Nonlinear System Identification with Guarantees
Horia Mania, Michael I. Jordan, Benjamin Recht
While the identification of nonlinear dynamical systems is a fundamental building block of model-based reinforcement learning and feedback control, its sample complexity is only un…
Model Similarity Mitigates Test Set Overuse
Horia Mania, John Miller, Ludwig Schmidt +2
Excessive reuse of test data has become commonplace in today's machine learning workflows. Popular benchmarks, competitions, industrial scale tuning, among other applications, all…
Neural Kernels Without Tangents
Vaishaal Shankar, Alex Fang, Wenshuo Guo +4
We investigate the connections between neural networks and simple building blocks in kernel space. In particular, using well established feature space tools such as direct sum, ave…
Representation Matters: Assessing the Importance of Subgroup Allocations in Training Data
Esther Rolf, Theodora Worledge, Benjamin Recht +1
Collecting more diverse and representative training data is often touted as a remedy for the disparate performance of machine learning predictors across subpopulations. However, a…
Least-Squares Temporal Difference Learning for the Linear Quadratic Regulator
Stephen Tu, Benjamin Recht
Reinforcement learning (RL) has been successfully used to solve many continuous control tasks. Despite its impressive results however, fundamental questions regarding the sample co…
Post-Estimation Smoothing: A Simple Baseline for Learning with Side Information
Esther Rolf, Michael I. Jordan, Benjamin Recht
Observational data are often accompanied by natural structural indices, such as time stamps or geographic locations, which are meaningful to prediction tasks but are often discarde…
Near Minimax Line Spectral Estimation
Gongguo Tang, Badri Narayan Bhaskar, Benjamin Recht
This paper establishes a nearly optimal algorithm for estimating the frequencies and amplitudes of a mixture of sinusoids from noisy equispaced samples. We derive our algorithm by…
The Effect of Natural Distribution Shift on Question Answering Models
John Miller, Karl Krauth, Benjamin Recht +1
We build four new test sets for the Stanford Question Answering Dataset (SQuAD) and evaluate the ability of question-answering systems to generalize to new data. Our first test set…
Parallel Correlation Clustering on Big Graphs
Xinghao Pan, Dimitris Papailiopoulos, Samet Oymak +3
Given a similarity graph between items, correlation clustering (CC) groups similar items together and dissimilar ones apart. One of the most popular CC algorithms is KwikCluster: a…
Saturating Splines and Feature Selection
Nicholas Boyd, Trevor Hastie, Stephen Boyd +2
We extend the adaptive regression spline model by incorporating saturation, the natural requirement that a function extend as a constant outside a certain range. We fit saturating…
Gradient Descent Converges to Minimizers
Jason D. Lee, Max Simchowitz, Michael I. Jordan +1
We show that gradient descent converges to a local minimizer, almost surely with random initialization. This is proved by applying the Stable Manifold Theorem from dynamical system…
Large Scale Kernel Learning using Block Coordinate Descent
Stephen Tu, Rebecca Roelofs, Shivaram Venkataraman +1
We demonstrate that distributed block coordinate descent can quickly solve kernel regression and classification problems with millions of data points. Armed with this capability, w…
Compressive classification and the rare eclipse problem
Afonso S. Bandeira, Dustin G. Mixon, Benjamin Recht
This paper addresses the fundamental question of when convex sets remain disjoint after random projection. We provide an analysis using ideas from high-dimensional convex geometry.…
Necessary and Sufficient Conditions for Success of the Nuclear Norm Heuristic for Rank Minimization
Benjamin Recht, Weiyu Xu, Babak Hassibi
Minimizing the rank of a matrix subject to constraints is a challenging problem that arises in many applications in control theory, machine learning, and discrete geometry. This cl…
Certainty Equivalence is Efficient for Linear Quadratic Control
Horia Mania, Stephen Tu, Benjamin Recht
We study the performance of the certainty equivalent controller on Linear Quadratic (LQ) control problems with unknown transition dynamics. We show that for both the fully and part…
A Bureaucratic Theory of Statistics
Benjamin Recht
This commentary proposes a framework for understanding the role of statistics in policy-making, regulation, and bureaucratic systems. I introduce the concept of "ex ante policy," d…
Finite-Data Performance Guarantees for the Output-Feedback Control of an Unknown System
Ross Boczar, Nikolai Matni, Benjamin Recht
As the systems we control become more complex, first-principle modeling becomes either impossible or intractable, motivating the use of machine learning techniques for the control…
Breaking Locality Accelerates Block Gauss-Seidel
Stephen Tu, Shivaram Venkataraman, Ashia C. Wilson +3
Recent work by Nesterov and Stich showed that momentum can be used to accelerate the rate of convergence for block Gauss-Seidel in the setting where a fixed partitioning of the coo…
A note on sampling biases in the Bangladesh mask trial
Maria Chikina, Wesley Pegden, Benjamin Recht
A recent cluster trial in Bangladesh randomized 600 villages into 300 treatment/control pairs, to evaluate the impact of an intervention to increase mask-wearing. Data was analyzed…
Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
Stephen Tu, Ross Boczar, Max Simchowitz +2
In this paper we study the problem of recovering a low-rank matrix from linear measurements. Our algorithm, which we call Procrustes Flow, starts from an initial estimate obtained…
Exact Matrix Completion via Convex Optimization
Emmanuel J. Candes, Benjamin Recht
We consider a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. Suppose that we observe m entries selected uniformly at rand…
Randomization Inference When N Equals One
Tengyuan Liang, Benjamin Recht
N-of-1 experiments, where a unit serves as its own control and treatment in different time windows, have been used in certain medical contexts for decades. However, due to effects…
Online Control for Adaptive Tapering of Medications
Paula Gradu, Benjamin Recht
We investigate adaptive protocols for the elimination or reduction of the use of medications or addictive substances. We formalize this problem as online optimization, minimizing t…
On the Approximation of Toeplitz Operators for Nonparametric -norm Estimation
Stephen Tu, Ross Boczar, Benjamin Recht
Given a stable SISO LTI system , we investigate the problem of estimating the -norm of , denoted , when is only accessible via noisy obs…
Guaranteeing Safety of Learned Perception Modules via Measurement-Robust Control Barrier Functions
Sarah Dean, Andrew J. Taylor, Ryan K. Cosner +2
Modern nonlinear control theory seeks to develop feedback controllers that endow systems with properties such as safety and stability. The guarantees ensured by these controllers o…
Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator
Sarah Dean, Horia Mania, Nikolai Matni +2
We consider adaptive control of the Linear Quadratic Regulator (LQR), where an unknown linear system is controlled subject to quadratic costs. Leveraging recent developments in the…
Efficient Discrete Approximations of Quantum Gates
Aram W. Harrow, Benjamin Recht, Isaac L. Chuang
Quantum compiling addresses the problem of approximating an arbitrary quantum gate with a string of gates drawn from a particular finite set. It has been shown that this is possibl…
A Simpler Approach to Matrix Completion
Benjamin Recht
This paper provides the best bounds to date on the number of randomly sampled entries required to reconstruct an unknown low rank matrix. These results improve on prior work by Can…
HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
Feng Niu, Benjamin Recht, Christopher Re +1
Stochastic Gradient Descent (SGD) is a popular algorithm that can achieve state-of-the-art performance on a variety of machine learning tasks. Several researchers have recently pro…
A Tour of Reinforcement Learning: The View from Continuous Control
Benjamin Recht
This manuscript surveys reinforcement learning from the perspective of optimization and control with a focus on continuous control applications. It surveys the general formulation,…
First-order Methods Almost Always Avoid Saddle Points
Jason D. Lee, Ioannis Panageas, Georgios Piliouras +3
We establish that first-order methods avoid saddle points for almost all initializations. Our results apply to a wide variety of first-order methods, including gradient descent, bl…
Blind Deconvolution using Convex Programming
Ali Ahmed, Benjamin Recht, Justin Romberg
We consider the problem of recovering two unknown vectors, and , of length from their circular convolution. We make the structural assumption t…
Factoring nonnegative matrices with linear programs
Victor Bittorf, Benjamin Recht, Christopher Re +1
This paper describes a new approach, based on linear programming, for computing nonnegative matrix factorizations (NMFs). The key idea is a data-driven model for the factorization…
A Generalizable and Accessible Approach to Machine Learning with Global Satellite Imagery
Esther Rolf, Jonathan Proctor, Tamma Carleton +5
Combining satellite imagery with machine learning (SIML) has the potential to address global challenges by remotely estimating socioeconomic and environmental conditions in data-po…
Understanding deep learning requires rethinking generalization
Chiyuan Zhang, Samy Bengio, Moritz Hardt +2
Despite their massive size, successful deep artificial neural networks can exhibit a remarkably small difference between training and test performance. Conventional wisdom attribut…
Minimax Lower Bounds for -Norm Estimation
Stephen Tu, Ross Boczar, Benjamin Recht
The problem of estimating the -norm of an LTI system from noisy input/output measurements has attracted recent attention as an alternative to parameter identifi…
What is the objective of reasoning with reinforcement learning?
Damek Davis, Benjamin Recht
We show that several popular algorithms for reinforcement learning in large language models with binary rewards can be viewed as stochastic gradient ascent on a monotone transform…
Robust Guarantees for Perception-Based Control
Sarah Dean, Nikolai Matni, Benjamin Recht +1
Motivated by vision-based control of autonomous vehicles, we consider the problem of controlling a known linear dynamical system for which partial state information, such as vehicl…
Superresolution without Separation
Geoffrey Schiebinger, Elina Robeva, Benjamin Recht
This paper provides a theoretical analysis of diffraction-limited superresolution, demonstrating that arbitrarily close point sources can be resolved in ideal situations. Precisely…
Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences
Benjamin Recht, Christopher Re
Randomized algorithms that base iteration-level decisions on samples from some pool are ubiquitous in machine learning and optimization. Examples include stochastic gradient descen…
Towards Robust Data-Driven Control Synthesis for Nonlinear Systems with Actuation Uncertainty
Andrew J. Taylor, Victor D. Dorobantu, Sarah Dean +3
Modern nonlinear control theory seeks to endow systems with properties such as stability and safety, and has been deployed successfully across various domains. Despite this success…
Finding Equilibrium in Multi-Agent Games with Payoff Uncertainty
Wenshuo Guo, Mihaela Curmei, Serena Wang +2
We study the problem of finding equilibrium strategies in multi-agent games with incomplete payoff information, where the payoff matrices are only known to the players up to some b…
Gradient Descent Learns Linear Dynamical Systems
Moritz Hardt, Tengyu Ma, Benjamin Recht
We prove that stochastic gradient descent efficiently converges to the global optimizer of the maximum likelihood objective of an unknown linear time-invariant dynamical system fro…
Flare Prediction Using Photospheric and Coronal Image Data
Eric Jonas, Monica G. Bobra, Vaishaal Shankar +2
The precise physical process that triggers solar flares is not currently understood. Here we attempt to capture the signature of this mechanism in solar image data of various wavel…
The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems
Nicholas Boyd, Geoffrey Schiebinger, Benjamin Recht
We propose a variant of the classical conditional gradient method for sparse inverse problems with differentiable measurement models. Such models arise in many practical problems i…
Plenoxels: Radiance Fields without Neural Networks
Alex Yu, Sara Fridovich-Keil, Matthew Tancik +3
We introduce Plenoxels (plenoptic voxels), a system for photorealistic view synthesis. Plenoxels represent a scene as a sparse 3D grid with spherical harmonics. This representation…
A General Analysis of the Convergence of ADMM
Robert Nishihara, Laurent Lessard, Benjamin Recht +2
We provide a new proof of the linear convergence of the alternating direction method of multipliers (ADMM) when one of the objective terms is strongly convex. Our proof is based on…
Train faster, generalize better: Stability of stochastic gradient descent
Moritz Hardt, Benjamin Recht, Yoram Singer
We show that parametric models trained by a stochastic gradient method (SGM) with few iterations have vanishing generalization error. We prove our results by arguing that SGM is al…
Non-Asymptotic Analysis of Robust Control from Coarse-Grained Identification
Stephen Tu, Ross Boczar, Andrew Packard +1
This work explores the trade-off between the number of samples required to accurately build models of dynamical systems and the degradation of performance in various control object…
The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime
Max Simchowitz, Kevin Jamieson, Benjamin Recht
We propose a novel technique for analyzing adaptive sampling called the {\em Simulator}. Our approach differs from the existing methods by considering not how much information coul…
Simple Bounds for Recovering Low-complexity Models
Emmanuel Candes, Benjamin Recht
This note presents a unified analysis of the recovery of simple objects from random linear measurements. When the linear functionals are Gaussian, we show that an s-sparse vector i…
The Marginal Value of Adaptive Gradient Methods in Machine Learning
Ashia C. Wilson, Rebecca Roelofs, Mitchell Stern +2
Adaptive optimization methods, which perform local optimization with a metric constructed from the history of iterates, are becoming increasingly popular for training deep neural n…
Atomic norm denoising with applications to line spectral estimation
Badri Narayan Bhaskar, Gongguo Tang, Benjamin Recht
Motivated by recent work on atomic norms in inverse problems, we propose a new approach to line spectral estimation that provides theoretical guarantees for the mean-squared-error…
KeystoneML: Optimizing Pipelines for Large-Scale Advanced Analytics
Evan R. Sparks, Shivaram Venkataraman, Tomer Kaftan +2
Modern advanced analytics applications make use of machine learning techniques and contain multiple steps of domain-specific and general-purpose processing with high resource requi…
CYCLADES: Conflict-free Asynchronous Machine Learning
Xinghao Pan, Maximilian Lam, Stephen Tu +6
We present CYCLADES, a general framework for parallelizing stochastic optimization algorithms in a shared memory setting. CYCLADES is asynchronous during shared model updates, and…
Signal Recovery in Unions of Subspaces with Applications to Compressive Imaging
Nikhil Rao, Benjamin Recht, Robert Nowak
In applications ranging from communications to genetics, signals can be modeled as lying in a union of subspaces. Under this model, signal coefficients that lie in certain subspace…
From Individual Experience to Collective Evidence: A Reporting-Based Framework for Identifying Systemic Harms
Jessica Dai, Paula Gradu, Inioluwa Deborah Raji +1
When an individual reports a negative interaction with some system, how can their personal experience be contextualized within broader patterns of system behavior? We study the rep…
Do Offline Metrics Predict Online Performance in Recommender Systems?
Karl Krauth, Sarah Dean, Alex Zhao +4
Recommender systems operate in an inherently dynamical setting. Past recommendations influence future behavior, including which data points are observed and how user preferences ch…
Quantifying Availability and Discovery in Recommender Systems via Stochastic Reachability
Mihaela Curmei, Sarah Dean, Benjamin Recht
In this work, we consider how preference models in interactive recommendation systems determine the availability of content and users' opportunities for discovery. We propose an ev…
Patterns, predictions, and actions: A story about machine learning
Moritz Hardt, Benjamin Recht
This graduate textbook on machine learning tells a story of how patterns in data support predictions and consequential actions. Starting with the foundations of decision making, we…
Do ImageNet Classifiers Generalize to ImageNet?
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt +1
We build new test sets for the CIFAR-10 and ImageNet datasets. Both benchmarks have been the focus of intense research for almost a decade, raising the danger of overfitting to exc…
Gradient Descent Provably Solves Nonlinear Tomographic Reconstruction
Sara Fridovich-Keil, Fabrizio Valdivia, Gordon Wetzstein +2
In computed tomography (CT), the forward model consists of a linear Radon transform followed by an exponential nonlinearity based on the attenuation of light according to the Beer-…
Measuring Robustness to Natural Distribution Shifts in Image Classification
Rohan Taori, Achal Dave, Vaishaal Shankar +3
We study how robust current ImageNet models are to distribution shifts arising from natural variations in datasets. Most research on robustness focuses on synthetic image perturbat…
Towards Psychologically-Grounded Dynamic Preference Models
Mihaela Curmei, Andreas Haupt, Dylan Hadfield-Menell +1
Designing recommendation systems that serve content aligned with time varying preferences requires proper accounting of the feedback effects of recommendations on human behavior an…
Aggregated Individual Reporting for Post-Deployment Evaluation
Jessica Dai, Inioluwa Deborah Raji, Benjamin Recht +1
The need for developing model evaluations beyond static benchmarking, especially in the post-deployment phase, is now well-understood. At the same time, concerns about the concentr…
Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
Benjamin Recht, Maryam Fazel, Pablo A. Parrilo
The affine rank minimization problem consists of finding a matrix of minimum rank that satisfies a given system of linear equality constraints. Such problems have appeared in the l…
Exponential Convergence Bounds using Integral Quadratic Constraints
Ross Boczar, Laurent Lessard, Benjamin Recht
The theory of integral quadratic constraints (IQCs) allows verification of stability and gain-bound properties of systems containing nonlinear or uncertain elements. Gain bounds of…
Recommendations and User Agency: The Reachability of Collaboratively-Filtered Information
Sarah Dean, Sarah Rich, Benjamin Recht
Recommender systems often rely on models which are trained to maximize accuracy in predicting user preferences. When the systems are deployed, these models determine the availabili…
The Convex Geometry of Linear Inverse Problems
Venkat Chandrasekaran, Benjamin Recht, Pablo A. Parrilo +1
In applications throughout science and engineering one is often faced with the challenge of solving an ill-posed inverse problem, where the number of available measurements is smal…
A System for Massively Parallel Hyperparameter Tuning
Liam Li, Kevin Jamieson, Afshin Rostamizadeh +4
Modern learning models are characterized by large hyperparameter spaces and long training times. These properties, coupled with the rise of parallel computing and the growing deman…
Do Image Classifiers Generalize Across Time?
Vaishaal Shankar, Achal Dave, Rebecca Roelofs +3
We study the robustness of image classifiers to temporal perturbations derived from videos. As part of this study, we construct two datasets, ImageNet-Vid-Robust and YTBB-Robust ,…
The Randomized Causation Coefficient
David Lopez-Paz, Krikamol Muandet, Benjamin Recht
We are interested in learning causal relationships between pairs of random variables, purely from observational data. To effectively address this task, the state-of-the-art relies…
A Lyapunov Analysis of Momentum Methods in Optimization
Ashia C. Wilson, Benjamin Recht, Michael I. Jordan
Momentum methods play a significant role in optimization. Examples include Nesterov's accelerated gradient method and the conditional gradient algorithm. Several momentum methods a…
The Actuary's Final Word on Algorithmic Decision Making
Benjamin Recht
Paul Meehl's foundational work "Clinical versus Statistical Prediction," provided early theoretical justification and empirical evidence of the superiority of statistical methods o…
Online Identification and Tracking of Subspaces from Highly Incomplete Information
Laura Balzano, Robert Nowak, Benjamin Recht
This work presents GROUSE (Grassmanian Rank-One Update Subspace Estimation), an efficient online algorithm for tracking subspaces from highly incomplete observations. GROUSE requir…
Ground Control to Major Tom: the importance of field surveys in remotely sensed data analysis
Ian Bolliger, Tamma Carleton, Solomon Hsiang +5
In this project, we build a modular, scalable system that can collect, store, and process millions of satellite images. We test the relative importance of both of the key limitatio…
Do CIFAR-10 Classifiers Generalize to CIFAR-10?
Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt +1
Machine learning is currently dominated by largely experimental work focused on improvements in a few key tasks. However, the impressive accuracy numbers of the best performing mod…
Perturbed Iterate Analysis for Asynchronous Stochastic Optimization
Horia Mania, Xinghao Pan, Dimitris Papailiopoulos +3
We introduce and analyze stochastic optimization methods where the input to each gradient update is perturbed by bounded noise. We show that this framework forms the basis of a uni…
A Successive-Elimination Approach to Adaptive Robotic Sensing
Esther Rolf, David Fridovich-Keil, Max Simchowitz +2
We study an adaptive source seeking problem, in which a mobile robot must identify the strongest emitter(s) of a signal in an environment with background emissions. Background sign…
numpywren: serverless linear algebra
Vaishaal Shankar, Karl Krauth, Qifan Pu +5
Linear algebra operations are widely used in scientific computing and machine learning applications. However, it is challenging for scientists and data analysts to run linear algeb…
Occupy the Cloud: Distributed Computing for the 99%
Eric Jonas, Qifan Pu, Shivaram Venkataraman +2
Distributed computing remains inaccessible to a large number of users, in spite of many open source platforms and extensive commercial offerings. While distributed computation fram…
Depth from Defocus via Direct Optimization
Holly Jackson, Caleb Adams, Ignacio Lopez-Francos +1
Though there exists a reasonable forward model for blur based on optical physics, recovering depth from a collection of defocused images remains a computationally challenging optim…
Meaningless comparisons lead to false optimism in medical machine learning
Orianna DeMasi, Konrad Kording, Benjamin Recht
A new trend in medicine is the use of algorithms to analyze big datasets, e.g. using everything your phone measures about you for diagnostics or monitoring. However, these algorith…
Isometric sketching of any set via the Restricted Isometry Property
Samet Oymak, Benjamin Recht, Mahdi Soltanolkotabi
In this paper we show that for the purposes of dimensionality reduction certain class of structured random matrices behave similarly to random Gaussian matrices. This class include…
On the Gap Between Strict-Saddles and True Convexity: An Omega(log d) Lower Bound for Eigenvector Approximation
Max Simchowitz, Ahmed El Alaoui, Benjamin Recht
We prove a \emph{query complexity} lower bound on rank-one principal component analysis (PCA). We consider an oracle model where, given a symmetric matrix $M \in \mathbb{R}^{d \tim…
Query Complexity of Derivative-Free Optimization
Kevin G. Jamieson, Robert D. Nowak, Benjamin Recht
This paper provides lower bounds on the convergence rate of Derivative Free Optimization (DFO) with noisy function evaluations, exposing a fundamental and unavoidable gap between t…
In Defense of Defensive Forecasting
Juan Carlos Perdomo, Benjamin Recht
This tutorial provides a survey of algorithms for Defensive Forecasting, where predictions are derived not by prognostication but by correcting past mistakes. Pioneered by Vovk, De…
Exponential Stability Analysis via Integral Quadratic Constraints
Ross Boczar, Laurent Lessard, Andrew Packard +1
The theory of integral quadratic constraints (IQCs) allows verification of stability and gain-bound properties of systems containing nonlinear or uncertain elements. Gain bounds of…
Tight Measurement Bounds for Exact Recovery of Structured Sparse Signals
Nikhil Rao, Benjamin Recht, Robert Nowak
Standard compressive sensing results state that to exactly recover an s sparse signal in R^p, one requires O(s. log(p)) measurements. While this bound is extremely useful in practi…
Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
Max Simchowitz, Horia Mania, Stephen Tu +2
We prove that the ordinary least-squares (OLS) estimator attains nearly minimax optimal performance for the identification of linear dynamical systems from a single observed trajec…
Best-of-K Bandits
Max Simchowitz, Kevin Jamieson, Benjamin Recht
This paper studies the Best-of-K Bandit game: At each time the player chooses a subset S among all N-choose-K possible options and observes reward max(X(i) : i in S) where X is a r…
Finite-time Analysis of Approximate Policy Iteration for the Linear Quadratic Regulator
Karl Krauth, Stephen Tu, Benjamin Recht
We study the sample complexity of approximate policy iteration (PI) for the Linear Quadratic Regulator (LQR), building on a recent line of work using LQR as a testbed to understand…
Certainty Equivalent Perception-Based Control
Sarah Dean, Benjamin Recht
In order to certify performance and safety, feedback control requires precise characterization of sensor errors. In this paper, we provide guarantees on such feedback systems when…
Simple random search provides a competitive approach to reinforcement learning
Horia Mania, Aurelia Guy, Benjamin Recht
A common belief in model-free reinforcement learning is that methods based on random search in the parameter space of policies exhibit significantly worse sample complexity than th…
Linear System Identification via Atomic Norm Regularization
Parikshit Shah, Badri Narayan Bhaskar, Gongguo Tang +1
This paper proposes a new algorithm for linear system identification from noisy measurements. The proposed algorithm balances a data fidelity term with a norm induced by the set of…
Interpolating Classifiers Make Few Mistakes
Tengyuan Liang, Benjamin Recht
This paper provides elementary analyses of the regret and generalization of minimum-norm interpolating classifiers (MNIC). The MNIC is the function of smallest Reproducing Kernel H…
Convolutional Kitchen Sinks for Transcription Factor Binding Site Prediction
Alyssa Morrow, Vaishaal Shankar, Devin Petersohn +3
We present a simple and efficient method for prediction of transcription factor binding sites from DNA sequence. Our method computes a random approximation of a convolutional kerne…
Learning Linear Dynamical Systems with Semi-Parametric Least Squares
Max Simchowitz, Ross Boczar, Benjamin Recht
We analyze a simple prefiltered variation of the least squares estimator for the problem of estimation with biased, semi-parametric noise, an error model studied more broadly in ca…