Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning
Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning
复制标题
DOI：
--
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Yifan Hu;Siqi Zhang;Xin Chen;Niao He
中科院分区：
文献类型：
--
作者：
Yifan Hu;Siqi Zhang;Xin Chen;Niao He
条件随机优化涵盖了从不变学习和因果推理到元学习的各种应用。然而，构造无偏梯度估计，这样的问题是具有挑战性的，由于组合结构。作为替代方案，我们提出了一个有偏随机梯度下降（BSGD）算法，并研究了不同的结构假设下的偏差方差权衡。在光滑和非光滑条件下，我们建立了强凸、凸和弱凸目标的BSGD的样本复杂性。我们的下界分析表明，BSGD的样本复杂性不能提高一般的凸目标和非凸目标，除了光滑非凸目标与Lipschitz连续梯度估计。对于这种特殊的设置，我们提出了一种加速算法称为偏置SpiderBoost（BSpiderBoost），匹配的下限复杂度。我们进一步对不变逻辑回归和模型不可知元学习进行数值实验，以说明BSGD和BSpiderBoost的性能。
Conditional stochastic optimization covers a variety of applications ranging from invariant learning and causal inference to meta-learning. However, constructing unbiased gradient estimators for such problems is challenging due to the composition structure. As an alternative, we propose a biased stochastic gradient descent (BSGD) algorithm and study the bias-variance tradeoff under different structural assumptions. We establish the sample complexities of BSGD for strongly convex, convex, and weakly convex objectives under smooth and non-smooth conditions. Our lower bound analysis shows that the sample complexities of BSGD cannot be improved for general convex objectives and nonconvex objectives except for smooth nonconvex objectives with Lipschitz continuous gradient estimator. For this special setting, we propose an accelerated algorithm called biased SpiderBoost (BSpiderBoost) that matches the lower bound complexity. We further conduct numerical experiments on invariant logistic regression and model-agnostic meta-learning to illustrate the performance of BSGD and BSpiderBoost.