Publications

Do CIFAR-10 Classifiers Generalize to CIFAR-10? Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. 2018.

Regret Bounds for Robust Adaptive Control of the Linear Quadratic Regulator. Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, Stephen Tu. 2018.

Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law. Max Simchowitz, Ahmed El Alaoui, and Benjaminn Recht. In STOC 2018.

Finite-Data Performance Guarantees for the Output-Feedback Control of an Unknown System. Ross Boczar, Nikola Matni, and Benjamin Recht. 2018.

Simple random search provides a competitive approach to reinforcement learning. Horia Mania, Aurelia Guy, Benjamin Recht. 2018.

Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification. Max Simchowitz, Horia Mania, Stephen Tu, Michael I. Jordan, and Benjamin Recht. In COLT 2018.

Least-Squares Temporal Difference Learning for the Linear Quadratic Regulator. Stephen Tu and Benjamin Recht. In ICML 2017.

On the Sample Complexity of the Linear Quadratic Regulator. Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. 2017.

Occupy the Cloud: Distributed Computing for the 99%. Eric Jonas, Qifan Pu, Shivaram Venkataraman, Ion Stoica, and Benjamin Recht. In ACM Symposium on Cloud Computing 2017.

Flare Prediction Using Photospheric and Coronal Image Data. Eric Jonas, Monica G. Bobra, Vaishaal Shankar, J. Todd Hoeksema, and Benjamin Recht. 2017.

On the Approximation of Toeplitz Operators for Nonparametric H-infinity-norm Estimation. Stephen Tu, Ross Boczar, Benjamin Recht. 2017.

Meaningless Comparisons Lead to False Optimism in Medical Machine Learning. Orianna DeMasi, Konrad Kording, Benjamin Recht. PLOS One. 12(9):e01846042017. 2017.

Nonasymptotic Analysis of Robust Control from Coarse-grained Identification. Stephen Tu, Ross Boczar, Andrew Packard, and Benjamin Recht. 2017.

The Marginal Value of Adaptive Gradient Methods in Machine Learning. Ashia C. Wilson, Rebecca Roelofs, Mitchell Stern, Nathan Srebro, and Benjamin Recht. In NIPS 2017.

On the Gap Between Strict-Saddles and True Convexity. Max Simchowitz, Ahmed El Alaoui, and Benjamin Recht. 2017.

Understanding Deep Learning Requires Rethinking Generalization. Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. In ICLR 2017.

Breaking Locality Accelerates Block Gauss-Seidel. Stephen Tu, Shivaram Venkataraman, Ashia C. Wilson,  Alex Gittens, Michael I. Jordan, and Benjamin Recht. In ICML 2017.

Convolutional Kitchen Sinks for Transcription Factor Binding Site Prediction. Alyssa Morrow, Vaishaal Shankar, Devin Petersohn, Anthony Joseph, Benjamin Recht, and Nir Yosef. In NIPS Workshop on Machine Learning in Computational Biology 2016.

A Lyapunov Analysis of Momentum Methods in Optimization. Ashia C. Wilson, Benjamin Recht, and Michael I. Jordan. 2016.

KeystoneML: Optimizing Pipelines for Large-Scale Advanced Analytics. Evan R. Sparks, Shivaram Venkataraman, Tomer Kaftan, Michael Franklin, Benjamin Recht In ICDE 2017.

Gradient Descent Learns Linear Dynamical Systems. Moritz Hardt, Tengyu Ma, and Benjamin Recht. 2016. To appear in Journal of Machine Learning Research.

CYCLADES: Conflict-free Asynchronous Machine Learning. Xinghao Pan, Maximilian Lam, Stephen Tu, Dimitris Papailiopoulos, Ce Zhang, Michael I. Jordan, Kannan Ramchandran, Chris Re, and Benjamin Recht. In NIPS 2016.

