論文の概要: A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2610.07290v1
- Date: Mon, 05 Oct 2026 19:26:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-08 02:58:29.617338
- Title: A Single-Loop, Constant-Batch First-Order Penalty Method for Stochastic Bilevel Optimization
- Title（参考訳）: 確率的二値最適化のための単ループ定数バッチ1次ペナルティ法
- Abstract要約: 非強凸二値問題の場合、既存の一階法はネストループに依存するのが一般的である。
2つの相補成分を組み合わせたSingle-loop Constant-1次ペナルティ法(ICOS)を提案する。
- 参考スコア（独自算出の注目度）: 66.48718943929202
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recent advances in penalty-based methods for stochastic bilevel optimization (SBO) have eliminated the need for second-order derivative oracles. However, for stochastic nonconvex-strongly convex bilevel problems, existing first-order methods typically rely on nested loops and/or large batch sizes for attaining $O(ε^{-6})$ or $O(ε^{-4})$ sample complexity under standard bounded-variance assumption or mean-square smoothness assumption. Achieving these rates with a single-loop penalty method and a constant batch size remains challenging due to a large penalty value needed for an accurate approximation. To address this challenge, we develop a stochastic SIngle-loop COnstant-Batch first-order penalty method (SICO) that combines two complementary ingredients. First, it performs one stochastic-gradient update per-iteration for both the original lower-level and penalized problems, with a projection that controls the separation between their iterates. Second, it applies an exponential moving average to stabilize the upper-level gradient estimator. We show that this combination achieves $ O(ε^{-6}) $ sample complexity using only $O(1)$ stochastic-gradient samples per iteration under unbiased, bounded-variance stochastic gradients. Under the additional mean-square smoothness assumption on the lower-level stochastic gradients, the same algorithm improves the complexity to $O(ε^{-4})$ also with $O(1)$ batch size. To the best of our knowledge, this is the first work to match the best-known convergence rate for fully first-order SBO methods using a single loop and a constant batch size. This result addresses an open problem posed in the literature.
- Abstract（参考訳）: 確率的二段階最適化(SBO)におけるペナルティに基づく手法の最近の進歩は、2階微分オラクルの必要性を排除している。
しかし、確率的でない凸凸二値問題に対しては、既存の一階法は通常、入れ子ループおよび/または大きなバッチサイズに依存して、標準的な有界分散仮定や平均二乗滑らか性仮定の下でのサンプル複雑性を$O(ε^{-6})$または$O(ε^{-4})$とする。
これらのレートを単一ループペナルティ法と一定のバッチサイズで達成することは、正確な近似に必要な大きなペナルティ値のため、依然として困難である。
この課題に対処するため,2つの相補成分を組み合わせた確率的Single-loop Constant-Batch 1次ペナルティ法(SICO)を開発した。
第一に、元の下位レベルとペナル化された問題の両方に対して、1回の確率的な段階的な更新を1回行い、イテレーション間の分離を制御するプロジェクションを実行する。
第2に、上層勾配推定器を安定させるために指数移動平均を適用した。
この組み合わせは、非バイアスで有界な確率勾配の下で、1イテレーションあたりのO(1)$確率勾配サンプルのみを用いて、$O(ε^{-6})$サンプル複雑性を達成することを示す。
下層確率勾配に対する平均2乗滑らかさの仮定が加わり、同じアルゴリズムは、O(ε^{-4})$ の複雑さを $O(1)$ のバッチサイズで改善する。
我々の知る限りでは、これは単一のループと一定のバッチサイズを用いて、完全一階SBO法に対して最もよく知られた収束率に適合する最初の研究である。
この結果は、文献で示されたオープンな問題に対処する。
関連論文リスト
- Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints [12.624604051853657]
線形不等式制約を用いた非コンパクト最適化問題に対するスムーズな原始双対アルゴリズムを提案する。
我々のアルゴリズムは、各サンプルの1つの勾配に基づいて、シングルループの反復である。
既存の手法とは異なり、我々のアルゴリズムは自由なサブ、大きなサイズ、パラメータの増加であり、実現可能性を保証するためにデュアル変数更新を使用する。
論文 参考訳（メタデータ） (2025-04-10T09:59:43Z) - A Nearly Optimal Single Loop Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness [15.656614304616006]
本稿では、上層関数が非定常で、潜在的に非有界な滑らかさを持ち、下層関数が凸であるような二層最適化の問題を考察する。
既存のアルゴリズムはネストループに依存しており、これは重要なチューニング作業を必要とし、実用的ではない。
論文 参考訳（メタデータ） (2024-12-28T04:40:27Z) - Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。
複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。
本稿では,ZPDVR法とZPDVR法を提案する。
論文 参考訳（メタデータ） (2024-05-28T02:27:53Z) - A Fully First-Order Method for Stochastic Bilevel Optimization [8.663726907303303]
一階勾配オラクルのみが利用できる場合、制約のない二段階最適化問題を考える。
完全一階近似法(F2SA)を提案し,その非漸近収束特性について検討する。
MNISTデータハイパクリーニング実験において,既存の2次手法よりも提案手法の実用性能が優れていることを示す。
論文 参考訳（メタデータ） (2023-01-26T05:34:21Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-05T18:28:42Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - 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) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。