論文の概要: SPABA: A Single-Loop and Probabilistic Stochastic Bilevel Algorithm Achieving Optimal Sample Complexity

• arxiv url: http://arxiv.org/abs/2405.18777v1
• Date: Wed, 29 May 2024 05:36:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-30 18:38:40.095551
• Title: SPABA: A Single-Loop and Probabilistic Stochastic Bilevel Algorithm Achieving Optimal Sample Complexity
• Title（参考訳）: SPABA: 最適サンプル複素性を実現する単一ループ確率確率確率的二値アルゴリズム
• Authors: Tianshu Chu, Dachuan Xu, Wei Yao, Jin Zhang,
• Abstract要約: SPABAを実装する際には,双レベル最適化と単レベル最適化の間に複雑性解析のギャップがないことが示されている。 本稿では,複雑性解析の状況を改善するために,他の2ループあるいはネストした2レベルアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 5.046146134689904
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: While stochastic bilevel optimization methods have been extensively studied for addressing large-scale nested optimization problems in machine learning, it remains an open question whether the optimal complexity bounds for solving bilevel optimization are the same as those in single-level optimization. Our main result resolves this question: SPABA, an adaptation of the PAGE method for nonconvex optimization in (Li et al., 2021) to the bilevel setting, can achieve optimal sample complexity in both the finite-sum and expectation settings. We show the optimality of SPABA by proving that there is no gap in complexity analysis between stochastic bilevel and single-level optimization when implementing PAGE. Notably, as indicated by the results of (Dagr\'eou et al., 2022), there might exist a gap in complexity analysis when implementing other stochastic gradient estimators, like SGD and SAGA. In addition to SPABA, we propose several other single-loop stochastic bilevel algorithms, that either match or improve the state-of-the-art sample complexity results, leveraging our convergence rate and complexity analysis. Numerical experiments demonstrate the superior practical performance of the proposed methods.
• Abstract（参考訳）: 機械学習における大規模ネスト最適化問題に対する確率的双レベル最適化手法は広く研究されているが、双レベル最適化を解くための最適複雑性境界がシングルレベル最適化と同一であるかどうかには疑問が残る。 SPABAは, (Li et al , 2021) における非凸最適化のための PAGE 法のバイレベル設定への適応であり, 有限サムおよび期待設定の両方において最適なサンプル複雑性を実現することができる。 PAGEを実装する際に,確率的双レベルと単一レベルの最適化の間に複雑性解析のギャップがないことを証明し,SPABAの最適性を示す。 特に、 (Dagr\'eou et al , 2022) の結果によって示されるように、SGD や SAGA のような他の確率勾配推定器を実装する際には、複雑性解析のギャップが存在する可能性がある。 SPABAに加えて、我々は、我々の収束率と複雑性解析を利用して、最先端のサンプル複雑性結果に適合または改善する、他のいくつかのシングルループ確率的二値アルゴリズムを提案する。 数値実験により提案手法の実用的な性能を実証した。

関連論文リスト

• Contextual Stochastic Bilevel Optimization [50.36775806399861]
  文脈情報と上層変数の期待を最小化する2レベル最適化フレームワークCSBOを導入する。 メタラーニング、パーソナライズドラーニング、エンド・ツー・エンドラーニング、Wassersteinはサイド情報(WDRO-SI)を分散的に最適化している。
  論文  参考訳（メタデータ） (2023-10-27T23:24:37Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  条件付き最適化は、不変学習タスク、AUPRC、AMLなど、幅広い機械学習タスクで見られる。 本稿では,分散フェデレーション学習のためのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-10-04T01:47:37Z)
• Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization [50.10952609321302]
  合成ミニマックス最適化は、さまざまな機械学習領域において重要な課題である。 構成最小最適化の現在の方法は、最適以下の複雑さや、大きなバッチサイズに大きく依存することによって悩まされている。 本稿では,Nested STOchastic Recursive Momentum (NSTORM)と呼ばれる新しい手法を提案する。
  論文  参考訳（メタデータ） (2023-08-18T14:57:21Z)
• Optimal Algorithms for Stochastic Bilevel Optimization under Relaxed Smoothness Conditions [9.518010235273785]
  両レベル最適化のための完全リリップループ・ヘシアン・インバージョンフリーなアルゴリズム・フレームワークを提案する。 我々は、我々のアプローチを少し修正することで、より汎用的な多目的ロバストな双レベル最適化問題に対処できることを示した。
  論文  参考訳（メタデータ） (2023-06-21T07:32:29Z)
• Fast Adaptive Federated Bilevel Optimization [14.579475552088692]
  本稿では,分散二レベル最適化問題の解法として,適応型二レベル最適化アルゴリズム(AdaFBiO)を提案する。 AdaFBiOは、統一適応行列を用いて、様々な適応学習率を柔軟に組み込んで、ULおよびLL問題の変数を更新する。 AdaFBiOアルゴリズムの収束解析フレームワークを提供し、$tildeO(epsilon-3)$の複雑さと$tildeO(epsilon-2)$のコミュニケーション複雑さのサンプルが必要であることを証明した。
  論文  参考訳（メタデータ） (2022-11-02T13:55:47Z)
• Will Bilevel Optimizers Benefit from Loops [63.22466953441521]
  AID-BiOとITD-BiOの2つの一般的な双レベルマトリクスは、自然に1つまたは2つのサブプロブレムを解決する。 AID-BiO と ITD-BiO の両ループ実装選択に適用可能な統合収束解析をまず確立する。
  論文  参考訳（メタデータ） (2022-05-27T20:28:52Z)
• Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
  本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。 また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
  論文  参考訳（メタデータ） (2021-07-26T16:18:43Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)
• Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimization [20.410012564838933]
  構成最適化は、強化学習における価値関数の評価やポートフォリオ管理など、多くの重要な機械学習タスクで発生する。 本稿では, 一般的なスムーズな非帰納的設定における一般的な構成最適化について検討する。
  論文  参考訳（メタデータ） (2019-12-31T18:59:13Z)

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

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