論文の概要: Optimal Algorithms for Stochastic Multi-Level Compositional Optimization

• arxiv url: http://arxiv.org/abs/2202.07530v1
• Date: Tue, 15 Feb 2022 16:02:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-16 15:55:52.642323
• Title: Optimal Algorithms for Stochastic Multi-Level Compositional Optimization
• Title（参考訳）: 確率的マルチレベル合成最適化のための最適アルゴリズム
• Authors: Wei Jiang, Bokun Wang, Yibo Wang, Lijun Zhang, Tianbao Yang
• Abstract要約: そこで本研究では,多レベル分散削減法が最適なサンプル複雑性を実現することを示す。 また、同じ複雑さを達成できるが、実際はより高速に収束するAdaptive SMVRを開発した。
• 参考スコア（独自算出の注目度）: 46.77664277596764
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we investigate the problem of stochastic multi-level compositional optimization, where the objective function is a composition of multiple smooth but possibly non-convex functions. Existing methods for solving this problem either suffer from sub-optimal sample complexities or need a huge batch size. To address this limitation, we propose a Stochastic Multi-level Variance Reduction method (SMVR), which achieves the optimal sample complexity of $\mathcal{O}\left(1 / \epsilon^{3}\right)$ to find an $\epsilon$-stationary point for non-convex objectives. Furthermore, when the objective function satisfies the convexity or Polyak-Lojasiewicz (PL) condition, we propose a stage-wise variant of SMVR and improve the sample complexity to $\mathcal{O}\left(1 / \epsilon^{2}\right)$ for convex functions or $\mathcal{O}\left(1 /(\mu\epsilon)\right)$ for non-convex functions satisfying the $\mu$-PL condition. The latter result implies the same complexity for $\mu$-strongly convex functions. To make use of adaptive learning rates, we also develop Adaptive SMVR, which achieves the same optimal complexities but converges faster in practice. All our complexities match the lower bounds not only in terms of $\epsilon$ but also in terms of $\mu$ (for PL or strongly convex functions), without using a large batch size in each iteration.
• Abstract（参考訳）: 本稿では,目的関数が複数の滑らかだが非凸関数の合成である確率的多値合成最適化の問題について検討する。 この問題を解決する既存の方法は、最適なサンプルの複雑さに苦しむか、巨大なバッチサイズを必要とする。 この制限に対処するため,Stochastic Multi-level Variance Reduction法 (SMVR) を提案し,非凸対象に対する$\epsilon$-stationary point を求めるために$\mathcal{O}\left(1 / \epsilon^{3}\right)$の最適なサンプル複雑性を実現する。 さらに、目的関数が凸性あるいはポリアック・ロジャシエヴィチ(PL)条件を満たすとき、SMVRのステージワイド変種を提案し、サンプル複雑性を$\mathcal{O}\left(1 / \epsilon^{2}\right)$または$\mathcal{O}\left(1 / (\mu\epsilon)\right)$に対して$\mu$-PL条件を満たす非凸関数に対して改善する。 後者の結果は$\mu$-strongly convex関数の複雑さを示している。 また,適応学習率を利用するために,適応型smvrを開発した。 すべての複雑性は、$\epsilon$の点でだけでなく、各イテレーションで大きなバッチサイズを使わずに$\mu$(plまたは強凸関数)の点でも下限に一致します。

関連論文リスト

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
  下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。 我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
  論文  参考訳（メタデータ） (2024-02-12T22:34:53Z)
• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。 エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。 提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
  論文  参考訳（メタデータ） (2022-05-30T14:28:02Z)
• Parallel Quasi-concave set optimization: A new frontier that scales without needing submodularity [14.93584434176082]
  擬凸集合関数のクラスは、単調結合関数への双対クラスとして誘導される。 我々は,グローバルな最大値保証を持つ多種多様な特徴サブセット選択の例を通して,幅広い応用の可能性を示す。
  論文  参考訳（メタデータ） (2021-08-19T15:50:41Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates [12.783783498844022]
  目的関数が$T$関数のネスト合成であるような,スムーズな多層合成最適化問題について検討する。 citeGhaRuswan20を$T$のレベルで一般化した最初のアルゴリズムは、$mathcalO (1/epsilon$6) のサンプル複雑性を実現することができることを示す。 これは、(アン)マルチレベル設定のために設計されたオンラインアルゴリズムが、標準仮定の下で同じサンプル複雑性を得るのはこれが初めてである。
  論文  参考訳（メタデータ） (2020-08-24T15:57:50Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)

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

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