174 citations · 680 across the 52 of their papers we have counts for
8 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…
Vector Contraction for Rademacher Complexity
Dylan J. Foster, Alexander Rakhlin
We show that the Rademacher complexity of any -valued function class composed with an -Lipschitz function is bounded by the maximum Rademacher comple…
Model selection for contextual bandits
Dylan J. Foster, Akshay Krishnamurthy, Haipeng Luo
We introduce the problem of model selection for contextual bandits, where a learner must adapt to the complexity of the optimal policy while balancing exploration and exploitation.…
Sum-of-squares meets square loss: Fast rates for agnostic tensor completion
Dylan J. Foster, Andrej Risteski
We study tensor completion in the agnostic setting. In the classical tensor completion problem, we receive entries of an unknown rank- tensor and wish to exactly complete th…
Hypothesis Set Stability and Generalization
Dylan J. Foster, Spencer Greenberg, Satyen Kale +3
We present a study of generalization for data-dependent hypothesis sets. We give a general learning guarantee for data-dependent hypothesis sets based on a notion of transductive R…
Distributed Learning with Sublinear Communication
Jayadev Acharya, Christopher De Sa, Dylan J. Foster +1
In distributed statistical learning, samples are split across machines and a learner wishes to use minimal communication to learn as well as if the examples were on a singl…
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…
Orthogonal Statistical Learning
Dylan J. Foster, Vasilis Syrgkanis
We provide non-asymptotic excess risk guarantees for statistical learning in a setting where the population risk with respect to which we evaluate the target parameter depends on a…