Fugu-MT 論文翻訳(概要): Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing

論文の概要: Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing

arxiv url: http://arxiv.org/abs/2404.00158v1
Date: Fri, 29 Mar 2024 21:12:25 GMT
ステータス: 処理完了
システム内更新日: 2024-04-04 07:07:01.795862
Title: Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing
Title（参考訳）: ガウス平滑化による完全ゼロ階バイレベルプログラミング
Authors: Alireza Aghasi, Saeed Ghadimi,
Abstract要約: ビルベル問題の解法としてゼロ階近似アルゴリズムを研究・解析する。我々の知る限りでは、完全ゼロ階二階最適化アルゴリズムのためにサンプル境界が確立されたのはこれが初めてである。
参考スコア（独自算出の注目度）: 7.143879014059895
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this paper, we study and analyze zeroth-order stochastic approximation algorithms for solving bilvel problems, when neither the upper/lower objective values, nor their unbiased gradient estimates are available. In particular, exploiting Stein's identity, we first use Gaussian smoothing to estimate first- and second-order partial derivatives of functions with two independent block of variables. We then used these estimates in the framework of a stochastic approximation algorithm for solving bilevel optimization problems and establish its non-asymptotic convergence analysis. To the best of our knowledge, this is the first time that sample complexity bounds are established for a fully stochastic zeroth-order bilevel optimization algorithm.
Abstract（参考訳）: 本稿では,上位・下位の目標値や偏りのない勾配推定値が得られない場合に,ビルベル問題を解くためのゼロ階確率近似アルゴリズムを研究・解析する。特に、スタインの恒等性を生かして、まずガウス滑らか化を用いて、2つの独立な変数ブロックを持つ函数の1階と2階の部分微分を推定する。次に、両レベル最適化問題の解法と非漸近収束解析の確立のための確率近似アルゴリズムの枠組みでこれらの推定値を用いた。我々の知る限りでは、完全確率ゼロ階二階最適化アルゴリズムのためにサンプル複雑性境界が確立されたのはこれが初めてである。

関連論文リスト

An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness [15.656614304616006]
本稿では,上層関数が非非有界な滑らかさであり,下層関数が強く凸であるような二層最適化問題のクラスについて検討する。これらの問題は、ニューラルネットワークを用いたテキスト分類など、データ学習に大きな応用がある。
論文参考訳（メタデータ） (2024-09-28T02:30:44Z)
Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
論文参考訳（メタデータ） (2023-06-03T17:05:13Z)
Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文参考訳（メタデータ） (2022-06-17T06:10:20Z)
An Algebraically Converging Stochastic Gradient Descent Algorithm for Global Optimization [14.336473214524663]
アルゴリズムの主要な構成要素は、目的関数の値に基づくランダム性である。アルゴリズムの収束を代数学で証明し、パラメータ空間でチューニングする。アルゴリズムの効率性とロバスト性を示す数値的な例をいくつか提示する。
論文参考訳（メタデータ） (2022-04-12T16:27:49Z)
A Fast and Convergent Proximal Algorithm for Regularized Nonconvex and Nonsmooth Bi-level Optimization [26.68351521813062]
既存のバイレベルアルゴリズムは、非滑らかまたは超滑らかな正規化器を扱えない。本稿では,包括的機械学習アプリケーションを高速化するために,暗黙差分法(AID)が有効であることを示す。
論文参考訳（メタデータ） (2022-03-30T18:53:04Z)
A framework for bilevel optimization that enables stochastic and global variance reduction algorithms [17.12280360174073]
双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAは$O(frac1T)$収束率を持ち、Polyak-Lojasciewicz仮定の下で線形収束を達成することを示した。
論文参考訳（メタデータ） (2022-01-31T18:17:25Z)
Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文参考訳（メタデータ） (2021-11-29T15:10:09Z)
High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文参考訳（メタデータ） (2021-06-10T17:54:21Z)
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)
Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
論文参考訳（メタデータ） (2020-06-11T19:40:38Z)
Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文参考訳（メタデータ） (2020-06-11T17:43:19Z)

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