論文の概要: Nonsmooth Implicit Differentiation: Deterministic and Stochastic Convergence Rates
- arxiv url: http://arxiv.org/abs/2403.11687v2
- Date: Thu, 28 Mar 2024 17:56:05 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-29 20:33:12.782496
- Title: Nonsmooth Implicit Differentiation: Deterministic and Stochastic Convergence Rates
- Title(参考訳): 非滑らかなインシシデント差:決定論的および確率的収束率
- Authors: Riccardo Grazzi, Massimiliano Pontil, Saverio Salzo,
- Abstract要約: パラメトリックな非微分可縮写像の固定点の微分を効率的に計算する問題について検討する。
我々は、反復的分化(ITD)と近似的暗黙的分化(AID)の2つの一般的なアプローチを分析する。
NSIDは、不偏推定器を通してのみアクセス可能な外部マップと内マップの合成として固定点が定義されるとき、導関数を計算するための新しい方法である。
- 参考スコア(独自算出の注目度): 34.81849268839475
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of efficiently computing the derivative of the fixed-point of a parametric nondifferentiable contraction map. This problem has wide applications in machine learning, including hyperparameter optimization, meta-learning and data poisoning attacks. We analyze two popular approaches: iterative differentiation (ITD) and approximate implicit differentiation (AID). A key challenge behind the nonsmooth setting is that the chain rule does not hold anymore. Building upon the recent work by Bolte et al. (2022), who proved linear convergence of nondifferentiable ITD, we provide an improved linear rate for ITD and a slightly better rate for AID, both in the deterministic case. We further introduce NSID, a new stochastic method to compute the implicit derivative when the fixed point is defined as the composition of an outer map and an inner map which is accessible only through a stochastic unbiased estimator. We establish rates for the convergence of NSID, encompassing the best available rates in the smooth setting. We present illustrative experiments confirming our analysis.
- Abstract(参考訳): パラメトリックな非微分可縮写像の固定点の微分を効率よく計算する問題について検討する。
この問題は、ハイパーパラメータ最適化、メタラーニング、データ中毒攻撃など、機械学習に広く応用されている。
我々は,反復的分化 (ITD) と近似的暗黙的分化 (AID) の2つの一般的なアプローチを分析した。
非滑らかな設定の鍵となる課題は、チェーンルールがもはや保たないことだ。
微分不能ITDの線形収束を証明したBolte et al (2022) による最近の研究に基づいて、ITDの線形収束率の改善と、AIDのわずかに良いレートを提供する。
さらに,確率的不偏推定器を通してのみアクセス可能な外部マップと内マップの合成として固定点が定義される場合に,暗黙的微分を計算する新しい確率的手法NSIDを導入する。
我々はNSIDの収束率を確立し、スムーズな環境での最良の利用率を含む。
本報告では,本分析の実証実験について述べる。
関連論文リスト
- Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳(メタデータ) (2023-10-20T12:45:12Z) - Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum
Minimization [52.25843977506935]
有限サム構造をもつ$L$-smooth, non-deuction関数に対して, AdaSpider と呼ばれる適応分散法を提案する。
そうすることで、$tildeOleft + st/epsilonコールで$epsilon-stationaryポイントを計算することができます。
論文 参考訳(メタデータ) (2022-11-03T14:41:46Z) - Data-Driven Influence Functions for Optimization-Based Causal Inference [105.5385525290466]
統計的汎関数に対するガトー微分を有限差分法で近似する構成的アルゴリズムについて検討する。
本研究では,確率分布を事前知識がないが,データから推定する必要がある場合について検討する。
論文 参考訳(メタデータ) (2022-08-29T16:16:22Z) - Gradient flows and randomised thresholding: sparse inversion and
classification [0.0]
スパースインバージョンと分類問題は、現代のデータサイエンスとイメージングにおいて至るところに存在している。
分類において、例えば、データの忠実度項と非滑らかなギンズバーグ-ランダウエネルギーの和を考える。
標準(サブ)勾配降下法はそのような問題にアプローチする際に非効率であることが示されている。
論文 参考訳(メタデータ) (2022-03-22T09:21:14Z) - A Stochastic Bundle Method for Interpolating Networks [18.313879914379008]
本稿では,実験的な損失をゼロにすることができるディープニューラルネットワークのトレーニング手法を提案する。
各イテレーションにおいて,本手法は目的学習近似のバンドルとして知られる最大線形近似を構成する。
論文 参考訳(メタデータ) (2022-01-29T23:02:30Z) - Accelerated and instance-optimal policy evaluation with linear function
approximation [17.995515643150657]
既存のアルゴリズムはこれらの下界の少なくとも1つと一致しない。
我々は,両下界を同時に一致させる高速時間差分アルゴリズムを開発し,インスタンス最適性という強い概念を実現する。
論文 参考訳(メタデータ) (2021-12-24T17:21:04Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳(メタデータ) (2021-07-21T17:10:14Z) - Stochastic optimization with momentum: convergence, fluctuations, and
traps avoidance [0.0]
本稿では,重球法,ネステロフ加速勾配法(S-NAG),広く使用されているアダム法など,勾配勾配勾配のいくつかの変種を統一する一般最適化手法について検討する。
この回避は、非自明な常微分方程式のノイズ離散化として研究される。
論文 参考訳(メタデータ) (2020-12-07T19:14:49Z) - Implicit differentiation of Lasso-type models for hyperparameter
optimization [82.73138686390514]
ラッソ型問題に適した行列逆転のない効率的な暗黙微分アルゴリズムを提案する。
提案手法は,解の空間性を利用して高次元データにスケールする。
論文 参考訳(メタデータ) (2020-02-20T18:43:42Z) - Support recovery and sup-norm convergence rates for sparse pivotal
estimation [79.13844065776928]
高次元スパース回帰では、ピボット推定器は最適な正規化パラメータがノイズレベルに依存しない推定器である。
非滑らかで滑らかな単一タスクとマルチタスク正方形ラッソ型推定器に対するミニマックス超ノルム収束率を示す。
論文 参考訳(メタデータ) (2020-01-15T16:11:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。