206 citations · 808 across the 40 of their papers we have counts for
4 papers · 1 filter
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…
Variance Reduction for Matrix Games
Yair Carmon, Yujia Jin, Aaron Sidford +1
We present a randomized primal-dual algorithm that solves the problem to additive error in time , fo…
Unlabeled Data Improves Adversarial Robustness
Yair Carmon, Aditi Raghunathan, Ludwig Schmidt +2
We demonstrate, theoretically and empirically, that adversarial robustness can significantly benefit from semisupervised learning. Theoretically, we revisit the simple Gaussian mod…
A Rank-1 Sketch for Matrix Multiplicative Weights
Yair Carmon, John C. Duchi, Aaron Sidford +1
We show that a simple randomized sketch of the matrix multiplicative weight (MMW) update enjoys (in expectation) the same regret bounds as MMW, up to a small constant factor. Unlik…