論文の概要: Achieving Better Local Regret Bound for Online Non-Convex Bilevel Optimization

• arxiv url: http://arxiv.org/abs/2602.06457v1
• Date: Fri, 06 Feb 2026 07:40:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-09 22:18:26.285115
• Title: Achieving Better Local Regret Bound for Online Non-Convex Bilevel Optimization
• Title（参考訳）: オンライン非凸二値最適化のためのローカルレグレトバウンドの実現
• Authors: Tingkai Jia, Haiguang Wang, Cheng Chen,
• Abstract要約: オンライン二段階最適化(OBO)は多くの機械学習問題の強力なフレームワークとして登場した。 両水準の局所的後悔と窓面平均的局所的後悔の双方に対して最適な後悔境界を定めている。
• 参考スコア（独自算出の注目度）: 5.433809054917617
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Online bilevel optimization (OBO) has emerged as a powerful framework for many machine learning problems. Prior works have developed several algorithms that minimize the standard bilevel local regret or the window-averaged bilevel local regret of the OBO problem, but the optimality of existing regret bounds remains unclear. In this work, we establish optimal regret bounds for both settings. For standard bilevel local regret, we propose an algorithm that achieves the optimal regret $Ω(1+V_T)$ with at most $O(T\log T)$ total inner-level gradient evaluations. We further develop a fully single-loop algorithm whose regret bound includes an additional gradient-variation terms. For the window-averaged bilevel local regret, we design an algorithm that captures sublinear environmental variation through a window-based analysis and achieves the optimal regret $Ω(T/W^2)$. Experiments validate our theoretical findings and demonstrate the practical effectiveness of the proposed methods.
• Abstract（参考訳）: オンライン二段階最適化(OBO)は多くの機械学習問題の強力なフレームワークとして登場した。 先行研究は、OBO問題に対する標準的な2レベル局所的後悔や、平均的な2レベル局所的後悔を最小限に抑えるアルゴリズムを開発してきたが、既存の後悔境界の最適性はいまだ不明である。 本研究では,両設定に最適な後悔境界を確立する。 標準的な二段階的局所的後悔に対して、最大で$O(T\log T)$全内部勾配評価を持つ最適後悔$Ω(1+V_T)を達成できるアルゴリズムを提案する。 我々はさらに、さらに勾配変分項を含む完全単ループアルゴリズムを開発する。 平均的2レベル局所的後悔に対して,ウィンドウベース解析により線形な環境変動を捉えるアルゴリズムを設計し,最適後悔$Ω(T/W^2)を達成した。 提案手法の有効性を検証し,提案手法の有効性を実証する実験を行った。

関連論文リスト

• Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications [7.195047020440563]
  オンライン凸最適化 (Online Convex Optimization, OCO) では、勾配が有限な場合、多くのアルゴリズムは確実にサブ線形後悔を保証する。 この研究は、より困難な重み付け設定において、OCOの異なる古いアルゴリズムを調べる。 注目すべきは、これらの後悔境界は全てのパラメータで完全に最適であることである。
  論文  参考訳（メタデータ） (2025-08-10T20:17:38Z)
• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• Second Order Methods for Bandit Optimization and Control [34.51425758864638]
  我々は,大規模な凸関数に対して,このアルゴリズムが最適($kappa$-2020と呼ぶ凸関数の観点で)となることを示す。 また,メモリを用いたオンライン凸最適化への2次帯域幅アルゴリズムの適用について検討した。
  論文  参考訳（メタデータ） (2024-02-14T04:03:38Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。 ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。 Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds [27.92755687977196]
  本稿では,2つの階層の環境に適応する線形帯域幅アルゴリズムを提案する。 高いレベルでは、提案アルゴリズムは様々な種類の環境に適応する。 提案アルゴリズムは、最適動作に対する累積損失のすべてに依存する、データ依存の後悔境界を有する。
  論文  参考訳（メタデータ） (2023-02-24T00:02:24Z)
• Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods [15.979169581445301]
  オンラインのシングルレベルアルゴリズムに対する既知の後悔の限界を、バイレベル設定にまで広げる。 本研究では,スムーズさを生かしたオンライン時間平均勾配法を提案する。
  論文  参考訳（メタデータ） (2022-07-06T17:36:59Z)
• Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
  バイレベル最適化は、機械学習における問題の1つだ。 双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
  論文  参考訳（メタデータ） (2022-02-08T07:10:06Z)
• Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
  本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。 また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
  論文  参考訳（メタデータ） (2021-07-26T16:18:43Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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