Saturating Splines and Feature Selection. Nicholas Boyd, Trevor Hastie, Stephen Boyd, Benjamin Recht, and Michael Jordan. 2016.

Universality of Mallows’ and Degeneracy of Kendall's Kernels for Rankings. Horia Mania, Aaditya Ramdas, Martin J. Wainwright, Michael I. Jordan, and Benjamin Recht. 2016.

Ernest: Efficient Performance Prediction for Large Scale Advanced Analytics. Shivaram Venkataraman, Zongheng Yang, Michael J Franklin, Benjamin Recht, and Ion Stoica. In NSDI 2016.

Best-of-K Bandits. Max Simchowitz, Kevin Jamieson, and Benjamin Recht. In COLT 2016.

Gradient Descent Converges to Minimizers. Jason D. Lee, Max Simchowitz, Michael I. Jordan, and Benjamin Recht. In COLT 2016.

Training Large Scale Kernel Machines with Block Coordinate Descent. Stephen Tu, Rebecca Roelofs, Shivaram Venkataraman, and Benjamin Recht. 2016.

Train Faster, Generalize Better: Stability of Stochastic Gradient Descent. Moritz Hardt, Benjamin Recht, and Yoram Singer. In ICML 2016.

Sharp Time–Data Tradeoffs for Linear Inverse Problems. Samet Oymak, Mahdi Soltanolkotabi, and Benjamin Recht. IEEE Transactions on Information Theory. 64(6):4129–4158. 2017.

Super-Resolution Without Separation. Geoffrey Schiebinger, Elina Robeva and Benjamin Recht. Information and Inference. 7(1):1–-30, 2017.

The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems. Nicholas Boyd, Geoffrey Schiebinger, and Benjamin Recht. SIAM Journal on Optimization. 27(2):616–639. 2017.

Low-rank Solutions of Linear Matrix Equations via Procrustes Flow. Stephen Tu, Ross Boczar, Mahdi Soltanolkotabi, and Benjamin Recht. In ICML 2016.

Isometric Sketching of Arbitrary Sets via the Restricted Isometry Property. Samet Oymak, Mahdi Soltanolkotabi, and Benjamin Recht. Information and Inference. iax019, (https:doi.org10.1093imaiai/iax019). 2018.

A Perturbed Iterate Framework for Asynchronous Stochastic Optimization Algorithms. Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Kannan Ramchandran, Michael I. Jordan, and Benjamin Recht. In NIPS 2015.

Parallel Correlation Clustering on Big Graphs. Xinghao Pan, Dimitris Papailiopoulos, Samet Oymak, Benjamin Recht, Kannan Ramchandran, and Michael I. Jordan. In NIPS 2015.

Exponential Stability Analysis via Integral Quadratic Constraints. Ross Boczar, Laurent Lessard, and Benjamin Recht. A preliminary version appeared as “Exponential Convergence Bounds using Integral Quadratic Constraints.” In Proceedings of the 54th Conference on Decision and Control 2015.

A General Analysis of the Convergence of ADMM. Robert Nishihara, Laurent Lessard, Benjamin Recht, Andrew Packard, and Michael I. Jordan. In ICML 2015.

Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints. Laurent Lessard, Andrew Packard, and Benjamin Recht. SIAM Journal on Optimization. 26(1):57–95, 2016.

3D imaging in volumetric scattering media using phase-space measurements. Hsiou-Yuan Liu, Eric Jonas, Lei Tian, Jingshan Zhong, Benjamin Recht, and Laura Waller. Optics Express. 23(11):14461–14471, 2015.

Efficient matrix completion for seismic data reconstruction. R. Kumar, C. Da Silva, O. Akalin, A.Y. Aravkin, H. Mansour, B. Recht, F.J. Herrmann. Geophysics. 80(5):V97–V114, 2015.

The Randomized Causation Coefficient. David Lopez-Paz, Krikamol Muandet, and Benjamin Recht. Journal of Machine Learning Research. 16:2901-2907, 2015.

