論文の概要: Sequential QCQP for Bilevel Optimization with Line Search

• arxiv url: http://arxiv.org/abs/2505.14647v2
• Date: Wed, 13 Aug 2025 21:20:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-15 15:52:16.873861
• Title: Sequential QCQP for Bilevel Optimization with Line Search
• Title（参考訳）: 線形探索による二値最適化のための逐次QCQP
• Authors: Sina Sharifi, Erfan Yazdandoost Hamedani, Mahyar Fazlyab,
• Abstract要約: 双レベル最適化は階層構造を伴い、1つの問題がもう1つの問題にネストされ、レベル間の複雑な相互依存性をもたらす。 低レベル最適条件の近似満足度を常に保証する単一ループチューニングフリーアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 6.6372542104227685
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bilevel optimization involves a hierarchical structure where one problem is nested within another, leading to complex interdependencies between levels. We propose a single-loop, tuning-free algorithm that guarantees anytime feasibility, i.e., approximate satisfaction of the lower-level optimality condition, while ensuring descent of the upper-level objective. At each iteration, a convex quadratically-constrained quadratic program (QCQP) with a closed-form solution yields the search direction, followed by a backtracking line search inspired by control barrier functions to ensure safe, uniformly positive step sizes. The resulting method is scalable, requires no hyperparameter tuning, and converges under mild local regularity assumptions. We establish an O(1/k) ergodic convergence rate in terms of a first-order stationary metric and demonstrate the algorithm's effectiveness on representative bilevel tasks.
• Abstract（参考訳）: 双レベル最適化は階層構造を伴い、1つの問題がもう1つの問題にネストされ、レベル間の複雑な相互依存性をもたらす。 本研究では,高次目標の降下を保証しつつ,低次最適条件の近似満足度を常に保証する単一ループチューニングフリーアルゴリズムを提案する。 各イテレーションにおいて、クローズドフォーム解を持つ凸二次プログラム(QCQP)が探索方向を導出し、その後、制御バリア関数にインスパイアされたバックトラックラインサーチにより、安全で均一なステップサイズが保証される。 得られた方法はスケーラブルであり、ハイパーパラメータチューニングを必要とせず、緩やかな局所正規性仮定の下で収束する。 我々は,O(1/k)エルゴディック収束率を1次定常距離で設定し,そのアルゴリズムが代表的二段階タスクにおいて有効であることを示す。

関連論文リスト

• Linearly Convergent Algorithms for Nonsmooth Problems with Unknown Smooth Pieces [38.01989268269625]
  本研究では,ドメインを滑らかな部分へ分割する関数を高速に最適化するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2025-07-25T17:50:43Z)
• New Lower Bounds for Stochastic Non-Convex Optimization through Divergence Decomposition [11.530542389959347]
  L-凸性(QC)、擬似成長(SmoothQG)、制限不等式(RSI)などの非次元設定における一階最適化の基本的限界を示す。
  論文  参考訳（メタデータ） (2025-02-19T19:21:00Z)
• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• Variable Substitution and Bilinear Programming for Aligning Partially Overlapping Point Sets [48.1015832267945]
  本研究では,RPMアルゴリズムの最小化目的関数を用いて要求を満たす手法を提案する。 分岐とバウンド(BnB)アルゴリズムが考案され、パラメータのみに分岐し、収束率を高める。 実験による評価は,非剛性変形,位置雑音,外れ値に対する提案手法の高剛性を示す。
  論文  参考訳（メタデータ） (2024-05-14T13:28:57Z)
• Regularized Q-Learning with Linear Function Approximation [2.765106384328772]
  線形汎関数近似を用いた正規化Q-ラーニングの2段階最適化について検討する。 特定の仮定の下では、提案アルゴリズムはマルコフ雑音の存在下で定常点に収束することを示す。
  論文  参考訳（メタデータ） (2024-01-26T20:45:40Z)
• A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization [53.14532968909759]
  ALEXRと呼ばれる,効率的な単ループプリマル・デュアルブロック座標アルゴリズムを提案する。 本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。 CFCCO の ROC 曲線の下での GDRO および部分領域の実験結果から,提案アルゴリズムの有望な性能を示す。
  論文  参考訳（メタデータ） (2023-12-04T19:00:07Z)
• A Generalized Alternating Method for Bilevel Learning under the Polyak-{\L}ojasiewicz Condition [63.66516306205932]
  バイレベル最適化は、その新興機械学習分野への応用により、最近、関心を取り戻している。 最近の結果は、単純な反復に基づくイテレーションは、低レベルな目標の凸に起因する利害と一致することを示しています。
  論文  参考訳（メタデータ） (2023-06-04T17:54:11Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
  論文  参考訳（メタデータ） (2022-11-29T05:52:17Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。 このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
  論文  参考訳（メタデータ） (2022-03-01T18:20:01Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)

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

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