論文の概要: The cost of useful natural gradient updates
- arxiv url: http://arxiv.org/abs/2609.33499v1
- Date: Sun, 27 Sep 2026 12:07:28 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-05 16:19:52.039103
- Title: The cost of useful natural gradient updates
- Title（参考訳）: 有用な自然勾配更新のコスト
- Abstract要約: 実現可能で、少なくとも$varepsilon$を失えば、その方向への最良の利得が得られます。
また、イベント傾きのサンプル境界、減衰フィッシャー解のサンプル境界、アフィン分類器の集団-KL証明も提供する。
- 参考スコア（独自算出の注目度）: 24.890782171333246
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: What information is needed to turn a natural-gradient direction into a useful finite update? Under a population Kullback-Leibler (KL) budget, we call a step useful if it is feasible and loses at most a fraction $\varepsilon$ of the best feasible gain along the direction. We construct a four-state exponential family whose laws share their initial gradient, scalar Fisher information and natural gradient, yet two laws have disjoint useful-step sets. With these quantities supplied exactly and the law otherwise known only through draws, the family's worst-case sample complexity is $Θ(\log(1/δ)/(p\varepsilon^2))$ for small $\varepsilon$, where $p$ scales rare-state probabilities and $δ$ is the failure probability. The budget is fixed and the optimal gain stays bounded away from zero, so the step length, not the direction, carries this cost. For succinctly described event-tilt models, returning a useful step is NP-hard even with the exact natural gradient and efficient exact sampling. Recovering the unit natural gradient to constant error is also NP-hard even in a two-parameter logistic family with Fisher condition number at most 3. We also give matching sample bounds for event tilts, sample bounds for damped Fisher solves and a population-KL certificate for affine classifiers. In frozen-feature classifier heads, stopping at a sampled KL boundary succeeds in about half of the trials, and a 10% KL margin raises joint success above 93% at a KL budget of 0.01. Thus, knowing where to move is not enough: how far to move can carry an update's entire cost.
- Abstract（参考訳）: 自然な段階的な方向を有用な有限更新に変換するには、どのような情報が必要ですか?
Kullback-Leibler (KL) の予算の下では、実現可能で、少なくとも$\varepsilon$を失えば、その方向への最良の利得の1歩を有用と呼ぶ。
法則が初期勾配、スカラーフィッシャー情報、自然勾配を共有する4状態指数関数族を構築するが、2つの法則は有用段階集合を不連結にしている。
これらの量と、それ以外は引き分けによってのみ知られている法則により、家族の最悪のサンプルの複雑さは、小さな$\varepsilon$に対して$(\log(1/δ)/(p\varepsilon^2))$であり、$p$は希少な状態確率をスケールし$δ$は失敗確率である。
予算は固定され、最適利得はゼロから切り離されたままなので、方向ではなくステップ長はこのコストがかかる。
簡潔に記述されたイベントチルトモデルに対して、有用なステップを返すことは、正確な自然な勾配と効率的な正確なサンプリングであってもNPハードである。
単位の自然勾配を一定誤差に戻すことは、フィッシャー条件数3の2パラメータロジスティック族においてもNPハードである。
また、イベント傾きのサンプル境界、減衰フィッシャー解のサンプル境界、アフィン分類器の集団-KL証明も提供する。
凍結機能分類器ヘッドでは、サンプルのKL境界での停止は試験の約半分で成功し、10%のKLマージンはKL予算0.01で93%以上の共同成功をもたらす。
従って、どこに移動すべきかを知るだけでは十分ではありません。
関連論文リスト
- Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise [66.13091490213743]
グラディエントクリッピングはトレーニングを安定させるために広く用いられているが、平均的なSGDの統計的精度を改善する必要はない。
有限条件の$p$-th モーメント,$pge2$ の条件下で, クリッピングおよび非クリッピングのPolyak-Ruppert平均 SGD の比較を導出した。
我々の主な結果は、$p>2$の場合、ガウス項が未開偏差境界を独占する明確な精度と信頼条件を与える。
論文 参考訳（メタデータ） (2026-09-26T21:47:14Z) - Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。
スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文 参考訳（メタデータ） (2026-09-07T01:38:41Z) - Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design [28.74829605004241]
我々は、最大極大目標(ロジスティック損失)に基づいて、勾配降下(GD)の有限サンプル推定性能と収束挙動を特徴付ける。
GD は、$*$の小さな近傍に線型収束し、$O(sqrt|*|5d/n)$の$ell$誤差を達成することを示す。
また、大きな$(|*|_2)$段数の下で同じ統計誤差に対するより高速な局所線型収束を確立する。
論文 参考訳（メタデータ） (2026-06-19T18:43:41Z) - Steady-State Behavior of Constant-Stepsize Stochastic Approximation: Gaussian Approximation and Tail Bounds [9.739744677824286]
定段近似(SA)は計算効率の学習に広く用いられている。
以前の研究は、段数 $downarrow 0$ のとき中心とスケールの定常状態がガウス確率ベクトルに弱収束することを示していた。
この論文は、固定された$に対して明示的で漸近的でないエラー境界を提供する。
論文 参考訳（メタデータ） (2026-02-15T02:34:50Z) - A Sharp KL-Convergence Analysis for Diffusion Models under Minimal Assumptions [20.628481624954187]
拡散に基づく生成モデルは、高品質なサンプルを合成するための非常に効果的な方法として登場した。
最近の研究は、最小限の仮定で生成プロセスの収束を分析することに重点を置いている。
我々は$varepsilon$への依存を改善する洗練された分析法を提案する。
論文 参考訳（メタデータ） (2025-08-22T11:29:06Z) - Global convergence of gradient descent for phase retrieval [3.7873341907492923]
位相探索におけるベニグアランドスケープのテンソルに基づく基準を提案し,勾配軌道の有界性を確立する。
これは、勾配降下がほとんどすべての初期点に対して大域最小値に収束することを意味する。
論文 参考訳（メタデータ） (2024-10-13T20:12:34Z) - Sharper Rates and Flexible Framework for Nonconvex SGD with Client and
Data Sampling [64.31011847952006]
我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。
我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。
我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
論文 参考訳（メタデータ） (2022-06-05T21:32:33Z) - High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad
Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。
我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。
我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文 参考訳（メタデータ） (2022-04-06T13:50:33Z) - Carath\'eodory Sampling for Stochastic Gradient Descent [79.55586575988292]
本稿では,Tchakaloff と Carath'eodory の古典的な結果から着想を得た手法を提案する。
我々は、測定値の低減を行う降下ステップを適応的に選択する。
これをBlock Coordinate Descentと組み合わせることで、測定の削減を極めて安価に行えるようにします。
論文 参考訳（メタデータ） (2020-06-02T17:52:59Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z) - Information-Theoretic Lower Bounds for Zero-Order Stochastic Gradient
Estimation [28.776950569604026]
ゼロ階オラクルモデルにおける任意の多次元滑らか関数の勾配を推定するために必要なサンプル数を解析する。
有界分散オラクルに対する有限差分法は、ゼロ第三高微分を持つ函数に対して$O(d4/3/sqrtT)$を持つことを示す。
論文 参考訳（メタデータ） (2020-03-31T00:11:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。