论文标题
非convex复合优化的随机方差降低的代理线性算法
Stochastic Variance-Reduced Prox-Linear Algorithms for Nonconvex Composite Optimization
论文作者
论文摘要
我们考虑最小化$ f（g（x））+h（x）$的复合函数，其中$ f $和$ h $是凸功能（可以是非平滑的），而$ g $是平滑的矢量映射。此外，我们假设$ g $是组件映射的有限数量或对随机组件映射家庭的期望。我们提出了一类随机方差降低的代理线性算法，以解决这些问题并限制其样本复杂性，以根据组件映射的评估总数及其jacobians的评估总数来找到$ε$稳定的点。当$ g $是$ n $组件的有限平均值时，我们获得样本复杂性$ \ MATHCAL {o}（n+ n^{4/5}ε^{ - 1}）$用于映射和Jacobian评估。当$ g $是一个普遍期望时，我们分别用于组件映射及其jacobians的$ \ mathcal {o}（ε^{ - 5/2}）$和$ \ MATHCAL {O}（ε^{ - 3/2}）$的样本复杂性。如果此外，$ f $还很流畅，则改进了$ \ MATHCAL {O}（N+N^{1/2}ε^{ - 1}）$和$ \ Mathcal {o}（ε^{ - 3/3/2}）$的$ g $是有限的平均值和常规评估的$ G $的样本复杂性。
We consider minimization of composite functions of the form $f(g(x))+h(x)$, where $f$ and $h$ are convex functions (which can be nonsmooth) and $g$ is a smooth vector mapping. In addition, we assume that $g$ is the average of finite number of component mappings or the expectation over a family of random component mappings. We propose a class of stochastic variance-reduced prox-linear algorithms for solving such problems and bound their sample complexities for finding an $ε$-stationary point in terms of the total number of evaluations of the component mappings and their Jacobians. When $g$ is a finite average of $N$ components, we obtain sample complexity $\mathcal{O}(N+ N^{4/5}ε^{-1})$ for both mapping and Jacobian evaluations. When $g$ is a general expectation, we obtain sample complexities of $\mathcal{O}(ε^{-5/2})$ and $\mathcal{O}(ε^{-3/2})$ for component mappings and their Jacobians respectively. If in addition $f$ is smooth, then improved sample complexities of $\mathcal{O}(N+N^{1/2}ε^{-1})$ and $\mathcal{O}(ε^{-3/2})$ are derived for $g$ being a finite average and a general expectation respectively, for both component mapping and Jacobian evaluations.
