論文の概要: 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の源は行列の反転を避けるためにノイマン級数近似を用いることによって現れる。
提案手法の有効性を実証するために,共変量シフト下でのディープニューラルネットワークの堅牢な特徴学習問題に適用し,その文脈における方法論の利点と利点を示す。
関連論文リスト
- Gradient-Free Methods for Deterministic and Stochastic Nonsmooth
Nonconvex Optimization [94.19177623349947]
非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。
2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。
GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
論文 参考訳(メタデータ) (2022-09-12T06:53:24Z) - Riemannian Stochastic Gradient Method for Nested Composition
Optimization [0.0]
この研究は、各函数が期待を含むリーマン多様体上のネスト形式の函数の構成の最適化を考える。
このような問題は、強化学習における政策評価やメタラーニングにおけるモデルカスタマイズといった応用において人気が高まっている。
論文 参考訳(メタデータ) (2022-07-19T15:58:27Z) - 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) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた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) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳(メタデータ) (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。