論文の概要: A Barrier-Metric First-Order Method for Linearly Constrained Bilevel Optimization

• arxiv url: http://arxiv.org/abs/2605.11476v1
• Date: Tue, 12 May 2026 03:44:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-13 21:48:56.554069
• Title: A Barrier-Metric First-Order Method for Linearly Constrained Bilevel Optimization
• Title（参考訳）: 線形制約付き二値最適化のためのバリア・メトリ一階法
• Authors: Tenglong Hong, Paul Grigas,
• Abstract要約: 固定された多面体下実現可能性集合を用いた双レベル最適化について検討した。 アクティブセットの変更は、上位の目的を非滑らかにすることができる。 既存の過次法は、典型的には低いヘッセン逆数や等価線型解を必要とする。
• 参考スコア（独自算出の注目度）: 1.4323566945483492
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study bilevel optimization with a fixed polyhedral lower feasible set. Such problems are challenging for two reasons: active-set changes can make the upper objective nonsmooth, and existing hypergradient methods typically require lower-Hessian inversions or equivalent linear solves, which are computationally expensive. To address these issues, we adopt a logarithmic barrier smoothing of the lower problem to obtain a differentiable approximation of the constrained bilevel objective, and develop a proxy-gradient algorithm for the resulting barrier-smoothed surrogate. The algorithm uses only gradients of the upper and lower objectives; its only second-order object is the explicit logarithmic barrier Hessian determined by the fixed polyhedral constraints. Barrier smoothing restores differentiability, but Euclidean smoothness constants are not uniformly bounded near the boundary. We therefore develop a local Dikin-geometry analysis in which the barrier-metric provides an oracle-free curvature scale near the moving lower centers. This leads to barrier-aware schedules that keep the iterates inside locally well-behaved regions. For the barrier-smoothed objective, we prove stationarity rates of $\widetilde{O}(K^{-2/3})$ in the deterministic setting and $\widetilde{O}(K^{-2/5})$ under upper-level-only bounded stochastic noise after $K$ outer iterations, together with quantitative bias control as the barrier parameter decreases.
• Abstract（参考訳）: 固定された多面体下実現可能性集合を用いた双レベル最適化について検討した。 このような問題は2つの理由により困難である: 能動集合の変化は上向きの目的を非滑らかにしうるし、既存の過次法は一般に計算コストの低いロー・ヘシアン反転や等価線型解を必要とする。 これらの問題に対処するために、より低い問題の対数的バリアスムーシングを採用し、制約された二レベル目的の微分可能な近似を求め、その結果のバリアスムーズなサロゲートに対するプロキシ勾配アルゴリズムを開発する。 このアルゴリズムは上と下の目的の勾配のみを用いており、その2階の対象は固定された多面体制約によって決定される明示的な対数障壁である。 バリアの滑らか化は微分可能性を取り戻すが、ユークリッドの滑らか度定数は境界付近で一様に有界ではない。 そこで我々は,移動する下方中心付近のオラクルフリーな曲率スケールをバリア・メトリックが与える局所ジキン・幾何学解析を開発した。 これによりバリア対応のスケジュールが実現し、イテレートをローカルに好都合なリージョン内に保持する。 バリア・スムースな目的のために、決定論的条件において$\widetilde{O}(K^{-2/3})$と$\widetilde{O}(K^{-2/5})$の定常性を証明した。

関連論文リスト

• Local LMO: Constrained Gradient Optimization via a Local Linear Minimization Oracle [51.714334316332476]
  Local Lは制約付き最適化のための新しいプロジェクションフリー型である。 局所LMOはGD(Gradient Descent)のオラクルと見なされる。
  論文  参考訳（メタデータ） (2026-05-09T10:03:24Z)
• Super-Level-Set Regression: Conditional Quantiles via Volume Minimization [46.298122008420414]
  我々はこの暗黙的な結合をうまく解決する新しい数学的枠組みであるスーパーレベル・セット・レグレッション(SLS)を導入する。 完全分布推定を回避し、フレキシブルな体積保存フロンティア関数を活用することにより、複素・多重モーダル・非共役条件構造をエンド・ツー・エンドにキャプチャする。
  論文  参考訳（メタデータ） (2026-05-07T13:14:45Z)
• Bridging Constraints and Stochasticity: A Fully First-Order Method for Stochastic Bilevel Optimization with Linear Constraints [3.567855687957749]
  この研究は、一階法のみを用いた線形制約付き双レベル最適化に対する最初の有限時間収束保証を提供する。 線形制約、雑音、有限時間解析を両レベル最適化において同時に扱うという前例のない課題に対処する。
  論文  参考訳（メタデータ） (2025-11-13T00:59:20Z)
• An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness [15.656614304616006]
  本稿では,上層関数が非凸であり,下層関数が強凸である二層最適化問題のクラスについて検討する。 これらの問題は、非有界ネットワークを用いたテキスト分類など、データ学習に大きな応用がある。 本稿では,AccBO という新しい高速化バイレベル最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-28T02:30:44Z)
• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization [18.47705532817026]
  適応勾配法は、最も成功したニューラルネットワークトレーニングアルゴリズムの一つである。 これらの手法は凸SGD-ノルマリティよりも次元依存性が優れていることが知られている。 本稿では,構造物の滑らかさと勾配雑音の分散に関する新しい仮定を紹介する。
  論文  参考訳（メタデータ） (2024-06-07T02:55:57Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)

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

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