38 citations · 247 across the 108 of their papers we have counts for
15 papers · 1 filter
Newton Meets Marchenko-Pastur: Massively Parallel Second-Order Optimization with Hessian Sketching and Debiasing
Elad Romanov, Fangzhao Zhang, Mert Pilanci
Motivated by recent advances in serverless cloud computing, in particular the "function as a service" (FaaS) model, we consider the problem of minimizing a convex function in a mas…
Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation
Aaron Mishkin, Mert Pilanci, Mark Schmidt
We prove new convergence rates for a generalized version of stochastic Nesterov acceleration under interpolation conditions. Unlike previous analyses, our approach accelerates any…
Optimal Shrinkage for Distributed Second-Order Optimization
Fangzhao Zhang, Mert Pilanci
In this work, we address the problem of Hessian inversion bias in distributed second-order optimization algorithms. We introduce a novel shrinkage-based estimator for the resolvent…
Sketching the Krylov Subspace: Faster Computation of the Entire Ridge Regularization Path
Yifei Wang, Mert Pilanci
We propose a fast algorithm for computing the entire ridge regression regularization path in nearly linear time. Our method constructs a basis on which the solution of ridge regres…
Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds
Burak Bartan, Mert Pilanci
We consider distributed optimization methods for problems where forming the Hessian is computationally challenging and communication is a significant bottleneck. We leverage random…
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…
Lower Bounds and a Near-Optimal Shrinkage Estimator for Least Squares using Random Projections
Srivatsan Sridhar, Mert Pilanci, Ayfer Özgür
In this work, we consider the deterministic optimization using random projections as a statistical estimation problem, where the squared distance between the predictions from the e…
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…
Global Convergence of Frank Wolfe on One Hidden Layer Networks
Alexandre d'Aspremont, Mert Pilanci
We derive global convergence bounds for the Frank Wolfe algorithm when training one hidden layer neural networks. When using the ReLU activation function, and under tractable preco…
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…
M-IHS: An Accelerated Randomized Preconditioning Method Avoiding Costly Matrix Decompositions
Ibrahim Kurban Ozaslan, Mert Pilanci, Orhan Arikan
Momentum Iterative Hessian Sketch (M-IHS) techniques, a group of solvers for large scale regularized linear Least Squares (LS) problems, are proposed and analyzed in detail. Propos…
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…
Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence
Mert Pilanci, Martin J. Wainwright
We propose a randomized second-order method for optimization known as the Newton Sketch: it is based on performing an approximate Newton step using a randomly projected or sub-samp…
Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
Mert Pilanci, Martin J. Wainwright
We study randomized sketching methods for approximately solving least-squares problem with a general convex constraint. The quality of a least-squares approximation can be assessed…