137 citations · 419 across the 10 of their papers we have counts for
6 papers · 1 filter
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…
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…
Tight Query Complexity Lower Bounds for PCA via Finite Sample Deformed Wigner Law
Max Simchowitz, Ahmed El Alaoui, Benjamin Recht
We prove a \emph{query complexity} lower bound for approximating the top dimensional eigenspace of a matrix. We consider an oracle model where, given a symmetric matrix $\mathb…
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…
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…
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…