14 citations · 41 across the 14 of their papers we have counts for
5 papers · 1 filter
Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update
Michał Dereziński, Jonathan Lacotte, Mert Pilanci +1
In second-order optimization, a potential bottleneck can be computing the Hessian matrix of the optimized function at every iteration. Randomized sketching has emerged as a powerfu…
Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality
Jonathan Lacotte, Yifei Wang, Mert Pilanci
We propose a randomized algorithm with quadratic convergence rate for convex optimization problems with a self-concordant, composite, strongly convex objective function. Our method…
Optimal Randomized First-Order Methods for Least-Squares Problems
Jonathan Lacotte, Mert Pilanci
We provide an exact analysis of a class of randomized algorithms for solving overdetermined least-squares problems. We consider first-order methods, where the gradients are pre-con…
Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform
Jonathan Lacotte, Sifan Liu, Edgar Dobriban +1
Random projections or sketching are widely used in many algorithmic and learning contexts. Here we study the performance of iterative Hessian sketch for least-squares problems. By…
High-Dimensional Optimization in Adaptive Random Subspaces
Jonathan Lacotte, Mert Pilanci, Marco Pavone
We propose a new randomized optimization method for high-dimensional problems which can be seen as a generalization of coordinate descent to random subspaces. We show that an adapt…