Blake E Woodworth — accepted AI-conference papers

2021

On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent

Shahar Azulay, Edward Moroshko, Mor Shpigel Nacson, Blake E Woodworth, Nathan Srebro, Amir Globerson +1

ICML 2021oral

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 initialization leads to the neural tangent kernel regime solution, whereas small initialization leads to so called “ric…

Cited by 97 Source ↗PDF ↗Scholar ↗

2020

Implicit Bias in Deep Linear Classification: Initialization Scale vs Training Accuracy

Edward Moroshko, Blake E Woodworth, Suriya Gunasekar, Jason Lee, Nati Srebro, Daniel Soudry

NeurIPS 2020spotlight

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 is the simplest model displaying a transition between "kernel" and non-kernel ("rich" or "active") regimes. We show ho…

Cited by 99 Source ↗PDF ↗Scholar ↗

2020

Minibatch vs Local SGD for Heterogeneous Distributed Learning

Blake E Woodworth, Kumar Kshitij Patel, Nati Srebro

NeurIPS 2020poster

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 a different, machine-specific, convex objective; the goal is to optimize w.r.t.~the average objective; and machines can…

Cited by 228 Source ↗PDF ↗Scholar ↗

2018

Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization

Blake E Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, Nati Srebro

NeurIPS 2018spotlight

We suggest a general oracle-based framework that captures parallel stochastic optimization in different parallelization settings described by a dependency graph, and derive generic lower bounds in terms of this graph. We then use the framework and derive lower bounds to study several speci…

Cited by 138 Source ↗PDF ↗Scholar ↗

2018

The Everlasting Database: Statistical Validity at a Fair Price

Blake E Woodworth, Vitaly Feldman, Saharon Rosset, Nati Srebro

NeurIPS 2018poster

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 invalid scientific discoveries. We propose a mechanism for answering an arbitrarily long sequence of potentially a…

Cited by 4 Source ↗PDF ↗Scholar ↗

2017

Implicit Regularization in Matrix Factorization

Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, Nati Srebro

NeurIPS 2017spotlight

We study implicit regularization when optimizing an underdetermined quadratic objective over a matrix $X$ with gradient descent on a factorization of X. We conjecture and provide empirical and theoretical evidence that with small enough step sizes and initialization close enough to the origin, grad…

Cited by 602 Source ↗PDF ↗Scholar ↗

2016

Tight Complexity Bounds for Optimizing Composite Objectives

Blake E Woodworth, Nati Srebro

NeurIPS 2016poster

We provide tight upper and lower bounds on the complexity of minimizing the average of m convex functions using gradient and prox oracles of the component functions. We show a significant gap between the complexity of deterministic vs randomized optimization. For smooth functions, we show that accel…

Cited by 240 Source ↗PDF ↗Scholar ↗