Fast Methods for Denoising Matrix Completion Formulations, with Applications to Robust Seismic Data Interpolation. Aleksandr Y. Aravkin, Rajiv Kumar, Hassan Mansour, Benjamin Recht, Felix J. Herrmann. SIAM Journal on Scientific Computing. 36(5):S237–S266, 2015.

Near Minimax Line Spectral Estimation. Gongguo Tang, Badri Narayan Bhaskar, and Benjamin Recht. IEEE Transactions on Information Theory. 61(1):499–512, 2015.

Robust Efficiency and Actuator Saturation Explain Healthy Heart Rate Control and Variability. Na Li, Jerry Cruz, Chenghao Simon Chien, Somayeh Sojoudi, Benjamin Recht, David Stone, Marie Csete, Daniel Bahmiller, John C. Doyle. Proceedings of the National Academy of Sciences. 111(33):E3476–85, 2014.

Compressive classification and the rare eclipse problem. Afonso S. Bandeira, Dustin G. Mixon, Benjamin Recht. Preprint, 2014.

Blind Deconvolution using Convex Programming. Ali Ahmed, Benjamin Recht, and Justin Romberg. IEEE Transactions on Information Theory. 60(3):1711–1732, 2014.

Improvement in fast particle track reconstruction with robust statistics. M. G. Aartsen, et al. Nuclear Instruments and Methods in Physics Research Section A: Accelerators, Spectrometers, Detectors and Associated Equipment. 736(1):143–149, 2014.

Sparse Recovery Over Continuous Dictionaries: Just Discretize. Gongguo Tang, Badri Narayan Bhaskar, and Benjamin Recht. In Proceedings of the Asilomar Conference on Signals, Systems, and Computers, 2013.

Compressed Sensing off the Grid. Gongguo Tang, Badri Narayan Bhaskar, Parikshit Shah, and Benjamin Recht. IEEE Transactions on Information Theory. 59(11)7465–7490, 2013.

Alterations in Cerebrospinal Fluid Proteins in a Presymptomatic Primary Glioma Model. John C. Whitin, Taichang Jang, Milton Merchant, Tom T-S. Yu, Kenneth Lau, Benjamin Recht, Harvey J. Cohen, and Lawrence Recht. PLOS One. 7(1):e49724.

Simple Bounds for Recovering Low-complexity Models. Emmanuel Candès and Benjamin Recht. Mathematical Programming. Series A. 141(1):577–589. 2013.

Factoring Nonnegative Matrices with Linear Programs. Victor Bittorf, Benjamin Recht, Christopher Re, and Joel A. Tropp. In Advances in Neural Information Processing Systems, 2012.

Query Complexity of Derivative-free Optimization. Kevin Jamieson, Robert Nowak, and Benjamin Recht. In Advances in Neural Information Processing Systems, 2012.

Linear System Identification via Atomic Norm Regularization. Parikshit Shah, Badri Narayan Bhaskar, Gongguo Tang, and Benjamin Recht. In Proceedings of the 51st Annual Conference on Decision and Control, 2012.

Security of Point-of-Sale Systems. WesLee Frisby, Benjamin Moench, Benjamin Recht, Thomas Ristenpart. In Proceedings of the 6th USENIX Workshop on Offensive Technologies, 2012.

Beneath the Valley of the Noncommutative Arithmetic-Geometric Mean Inequality: conjectures, case-studies, and consequences. Benjamin Recht and Christopher Re. In Conference on Learning Theory (COLT), 2012.

Towards a Unified Architecture for in-RDBMS Analytics. Xixuan Feng, Arun Kumar, Benjamin Recht, and Christopher Re. In Proceedings of the ACM SIGMOD Conference, 2012.

Measurement Bounds for Exact Recovery of Structured Sparse Signals. Nikhil Rao, Benjamin Recht, and Robert Nowak. In Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, 2012.

HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent. Feng Niu, Benjamin Recht, Christopher Re, and Stephen J. Wright. In Advances in Neural Information Processing Systems, 2011.

Parallel Stochastic Gradient Algorithms for Large-Scale Matrix Completion. Benjamin Recht and Christopher Re. Mathematical Programming Computation. 5(2):201–226, 2013.

Decomposition Methods for Large Scale Linear Programming Decoding. Siddharth Barman, Stark Draper, Xishuo Liu, and Benjamin Recht. IEEE Transactions on Information Theory. 59(12):7870–7886, 2013. An early version of this paper appeared in the 2011 Allerton Conference.

Atomic Norm Denoising with Applications to Line Spectral Estimation. Badri Narayan Bhaskar and Benjamin Recht. IEEE Transactions on Signal Processing. 61(23):5987–5999, 2013. An early version of this paper appeared in the 2011 Allerton Conference.

A Framework for Incorporating General Domain Knowledge into Latent Dirichlet Allocation using First-Order Logic. David Andrzejewski, Xiaojin Zhu, Mark Craven, and Benjamin Recht. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence, 2011.

Dimensionality reduction: beyond the Johnson-Lindenstrauss bound. Yair Bartal, Benjamin Recht, and Leonard Schulman. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2011.

Practical Large-Scale Optimization for Max-Norm Regularization Jason Lee, Benjamin Recht, Ruslan Salakhutdinov, Nathan Srebro, and Joel A. Tropp. In Advances in Neural Information Processing Systems, 2010.

Transduction with Matrix Completion: Three Birds with One Stone. Andrew Goldberg Xiaojin Zhu, Benjamin Recht, Junming Sui, and Robert Nowak. In Advances in Neural Information Processing Systems, 2010.

Tensor completion and low-n-rank tensor recovery via convex optimization. Silvia Gandy, Benjamin Recht and Isao Yamada. Inverse Problems. 25(3):025010, 2011.

Online Identification and Tracking of Subspaces from Highly Incomplete Information. Laura Balzano, Robert Nowak, and Benjamin Recht. In /Proceedings of the 48th annual Allerton Conference on Communication, Control, and Computing’, 2010.

The Convex Algebraic Geometry of Linear Inverse Problems. Venkat Chandrasekaran, Benjamin Recht, Pablo A. Parrilo, and Alan S. Willsky. Foundations of Computational Mathematics. 12(6):805–849, 2012.

High-Dimensional Matched Subspace Detection When Data are Missing. Laura Balzano, Robert Nowak, and Benjamin Recht. In Proceedings of the IEEE International Symposium on Information Theory, 2010.

Sample Complexity for 1-bit Compressed Sensing and Sparse Classification. Ankit Gupta, Robert Nowak, and Benjamin Recht. In Proceedings of the IEEE International Symposium on Information Theory. 2010.

A Simpler Approach to Matrix Completion. Benjamin Recht. Journal of Machine Learning Research. 12:3413-—3430, 2011.

Probability of Unique Integer Solution to a System of Linear Equations. Olvi Mangasarian and Benjamin Recht. European Journal of Operational Research. 214(1):27—30, 2011.

Exact Matrix Completion via Convex Optimization. Emmanuel Candès and Benjamin Recht. Foundations of Computational Mathematics. 9(6):717-–772, 2009. Communications of the ACM Research Highlight, 55(6):111-119, 2012.

Learning kernels from indefinite similarities. Yihua Chen, Maya R. Gupta, and Benjamin Recht. In Proceedings of the International Conference on Machine Learning, 2009.

Null space conditions and thresholds for rank minimization. Benjamin Recht, Weiyu Xu, and Babak Hassibi. Mathematical Programming, Series B. 127:175-–202, 2011. An early version appeared as Necessary and Sufficient Conditions for Success of the Nuclear Norm Heuristic for Rank Minimization. in Proceedings of the 47th IEEE Conference on Decision and Control, 2008.

