論文の概要: Improving the Convergence Rates of Forward Gradient Descent with Repeated Sampling
- arxiv url: http://arxiv.org/abs/2411.17567v1
- Date: Tue, 26 Nov 2024 16:28:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-27 13:32:55.070806
- Title: Improving the Convergence Rates of Forward Gradient Descent with Repeated Sampling
- Title(参考訳): 繰り返しサンプリングによる前向き勾配の収束率の向上
- Authors: Niklas Dexheimer, Johannes Schmidt-Hieber,
- Abstract要約: 前向き勾配降下(FGD)は、生物学的により妥当な勾配降下の代替として提案されている。
本稿では、各トレーニングサンプルに基づいて、$ell$FGDステップを計算することにより、この亜最適係数が$d/(ell wedge d)$となることを示す。
また、繰り返しサンプリングしたFGDは入力分布の低次元構造に適応できることを示す。
- 参考スコア(独自算出の注目度): 5.448070998907116
- License:
- Abstract: Forward gradient descent (FGD) has been proposed as a biologically more plausible alternative of gradient descent as it can be computed without backward pass. Considering the linear model with $d$ parameters, previous work has found that the prediction error of FGD is, however, by a factor $d$ slower than the prediction error of stochastic gradient descent (SGD). In this paper we show that by computing $\ell$ FGD steps based on each training sample, this suboptimality factor becomes $d/(\ell \wedge d)$ and thus the suboptimality of the rate disappears if $\ell \gtrsim d.$ We also show that FGD with repeated sampling can adapt to low-dimensional structure in the input distribution. The main mathematical challenge lies in controlling the dependencies arising from the repeated sampling process.
- Abstract(参考訳): 前向き勾配降下 (FGD) は、後向き通過なしで計算できるため、生物学的により妥当な勾配降下の代替として提案されている。
パラメータが$d$の線形モデルを考えると、FGDの予測誤差は確率勾配降下(SGD)の予測誤差よりも遅い。
本稿では、各トレーニングサンプルに基づいて$\ell$FGDステップを計算することにより、このサブ最適係数が$d/(\ell \wedge d)$となり、$\ell \gtrsim d の場合、レートのサブ最適度が消えることを示す。
繰り返しサンプリングされたFGDは入力分布の低次元構造に適応できることを示す。
主な数学的課題は、繰り返しサンプリングプロセスから生じる依存関係を制御することである。
関連論文リスト
- Asymptotics of Stochastic Gradient Descent with Dropout Regularization in Linear Models [8.555650549124818]
本稿では,線形回帰における勾配勾配勾配(SGD)のオンライン推論とドロップアウト正規化を反復する理論を提案する。
十分に大きなサンプルの場合,ASGDの投棄による信頼区間は,名目カバレッジの確率をほぼ達成している。
論文 参考訳(メタデータ) (2024-09-11T17:28:38Z) - Uncertainty quantification for iterative algorithms in linear models with application to early stopping [4.150180443030652]
本稿では,高次元線形回帰問題における反復アルゴリズムから得られた繰り返し$hbb1,dots,hbbT$について検討する。
解析および提案した推定器は、GD(Gradient Descent)、GD(GD)およびFast Iterative Soft-Thresholding(FISTA)などの加速変種に適用できる。
論文 参考訳(メタデータ) (2024-04-27T10:20:41Z) - Large Stepsize Gradient Descent for Logistic Loss: Non-Monotonicity of the Loss Improves Optimization Efficiency [47.8739414267201]
線形分離可能なデータを用いたロジスティック回帰に一定の段差を持つ勾配降下(GD)を考える。
GD はこの初期振動位相を急速に終了し、$mathcalO(eta)$ steps となり、その後$tildemathcalO (1 / (eta t) )$ convergence rate が得られることを示す。
我々の結果は、予算が$T$ ステップであれば、GD は攻撃的なステップサイズで $tildemathcalO (1/T2)$ の加速損失を達成できることを示している。
論文 参考訳(メタデータ) (2024-02-24T23:10:28Z) - SIMPLE: A Gradient Estimator for $k$-Subset Sampling [42.38652558807518]
この作業では、フォワードパスの離散$k$-subsetサンプリングに戻ります。
勾配推定器 SIMPLE は, 最先端推定器と比較して, バイアスやばらつきが低いことを示す。
実験結果から,線形回帰を説明・スパースする学習性能が向上した。
論文 参考訳(メタデータ) (2022-10-04T22:33:16Z) - Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
我々は、勾配降下(SGD)による頑健な回帰を解くためのデータ構造を導入する。
我々のアルゴリズムは、サブ線形空間を使用し、データに1回パスするだけで、SGDの$T$ステップを重要サンプリングで効果的に実行します。
論文 参考訳(メタデータ) (2022-07-16T03:09:30Z) - MSTGD:A Memory Stochastic sTratified Gradient Descent Method with an
Exponential Convergence Rate [0.0]
本稿では,指数収束率を持つ新しいアンダーラインメモリStochastic sunderlineTratified Gradient Descend(underlineMSTGD)アルゴリズムを設計する。
特に、MSTGDは2つの分散還元戦略を用いており、第1の戦略は、使用履歴勾配の比例pに応じて分散還元を行うことである。
指数収束率を達成すると主張する他のほとんどのアルゴリズムとは異なり、収束率はデータセットサイズN、バッチサイズnなどのパラメータとは独立である。
論文 参考訳(メタデータ) (2022-02-21T01:36:26Z) - Heavy-tailed Streaming Statistical Estimation [58.70341336199497]
ストリーミング$p$のサンプルから重み付き統計推定の課題を考察する。
そこで我々は,傾きの雑音に対して,よりニュアンスな条件下での傾きの傾きの低下を設計し,より詳細な解析を行う。
論文 参考訳(メタデータ) (2021-08-25T21:30:27Z) - A Variance Controlled Stochastic Method with Biased Estimation for
Faster Non-convex Optimization [0.0]
減少勾配(SVRG)の性能を向上させるために, 分散制御勾配(VCSG)という新しい手法を提案する。
ラムダ$はVCSGで導入され、SVRGによる分散の過剰還元を避ける。
$mathcalO(min1/epsilon3/2,n1/4/epsilon)$ 勾配評価の数。
論文 参考訳(メタデータ) (2021-02-19T12:22:56Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳(メタデータ) (2020-10-19T15:23:18Z) - Private Stochastic Non-Convex Optimization: Adaptive Algorithms and
Tighter Generalization Bounds [72.63031036770425]
有界非次元最適化のための差分プライベート(DP)アルゴリズムを提案する。
標準勾配法に対する経験的優位性について,2つの一般的なディープラーニング手法を実証する。
論文 参考訳(メタデータ) (2020-06-24T06:01:24Z) - Carath\'eodory Sampling for Stochastic Gradient Descent [79.55586575988292]
本稿では,Tchakaloff と Carath'eodory の古典的な結果から着想を得た手法を提案する。
我々は、測定値の低減を行う降下ステップを適応的に選択する。
これをBlock Coordinate Descentと組み合わせることで、測定の削減を極めて安価に行えるようにします。
論文 参考訳(メタデータ) (2020-06-02T17:52:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。