38 citations · 76 across the 24 of their papers we have counts for
12 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…
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…