論文の概要: A Fast and Convergent Proximal Algorithm for Regularized Nonconvex and
Nonsmooth Bi-level Optimization
- arxiv url: http://arxiv.org/abs/2203.16615v1
- Date: Wed, 30 Mar 2022 18:53:04 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-01 16:11:51.153646
- Title: A Fast and Convergent Proximal Algorithm for Regularized Nonconvex and
Nonsmooth Bi-level Optimization
- Title（参考訳）: 正則化非凸および非滑らか二値最適化のための高速収束近位アルゴリズム
- Authors: Ziyi Chen, Bhavya Kailkhura, Yi Zhou
- Abstract要約: 既存のバイレベルアルゴリズムは、非滑らかまたは超滑らかな正規化器を扱えない。
本稿では,包括的機械学習アプリケーションを高速化するために,暗黙差分法(AID)が有効であることを示す。
- 参考スコア（独自算出の注目度）: 26.68351521813062
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many important machine learning applications involve regularized nonconvex
bi-level optimization. However, the existing gradient-based bi-level
optimization algorithms cannot handle nonconvex or nonsmooth regularizers, and
they suffer from a high computation complexity in nonconvex bi-level
optimization. In this work, we study a proximal gradient-type algorithm that
adopts the approximate implicit differentiation (AID) scheme for nonconvex
bi-level optimization with possibly nonconvex and nonsmooth regularizers. In
particular, the algorithm applies the Nesterov's momentum to accelerate the
computation of the implicit gradient involved in AID. We provide a
comprehensive analysis of the global convergence properties of this algorithm
through identifying its intrinsic potential function. In particular, we
formally establish the convergence of the model parameters to a critical point
of the bi-level problem, and obtain an improved computation complexity
$\mathcal{O}(\kappa^{3.5}\epsilon^{-2})$ over the state-of-the-art result.
Moreover, we analyze the asymptotic convergence rates of this algorithm under a
class of local nonconvex geometries characterized by a {\L}ojasiewicz-type
gradient inequality. Experiment on hyper-parameter optimization demonstrates
the effectiveness of our algorithm.
- Abstract（参考訳）: 多くの重要な機械学習アプリケーションは、正規化された非凸二レベル最適化を伴う。
しかし、既存の勾配に基づく二レベル最適化アルゴリズムは非凸あるいは非滑らかな正規化器を扱えないため、非凸二レベル最適化において高い計算複雑性に悩まされる。
本研究では,非凸および非滑らかな正規化器を用いた非凸二レベル最適化に対して,近似的暗黙差分法(AID)方式を用いた近似勾配型アルゴリズムを提案する。
特に、アルゴリズムはネステロフの運動量を適用し、AIDに関連する暗黙の勾配の計算を高速化する。
本稿では,本アルゴリズムの内在ポテンシャル関数を同定し,大域収束特性の包括的解析を行う。
特に, 2段階問題の臨界点へのモデルパラメータの収束を正式に確立し, 改良された計算複雑性 $\mathcal{O}(\kappa^{3.5}\epsilon^{-2})$ を得る。
さらに,このアルゴリズムの漸近収束率を,ojasiewicz型勾配不等式を特徴とする局所非凸幾何学のクラスで解析した。
ハイパーパラメータ最適化実験は,アルゴリズムの有効性を実証する。
関連論文リスト
- Efficient Gradient Approximation Method for Constrained Bilevel
Optimization [2.0305676256390934]
大規模高次元データを用いたバイレベル最適化が開発されている。
本稿では凸と微分不可能な近似を伴う制約付き二値問題について考察する。
論文 参考訳（メタデータ） (2023-02-03T19:34:56Z) - Efficiently Escaping Saddle Points in Bilevel Optimization [48.925688192913]
バイレベル最適化は、機械学習における問題の1つだ。
双レベル最適化の最近の進歩は、最初の基本的非適応的多段階解析に収束する。
論文 参考訳（メタデータ） (2022-02-08T07:10:06Z) - Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex
Minimax Machine Learning [12.069630105460766]
AltGDA(Alternating Table-descentascent)は、様々な機械学習アプリケーションで広く使われている計算最適化アルゴリズムである。
本論文では,最小限の最適化問題を解くために,単一ループの高速なループ勾配計算アルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-12-22T04:33:27Z) - 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) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳（メタデータ） (2020-10-15T18:09:48Z) - Proximal Gradient Algorithm with Momentum and Flexible Parameter Restart
for Nonconvex Optimization [73.38702974136102]
アルゴリズムの高速化のために,パラメータ再起動方式が提案されている。
本論文では,非滑らかな問題を解くアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:06:27Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。