Timezone: »

On the Bias-Variance-Cost Tradeoff of Stochastic Optimization
Yifan Hu · Xin Chen · Niao He

Tue Dec 07 08:30 AM -- 10:00 AM (PST) @

We consider stochastic optimization when one only has access to biased stochastic oracles of the objective, and obtaining stochastic gradients with low biases comes at high costs. This setting captures a variety of optimization paradigms widely used in machine learning, such as conditional stochastic optimization, bilevel optimization, and distributionally robust optimization. We examine a family of multi-level Monte Carlo (MLMC) gradient methods that exploit a delicate trade-off among the bias, the variance, and the oracle cost. We provide a systematic study of their convergences and total computation complexities for strongly convex, convex, and nonconvex objectives, and demonstrate their superiority over the naive biased stochastic gradient method. Moreover, when applied to conditional stochastic optimization, the MLMC gradient methods significantly improve the best-known sample complexity in the literature.

Author Information

Yifan Hu (University of Illinois at Urbana-Champaign)
Xin Chen (University of Illinois at Urbana-Champaign)
Niao He (ETH Zurich)

More from the Same Authors