論文の概要: Stochastic Bilevel Optimization with Heavy-Tailed Noise

• arxiv url: http://arxiv.org/abs/2509.14952v1
• Date: Thu, 18 Sep 2025 13:37:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-19 17:26:53.242682
• Title: Stochastic Bilevel Optimization with Heavy-Tailed Noise
• Title（参考訳）: 重音を用いた確率的二レベル最適化
• Authors: Zhuanghua Liu, Luo Luo,
• Abstract要約: 本稿では,低次問題を強く凸し,高次問題を非定常雑音レベルとするスムーズな二段階最適化について考察する。
• 参考スコア（独自算出の注目度）: 27.792016944321627
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper considers the smooth bilevel optimization in which the lower-level problem is strongly convex and the upper-level problem is possibly nonconvex. We focus on the stochastic setting that the algorithm can access the unbiased stochastic gradient evaluation with heavy-tailed noise, which is prevalent in many machine learning applications such as training large language models and reinforcement learning. We propose a nested-loop normalized stochastic bilevel approximation (N$^2$SBA) for finding an $\epsilon$-stationary point with the stochastic first-order oracle (SFO) complexity of $\tilde{\mathcal{O}}\big(\kappa^{\frac{7p-3}{p-1}} \sigma^{\frac{p}{p-1}} \epsilon^{-\frac{4 p - 2}{p-1}}\big)$, where $\kappa$ is the condition number, $p\in(1,2]$ is the order of central moment for the noise, and $\sigma$ is the noise level. Furthermore, we specialize our idea to solve the nonconvex-strongly-concave minimax optimization problem, achieving an $\epsilon$-stationary point with the SFO complexity of $\tilde{\mathcal O}\big(\kappa^{\frac{2p-1}{p-1}} \sigma^{\frac{p}{p-1}} \epsilon^{-\frac{3p-2}{p-1}}\big)$. All above upper bounds match the best-known results under the special case of the bounded variance setting, i.e., $p=2$.
• Abstract（参考訳）: 本稿では,下層問題が強く凸であり,上層問題が非凸であるようなスムーズな二層最適化について考察する。 我々は,大規模言語モデルの学習や強化学習など,多くの機械学習アプリケーションで広く用いられている重み付き雑音による確率勾配評価に,アルゴリズムがアクセス可能であるという確率的設定に焦点をあてる。 ネストループ正規化された確率的二値近似 (N$^2$SBA) を用いて、確率的1次オラクル (SFO) の複雑さを$\tilde{\mathcal{O}}\big(\kappa^{\frac{7p-3}{p-1}} \sigma^{\frac{p}{p-1}} \epsilon^{-\frac{4 p - 2}{p-1}}\big)$, $\kappa$は条件番号, $\p\in(1,2]$はノイズの中心モーメントである。 さらに、SFOの複雑性を$\tilde{\mathcal O}\big(\kappa^{\frac{2p-1}{p-1}} \sigma^{\frac{p}{p-1}} \epsilon^{-\frac{3p-2}{p-1}}\big)$とする$\epsilon$-stationary Pointを達成して、非凸強対極小最適化問題を解決するというアイデアを専門化します。 上の上限は、有界分散設定の特別な場合、すなわち$p=2$の場合に最もよく知られた結果と一致する。

関連論文リスト

• Faster Gradient Methods for Highly-smooth Stochastic Bilevel Optimization [27.377966916440432]
  上層問題と下層問題とが凸である場合、二レベル最適化のための$epsilon-gradient pointを求める複雑性を示す。 最近の研究は、一階スムーズな問題に対して$tildemathcalO(epsilon-4)$ lower boundを達成した、一階近似 F$2$SA を提案した。
  論文  参考訳（メタデータ） (2025-09-03T02:02:52Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problem [16.9187409976238]
  凸二レベル最適化のクラス、あるいは単純二レベル最適化(Simple bilevel optimization)のクラスについて検討する。 低レベルの問題の解集合を近似する新しい二段階最適化手法を導入する。
  論文  参考訳（メタデータ） (2023-08-15T02:37:11Z)
• Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
  本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。 また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
  論文  参考訳（メタデータ） (2023-06-30T20:36:44Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization [25.00475462213752]
  Decentralized Recursive Dec. Method (DREAM) 具体的には、$mathcalO(minminappaappa3eps-3,kappa2N)$ one-order oracle (SFO)コールと$tildemathcalO(kappa2 epsilon-2)通信ラウンドが必要です。 我々の数値実験は,従来の手法の優越性を検証した。
  論文  参考訳（メタデータ） (2022-12-05T16:09:39Z)
• Differentially Private Stochastic Gradient Descent with Low-Noise [49.981789906200035]
  現代の機械学習アルゴリズムは、データからきめ細かい情報を抽出して正確な予測を提供することを目的としており、プライバシー保護の目標と矛盾することが多い。 本稿では、プライバシを保ちながら優れたパフォーマンスを確保するために、プライバシを保存する機械学習アルゴリズムを開発することの実践的および理論的重要性について論じる。
  論文  参考訳（メタデータ） (2022-09-09T08:54:13Z)
• Decentralized Stochastic Variance Reduced Extragradient Method [25.21457349137344]
  本稿では,$min_xmax_y fx,y triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumiの分散凸-凹極小最適化問題を考察する。
  論文  参考訳（メタデータ） (2022-02-01T16:06:20Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)

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

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