論文の概要: Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD
- arxiv url: http://arxiv.org/abs/2410.20135v1
- Date: Sat, 26 Oct 2024 10:14:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-29 12:17:56.817674
- Title: Near-Optimal Streaming Heavy-Tailed Statistical Estimation with Clipped SGD
- Title（参考訳）: クラップしたSGDを用いた準最適ストリーミング重値統計的推定
- Authors: Aniket Das, Dheeraj Nagaraj, Soumyabrata Pal, Arun Suggala, Prateek Varshney,
- Abstract要約: Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsfTr(Sigma)+sqrtmathsff
- 参考スコア（独自算出の注目度）: 16.019880089338383
- License:
- Abstract: We consider the problem of high-dimensional heavy-tailed statistical estimation in the streaming setting, which is much harder than the traditional batch setting due to memory constraints. We cast this problem as stochastic convex optimization with heavy tailed stochastic gradients, and prove that the widely used Clipped-SGD algorithm attains near-optimal sub-Gaussian statistical rates whenever the second moment of the stochastic gradient noise is finite. More precisely, with $T$ samples, we show that Clipped-SGD, for smooth and strongly convex objectives, achieves an error of $\sqrt{\frac{\mathsf{Tr}(\Sigma)+\sqrt{\mathsf{Tr}(\Sigma)\|\Sigma\|_2}\log(\frac{\log(T)}{\delta})}{T}}$ with probability $1-\delta$, where $\Sigma$ is the covariance of the clipped gradient. Note that the fluctuations (depending on $\frac{1}{\delta}$) are of lower order than the term $\mathsf{Tr}(\Sigma)$. This improves upon the current best rate of $\sqrt{\frac{\mathsf{Tr}(\Sigma)\log(\frac{1}{\delta})}{T}}$ for Clipped-SGD, known only for smooth and strongly convex objectives. Our results also extend to smooth convex and lipschitz convex objectives. Key to our result is a novel iterative refinement strategy for martingale concentration, improving upon the PAC-Bayes approach of Catoni and Giulini.
- Abstract（参考訳）: 本稿では,ストリーミング環境における高次元重み付き統計的推定の問題について考察する。
この問題を,重み付き確率勾配を用いた確率凸最適化とみなし,確率勾配雑音の第2モーメントが有限であるときに,広く用いられるClipped-SGDアルゴリズムが準ガウス確率の準最適統計率を得ることを示した。
より正確には、$T$サンプルを用いてClipped-SGDが滑らかで強凸な目的に対して、$\sqrt {\frac{\mathsf{Tr}(\Sigma)+\sqrt{\mathsf{Tr}(\Sigma)\|\Sigma\|_2}\log(\frac{\log(T)}{\delta})}{T}}$の誤差を、確率1-\delta$で達成することを示す。
ゆらぎ ($\frac{1}{\delta}$) は $\mathsf{Tr}(\Sigma)$ よりも低い順序である。
これにより、現在の最高速度である$\sqrt {\frac{\mathsf{Tr}(\Sigma)\log(\frac{1}{\delta})}{T}}$は、滑らかで凸な目的のためにのみ知られているClipped-SGDに対して改善される。
また,スムーズな凸面およびリプシッツ凸面にも拡張した。
その結果, カトニ, ジュリーニのPAC-Bayesアプローチを改良し, マルティンゲール濃度の反復的改善戦略が得られた。
関連論文リスト
- Mirror Descent Algorithms with Nearly Dimension-Independent Rates for
Differentially-Private Stochastic Saddle-Point Problems [6.431793114484429]
多面体設定における微分プライベートなサドル点の問題を解くために、$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$を提案する。
我々のアルゴリズムは、一定の成功率で$sqrtlog(d)/sqrtn + log(d)/[nvarepsilon]2/5$に達することを示す。
論文 参考訳（メタデータ） (2024-03-05T12:28:00Z) - (Accelerated) Noise-adaptive Stochastic Heavy-Ball Momentum [7.095058159492494]
ヘビーボール運動量(SHB)は、機械学習モデルのトレーニングに一般的に用いられ、勾配降下の反復よりも経験的な改善を提供することが多い。
SHB は小サイズが $kappa の閾値 $b* よりも大きい場合に加速できることを示す。
論文 参考訳（メタデータ） (2024-01-12T18:17:28Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - High Probability Convergence of Stochastic Gradient Methods [15.829413808059124]
最適解への初期距離に依存する有界収束を示す。
AdaGrad-Normのハイバウンドが得られることを示す。
論文 参考訳（メタデータ） (2023-02-28T18:42:11Z) - Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization [40.19608203064051]
本稿では,SEAモデルに対する楽観的オンラインミラー降下(OMD)の理論的保証について検討する。
強い凸と滑らかな関数に対して、$mathcalO(sigma_max2 + Sigma_max2) log T よりも優れた $mathcalO(sigma_max2 + Sigma_max2) log T を確立する。
非定常シナリオにおける静的な後悔境界よりも有利な凸関数と滑らかな関数を持つモデルに対する最初の動的後悔保証を確立する。
論文 参考訳（メタデータ） (2023-02-09T10:42:11Z) - Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。
漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文 参考訳（メタデータ） (2022-06-17T06:10:20Z) - Generalization Bounds for Gradient Methods via Discrete and Continuous
Prior [8.76346911214414]
次数$O(frac1n + fracL2nsum_t=1T(gamma_t/varepsilon_t)2)$の新たな高確率一般化境界を示す。
また、あるSGDの変種に対する新しい境界を得ることもできる。
論文 参考訳（メタデータ） (2022-05-27T07:23:01Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳（メタデータ） (2022-05-23T17:59:18Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - 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) - Tight Regret Bounds for Noisy Optimization of a Brownian Motion [118.65407541895851]
本稿では,1次元ブラウン運動のベイズ最適化の問題点について考察する。
Omega(sigmasqrtT cdot log T)$.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT cdot log T)$.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.sigmasqrtT.
論文 参考訳（メタデータ） (2020-01-25T14:44:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。