論文の概要: Stochastic Nested Compositional Bi-level Optimization for Robust Feature Learning

• arxiv url: http://arxiv.org/abs/2307.05384v1
• Date: Tue, 11 Jul 2023 15:52:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-12 14:16:22.841340
• Title: Stochastic Nested Compositional Bi-level Optimization for Robust Feature Learning
• Title（参考訳）: ロバスト特徴学習のための確率ネスト構成二レベル最適化
• Authors: Xuxing Chen, Krishnakumar Balasubramanian, Saeed Ghadimi
• Abstract要約: ネストされた二段階最適化問題を解くアルゴリズムを開発し,解析する。 提案アルゴリズムは,行列複雑性やミニバッチに依存しない。
• 参考スコア（独自算出の注目度）: 11.236838268731804
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop and analyze stochastic approximation algorithms for solving nested compositional bi-level optimization problems. These problems involve a nested composition of $T$ potentially non-convex smooth functions in the upper-level, and a smooth and strongly convex function in the lower-level. Our proposed algorithm does not rely on matrix inversions or mini-batches and can achieve an $\epsilon$-stationary solution with an oracle complexity of approximately $\tilde{O}_T(1/\epsilon^{2})$, assuming the availability of stochastic first-order oracles for the individual functions in the composition and the lower-level, which are unbiased and have bounded moments. Here, $\tilde{O}_T$ hides polylog factors and constants that depend on $T$. The key challenge we address in establishing this result relates to handling three distinct sources of bias in the stochastic gradients. The first source arises from the compositional nature of the upper-level, the second stems from the bi-level structure, and the third emerges due to the utilization of Neumann series approximations to avoid matrix inversion. To demonstrate the effectiveness of our approach, we apply it to the problem of robust feature learning for deep neural networks under covariate shift, showcasing the benefits and advantages of our methodology in that context.
• Abstract（参考訳）: ネスト型合成二段階最適化問題に対する確率近似アルゴリズムの開発と解析を行う。 これらの問題には、上層階における$t$ の非凸滑らかな関数の入れ子構成と、下層階における滑らかで強い凸関数が含まれる。 提案するアルゴリズムは行列の反転やミニバッチに依存しず、約$\tilde{o}_t(1/\epsilon^{2})$というoracleの複雑さを持つ$\epsilon$-stationaryソリューションを実現できる。 ここで$\tilde{o}_t$は、$t$に依存するポリログ因子と定数を隠蔽する。 この結果の確立における重要な課題は、確率勾配において3つの異なるバイアス源を扱うことである。 第1の源は上階の組成の性質から生まれ、第2の源は二階構造から始まり、第3の源は行列の反転を避けるためにノイマン級数近似を用いることによって現れる。 提案手法の有効性を実証するために,共変量シフト下でのディープニューラルネットワークの堅牢な特徴学習問題に適用し,その文脈における方法論の利点と利点を示す。

関連論文リスト

• An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness [15.656614304616006]
  本稿では,上層関数が非非有界な滑らかさであり,下層関数が強く凸であるような二層最適化問題のクラスについて検討する。 これらの問題は、ニューラルネットワークを用いたテキスト分類など、データ学習に大きな応用がある。
  論文  参考訳（メタデータ） (2024-09-28T02:30:44Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization [94.19177623349947]
  非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。 2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。 GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
  論文  参考訳（メタデータ） (2022-09-12T06:53:24Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization [12.096252285460814]
  合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。 提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
  論文  参考訳（メタデータ） (2022-02-09T06:05:38Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  機械学習に多くの応用がある非SBO問題を考察する。 本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-05T18:28:42Z)
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction [18.65143269806133]
  我々は、個々のコンポーネントごとに勾配および近位オラクルにアクセスできる近位インクリメンタルファーストオーダー(PIFO)アルゴリズムを検討する。 古典的な例の三対角行列を$n$群に分割する逆問題を構築するための新しいアプローチを開発する。
  論文  参考訳（メタデータ） (2021-03-15T11:20:31Z)
• 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)
• Nearly Optimal Robust Method for Convex Compositional Problems with Heavy-Tailed Noise [46.94819585976063]
  我々は、$f(E_xi g(cdot; xi)) + r(cdot)$という形の凸合成問題を解くための頑健なアルゴリズムを提案する。 我々の知る限りでは、これは重尾の仮定の下で構成問題に対するほぼ最適な準ガウス的自信境界を確立する最初の研究である。
  論文  参考訳（メタデータ） (2020-06-17T18:36:05Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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