論文の概要: High-dimensional Central Limit Theorems for Linear Functionals of Online
Least-Squares SGD
- arxiv url: http://arxiv.org/abs/2302.09727v1
- Date: Mon, 20 Feb 2023 02:38:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-21 16:55:46.969215
- Title: High-dimensional Central Limit Theorems for Linear Functionals of Online
Least-Squares SGD
- Title(参考訳): オンライン最小二乗SGDの線形関数に対する高次元中心極限定理
- Authors: Bhavya Agrawalla, Krishnakumar Balasubramanian, Promit Ghosal
- Abstract要約: 勾配降下 (SGD) は、データ科学者のツールボックスにおいて重要な方法として登場した。
オンライン最小二乗SGDの線形汎関数に対する高次元中央極限定理(CLT)を確立する。
本研究の主な成果は,オンラインSGDの反復回数において次元が指数関数的に指数関数である場合でも,CLTは成り立つことを示す。
- 参考スコア(独自算出の注目度): 8.658596218544774
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Stochastic gradient descent (SGD) has emerged as the quintessential method in
a data scientist's toolbox. Much progress has been made in the last two decades
toward understanding the iteration complexity of SGD (in expectation and
high-probability) in the learning theory and optimization literature. However,
using SGD for high-stakes applications requires careful quantification of the
associated uncertainty. Toward that end, in this work, we establish
high-dimensional Central Limit Theorems (CLTs) for linear functionals of online
least-squares SGD iterates under a Gaussian design assumption. Our main result
shows that a CLT holds even when the dimensionality is of order exponential in
the number of iterations of the online SGD, thereby enabling high-dimensional
inference with online SGD. Our proof technique involves leveraging Berry-Esseen
bounds developed for martingale difference sequences and carefully evaluating
the required moment and quadratic variation terms through recent advances in
concentration inequalities for product random matrices. We also provide an
online approach for estimating the variance appearing in the CLT (required for
constructing confidence intervals in practice) and establish consistency
results in the high-dimensional setting.
- Abstract(参考訳): 確率的勾配降下(sgd)は、データサイエンティストのツールボックスにおいて重要な手法である。
学習理論と最適化文学におけるSGDの反復複雑性(期待と高い確率)を理解するために、過去20年間に多くの進歩がなされてきた。
しかし、sgdを高スループットアプリケーションに適用するには、関連する不確かさを慎重に定量化する必要がある。
そこで本研究では,オンライン最小二乗 SGD の線型汎関数に対する高次元中心極限定理(CLT)をガウス的設計仮定の下で反復する。
本研究の主目的は,オンラインSGDの反復回数において次元が指数関数的に指数関数である場合でもCLTは成り立ち,オンラインSGDによる高次元推論を可能にすることである。
本手法は,マルティンゲール差分列用に開発されたベリー・エスセン境界を活用し,製品乱数行列に対する最近の濃度不等式の発展を通じて,必要なモーメントと二次変動項を注意深く評価するものである。
また,clt(実際に信頼区間を構築するために要求される)に現れる分散を推定し,高次元設定における一貫性を確立するためのオンライン手法を提案する。
関連論文リスト
- High-probability Convergence Bounds for Nonlinear Stochastic Gradient
Descent Under Heavy-tailed Noise [62.227421825689895]
本研究では, 広帯域非線形SGD法における収束境界テクスタイチン高確率について検討する。
リプシッツ連続勾配の強い凸損失関数に対して、ノイズが重く抑えられた場合でも、故障確率に対数依存があることを証明する。
論文 参考訳(メタデータ) (2023-10-28T18:53:41Z) - Resampling Stochastic Gradient Descent Cheaply for Efficient Uncertainty
Quantification [6.832893024035705]
本稿では,SGDソリューションの信頼性区間を構築するために,計算的に安価に再サンプリングする2つの手法について検討する。
データのリサンプリングと置換によって複数のSGDを並行して使用するものもあれば、オンライン形式で運用するものもある。
論文 参考訳(メタデータ) (2023-10-17T08:18:10Z) - Implicit Bias of Gradient Descent for Logistic Regression at the Edge of
Stability [69.01076284478151]
機械学習の最適化において、勾配降下(GD)はしばしば安定性の端(EoS)で動く
本稿では,EoS系における線形分離可能なデータに対するロジスティック回帰のための定数段差GDの収束と暗黙バイアスについて検討する。
論文 参考訳(メタデータ) (2023-05-19T16:24:47Z) - SketchySGD: Reliable Stochastic Optimization via Randomized Curvature
Estimates [19.420605210427635]
SketchySGDは、サブサンプルヘッセンに対するランダム化低ランク近似を用いることで、機械学習の既存の勾配法を改善する。
固定段数を持つSketchySGDが最適の周りの小さな球に線形に収束することを理論的に示す。
条件のない設定では、最小二乗問題に対してSketchySGDはSGDよりも高速に収束することを示す。
論文 参考訳(メタデータ) (2022-11-16T01:05:41Z) - From Gradient Flow on Population Loss to Learning with Stochastic
Gradient Descent [50.4531316289086]
SGD(Gradient Descent)は、大規模非ルートモデルの学習方法である。
集団損失のGFが収束すると仮定して、総合的な条件 SGD が収束する。
我々は、凸損失のような古典的な設定だけでなく、Retrieval Matrix sq-rootのようなより複雑な問題に対してもGD/SGDを統一的に解析する。
論文 参考訳(メタデータ) (2022-10-13T03:55:04Z) - Fast and Robust Online Inference with Stochastic Gradient Descent via
Random Scaling [0.9806910643086042]
本稿では,勾配降下アルゴリズムの平均化法により推定されるパラメータのベクトルに対するオンライン推論法を提案する。
我々のアプローチはオンラインデータで完全に運用されており、機能中心極限定理によって厳格に支えられている。
論文 参考訳(メタデータ) (2021-06-06T15:38:37Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳(メタデータ) (2021-03-23T17:15:53Z) - Direction Matters: On the Implicit Bias of Stochastic Gradient Descent
with Moderate Learning Rate [105.62979485062756]
本稿では,中等度学習におけるSGDの特定の正規化効果を特徴付けることを試みる。
SGDはデータ行列の大きな固有値方向に沿って収束し、GDは小さな固有値方向に沿って収束することを示す。
論文 参考訳(メタデータ) (2020-11-04T21:07:52Z) - Understanding Gradient Clipping in Private SGD: A Geometric Perspective [68.61254575987013]
ディープラーニングモデルは、トレーニングデータが機密情報を含む可能性がある多くの機械学習アプリケーションで、ますます人気が高まっている。
多くの学習システムは、(異なる)プライベートSGDでモデルをトレーニングすることで、差分プライバシーを取り入れている。
各プライベートSGDアップデートにおける重要なステップは勾配クリッピングであり、L2ノルムがしきい値を超えると、個々の例の勾配を小さくする。
論文 参考訳(メタデータ) (2020-06-27T19:08:12Z) - Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks [27.54155197562196]
勾配降下(SGD)の軌跡は,emphFeller法によりよく近似できることを示す。
このような一般化の成功を測る「容量メートル法」を提案する。
論文 参考訳(メタデータ) (2020-06-16T16:57:12Z) - Online Covariance Matrix Estimation in Stochastic Gradient Descent [10.153224593032677]
勾配降下(SGD)は,特に大規模データセットやオンライン学習においてパラメータ推定に広く用いられている。
本稿では,オンライン環境でのSGDに基づく推定値の統計的推測を定量化することを目的とする。
論文 参考訳(メタデータ) (2020-02-10T17:46:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。