论文标题
非凸组成优化的随机高斯牛顿算法
Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization
论文作者
论文摘要
我们开发了两种新的随机高斯 - 纽顿算法，用于解决一类非凸的随机组成优化问题，经常在实践中引起。我们考虑在标准假设下的期望和有限和有限设置，并同时使用经典随机和莎拉估计量来近似功能值和雅各布人。在预期情况下，我们建立了$ \ MATHCAL {O}（\ VAREPSILON^{ - 2}）$迭代 - 复杂性，以实现预期的平稳点，并估算随机甲骨文的总数，既需要功能值及其雅各布式的jacobian，n $ \ varepsilon $均可精确。在有限的总和情况下，我们还估计$ \ Mathcal {o}（\ Varepsilon^{ - 2}）$ itseration-complexity和总甲骨文的总概率高。据我们所知，这是第一次为随机的高斯方法建立这样的全球随机甲骨文复杂性。最后，我们通过在合成数据集和真实数据集上的两个数值示例来说明我们的理论结果。
We develop two new stochastic Gauss-Newton algorithms for solving a class of non-convex stochastic compositional optimization problems frequently arising in practice. We consider both the expectation and finite-sum settings under standard assumptions, and use both classical stochastic and SARAH estimators for approximating function values and Jacobians. In the expectation case, we establish $\mathcal{O}(\varepsilon^{-2})$ iteration-complexity to achieve a stationary point in expectation and estimate the total number of stochastic oracle calls for both function value and its Jacobian, where $\varepsilon$ is a desired accuracy. In the finite sum case, we also estimate $\mathcal{O}(\varepsilon^{-2})$ iteration-complexity and the total oracle calls with high probability. To our best knowledge, this is the first time such global stochastic oracle complexity is established for stochastic Gauss-Newton methods. Finally, we illustrate our theoretical results via two numerical examples on both synthetic and real datasets.
