論文の概要: On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation
- arxiv url: http://arxiv.org/abs/2602.23633v1
- Date: Fri, 27 Feb 2026 03:12:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-02 19:48:24.223139
- Title: On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation
- Title（参考訳）: 近似入射差分法による単ループ確率的二値最適化の収束性について
- Authors: Yubo Zhou, Luo Luo, Guang Dai, Haishan Ye,
- Abstract要約: 単一ループ近似インプリシト差分法(SSAID)アルゴリズムの洗練された収束解析を行う。
i) 最適な$mathcalO(-2)$最先端のマルチループメソッドのレートと一致し、 (ii) $-dependenceの最初の明示的できめ細かい特徴を提供する。
- 参考スコア（独自算出の注目度）: 44.084531611147305
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic Bilevel Optimization has emerged as a fundamental framework for meta-learning and hyperparameter optimization. Despite the practical prevalence of single-loop algorithms--which update lower and upper variables concurrently--their theoretical understanding, particularly in the stochastic regime, remains significantly underdeveloped compared to their multi-loop counterparts. Existing analyses often yield suboptimal convergence rates or obscure the critical dependence on the lower-level condition number $κ$, frequently burying it within generic Lipschitz constants. In this paper, we bridge this gap by providing a refined convergence analysis of the Single-loop Stochastic Approximate Implicit Differentiation (SSAID) algorithm. We prove that SSAID achieves an $ε$-stationary point with an oracle complexity of $\mathcal{O}(κ^7 ε^{-2})$. Our result is noteworthy in two aspects: (i) it matches the optimal $\mathcal{O}(ε^{-2})$ rate of state-of-the-art multi-loop methods (e.g., stocBiO) while maintaining the computational efficiency of a single-loop update; and (ii) it provides the first explicit, fine-grained characterization of the $κ$-dependence for stochastic AID-based single-loop methods. This work demonstrates that SSAID is not merely a heuristic approach, but admits a rigorous theoretical foundation with convergence guarantees competitive with mainstream multi-loop frameworks.
- Abstract（参考訳）: Stochastic Bilevel Optimizationはメタラーニングとハイパーパラメータ最適化の基本的なフレームワークとして登場した。
より低い変数と上位変数を同時に更新するシングルループアルゴリズムの実践的な普及にもかかわらず、理論的理解は、特に確率的状態において、マルチループアルゴリズムと比較して著しく不十分なままである。
既存の解析は、しばしば準最適収束率を得るか、下層条件数$κ$に対する臨界依存を曖昧にし、しばしばジェネリックリプシッツ定数に埋める。
本稿では,SSAID(Single-loop Stochastic Approximate Implicit Differentiation)アルゴリズムの洗練された収束解析を提供することにより,このギャップを埋める。
SSAID は $\mathcal{O}(κ^7 ε^{-2})$ のオラクル複雑性を持つ$ε$-定常点を達成することを証明している。
私たちの結果は2つの点で注目に値する。
i) 単一ループ更新の計算効率を維持しつつ、最先端のマルチループ手法(例えば、stocBiO)の最適$\mathcal{O}(ε^{-2})$レートに適合する。
(ii)確率的AIDに基づく単一ループ法に対するκ$-dependenceの最初の明示的できめ細かい特徴付けを提供する。
この研究は、SSAIDが単なるヒューリスティックなアプローチであるだけでなく、収束が主流のマルチループフレームワークとの競合を保証するという厳密な理論基盤があることを実証している。
関連論文リスト
- Active Bipartite Ranking with Smooth Posterior Distributions [1.9838140219494644]
双部格付けは、多くのアプリケーションにかかわる統計的学習問題であり、受動的文脈において広く研究されている。
本研究では,推定ランキングルールのROC曲線と$sup$ノルムの最適値との距離を最小化することを目的とした,スムーズランクと呼ばれる新しいアルゴリズムを提案する。
本研究では,スムーズランクのサンプリング時間に依存する問題と,任意のPAC$(,)$アルゴリズムのサンプリング時間に依存する問題を確立する。
論文 参考訳（メタデータ） (2026-02-27T18:32:08Z) - From Inexact Gradients to Byzantine Robustness: Acceleration and Optimization under Similarity [12.097833603814252]
そこで,Byzantine-Robust分散最適化は,不正確な勾配オラクルを用いた一般化最適化として適用可能であることを示す。
収束を高速化する2つの最適化手法を提案する。
論文 参考訳（メタデータ） (2026-02-03T09:56:23Z) - Scalable Second-order Riemannian Optimization for $K$-means Clustering [22.839486642997187]
K$-meansクラスタリング問題をサブ多様体として新たに定式化する。
K$-平均多様体を積多様体に分解することにより、ニュートン部分確率がどのように解けるかを示す。
実験の結果,提案手法は最先端の1次負の非負の非負の分解法よりもはるかに高速に収束することがわかった。
論文 参考訳（メタデータ） (2025-09-25T22:49:00Z) - Near-Optimal Non-Convex Stochastic Optimization under Generalized
Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。
しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。
本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文 参考訳（メタデータ） (2023-02-13T00:22:28Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳（メタデータ） (2021-07-02T16:21:52Z) - Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。
また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
論文 参考訳（メタデータ） (2021-04-30T08:50:24Z) - Stochastic optimization with momentum: convergence, fluctuations, and
traps avoidance [0.0]
本稿では,重球法,ネステロフ加速勾配法(S-NAG),広く使用されているアダム法など,勾配勾配勾配のいくつかの変種を統一する一般最適化手法について検討する。
この回避は、非自明な常微分方程式のノイズ離散化として研究される。
論文 参考訳（メタデータ） (2020-12-07T19:14:49Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳（メタデータ） (2020-10-15T18:09:48Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳（メタデータ） (2020-06-12T00:32:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。