Multilevel Stochastic Gradient Methods for Nested Composition Optimization
Multilevel Stochastic Gradient Methods for Nested Composition Optimization
复制标题
DOI：
10.1137/18m1164846
复制
发表时间：
2018-01
期刊：
影响因子：
--
通讯作者：
Shuoguang Yang;Mengdi Wang;Ethan X. Fang
中科院分区：
文献类型：
--
作者：
Shuoguang Yang;Mengdi Wang;Ethan X. Fang
随机梯度方法对于解决涉及损失函数经验期望的大规模优化问题具有可扩展性。现有的结果主要适用于目标为一级或二级期望的优化问题。本文研究了在随机路径上包含多层分量函数和嵌套期望的多层组合优化问题。它可以在风险规避优化和顺序规划中找到应用。我们提出了一类基于多时间尺度随机逼近方法的多级随机梯度方法。首先，我们提出了一种基本的$T$级随机组合梯度算法，建立了它的几乎肯定收敛性，并得到了$n$-迭代误差界$O (n^{-1/2^T})$。然后，利用各分量函数的平滑性，采用外推-内插的方法开发了加速多级随机梯度方法。当所有分量函数都是光滑时，我们证明了收敛速度提高到$O(n^{-4/(7+T)})$对于一般目标和$O(n^{-4/(3+T)})$对于强凸目标。对于非凸问题，我们也给出了几乎肯定的收敛性和收敛速度的结果。数值实验验证了所提方法和理论结果。
Stochastic gradient methods are scalable for solving large-scale optimization problems that involve empirical expectations of loss functions. Existing results mainly apply to optimization problems where the objectives are one- or two-level expectations. In this paper, we consider the multi-level compositional optimization problem that involves compositions of multi-level component functions and nested expectations over a random path. It finds applications in risk-averse optimization and sequential planning. We propose a class of multi-level stochastic gradient methods that are motivated from the method of multi-timescale stochastic approximation. First we propose a basic $T$-level stochastic compositional gradient algorithm, establish its almost sure convergence and obtain an $n$-iteration error bound $O (n^{-1/2^T})$. Then we develop accelerated multi-level stochastic gradient methods by using an extrapolation-interpolation scheme to take advantage of the smoothness of individual component functions. When all component functions are smooth, we show that the convergence rate improves to $O(n^{-4/(7+T)})$ for general objectives and $O (n^{-4/(3+T)})$ for strongly convex objectives. We also provide almost sure convergence and rate of convergence results for nonconvex problems. The proposed methods and theoretical results are validated using numerical experiments.