論文の概要: LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace
- arxiv url: http://arxiv.org/abs/2404.03331v1
- Date: Thu, 4 Apr 2024 09:57:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-05 15:14:12.779633
- Title: LancBiO: dynamic Lanczos-aided bilevel optimization via Krylov subspace
- Title（参考訳）: LancBiO: Krylov部分空間による動的Laczos支援バイレベル最適化
- Authors: Bin Gao, Yan Yang, Ya-xiang Yuan,
- Abstract要約: 本稿では、ランツォス過程の助けを借りて、低次元近似クリロフ部分空間の列を構築する。
構成された部分空間は、動的かつ漸進的にヘッセン逆ベクトル積を近似することができる。
また,小さな三角形線形系を解くための中心ステップとして,二段階問題に対する改良可能な部分空間ベースのフレームワークを提案する。
- 参考スコア（独自算出の注目度）: 4.917399520581689
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Bilevel optimization, with broad applications in machine learning, has an intricate hierarchical structure. Gradient-based methods have emerged as a common approach to large-scale bilevel problems. However, the computation of the hyper-gradient, which involves a Hessian inverse vector product, confines the efficiency and is regarded as a bottleneck. To circumvent the inverse, we construct a sequence of low-dimensional approximate Krylov subspaces with the aid of the Lanczos process. As a result, the constructed subspace is able to dynamically and incrementally approximate the Hessian inverse vector product with less effort and thus leads to a favorable estimate of the hyper-gradient. Moreover, we propose a~provable subspace-based framework for bilevel problems where one central step is to solve a small-size tridiagonal linear system. To the best of our knowledge, this is the first time that subspace techniques are incorporated into bilevel optimization. This successful trial not only enjoys $\mathcal{O}(\epsilon^{-1})$ convergence rate but also demonstrates efficiency in a synthetic problem and two deep learning tasks.
- Abstract（参考訳）: 機械学習に広く応用されたバイレベル最適化は、複雑な階層構造を持つ。
大規模二段階問題に対する一般的なアプローチとしてグラディエントベースの手法が登場している。
しかし、ヘッセン逆ベクトル積を含む超勾配の計算は効率を抑え、ボトルネックと見なされる。
逆を回避するために、ランツォス過程の助けを借りて、低次元近似クリロフ部分空間の列を構築する。
結果として、構築された部分空間は、より少ない労力でヘッセン逆ベクトル積を動的かつ漸進的に近似することができ、したがって超次数の推定に有利な結果をもたらす。
さらに,小さな三角形線形系を解くための中心ステップが1つある二段階問題に対して,証明可能な部分空間ベースのフレームワークを提案する。
我々の知る限りでは、サブスペース技術が双レベル最適化に取り入れられるのはこれが初めてである。
この成功した試行は、$\mathcal{O}(\epsilon^{-1})$収束率を楽しむだけでなく、合成問題と2つのディープラーニングタスクの効率も示す。
関連論文リスト
- Memory-Efficient Gradient Unrolling for Large-Scale Bi-level Optimization [71.35604981129838]
従来の勾配に基づく二段階最適化アルゴリズムは、大規模アプリケーションの要求を満たすには不適である。
両レベル最適化のためのメタ勾配の偏りのない近似を実現するための$(textFG)2textU$を導入する。
$(textFG)2textU$は本質的に並列コンピューティングをサポートするように設計されており、大規模分散コンピューティングシステムを効果的に活用することができる。
論文 参考訳（メタデータ） (2024-06-20T08:21:52Z) - Convex Bi-Level Optimization Problems with Non-smooth Outer Objective
Function [0.0]
そこで,Bi-SGは,内的および外的目的関数の両面最適化問題と準線形率に対処することを示した。
生成列から最適解の集合への距離が 0 に収束することを証明した。
論文 参考訳（メタデータ） (2023-07-17T05:03:53Z) - A Generalized Alternating Method for Bilevel Learning under the
Polyak-{\L}ojasiewicz Condition [63.66516306205932]
バイレベル最適化は、その新興機械学習分野への応用により、最近、関心を取り戻している。
最近の結果は、単純な反復に基づくイテレーションは、低レベルな目標の凸に起因する利害と一致することを示しています。
論文 参考訳（メタデータ） (2023-06-04T17:54:11Z) - 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) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - Inexact bilevel stochastic gradient methods for constrained and
unconstrained lower-level problems [0.0]
2段階の定式探索最適化は多くの機械学習の文脈で有効になっている。
2階微分を必要としない新しい低ランク二階勾配法が開発されている。
論文 参考訳（メタデータ） (2021-10-01T18:20:14Z) - Enhanced Bilevel Optimization via Bregman Distance [104.96004056928474]
本稿では,Bregman Bregman関数に基づく二段階最適化手法を提案する。
また,分散還元法によるSBiO-BreD法(ASBiO-BreD)の高速化版も提案する。
論文 参考訳（メタデータ） (2021-07-26T16:18:43Z) - A Value-Function-based Interior-point Method for Non-convex Bi-level
Optimization [38.75417864443519]
バイレベル最適化モデルは、実践的な関心を持って、幅広い複雑な学習タスクをキャプチャすることができる。
そこで我々は,下層問題における正規化値関数を上層目標にペナルティ化する,新しい内部Biレベル値に基づく内点法を提案する。
論文 参考訳（メタデータ） (2021-06-15T09:10:40Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳（メタデータ） (2020-06-16T13:41:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。