6 citations · 11 across the 4 of their papers we have counts for
11 papers
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…
Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners
Jonathan Lacotte, Mert Pilanci
We consider least-squares problems with quadratic regularization and propose novel sketching-based iterative methods with an adaptive sketch size. The sketch size can be as small a…
Adaptive and Oblivious Randomized Subspace Methods for High-Dimensional Optimization: Sharp Analysis and Lower Bounds
Jonathan Lacotte, Mert Pilanci
We propose novel randomized optimization methods for high-dimensional convex problems based on restrictions of variables to random subspaces. We consider oblivious and data-adaptiv…
Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization
Jonathan Lacotte, Mert Pilanci
We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching. We consider two of the most popular random embeddings, namely, Gaussian…
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…