論文の概要: Bridging Constraints and Stochasticity: A Fully First-Order Method for Stochastic Bilevel Optimization with Linear Constraints

• arxiv url: http://arxiv.org/abs/2511.09845v1
• Date: Fri, 14 Nov 2025 01:12:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-14 22:53:22.523616
• Title: Bridging Constraints and Stochasticity: A Fully First-Order Method for Stochastic Bilevel Optimization with Linear Constraints
• Title（参考訳）: ブリッジング制約と確率性:線形制約を用いた確率的二値最適化のための完全一階法
• Authors: Cac Phan,
• Abstract要約: この研究は、一階法のみを用いた線形制約付き双レベル最適化に対する最初の有限時間収束保証を提供する。 線形制約、雑音、有限時間解析を両レベル最適化において同時に扱うという前例のない課題に対処する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work provides the first finite-time convergence guarantees for linearly constrained stochastic bilevel optimization using only first-order methods, requiring solely gradient information without any Hessian computations or second-order derivatives. We address the unprecedented challenge of simultaneously handling linear constraints, stochastic noise, and finite-time analysis in bilevel optimization, a combination that has remained theoretically intractable until now. While existing approaches either require second-order information, handle only unconstrained stochastic problems, or provide merely asymptotic convergence results, our method achieves finite-time guarantees using gradient-based techniques alone. We develop a novel framework that constructs hypergradient approximations via smoothed penalty functions, using approximate primal and dual solutions to overcome the fundamental challenges posed by the interaction between linear constraints and stochastic noise. Our theoretical analysis provides explicit finite-time bounds on the bias and variance of the hypergradient estimator, demonstrating how approximation errors interact with stochastic perturbations. We prove that our first-order algorithm converges to $(δ, ε)$-Goldstein stationary points using $Θ(δ^{-1}ε^{-5})$ stochastic gradient evaluations, establishing the first finite-time complexity result for this challenging problem class and representing a significant theoretical breakthrough in constrained stochastic bilevel optimization.
• Abstract（参考訳）: この研究は、一階法のみを用いて線形に制約付き確率的二階最適化を行うための最初の有限時間収束保証を提供する。 線形制約、確率ノイズ、有限時間解析を両レベル最適化において同時に扱うという前例のない課題に対処する。 既存の手法は2次情報を必要とするか、制約のない確率問題のみを扱うか、あるいは単に漸近収束結果を与えるかのいずれかであるが、本手法は勾配法のみを用いて有限時間保証を実現する。 線形制約と確率的雑音の相互作用によって生じる根本的な課題を克服するために、近似的原始解と双対解を用いて、滑らかなペナルティ関数による過次近似を構築する新しいフレームワークを開発する。 我々の理論解析は、過次推定器の偏りと分散に関する明示的な有限時間境界を提供し、近似誤差が確率的摂動とどのように相互作用するかを示す。 1次アルゴリズムが$(δ, ε)$-Goldstein定常点に収束することを証明し、$(δ^{-1}ε^{-5})$確率勾配評価を行い、この難題クラスに対する最初の有限時間複雑性結果を確立し、制約付き確率的二値最適化における重要な理論的ブレークスルーを示す。

関連論文リスト

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Online Non-convex Optimization with Long-term Non-convex Constraints [7.68925638410622]
  一般の長期制約最適化問題をオンライン手法で解くために,新しいFollow-the-Perturbed-Leader型アルゴリズムを提案し,解析した。 提案手法は,長期制約のある情報源同定問題に対処し,理論結果の検証を行い,既存手法と比較して優れた性能を示す。
  論文  参考訳（メタデータ） (2023-11-04T15:08:36Z)
• A Sequential Quadratic Programming Method with High Probability Complexity Bounds for Nonlinear Equality Constrained Stochastic Optimization [2.3814052021083354]
  制約関数値と導関数は利用可能であると仮定されるが、対象関数とその関連する導関数のプログラミング近似のみを計算することができる。 1次定常性を近似するためにアルゴリズムの反復複雑性に縛られる高い確率が導出される。
  論文  参考訳（メタデータ） (2023-01-01T21:46:50Z)
• Convergence Rates of Two-Time-Scale Gradient Descent-Ascent Dynamics for Solving Nonconvex Min-Max Problems [2.0305676256390934]
  連立勾配降下指数アルゴリズムの連続時間変動の有限時間特性を特徴付ける。 連続時間アルゴリズムの挙動に関する結果は、離散時間アルゴリズムの収束特性を高めるために用いられる。
  論文  参考訳（メタデータ） (2021-12-17T15:51:04Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)

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

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