論文の概要: Bilevel Optimization with Lower-Level Uniform Convexity: Theory and Algorithm

• arxiv url: http://arxiv.org/abs/2603.00027v1
• Date: Wed, 04 Feb 2026 03:09:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-09 01:20:07.973001
• Title: Bilevel Optimization with Lower-Level Uniform Convexity: Theory and Algorithm
• Title（参考訳）: 低レベル均一凸性を用いた二値最適化:理論とアルゴリズム
• Authors: Yuman Wu, Xiaochuan Gong, Jie Hao, Mingrui Liu,
• Abstract要約: 双レベル最適化は、上位レベルの問題が下位レベルの問題によって制約される階層的なフレームワークである。 既存の二レベル最適化手法は、低レベル関数に対する強い凸性やポリアック・オジャシエヴィチ(PL)条件を仮定する。 両レベル最適化は, 一般凸下層関数に対して本質的に難解であり, 極小過次関数の探索が目的であることを示す。
• 参考スコア（独自算出の注目度）: 28.40732302523826
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bilevel optimization is a hierarchical framework where an upper-level optimization problem is constrained by a lower-level problem, commonly used in machine learning applications such as hyperparameter optimization. Existing bilevel optimization methods typically assume strong convexity or Polyak-Łojasiewicz (PL) conditions for the lower-level function to establish non-asymptotic convergence to a solution with small hypergradient. However, these assumptions may not hold in practice, and recent work~\citep{chen2024finding} has shown that bilevel optimization is inherently intractable for general convex lower-level functions with the goal of finding small hypergradients. In this paper, we identify a tractable class of bilevel optimization problems that interpolates between lower-level strong convexity and general convexity via \emph{lower-level uniform convexity}. For uniformly convex lower-level functions with exponent $p\geq 2$, we establish a novel implicit differentiation theorem characterizing the hyperobjective's smoothness property. Building on this, we design a new stochastic algorithm, termed UniBiO, with provable convergence guarantees, based on an oracle that provides stochastic gradient and Hessian-vector product information for the bilevel problems. Our algorithm achieves $\widetilde{O}(ε^{-5p+6})$ oracle complexity bound for finding $ε$-stationary points. Notably, our complexity bounds match the optimal rates in terms of the $ε$ dependency for strongly convex lower-level functions ($p=2$), up to logarithmic factors. Our theoretical findings are validated through experiments on synthetic tasks and data hyper-cleaning, demonstrating the effectiveness of our proposed algorithm.
• Abstract（参考訳）: 双レベル最適化は、高パラメータ最適化などの機械学習アプリケーションで一般的に使用される、上位レベルの最適化問題が下位レベルの問題によって制約される階層的なフレームワークである。 既存の双レベル最適化法は通常、低次函数に対する強い凸性やポリアック・ジョジャシエヴィチ (PL) 条件を仮定し、低次解に対する非漸近収束を確立する。 しかし、これらの仮定は実際は成立せず、最近の研究から、双レベル最適化は、小さな過次函数を見つけることを目的として、一般凸低次函数に対して本質的に難解であることを示した。 本稿では,低レベル強い凸性と一般凸性の間の補間を行う2レベル最適化問題の抽出可能なクラスを,'emph{lower-level convexity} を介して同定する。 指数 $p\geq 2$ で一様凸な低次函数に対して、超対象の滑らかさ特性を特徴づける新しい暗黙微分定理を確立する。 これに基づいて,両レベルの問題に対して確率勾配とヘッセンベクトル積情報を提供する託宣に基づく,証明可能な収束保証を備えた,UniBiOと呼ばれる新しい確率的アルゴリズムを設計する。 我々のアルゴリズムは、ε$定常点を求めるために、$\widetilde{O}(ε^{-5p+6})$ Oracle complexity を達成する。 特に、我々の複雑性は、対数的因子を除いて、強い凸な下層函数(p=2$)に対する$ε$依存の観点からの最適率と一致する。 提案アルゴリズムの有効性を実証し, 合成課題とデータの超クリーン化実験により理論的知見を検証した。

関連論文リスト

• Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization [68.22688819802622]
  我々は、(ほぼ)$レベルのKKTソリューションを見つけるために、$O(/epsilon)$の最先端の複雑さを新たに提案する。 O(/epsilon)$ の(ほぼ) $ レベルの KKT ソリューションを見つけるための技術的複雑さを適用することで、(ほぼ) $ レベルの KKT ソリューションを見つけるための $O(/epsilon)$ の最先端の複雑さを新たに達成する。
  論文  参考訳（メタデータ） (2025-06-03T06:31:59Z)
• A Generalized Alternating Method for Bilevel Learning under the Polyak-{\L}ojasiewicz Condition [63.66516306205932]
  バイレベル最適化は、その新興機械学習分野への応用により、最近、関心を取り戻している。 最近の結果は、単純な反復に基づくイテレーションは、低レベルな目標の凸に起因する利害と一致することを示しています。
  論文  参考訳（メタデータ） (2023-06-04T17:54:11Z)
• On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysis [18.08351275534193]
  双レベル最適化は、そうでなければ斜め最適化問題の内部構造を明らかにする。 双レベル最適化における共通のゴールは、要素の集合の解に暗黙的に依存する超対象である。
  論文  参考訳（メタデータ） (2023-01-02T15:09:12Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。 このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
  論文  参考訳（メタデータ） (2022-03-01T18:20:01Z)
• 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 Accelerated Algorithms for Bilevel Optimization [62.192297758346484]
  バイレベル最適化は、最近の機械学習問題に広く応用されているため、近年、関心が高まりつつある。 結果がminimaxアプリケーションよりも難しいことを示します。
  論文  参考訳（メタデータ） (2021-02-07T21:46:29Z)

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

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