Interconnections in Biochemical Networks Using Linear Programming. Elias August, Antonis Papachristodoulou, Benjamin Recht, Mark Andrew James Roberts, and Ali Jadbabaie. In Proceedings of the 47th IEEE Conference on Decision and Control, 2008.

Weighted Sums of Random Kitchen Sinks: Replacing minimization with randomization in Learning. Ali Rahimi and Benjamin Recht. In Advances in Neural Information Processing Systems, 2008.

Uniform Approximation of Functions with Random Bases. Ali Rahimi and Benjamin Recht. In Proceedings of the 46th Annual Allerton Conference on Communication, Control, and Computing, 2008.

A distinct phenotypic change in gliomas at the time of magnetic resonance imaging detection. Taichang Jang, Binulal Sathy, Yi-Hua Hsu, Milton Merchant, Benjamin Recht, Chen Chang, and Lawrence Recht. Journal of Neurosurgery. 108(4):782–790, 2008.

Random Features for Large-Scale Kernel Machines. Ali Rahimi and Benjamin Recht. In Advances in Neural Information Processing Systems, 2007.

Guaranteed Minimum Rank Solutions to Linear Matrix Equations via Nuclear Norm Minimization. Benjamin Recht, Maryam Fazel, and Pablo A. Parrilo. SIAM Review. 52(3):471–501, 2010. An early version of this paper appeared in the 2007 Allerton Conference.

Determining Interconnections in Chemical Reaction Networks. Antonis Papachristodoulou and Benjamin Recht. In Proceedings of the American Control Conference, 2007.

Learning to Transform Time Series with a Few Examples. Ali Rahimi, Benjamin Recht, and Trevor Darrell. IEEE Transactions on Pattern Analysis and Machine Intelligence. 29(10):1759–1775, 2007.

Unsupervised Regression with Applications to Nonlinear System Identification. Ali Rahimi and Benjamin Recht. In Advances in Neural Information Processing Systems, 2006.

Interaction Techniques for Musical Performance with Tabletop Tangible Interfaces. James Patten, Benjamin Recht, and Hiroshi Ishii. In Advances in Computer Entertainment, 2006.

Learning Appearance Manifolds from Video. Ali Rahimi, Benjamin Recht, and Trevor Darrell. In Computer Vision and Pattern Recognition, 2005.

Clustering with Normalized Cuts is Clustering with a Hyperplane. Ali Rahimi and Benjamin Recht. In Statistical Learning in Computer Vision, 2004.

Distributed Control of Systems over Discrete Groups. Benjamin Recht and Raffaello D'Andrea. IEEE Transactions on Automatic Control. 49(9):1446–1452. 2004. An early version of this paper appeared in the 42nd IEEE Conference on Decision and Control with the title Exploiting Symmetry for the Distributed Control of Spatially Interconnected Systems.

Musically Expressive Sound Textures from Generalized Audio. Benjamin Recht and Brian Whitman. In /Proceedings of the 6th International Conference on Digital Audio Effects’, 2003.

Efficient Discrete Approximations of Quantum Gates. Aram W. Harrow, Benjamin Recht, and Isaac L. Chuang. Journal of Mathematical Physics. 43(9):4445–4451, 2002.

Using unitary operations to preserve quantum states in the presence of relaxation. Benjamin Recht, Yael Maguire, Seth Lloyd, Isaac L. Chuang, and Neial A. Gershenfeld. Technical Report, 2002.

Physical One-Way Functions. Ravikanth Pappu, Benjamin Recht, Jason Taylor, and Neil Gershenfeld. Science. 297(5589):2026–2030, 2002.

Audiopad: A Tag-based Interface for Musical Performance. James Patten, Benjamin Recht, Hiroshi Ishii. In Proceedings of the Conference on New Interfaces for Musical Expression, 2002.