論文の概要: A framework for bilevel optimization that enables stochastic and global
variance reduction algorithms
- arxiv url: http://arxiv.org/abs/2201.13409v1
- Date: Mon, 31 Jan 2022 18:17:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-01 16:24:39.887620
- Title: A framework for bilevel optimization that enables stochastic and global
variance reduction algorithms
- Title（参考訳）: 確率的および大域的分散低減アルゴリズムを実現する二段階最適化の枠組み
- Authors: Mathieu Dagr\'eou, Pierre Ablin, Samuel Vaiter, Thomas Moreau
- Abstract要約: 双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。
本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。
我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAは$O(frac1T)$収束率を持ち、Polyak-Lojasciewicz仮定の下で線形収束を達成することを示した。
- 参考スコア（独自算出の注目度）: 17.12280360174073
- License: http://creativecommons.org/licenses/by/4.0/
- 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 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。