論文の概要: A framework for bilevel optimization that enables stochastic and global variance reduction algorithms
- arxiv url: http://arxiv.org/abs/2201.13409v4
- Date: Sat, 30 Nov 2024 10:12:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-03 16:55:58.865788
- Title: A framework for bilevel optimization that enables stochastic and global variance reduction algorithms
- Title（参考訳）: 確率的および大域的分散低減アルゴリズムを実現する二段階最適化のためのフレームワーク
- Authors: Mathieu Dagréou, Pierre Ablin, Samuel Vaiter, Thomas Moreau,
- Abstract要約: 双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。
本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。
我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAが$O(frac1T)$収束率を持つことを示す。
- 参考スコア（独自算出の注目度）: 21.67411847762289
- License:
- Abstract: Bilevel optimization, the problem of minimizing a value function which involves the arg-minimum of another function, appears in many areas of machine learning. In a large scale empirical risk minimization setting where the number of samples is huge, it is crucial to develop stochastic methods, which only use a few samples at a time to progress. However, computing the gradient of the value function involves solving a linear system, which makes it difficult to derive unbiased stochastic estimates. To overcome this problem we introduce a novel framework, in which the solution of the inner problem, the solution of the linear system, and the main variable evolve at the same time. These directions are written as a sum, making it straightforward to derive unbiased estimates. The simplicity of our approach allows us to develop global variance reduction algorithms, where the dynamics of all variables is subject to variance reduction. We demonstrate that SABA, an adaptation of the celebrated SAGA algorithm in our framework, has $O(\frac1T)$ convergence rate, and that it achieves linear convergence under Polyak-Lojasciewicz assumption. This is the first stochastic algorithm for bilevel optimization that verifies either of these properties. Numerical experiments validate the usefulness of our method.
- Abstract（参考訳）: 2レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題であり、機械学習の多くの領域に現れる。
サンプル数が膨大である大規模な経験的リスク最小化環境では、進行に数個のサンプルしか使用しない確率的手法を開発することが重要である。
しかし、値関数の勾配を計算するには線形系を解く必要があるため、偏りのない確率的推定を導出することは困難である。
この問題を克服するために、内部問題の解、線形システムの解、および主変数を同時に発展させる新しい枠組みを導入する。
これらの方向は和として書かれており、偏りのない見積もりを導き出すのが簡単である。
提案手法の単純さにより,全変数のダイナミクスが分散還元の対象となる大域的分散低減アルゴリズムの開発が可能となる。
我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAは$O(\frac1T)$収束率を持ち、Polyak-Lojasciewicz仮定の下で線形収束を達成することを示した。
これは、これらの特性のどちらかを検証する二段階最適化のための最初の確率的アルゴリズムである。
数値実験により本手法の有用性が検証された。
関連論文リスト
- A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
我々は,現代のディープラーニングにおいて広く普及している一般的なメタ学習問題に対処する。
これらの問題は、しばしばBi-Level Optimizations (BLO)として定式化される。
我々は,与えられたBLO問題を,内部損失関数が滑らかな分布となり,外損失が内部分布に対する期待損失となるようなii最適化に変換することにより,新たな視点を導入する。
論文 参考訳（メタデータ） (2024-10-14T12:10:06Z) - Efficient Gradient Approximation Method for Constrained Bilevel
Optimization [2.0305676256390934]
大規模高次元データを用いたバイレベル最適化が開発されている。
本稿では凸と微分不可能な近似を伴う制約付き二値問題について考察する。
論文 参考訳（メタデータ） (2023-02-03T19:34:56Z) - Continuation Newton methods with deflation techniques for global
optimization problems [3.705839280172101]
最適化問題のグローバルな最小点はエンジニアリングである。
本稿では,この非線形大規模問題に対する新しいメメティックアルゴリズムについて考察する。
我々の数値実験によると、新しいアルゴリズムは制約のない未制約問題に対してうまく機能する。
論文 参考訳（メタデータ） (2021-07-29T09:53:49Z) - Adaptive Importance Sampling for Finite-Sum Optimization and Sampling
with Decreasing Step-Sizes [4.355567556995855]
ステップサイズを小さくした有限サム最適化とサンプリングのための適応的重要度サンプリングのための簡易かつ効率的なアルゴリズムであるavareを提案する。
標準的な技術的条件下では、$mathcalO(T2/3)$と$mathcalO(T5/6)$の動的後悔をそれぞれ、$mathcalO(T5/6)$のステップサイズで実行するときに達成している。
論文 参考訳（メタデータ） (2021-03-23T00:28:15Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - 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) - Aligning Partially Overlapping Point Sets: an Inner Approximation
Algorithm [80.15123031136564]
変換の値に関する事前情報がない点集合を整列するロバストな手法を提案する。
我々のアルゴリズムは変換の正規化を必要とせず、変換の値に関する事前情報がない状況に対処できる。
実験により,提案手法が最先端のアルゴリズムよりも高いロバスト性を示した。
論文 参考訳（メタデータ） (2020-07-05T15:23:33Z) - Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax
Problems [26.24895953952318]
我々は,非ガンスミニマックス問題のクラスを解くアルゴリズムを開発した。
また、単一または2つのミニバッチ誘導体でも機能する。
論文 参考訳（メタデータ） (2020-06-27T03:05:18Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Optimizing generalization on the train set: a novel gradient-based
framework to train parameters and hyperparameters simultaneously [0.0]
一般化は機械学習における中心的な問題である。
本稿では,新たなリスク尺度に基づく新しい手法を提案する。
論文 参考訳（メタデータ） (2020-06-11T18:04:36Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。