論文の概要: Fully First-Order Algorithms for Online Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2602.11665v1
- Date: Thu, 12 Feb 2026 07:36:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-13 21:07:25.697058
- Title: Fully First-Order Algorithms for Online Bilevel Optimization
- Title（参考訳）: オンライン二段階最適化のための完全一階アルゴリズム
- Authors: Tingkai Jia, Cheng Chen,
- Abstract要約: 我々はOBOの完全一階述語アルゴリズムを提案する。
適応的内在化スキームを用いた変種を開発し, 内準最適解の依存性を除去する。
- 参考スコア（独自算出の注目度）: 4.404939623902205
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we study non-convex-strongly-convex online bilevel optimization (OBO). Existing OBO algorithms are mainly based on hypergradient descent, which requires access to a Hessian-vector product (HVP) oracle and potentially incurs high computational costs. By reformulating the original OBO problem as a single-level online problem with inequality constraints and constructing a sequence of Lagrangian function, we eliminate the need for HVPs arising from implicit differentiation. Specifically, we propose a fully first-order algorithm for OBO, and provide theoretical guarantees showing that it achieves regret of $O(1 + V_T + H_{2,T})$. Furthermore, we develop an improved variant with an adaptive inner-iteration scheme, which removes the dependence on the drift variation of the inner-level optimal solution and achieves regret of $O(\sqrt{T} + V_T)$. This regret have the advatange when $V_{T}\ge O(\sqrt{T})$.
- Abstract（参考訳）: 本研究では,非凸-強凸オンライン二値最適化(OBO)について検討する。
既存のOBOアルゴリズムは主に過次降下に基づいており、これはヘッセンベクトル積 (HVP) のオラクルへのアクセスを必要とし、高い計算コストを発生させる可能性がある。
不等式制約のある単一レベルのオンライン問題として元のOBO問題を再構成し、ラグランジュ関数の列を構成することにより、暗黙の微分から生じるHVPの必要性を排除した。
具体的には、OBOの完全一階アルゴリズムを提案し、$O(1 + V_T + H_{2,T})$を後悔していることを示す理論的保証を提供する。
さらに,適応型内点定法により,内面最適解のドリフト変動への依存を排除し,$O(\sqrt{T} + V_T)$を後悔する改良版を開発した。
この後悔は、$V_{T}\ge O(\sqrt{T})$ のときのアバターを持つ。
関連論文リスト
- A Single-Loop First-Order Algorithm for Linearly Constrained Bilevel Optimization [24.729018766550606]
両レベル最適化問題において,低レベル問題は強い凸性を持ち,線形制約が結合している場合について検討する。
線形制約付き二レベル最適化(SFLCB)のための単一ループ1次アルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-10-28T17:58:17Z) - Safe and Efficient Online Convex Optimization with Linear Budget Constraints and Partial Feedback [3.5554907645160605]
本稿では,未知の線形予算制約を伴うオンライン凸最適化について検討する。
本稿では,安全かつ効率的なLyapunov-Optimizationアルゴリズム(SELO)を提案する。
論文 参考訳（メタデータ） (2024-12-05T08:58:41Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - New Projection-free Algorithms for Online Convex Optimization with
Adaptive Regret Guarantees [21.30065439295409]
オンライン凸最適化(OCO)のための効率的なテキストプロジェクションフリーアルゴリズムを提案する。
提案アルゴリズムは,テキストインファシブルプロジェクション(textitinfeasible projections)と呼ばれる新しい,効率的なアプローチによるテクスタイトライン勾配降下アルゴリズムに基づいている。
我々は、全体として$O(T)$コールを使用して分離オラクルを呼び出し、$O(sqrtT)$アダプティブな後悔と$O(T3/4)$アダプティブな期待された後悔を保証します。
論文 参考訳（メタデータ） (2022-02-09T20:56:16Z) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳（メタデータ） (2021-12-09T02:27:52Z) - BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
バイレベル最適化は多くの応用のために機械学習への関心が高まっている。
制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
論文 参考訳（メタデータ） (2021-06-21T20:16:40Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Online Linear Optimization with Many Hints [72.4277628722419]
本研究では,学習者が決定に先立って各ラウンドでK$"hint"ベクトルにアクセス可能なオンライン線形最適化(OLO)問題について検討する。
この設定では、コストベクトルと正の相関を持つ$K$ヒントの凸結合が存在する場合、対数後悔を求めるアルゴリズムを考案する。
論文 参考訳（メタデータ） (2020-10-06T23:25:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。