論文の概要: Super-efficiency of automatic differentiation for functions defined as a minimum

• arxiv url: http://arxiv.org/abs/2002.03722v1
• Date: Mon, 10 Feb 2020 13:23:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-02 07:51:12.425181
• Title: Super-efficiency of automatic differentiation for functions defined as a minimum
• Title（参考訳）: 最小として定義される関数の自動微分の超効率
• Authors: Pierre Ablin, Gabriel Peyr\'e and Thomas Moreau
• Abstract要約: min-min最適化では、最小値として定義される関数の勾配を計算する必要がある。 本稿では,これらの推定器による誤差を最適化誤差の関数として検討する。
• 参考スコア（独自算出の注目度）: 16.02151272607889
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In min-min optimization or max-min optimization, one has to compute the gradient of a function defined as a minimum. In most cases, the minimum has no closed-form, and an approximation is obtained via an iterative algorithm. There are two usual ways of estimating the gradient of the function: using either an analytic formula obtained by assuming exactness of the approximation, or automatic differentiation through the algorithm. In this paper, we study the asymptotic error made by these estimators as a function of the optimization error. We find that the error of the automatic estimator is close to the square of the error of the analytic estimator, reflecting a super-efficiency phenomenon. The convergence of the automatic estimator greatly depends on the convergence of the Jacobian of the algorithm. We analyze it for gradient descent and stochastic gradient descent and derive convergence rates for the estimators in these cases. Our analysis is backed by numerical experiments on toy problems and on Wasserstein barycenter computation. Finally, we discuss the computational complexity of these estimators and give practical guidelines to chose between them.
• Abstract（参考訳）: min-min最適化やmax-min最適化では、最小として定義される関数の勾配を計算する必要がある。 ほとんどの場合、最小値は閉形式を持たず、近似は反復アルゴリズムによって得られる。 関数の勾配を推定する通常の方法は2つあり、近似の正確さを仮定した解析式とアルゴリズムによる自動微分のいずれかを用いる。 本稿では,これらの推定器による漸近誤差を最適化誤差の関数として検討する。 その結果, 自動推定器の誤差は, 超効率現象を反映した解析推定器の誤差の2乗に近いことがわかった。 自動推定器の収束はアルゴリズムのヤコビアンの収束に大きく依存する。 本研究は, 勾配降下および確率勾配降下について解析し, 推定器の収束率を導出する。 本解析は玩具問題およびwasserstein barycenter計算に関する数値実験によって裏付けられている。 最後に,これらの推定器の計算複雑性を議論し,それらの間に選択する実践的指針を与える。

関連論文リスト

• A Mean-Field Analysis of Neural Stochastic Gradient Descent-Ascent for Functional Minimax Optimization [90.87444114491116]
  本稿では,超パラメトリック化された2層ニューラルネットワークの無限次元関数クラス上で定義される最小最適化問題について検討する。 i) 勾配降下指数アルゴリズムの収束と, (ii) ニューラルネットワークの表現学習に対処する。 その結果、ニューラルネットワークによって誘導される特徴表現は、ワッサーシュタイン距離で測定された$O(alpha-1)$で初期表現から逸脱することが許された。
  論文  参考訳（メタデータ） (2024-04-18T16:46:08Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• One-step differentiation of iterative algorithms [7.9495796547433395]
  本稿では, 自動微分法としての一段階微分法, あるいはジャコビアンフリーバックプロパゲーションについて検討する。 両レベル最適化の結果とともに, 具体例を用いた完全理論的近似解析を行う。
  論文  参考訳（メタデータ） (2023-05-23T07:32:37Z)
• A Gradient Smoothed Functional Algorithm with Truncated Cauchy Random Perturbations for Stochastic Optimization [10.820943271350442]
  本稿では,雑音の多いコストサンプルに対する期待値であるスムーズな目的関数を最小化するための凸勾配アルゴリズムを提案する。 また,本アルゴリズムは局所最小値への収束を示唆し,レートリリアを回避できることも示している。
  論文  参考訳（メタデータ） (2022-07-30T18:50:36Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• The estimation error of general first order methods [12.472245917779754]
  我々は,高次元回帰と低次元行列推定という2種類の推定問題を考察する。 我々は、観測数とパラメータ数の両方が分岐する高次元最適値の誤差を下界に導出する。 これらの下界は、推定誤差が下界とわずかに無視可能な項に一致するアルゴリズムが存在することを意味している。
  論文  参考訳（メタデータ） (2020-02-28T18:13:47Z)
• Stochastic Optimization for Regularized Wasserstein Estimators [10.194798773447879]
  ワッサーシュタイン推定器勾配の正規化版を、自然次元のサブ線形なステップ毎の時間で解くアルゴリズムを導入する。 このアルゴリズムは他のタスクにも拡張可能であることを示し、その中にはWasserstein Barycentersの推定も含まれる。
  論文  参考訳（メタデータ） (2020-02-20T12:04:05Z)
• Variance Reduction with Sparse Gradients [82.41780420431205]
  SVRGやSpiderBoostのような分散還元法では、大きなバッチ勾配と小さなバッチ勾配が混在している。 我々は、新しい空間演算子:ランダムトップk演算子を導入する。 我々のアルゴリズムは、画像分類、自然言語処理、スパース行列分解など様々なタスクにおいて、一貫してSpiderBoostより優れています。
  論文  参考訳（メタデータ） (2020-01-27T08:23:58Z)

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

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