論文の概要: qNBO: quasi-Newton Meets Bilevel Optimization
- arxiv url: http://arxiv.org/abs/2502.01076v1
- Date: Mon, 03 Feb 2025 05:36:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-05 14:53:32.631865
- Title: qNBO: quasi-Newton Meets Bilevel Optimization
- Title(参考訳): qNBO:準ニュートンがバイレベル最適化に挑戦
- Authors: Sheng Fang, Yong-Jin Liu, Wei Yao, Chengming Yu, Jin Zhang,
- Abstract要約: 階層的な学習タスクにおける課題に対処するバイレベル最適化は、機械学習に大きな関心を集めている。
我々はこれらの計算課題に協調的に対処するための一般的な枠組みを導入する。
具体的には、準ニュートンアルゴリズムを利用して、逆ヘッセンベクトル積を効率的に近似しながら、下層問題の解法を高速化する。
- 参考スコア(独自算出の注目度): 26.0555315825777
- License:
- Abstract: Bilevel optimization, addressing challenges in hierarchical learning tasks, has gained significant interest in machine learning. The practical implementation of the gradient descent method to bilevel optimization encounters computational hurdles, notably the computation of the exact lower-level solution and the inverse Hessian of the lower-level objective. Although these two aspects are inherently connected, existing methods typically handle them separately by solving the lower-level problem and a linear system for the inverse Hessian-vector product. In this paper, we introduce a general framework to address these computational challenges in a coordinated manner. Specifically, we leverage quasi-Newton algorithms to accelerate the resolution of the lower-level problem while efficiently approximating the inverse Hessian-vector product. Furthermore, by exploiting the superlinear convergence properties of BFGS, we establish the non-asymptotic convergence analysis of the BFGS adaptation within our framework. Numerical experiments demonstrate the comparable or superior performance of the proposed algorithms in real-world learning tasks, including hyperparameter optimization, data hyper-cleaning, and few-shot meta-learning.
- Abstract(参考訳): 階層的な学習タスクにおける課題に対処するバイレベル最適化は、機械学習に大きな関心を集めている。
双レベル最適化への勾配降下法の実践的実装は計算ハードルに遭遇し、特に、厳密な低レベル解の計算と、低レベルの目的の逆ヘシアン(英語版)の計算に遭遇する。
これらの2つの側面は本質的に連結であるが、既存の方法は通常、逆ヘッセンベクトル積に対する下層問題と線型系を解くことによってそれらを分離的に扱う。
本稿では,これらの計算課題に協調的に対処するための一般的な枠組みを提案する。
具体的には、準ニュートンアルゴリズムを利用して、逆ヘッセンベクトル積を効率的に近似しながら、下層問題の解法を高速化する。
さらに,BFGSの超線形収束特性を利用して,BFGS適応の非漸近収束解析を行う。
数値実験では、ハイパーパラメータ最適化、データハイパークリーニング、数ショットメタラーニングなど、現実世界の学習タスクにおける提案アルゴリズムの同等あるいは優れた性能を示す。
関連論文リスト
- Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。
本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。
合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
論文 参考訳(メタデータ) (2024-11-07T17:05:31Z) - A Primal-Dual-Assisted Penalty Approach to Bilevel Optimization with Coupled Constraints [66.61399765513383]
We developed a BLOCC algorithm to tackle BiLevel Optimization problems with Coupled Constraints。
2つのよく知られた実世界のアプリケーションでその効果を実証する。
論文 参考訳(メタデータ) (2024-06-14T15:59:36Z) - Constrained Bi-Level Optimization: Proximal Lagrangian Value function
Approach and Hessian-free Algorithm [8.479947546216131]
We developed a Hessian-free gradient-based algorithm-termed proximal Lagrangian Value function-based Hessian-free Bi-level Algorithm (LV-HBA)
LV-HBAは特に機械学習アプリケーションに適している。
論文 参考訳(メタデータ) (2024-01-29T13:50:56Z) - Effective Bilevel Optimization via Minimax Reformulation [23.5093932552053]
ミニマックス問題としてバイレベル最適化の再構成を提案する。
穏やかな条件下では、これらの2つの問題が等価であることを示す。
提案手法は, 計算コストを大幅に削減しつつ, 最先端の2段階法より優れる。
論文 参考訳(メタデータ) (2023-05-22T15:41:33Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳(メタデータ) (2023-02-24T18:41:48Z) - Efficient Gradient Approximation Method for Constrained Bilevel
Optimization [2.0305676256390934]
大規模高次元データを用いたバイレベル最適化が開発されている。
本稿では凸と微分不可能な近似を伴う制約付き二値問題について考察する。
論文 参考訳(メタデータ) (2023-02-03T19:34:56Z) - Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。
厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。
このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
論文 参考訳(メタデータ) (2021-11-29T15:10:09Z) - Bilevel Optimization for Machine Learning: Algorithm Design and
Convergence Analysis [12.680169619392695]
この論文は、2レベル最適化アルゴリズムに対する総合収束率解析を提供する。
問題に基づく定式化では、AIDおよびITDに基づく2レベルアルゴリズムの収束率解析を行う。
そこで我々は,ゆるやかな仮定で形状収束解析を行う加速バイレベルアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-07-31T22:05:47Z) - A Value-Function-based Interior-point Method for Non-convex Bi-level
Optimization [38.75417864443519]
バイレベル最適化モデルは、実践的な関心を持って、幅広い複雑な学習タスクをキャプチャすることができる。
そこで我々は,下層問題における正規化値関数を上層目標にペナルティ化する,新しい内部Biレベル値に基づく内点法を提案する。
論文 参考訳(メタデータ) (2021-06-15T09:10:40Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳(メタデータ) (2020-10-15T18:09:48Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳(メタデータ) (2020-06-16T13:41:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。