論文の概要: SGD with Dependent Data: Optimal Estimation, Regret, and Inference

• arxiv url: http://arxiv.org/abs/2601.01371v1
• Date: Sun, 04 Jan 2026 04:52:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-06 16:25:22.261441
• Title: SGD with Dependent Data: Optimal Estimation, Regret, and Inference
• Title（参考訳）: 依存データを用いたSGD:最適推定、レグレト、推論
• Authors: Yinan Shen, Yichen Zhang, Wen-Xin Zhou,
• Abstract要約: 勾配降下 (SGD) は, 広範囲の段階的スケジュールと探索率スキームの下で, 独立情報と依存情報の両方に対応できることが示されている。 SGDは統計的に最適な推定誤差と後悔を同時に達成し,既存の結果を拡張し,改善することを示す。 オンラインのスパースレグレッションのために、我々はSGDベースの新しいアルゴリズムを開発し、ストレージの$d$のみを使用し、1イテレーションあたり$O(d)$フロップを必要とする。
• 参考スコア（独自算出の注目度）: 3.038061705362137
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work investigates the performance of the final iterate produced by stochastic gradient descent (SGD) under temporally dependent data. We consider two complementary sources of dependence: $(i)$ martingale-type dependence in both the covariate and noise processes, which accommodates non-stationary and non-mixing time series data, and $(ii)$ dependence induced by sequential decision making. Our formulation runs in parallel with classical notions of (local) stationarity and strong mixing, while neither framework fully subsumes the other. Remarkably, SGD is shown to automatically accommodate both independent and dependent information under a broad class of stepsize schedules and exploration rate schemes. Non-asymptotically, we show that SGD simultaneously achieves statistically optimal estimation error and regret, extending and improving existing results. In particular, our tail bounds remain sharp even for potentially infinite horizon $T=+\infty$. Asymptotically, the SGD iterates converge to a Gaussian distribution with only an $O_{\PP}(1/\sqrt{t})$ remainder, demonstrating that the supposed estimation-regret trade-off claimed in prior work can in fact be avoided. We further propose a new ``conic'' approximation of the decision region that allows the covariates to have unbounded support. For online sparse regression, we develop a new SGD-based algorithm that uses only $d$ units of storage and requires $O(d)$ flops per iteration, achieving the long term statistical optimality. Intuitively, each incoming observation contributes to estimation accuracy, while aggregated summary statistics guide support recovery.
• Abstract（参考訳）: 本研究は,確率勾配降下(SGD)によって生成される最終イテレーションの時間依存データによる性能について検討する。 私たちは2つの相補的な依存源を考えます。 (i)非定常および非混合時系列データに対応する共変量および雑音過程におけるマーチンゲール型依存性$$$ (ii)シーケンシャルな意思決定によって引き起こされる従属 我々の定式化は古典的な(局所的な)定常性と強い混合の概念と平行して行われるが、どちらのフレームワークも他方を完全に仮定しない。 注目すべきは、SGDは、広範囲の段階的なスケジュールと探索率スキームの下で、独立情報と依存情報の両方を自動で適合させることである。 非漸近的に、SGDは統計的に最適な推定誤差と後悔を同時に達成し、既存の結果を拡張し改善することを示した。 特に、我々のテール境界は、潜在的に無限の地平線$T=+\infty$に対しても鋭いままである。 漸近的に、SGDイテレートは$O_{\PP}(1/\sqrt{t})$剰余でガウス分布に収束し、前処理で主張される推定-回帰トレードオフが実際には避けられることを示す。 さらに,共変数が非有界な支持を得られるような「コニック」決定領域の近似を新たに提案する。 オンラインスパースレグレッションにおいて,SGD ベースの新しいアルゴリズムを開発した。これはストレージの$d$のみを使用し,反復毎に$O(d)$フロップを要し,長期の統計的最適性を実現する。 直感的には、各観測結果は推定精度に寄与し、集計された要約統計は回復を支援する。

関連論文リスト

• Stopping Rules for Stochastic Gradient Descent via Anytime-Valid Confidence Sequences [51.56484100374058]
  凸最適化のための勾配降下(SGD)の停止規則について検討した。 我々は、投影されたSGDの重み付き平均準最適度に対して、任意の有意、データ依存の高信頼シーケンスを開発する。 これらは、厳格でタイムユニフォームなパフォーマンス保証と、有限時間$varepsilon$-optimality証明書である。
  論文  参考訳（メタデータ） (2025-12-15T09:26:45Z)
• Finite-Time Bounds for Distributionally Robust TD Learning with Linear Function Approximation [5.638124543342179]
  線形関数近似を用いた最初の頑健な時間差学習を提案する。 我々の結果は、ロバストなRLアルゴリズムの実証的な成功と、ロバストでないアルゴリズムが享受する漸近的保証との間に重要なギャップを埋める。
  論文  参考訳（メタデータ） (2025-10-02T07:01:41Z)
• Distributed Stochastic Gradient Descent with Staleness: A Stochastic Delay Differential Equation Based Framework [56.82432591933544]
  分散勾配降下(SGD)は、計算リソースのスケーリング、トレーニング時間の短縮、マシンラーニングにおけるユーザのプライバシ保護の支援などにより、近年注目されている。 本稿では,遅延微分方程式(SDDE)と勾配到着の近似に基づく分散SGDの実行時間と安定化について述べる。 活性化作業員の増加は, 安定度による分散SGDを必ずしも加速させるものではないことが興味深い。
  論文  参考訳（メタデータ） (2024-06-17T02:56:55Z)
• Demystifying SGD with Doubly Stochastic Gradients [13.033133586372612]
  一般条件下では、独立なミニバッチとランダムリシャッフルを併用した2重SGDの収束特性を確立する。 ランダムリシャッフルによりサブサンプリングノイズの複雑性依存性が向上することが証明された。
  論文  参考訳（メタデータ） (2024-06-03T01:13:19Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。 解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
  論文  参考訳（メタデータ） (2023-10-28T18:53:41Z)
• Online covariance estimation for stochastic gradient descent under Markovian sampling [20.02012768403544]
  位数$Obig(sqrtd,n-1/8(log n)1/4big)$の収束率は、状態依存および状態依存マルコフサンプリングの下で確立される。 本手法はロジスティック回帰を用いた戦略分類に適用され, 学習中の特徴を適応的に修正し, 対象クラス分類に影響を与える。
  論文  参考訳（メタデータ） (2023-08-03T00:21:30Z)
• Retire: Robust Expectile Regression in High Dimensions [3.9391041278203978]
  ペナル化量子化法と期待回帰法は、高次元データの異方性検出に有用な手段を提供する。 我々は,頑健な期待回帰(退職)を提案し,研究する。 提案手法は半平滑なニュートン座標降下アルゴリズムにより効率よく解けることを示す。
  論文  参考訳（メタデータ） (2022-12-11T18:03:12Z)

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

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