論文の概要: Optimal Algorithms for Convex Nested Stochastic Composite Optimization

• arxiv url: http://arxiv.org/abs/2011.10076v5
• Date: Tue, 21 Jun 2022 15:53:19 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-23 20:41:21.603067
• Title: Optimal Algorithms for Convex Nested Stochastic Composite Optimization
• Title（参考訳）: Convex Nested Stochastic Composite Optimizationのための最適アルゴリズム
• Authors: Zhe Zhang, Guanghui Lan
• Abstract要約: 凸ネスト複合最適化 (NSCO) は、強化学習およびリスク-逆最適化におけるその応用に多大な注目を集めている。 現在の NSCO アルゴリズムは、ネスト構造を持たない単純な合成最適化問題よりも、桁違いに、オラクルの複雑さが悪化している。 我々は、滑らかで構造化された非滑らかで一般の非滑らかな層関数からなる任意の構成から構成した凸 NSCO 問題に対する順序最適化アルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 13.200502573462712
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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/\epsilon^2)$ ($\mathcal{O}(1/\epsilon)$) 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/\epsilon^2)$. We provide a lower complexity bound to show the latter $\mathcal{O}(1/\epsilon^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.
• Abstract（参考訳）: 近年,convex nested stochastic composite optimization (nsco) が強化学習とリスク回避最適化への応用で注目を集めている。 現在の NSCO アルゴリズムは、入れ子構造を持たない単純な確率的複合最適化問題(例えば、滑らかな関数と非滑らかな関数の和)よりも、桁違いに確率的オラクルの複雑さが劣る。 さらに、それらはすべての外層関数を滑らかにする必要があるが、重要なアプリケーションでは満足できない。 ネストされたコンポジションは、oracleの複雑さの順序の点で、確率的最適化をより難しくしますか? 本稿では,滑らかで構造化された非滑らかで一般の非滑らかな層関数からなる任意の構成から構築した凸 NSCO 問題に対する順序最適化アルゴリズムを開発することにより,この問題に答える。 すべての外層関数が滑らかなとき、問題が(強に)凸であるときに、$\mathcal{O}(1/\epsilon^2)$$$$\mathcal{O}(1/\epsilon)$のオラクル複雑性を達成する確率的シーケンシャル双対(SSD)法を提案する。 構造化された非滑らかあるいは一般の非滑らかな外層関数が存在する場合、$\mathcal{O}(1/\epsilon^2)$のオラクル複雑性を達成するために、非滑らかな確率的シーケンシャル双対(nSSD)法を提案する。 強い凸条件の下でも、後者の$\mathcal{O}(1/\epsilon^2)$複雑性が改善不可能であることを示すために、より低い複雑性を提供する。 これらの複雑さのすべては文献に新しいもので、convex nscoの問題は、強い凸と外側のスムース問題を除いて、入れ子のない構成でoracleの複雑さの順序が同じであることを示している。

関連論文リスト

• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Optimal Algorithms for Stochastic Multi-Level Compositional Optimization [46.77664277596764]
  目的関数が複数の最適でない関数の制限である多段階合成最適化の問題を解く。 また,適応型多レベル分散低減法 (SMVR) を用いることで,同じ複雑性を実現するが,実際はより高速に収束する。
  論文  参考訳（メタデータ） (2022-02-15T16:02:32Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  機械学習に多くの応用がある非SBO問題を考察する。 本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-05T18:28:42Z)
• Oracle Complexity in Nonsmooth Nonconvex Optimization [49.088972349825085]
  円滑で有界な$$stationaryポイントを考えると、Oracleベースのメソッドは円滑さの円滑な近似を見つけることができることがよく知られている。 本稿では,最適化と平滑化次元とのトレードオフを実証する。
  論文  参考訳（メタデータ） (2021-04-14T10:42:45Z)
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems [45.88640334610308]
  本稿では,非滑らかな問題に対する分散最適化アルゴリズムを提案する。 提案アルゴリズムは,過度な通信を実現することができることを示す。 提案アルゴリズムの有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2020-11-10T13:12:21Z)
• Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimization [20.410012564838933]
  構成最適化は、強化学習における価値関数の評価やポートフォリオ管理など、多くの重要な機械学習タスクで発生する。 本稿では, 一般的なスムーズな非帰納的設定における一般的な構成最適化について検討する。
  論文  参考訳（メタデータ） (2019-12-31T18:59:13Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。