論文の概要: Debiasing a First-order Heuristic for Approximate Bi-level Optimization

• arxiv url: http://arxiv.org/abs/2106.02487v1
• Date: Fri, 4 Jun 2021 13:46:48 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-07 14:57:11.847887
• Title: Debiasing a First-order Heuristic for Approximate Bi-level Optimization
• Title（参考訳）: 近似バイレベル最適化のための1次ヒューリスティックのデバイアス
• Authors: Valerii Likhosherstov, Xingyou Song, Krzysztof Choromanski, Jared Davis, Adrian Weller
• Abstract要約: 近似バイレベル最適化(ABLO)は、数値的な(インナーレベルの)最適化ループを含む(外部レベルの)最適化問題からなる。 FOMの収束性に関する理論的理解の欠如がある。 本稿では,メモリの複雑さを一定に保った非バイアスなFOMを$r$の関数として提案する。
• 参考スコア（独自算出の注目度）: 38.068090269482425
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Approximate bi-level optimization (ABLO) consists of (outer-level) optimization problems, involving numerical (inner-level) optimization loops. While ABLO has many applications across deep learning, it suffers from time and memory complexity proportional to the length $r$ of its inner optimization loop. To address this complexity, an earlier first-order method (FOM) was proposed as a heuristic that omits second derivative terms, yielding significant speed gains and requiring only constant memory. Despite FOM's popularity, there is a lack of theoretical understanding of its convergence properties. We contribute by theoretically characterizing FOM's gradient bias under mild assumptions. We further demonstrate a rich family of examples where FOM-based SGD does not converge to a stationary point of the ABLO objective. We address this concern by proposing an unbiased FOM (UFOM) enjoying constant memory complexity as a function of $r$. We characterize the introduced time-variance tradeoff, demonstrate convergence bounds, and find an optimal UFOM for a given ABLO problem. Finally, we propose an efficient adaptive UFOM scheme.
• Abstract（参考訳）: 近似二レベル最適化(ablo)は、数値(インナーレベル)最適化ループを含む(外部レベル)最適化問題からなる。 ABLOはディープラーニングにまたがる多くのアプリケーションを持っているが、時間とメモリの複雑さは内部最適化ループの$r$に比例する。 この複雑さに対処するため、初期の1次法(FOM)は2次微分項を省略し、大きな速度ゲインをもたらし、メモリを一定に保つヒューリスティックとして提案された。 FOMの人気にもかかわらず、収束性に関する理論的理解が欠けている。 我々は,FOMの勾配バイアスを軽度仮定の下で理論的に特徴づけることにより寄与する。 さらに、FOMをベースとしたSGDがABLO目標の定常点に収束しないような、豊富な例の族を示す。 この懸念に対処するために、不偏のFOM(UFOM)を$r$の関数として一定のメモリ複雑性を享受することを提案する。 導入した時間分散トレードオフを特徴付け、収束境界を示し、与えられたABLO問題に対して最適なUFOMを求める。 最後に,効率的な適応ufomスキームを提案する。

関連論文リスト

• A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
  我々は,現代のディープラーニングにおいて広く普及している一般的なメタ学習問題に対処する。 これらの問題は、しばしばBi-Level Optimizations (BLO)として定式化される。 我々は,与えられたBLO問題を,内部損失関数が滑らかな分布となり,外損失が内部分布に対する期待損失となるようなii最適化に変換することにより,新たな視点を導入する。
  論文  参考訳（メタデータ） (2024-10-14T12:10:06Z)
• Enhancing Zeroth-order Fine-tuning for Language Models with Low-rank Structures [21.18741772731095]
  ゼロ階数(ZO)アルゴリズムは、関数値の有限差を用いて勾配を近似することで、有望な代替手段を提供する。 既存のZO法は、LLM微調整で一般的な低ランク勾配構造を捉えるのに苦労し、準最適性能をもたらす。 本稿では,LLMにおけるこの構造を効果的に捕捉する低ランクZOアルゴリズム(LOZO)を提案する。
  論文  参考訳（メタデータ） (2024-10-10T08:10:53Z)
• Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
  ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。 複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。 本稿では,ZPDVR法とZPDVR法を提案する。
  論文  参考訳（メタデータ） (2024-05-28T02:27:53Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• Versatile Single-Loop Method for Gradient Estimator: First and Second Order Optimality, and its Application to Federated Learning [45.78238792836363]
  本稿では,SLEDGE (Single-Loop-E Gradient Estimator) という単一ループアルゴリズムを提案する。 既存の手法とは異なり、SLEDGEは、(ii)2階最適、(ii)PL領域における、(iii)少ないデータ以下の複雑さの利点を持つ。
  論文  参考訳（メタデータ） (2022-09-01T11:05:26Z)
• Global convergence of optimized adaptive importance samplers [0.0]
  我々は,モンテカルロを一般提案と統合するために最適化された適応的重要度サンプリング器 (OAIS) を解析した。 我々は、提案に対する$chi2$-divergenceの大域的勾配に対する漸近的境界を導出する。
  論文  参考訳（メタデータ） (2022-01-02T19:56:36Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• UFO-BLO: Unbiased First-Order Bilevel Optimization [42.49533978193117]
  我々は,この収束を理論的に保証できる,新しいFOBLOに基づく外層勾配の非バイアス推定法を提案する。 この結果はOmniglotとMini-ImageNet,人気の数ショットメタラーニングベンチマークの実験結果によって裏付けられている。
  論文  参考訳（メタデータ） (2020-06-05T18:53:45Z)

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

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