937 citations · 8.2k across the 142 of their papers we have counts for
7 papers · 1 filter
Optimal and instance-dependent guarantees for Markovian linear stochastic approximation
Wenlong Mou, Ashwin Pananjady, Martin J. Wainwright +1
We study stochastic approximation procedures for approximately solving a -dimensional linear fixed point equation based on observing a trajectory of length from an ergodic M…
ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm
Chris Junchi Li, Wenlong Mou, Martin J. Wainwright +1
We study the problem of solving strongly convex and smooth unconstrained optimization problems using stochastic first-order algorithms. We devise a novel algorithm, referred to as…
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…
Optimal rates for zero-order convex optimization: the power of two function evaluations
John C. Duchi, Michael I. Jordan, Martin J. Wainwright +1
We consider derivative-free algorithms for stochastic and non-stochastic convex optimization problems that use only function values rather than gradients. Focusing on non-asymptoti…
Randomized Smoothing for Stochastic Optimization
John C. Duchi, Peter L. Bartlett, Martin J. Wainwright
We analyze convergence rates of stochastic optimization procedures for non-smooth convex optimization problems. By combining randomized smoothing techniques with accelerated gradie…