論文の概要: Online Covariance Estimation in Nonsmooth Stochastic Approximation
- arxiv url: http://arxiv.org/abs/2502.05305v1
- Date: Fri, 07 Feb 2025 20:16:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-11 14:34:05.244835
- Title: Online Covariance Estimation in Nonsmooth Stochastic Approximation
- Title(参考訳): 非平滑確率近似におけるオンライン共分散推定
- Authors: Liwei Jiang, Abhishek Roy, Krishna Balasubramanian, Damek Davis, Dmitriy Drusvyatskiy, Sen Na,
- Abstract要約: 非滑らかな変分包含問題を解くために近似法(SA)を適用することを検討する。
我々の収束構造は、統計的推定法で最もよく知られているものを確立する。
- 参考スコア(独自算出の注目度): 14.818683408659764
- License:
- Abstract: We consider applying stochastic approximation (SA) methods to solve nonsmooth variational inclusion problems. Existing studies have shown that the averaged iterates of SA methods exhibit asymptotic normality, with an optimal limiting covariance matrix in the local minimax sense of H\'ajek and Le Cam. However, no methods have been proposed to estimate this covariance matrix in a nonsmooth and potentially non-monotone (nonconvex) setting. In this paper, we study an online batch-means covariance matrix estimator introduced in Zhu et al.(2023). The estimator groups the SA iterates appropriately and computes the sample covariance among batches as an estimate of the limiting covariance. Its construction does not require prior knowledge of the total sample size, and updates can be performed recursively as new data arrives. We establish that, as long as the batch size sequence is properly specified (depending on the stepsize sequence), the estimator achieves a convergence rate of order $O(\sqrt{d}n^{-1/8+\varepsilon})$ for any $\varepsilon>0$, where $d$ and $n$ denote the problem dimensionality and the number of iterations (or samples) used. Although the problem is nonsmooth and potentially non-monotone (nonconvex), our convergence rate matches the best-known rate for covariance estimation methods using only first-order information in smooth and strongly-convex settings. The consistency of this covariance estimator enables asymptotically valid statistical inference, including constructing confidence intervals and performing hypothesis testing.
- Abstract(参考訳): 非滑らかな変分包含問題を解くために確率近似法(SA)を適用することを検討する。
既存の研究では、SA法の平均的な反復は漸近正規性を示し、H'ajek と Le Cam の局所ミニマックス感覚における最適制限共分散行列が示されている。
しかしながら、この共分散行列を非滑らかで潜在的に非単調な(非凸)環境で推定する方法は提案されていない。
本稿では,Zhu et al (2023)で導入されたオンラインバッチ平均共分散行列推定器について検討する。
推定器は、SAが適切に反復し、バッチ間のサンプル共分散を制限共分散の推定として計算する。
全体のサンプルサイズに関する事前の知識は必要とせず、新しいデータが到着すると更新を再帰的に行うことができる。
バッチサイズシーケンスが適切に指定されている限り(ステップサイズシーケンスに依存する)、推定器は、任意の$\varepsilon>0$に対して$O(\sqrt{d}n^{-1/8+\varepsilon})$の収束率を達成する。
問題は非滑らかかつ潜在的にモノトーン(非凸)であるが、この収束率は、滑らかで強凸な設定における一階情報のみを用いた共分散推定法において、最もよく知られた速度と一致する。
この共分散推定器の一貫性は、信頼区間の構築や仮説テストの実行を含む漸近的に有効な統計的推測を可能にする。
関連論文リスト
- Towards Self-Supervised Covariance Estimation in Deep Heteroscedastic Regression [102.24287051757469]
深部異方性回帰における自己教師付き共分散推定について検討する。
正規分布の間の2-ワッサーシュタイン距離の上界を導出する。
幅広い合成データセットと実データセットに対する実験により、提案された2-ワッサーシュタインと擬似ラベルアノテーションが結合した結果、計算的に安価で正確な深部ヘテロ代用回帰が導かれることが示された。
論文 参考訳(メタデータ) (2025-02-14T22:37:11Z) - Multivariate root-n-consistent smoothing parameter free matching estimators and estimators of inverse density weighted expectations [51.000851088730684]
我々は、パラメトリックな$sqrt n $-rateで収束する、最も近い隣人の新しい修正とマッチング推定器を開発する。
我々は,非パラメトリック関数推定器は含まないこと,特に標本サイズ依存パラメータの平滑化には依存していないことを強調する。
論文 参考訳(メタデータ) (2024-07-11T13:28:34Z) - Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。
複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。
本稿では,ZPDVR法とZPDVR法を提案する。
論文 参考訳(メタデータ) (2024-05-28T02:27:53Z) - Nearest Neighbor Sampling for Covariate Shift Adaptation [7.940293148084844]
重みを推定しない新しい共変量シフト適応法を提案する。
基本的な考え方は、ソースデータセットの$k$-nearestの隣人によってラベル付けされたラベル付けされていないターゲットデータを直接扱うことだ。
実験の結果, 走行時間を大幅に短縮できることがわかった。
論文 参考訳(メタデータ) (2023-12-15T17:28:09Z) - TIC-TAC: A Framework for Improved Covariance Estimation in Deep Heteroscedastic Regression [109.69084997173196]
奥行き回帰は、予測分布の平均と共分散を負の対数類似度を用いて共同最適化する。
近年の研究では, 共分散推定に伴う課題により, 準最適収束が生じる可能性が示唆されている。
1)予測共分散は予測平均のランダム性を真に捉えているか?
その結果, TICは共分散を正確に学習するだけでなく, 負の対数類似性の収束性の向上も促進することがわかった。
論文 参考訳(メタデータ) (2023-10-29T09:54:03Z) - Covariance Estimators for the ROOT-SGD Algorithm in Online Learning [7.00422423634143]
ROOT-SGDのアルゴリズム共分散に対する2つの推定器を開発した。
最初の推定器はプラグインの考え方を採用し, 共分散公式の未知の要素ごとに, 経験的手法で置き換える。
2つ目の推定器は、制限を克服するヘッセン自由推定器である。
論文 参考訳(メタデータ) (2022-12-02T15:55:52Z) - A lower confidence sequence for the changing mean of non-negative right
heavy-tailed observations with bounded mean [9.289846887298854]
信頼シーケンスは、時間パラメトリックカバレッジ保証付き予測可能なパラメータシーケンスに対する適応されたセット列を生成する。
この研究は、スラックが0に収束するランニング平均条件付き期待値に対して、漸近的でない低CSを構成する。
論文 参考訳(メタデータ) (2022-10-20T09:50:05Z) - Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
制約付き非線形最適化問題のオンライン統計的推測を考察する。
これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - Near-optimal inference in adaptive linear regression [60.08422051718195]
最小二乗法のような単純な方法でさえ、データが適応的に収集されるときの非正規な振る舞いを示すことができる。
我々は,これらの分布異常を少なくとも2乗推定で補正するオンラインデバイアス推定器のファミリーを提案する。
我々は,マルチアームバンディット,自己回帰時系列推定,探索による能動的学習などの応用を通して,我々の理論の有用性を実証する。
論文 参考訳(メタデータ) (2021-07-05T21:05:11Z) - On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and
Non-Asymptotic Concentration [115.1954841020189]
The inequality and non-asymptotic properties of approximation procedure with Polyak-Ruppert averaging。
一定のステップサイズと無限大となる反復数を持つ平均的反復数に対する中心極限定理(CLT)を証明する。
論文 参考訳(メタデータ) (2020-04-09T17:54:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。