137 citations · 419 across the 10 of their papers we have counts for
10 papers
First-order methods almost always avoid saddle points: the case of vanishing step-sizes
Ioannis Panageas, Georgios Piliouras, Xiao Wang
In a series of papers \cite{LSJR16, PP17, LPP}, it was established that some of the most commonly used first order methods almost surely (under random initializations) and with ste…
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…
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…