167 citations · 679 across the 25 of their papers we have counts for
27 papers
Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxy
Blake Woodworth, Konstantin Mishchenko, Francis Bach
We present an algorithm for minimizing an objective with hard-to-compute gradients by using a related, easier-to-access function as a proxy. Our algorithm is based on approximate p…
Asynchronous SGD Beats Minibatch SGD Under Arbitrary Delays
Konstantin Mishchenko, Francis Bach, Mathieu Even +1
The existing analysis of asynchronous stochastic gradient descent (SGD) degrades dramatically when any delay is large, giving the impression that performance depends primarily on t…
Non-Convex Optimization with Certificates and Fast Rates Through Kernel Sums of Squares
Blake Woodworth, Francis Bach, Alessandro Rudi
We consider potentially non-convex optimization problems, for which optimal rates of approximation depend on the dimension of the parameter space and the smoothness of the function…
A Stochastic Newton Algorithm for Distributed Convex Optimization
Brian Bullins, Kumar Kshitij Patel, Ohad Shamir +2
We propose and analyze a stochastic Newton algorithm for homogeneous distributed stochastic convex optimization, where each machine can calculate stochastic gradients of the same p…
The Minimax Complexity of Distributed Optimization
Blake Woodworth
In this thesis, I study the minimax oracle complexity of distributed stochastic optimization. First, I present the "graph oracle model", an extension of the classic oracle complexi…
A Field Guide to Federated Optimization
Jianyu Wang, Zachary Charles, Zheng Xu +50
Federated learning and analytics are a distributed approach for collaboratively learning models (or statistics) from decentralized data, motivated by and designed for privacy prote…
An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
Blake Woodworth, Nathan Srebro
We present and analyze an algorithm for optimizing smooth and convex or strongly convex objectives using minibatch stochastic gradient estimates. The algorithm is optimal with resp…
On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent
Shahar Azulay, Edward Moroshko, Mor Shpigel Nacson +4
Recent work has highlighted the role of initialization scale in determining the structure of the solutions that gradient methods converge to. In particular, it was shown that large…
The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication
Blake Woodworth, Brian Bullins, Ohad Shamir +1
We resolve the min-max complexity of distributed stochastic convex optimization (up to a log factor) in the intermittent communication setting, where machines work in parallel…
Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy
Edward Moroshko, Suriya Gunasekar, Blake Woodworth +3
We provide a detailed asymptotic study of gradient flow trajectories and their implicit optimization bias when minimizing the exponential loss over "diagonal linear networks". This…
Minibatch vs Local SGD for Heterogeneous Distributed Learning
Blake Woodworth, Kumar Kshitij Patel, Nathan Srebro
We analyze Local SGD (aka parallel or federated SGD) and Minibatch SGD in the heterogeneous distributed setting, where each machine has access to stochastic gradient estimates for…
Mirrorless Mirror Descent: A Natural Derivation of Mirror Descent
Suriya Gunasekar, Blake Woodworth, Nathan Srebro
We present a primal only derivation of Mirror Descent as a "partial" discretization of gradient flow on a Riemannian manifold where the metric tensor is the Hessian of the Mirror D…
Kernel and Rich Regimes in Overparametrized Models
Blake Woodworth, Suriya Gunasekar, Jason D. Lee +5
A recent line of work studies overparametrized neural networks in the "kernel regime," i.e. when the network behaves during training as a kernelized linear predictor, and thus trai…
Is Local SGD Better than Minibatch SGD?
Blake Woodworth, Kumar Kshitij Patel, Sebastian U. Stich +5
We study local SGD (also known as parallel SGD and federated averaging), a natural and frequently used stochastic distributed optimization method. Its theoretical foundations are c…
Lower Bounds for Non-Convex Stochastic Optimization
Yossi Arjevani, Yair Carmon, John C. Duchi +3
We lower bound the complexity of finding -stationary points (with gradient norm at most ) using stochastic first-order methods. In a well-studied model where algorithms acces…
The gradient complexity of linear regression
Mark Braverman, Elad Hazan, Max Simchowitz +1
We investigate the computational complexity of several basic linear algebra primitives, including largest eigenvector computation and linear regression, in the computational model…
Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory
Blake Woodworth, Nathan Srebro
We note that known methods achieving the optimal oracle complexity for first order convex optimization require quadratic memory, and ask whether this is necessary, and more broadly…
Guaranteed Validity for Empirical Approaches to Adaptive Data Analysis
Ryan Rogers, Aaron Roth, Adam Smith +3
We design a general framework for answering adaptive statistical queries that focuses on providing explicit confidence intervals along with point estimates. Prior work in this area…
Kernel and Rich Regimes in Overparametrized Models
Blake Woodworth, Suriya Gunasekar, Pedro Savarese +5
A recent line of work studies overparametrized neural networks in the "kernel regime," i.e. when the network behaves during training as a kernelized linear predictor, and thus trai…
The Complexity of Making the Gradient Small in Stochastic Convex Optimization
Dylan J. Foster, Ayush Sekhari, Ohad Shamir +3
We give nearly matching upper and lower bounds on the oracle complexity of finding -stationary points () in stochastic convex optimization. We jointly a…
Training Well-Generalizing Classifiers for Fairness Metrics and Other Data-Dependent Constraints
Andrew Cotter, Maya Gupta, Heinrich Jiang +5
Classifiers can be trained with data-dependent constraints to satisfy fairness goals, reduce churn, achieve a targeted false positive rate, or other policy goals. We study the gene…
Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization
Blake Woodworth, Jialei Wang, Adam Smith +2
We suggest a general oracle-based framework that captures different parallel stochastic optimization settings described by a dependency graph, and derive generic lower bounds in te…
The Everlasting Database: Statistical Validity at a Fair Price
Blake Woodworth, Vitaly Feldman, Saharon Rosset +1
The problem of handling adaptivity in data analysis, intentional or not, permeates a variety of fields, including test-set overfitting in ML challenges and the accumulation of inva…
Lower Bound for Randomized First Order Convex Optimization
Blake Woodworth, Nathan Srebro
We provide an explicit construction and direct proof for the lower bound on the number of first order oracle accesses required for a randomized algorithm to minimize a convex Lipsc…