論文の概要: Statistical Inference for Linear Functionals of Online Least-squares SGD when $t \gtrsim d^{1+δ}$

• arxiv url: http://arxiv.org/abs/2510.19734v1
• Date: Wed, 22 Oct 2025 16:25:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:16.138956
• Title: Statistical Inference for Linear Functionals of Online Least-squares SGD when $t \gtrsim d^{1+δ}$
• Title（参考訳）: オンライン最小二乗SGDの$t \gtrsim d^{1+δ}$における線形関数の統計的推測
• Authors: Bhavya Agrawalla, Krishnakumar Balasubramanian, Promit Ghosal,
• Abstract要約: グラディエント・Descent (SGD) は、現代のデータ科学における基礎的な手法となっている。 本研究では,オンライン最小二乗 SGD の線型汎函数に対して,非漸近的ベリー-エッセイン境界を確立する。
• 参考スコア（独自算出の注目度）: 7.884611719110979
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stochastic Gradient Descent (SGD) has become a cornerstone method in modern data science. However, deploying SGD in high-stakes applications necessitates rigorous quantification of its inherent uncertainty. In this work, we establish \emph{non-asymptotic Berry--Esseen bounds} for linear functionals of online least-squares SGD, thereby providing a Gaussian Central Limit Theorem (CLT) in a \emph{growing-dimensional regime}. Existing approaches to high-dimensional inference for projection parameters, such as~\cite{chang2023inference}, rely on inverting empirical covariance matrices and require at least $t \gtrsim d^{3/2}$ iterations to achieve finite-sample Berry--Esseen guarantees, rendering them computationally expensive and restrictive in the allowable dimensional scaling. In contrast, we show that a CLT holds for SGD iterates when the number of iterations grows as $t \gtrsim d^{1+\delta}$ for any $\delta > 0$, significantly extending the dimensional regime permitted by prior works while improving computational efficiency. The proposed online SGD-based procedure operates in $\mathcal{O}(td)$ time and requires only $\mathcal{O}(d)$ memory, in contrast to the $\mathcal{O}(td^2 + d^3)$ runtime of covariance-inversion methods. To render the theory practically applicable, we further develop an \emph{online variance estimator} for the asymptotic variance appearing in the CLT and establish \emph{high-probability deviation bounds} for this estimator. Collectively, these results yield the first fully online and data-driven framework for constructing confidence intervals for SGD iterates in the near-optimal scaling regime $t \gtrsim d^{1+\delta}$.
• Abstract（参考訳）: Stochastic Gradient Descent (SGD) は、現代のデータ科学における基礎的な手法となっている。 しかし、SGDを高精細なアプリケーションにデプロイするには、その固有の不確実性の厳密な定量化が必要である。 本研究では、オンライン最小二乗空間 SGD の線型汎函数に対して \emph{non-asymsymotic Berry--Esseen bounds} を確立することにより、 \emph{ growing-dimensional regime} におけるガウス中心極限定理(CLT)を提供する。 例えば~\cite{chang2023inference} のような射影パラメータの高次元推論への既存のアプローチは、経験的共分散行列の反転に依存し、有限サンプルベリー-エッシーの保証を達成するために少なくとも$t \gtrsim d^{3/2} の反復を必要とする。 対照的に、CLT は SGD に対して、反復数が $t {\displaystyle \gtrsim d^{1+\delta}$ for any $\delta > 0$ として増加すると反復し、計算効率を向上しながら、先行研究で許容される次元構造を大幅に拡張することを示す。 提案されたオンラインSGDベースのプロシージャは、$\mathcal{O}(td)$ timeで動作し、$\mathcal{O}(td^2 + d^3)$の共分散反転メソッドのランタイムとは対照的に、$\mathcal{O}(d)$ memoryのみを必要とする。 この理論を実際に適用するために、CLTに現れる漸近的分散に対する \emph{online variance estimator} を更に発展させ、この推定器に対して \emph{high-probability deviation bounds} を確立する。 これらの結果は、SGDがほぼ最適なスケーリング体制である $t \gtrsim d^{1+\delta}$ において、SGDの信頼区間を構築するための最初の完全オンラインおよびデータ駆動のフレームワークとなる。

関連論文リスト

• Parameter-free Algorithms for the Stochastically Extended Adversarial Model [59.81852138768642]
  拡張逆数(SEA)モデルの既存のアプローチは、ドメインの直径$D$や損失関数のリプシッツ定数$G$といった問題固有のパラメータの事前知識を必要とする。 パラメータを不要にするためにOptimistic Online Newton Step (OONS) アルゴリズムを利用するパラメータフリー手法を開発した。
  論文  参考訳（メタデータ） (2025-10-06T10:53:37Z)
• Can SGD Handle Heavy-Tailed Noise? [6.111519084375339]
  Gradient Descent (SGD) は大規模最適化のための機械学習プロジェクトであるが、重尾雑音下での理論的挙動は理解されていない。 このような悪条件下でSGDが確実に成功できるかどうかを精査する。
  論文  参考訳（メタデータ） (2025-08-06T20:09:41Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regression [14.521929085104441]
  勾配降下 (SGD) は、データ科学者のツールボックスにおいて重要な方法として登場した。 我々は,オンラインSGDの線形汎関数に対する高次元中心極限定理(CLT)を確立し,非等方的ガウス入力を用いた過度な最小二乗回帰を行う。 我々は,CLTに現れる分散項を推定するオンライン手法を開発し,開発したオンライン推定器の高確率バウンダリを確立する。
  論文  参考訳（メタデータ） (2023-02-20T02:38:36Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime [19.05750582096579]
  基本最小二乗構成におけるノイズレスモデルについて検討する。 最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
  論文  参考訳（メタデータ） (2021-02-05T14:02:20Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• NeCPD: An Online Tensor Decomposition with Optimal Stochastic Gradient Descent [1.0953917735844645]
  マルチウェイオンラインデータに基づく$(N)Nにおける非効率的な問題に対して,NeCPDという新しい効率的な分解アルゴリズムを提案する。 さらに,本手法を構造的データセットを用いた実生活モニタリングの分野に適用する。
  論文  参考訳（メタデータ） (2020-03-18T04:44:05Z)
• Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
  制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。 本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-03-01T17:47:03Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。