论文标题
凸嵌套随机复合优化的最佳算法
Optimal Algorithms for Convex Nested Stochastic Composite Optimization
论文作者
论文摘要
最近，凸面随机复合优化（NSCO）因其在增强学习和规避风险优化方面的应用而受到了极大的关注。当前的NSCO算法通过数量级的随机甲骨文复杂性比没有嵌套结构的没有嵌套结构的更简单的随机复合优化问题（例如，平滑和非平滑函数的总和）。此外，它们要求所有外层函数都平滑，这对某些重要的应用不满足。这些差异促使我们提出：````嵌套成分是否会使随机优化在甲骨文的复杂性方面更加困难？”在本文中，我们通过为凸的NSCO问题制定订单 - 优越的算法来回答这个问题，该问题是为平稳的，结构性的非平稳和普通的，平稳的启动供应，这些均具有平稳的启动何时，当时是平稳的启动范围，当时是平稳的，所有的外在功能是所有的外在效果。双重（SSD）的方法是达到$ \ Mathcal {O}（1/ε^2）$（$ \ Mathcal {O}（1/ε）$）的甲骨文复杂性，当问题不是（强烈的）convex时，该问题是非固定的非平滑或不太含量的序列序列的，即我们的序列序列，我们会提出序列，即我们的序列序列。为了获得$ \ Mathcal {O}（1/ε^2）$的甲骨文复杂性，我们提供了较低的复杂性。除了强烈的凸出和外部平滑的问题外，所有嵌套的组成。
Recently, convex nested stochastic composite optimization (NSCO) has received considerable attention for its applications in reinforcement learning and risk-averse optimization. The current NSCO algorithms have worse stochastic oracle complexities, by orders of magnitude, than those for simpler stochastic composite optimization problems (e.g., sum of smooth and nonsmooth functions) without the nested structure. Moreover, they require all outer-layer functions to be smooth, which is not satisfied by some important applications. These discrepancies prompt us to ask: ``does the nested composition make stochastic optimization more difficult in terms of the order of oracle complexity?" In this paper, we answer the question by developing order-optimal algorithms for the convex NSCO problem constructed from an arbitrary composition of smooth, structured non-smooth and general non-smooth layer functions. When all outer-layer functions are smooth, we propose a stochastic sequential dual (SSD) method to achieve an oracle complexity of $\mathcal{O}(1/ε^2)$ ($\mathcal{O}(1/ε)$) when the problem is non-strongly (strongly) convex. When there exists some structured non-smooth or general non-smooth outer-layer function, we propose a nonsmooth stochastic sequential dual (nSSD) method to achieve an oracle complexity of $\mathcal{O}(1/ε^2)$. We provide a lower complexity bound to show the latter $\mathcal{O}(1/ε^2)$ complexity to be unimprovable even under a strongly convex setting. All these complexity results seem to be new in the literature and they indicate that the convex NSCO problem has the same order of oracle complexity as those without the nested composition in all but the strongly convex and outer-non-smooth problem.
