論文の概要: The Cost of Working Memory in Streaming Mean Estimation
- arxiv url: http://arxiv.org/abs/2610.39540v1
- Date: Thu, 29 Oct 2026 07:42:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-31 05:25:12.474845
- Title: The Cost of Working Memory in Streaming Mean Estimation
- Title（参考訳）: ストリーミング平均推定における作業記憶のコスト
- Abstract要約: ストリーミング推定器は、メモリに適合するエビデンスから計算しなければならない。
我々は、K$持続状態、既知の地平線、公開時間指数の2乗誤差の下でミニマックスレートを確立する。
一致する構成は、多スケールのモジュラーカウンタと座標群間のワークスペースを組み合わせたものである。
- 参考スコア（独自算出の注目度）: 26.288676265305014
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A streaming estimator must compute from the evidence that fits in memory. We determine when storing an accurate mean is easier than computing it. For Gaussian mean estimation over the Euclidean unit ball in $\mathbb{R}^d$, we establish the minimax rate under squared error with $K$ persistent states, a known horizon, and a public time index: $\min\{1, K^{-2/d}+\frac{d}{n} (1+\frac{\log(ed)}{1+(\log K)/d})\}$. Unrestricted computation followed by $K$-level encoding has rate $\min\{1,d/n+K^{-2/d}\}$. At a fixed sufficiently small error, statistically optimal sample size therefore requires order $d\log d$ working bits, while order $d$ bits suffice to store the answer. The lower bound tracks repeated state compression through an entropy potential obtained by Gaussian smoothing. A matching construction combines a multiscale modular counter with workspace reused across coordinate groups. In one dimension, it attains the terminal rate $n^{-1}+K^{-2}$. Any fixed confidence requirement that the realized loss not exceed the zero baseline preserves these rates. Increasing confidence creates a further memory requirement: at fixed nontrivial risk in every fixed dimension, failure probability $e^{-γn}$ requires and permits order $\log n$ working states for sufficiently small fixed $γ>0$. In the scalar problem, a fixed terminal alphabet suffices under the same protection. These bounds separate the memory needed to represent an answer from the memory needed to accumulate evidence and validate a decision.
- Abstract（参考訳）: ストリーミング推定器は、メモリに適合するエビデンスから計算しなければならない。
正確な平均を保存することは、計算するよりも容易である。
ガウス平均が$\mathbb{R}^d$ のユークリッド単位球上の推定に対して、最小最大値は$K$持続状態、既知の地平線、および公共時間指数:$\min\{1, K^{-2/d}+\frac{d}{n} (1+\frac{\log(ed)}{1+(\log K)/d})\}$ で二乗誤差の下で成立する。
制限のない計算に続いて$K$レベルのエンコーディングは$\min\{1,d/n+K^{-2/d}\}$である。
十分な小さな誤差で、統計的に最適なサンプルサイズでは、その答えを保持するのに$d$ビットをオーダーするのに対して、$d\log d$ワーキングビットを必要とする。
下位境界線はガウス平滑化により得られるエントロピーポテンシャルを通じて繰り返し状態圧縮を行う。
一致する構成は、座標群間で再利用されたワークスペースとマルチスケールのモジュラーカウンタを組み合わせたものである。
一次元では、端末レートが$n^{-1}+K^{-2}$に達する。
実現された損失がゼロベースラインを超えないような固定された信頼要件は、これらのレートを保存する。
すべての固定次元における固定された非自明なリスクにおいて、失敗確率$e^{-γn}$は必要であり、十分に小さな固定された$γ>0$に対して順序$\log n$ワーキングステートを許容する。
スカラー問題では、固定終端アルファベットは同じ保護の下で十分である。
これらの境界は、答えを表すために必要なメモリと、証拠を蓄積し、決定を検証するために必要なメモリを分離する。
関連論文リスト
- Bayesian Fixed-Confidence Best-Arm Identification with Abstention [51.253617466579335]
本研究では,学習者が端末の推薦を控えることができるベイジアン固定自信ベストアーム識別問題について検討する。
目標誤差確率$$および棄権予算$に対して、S&C(Screen-and-Confirm)を提案し、その予測停止時間を分析する。
論文 参考訳（メタデータ） (2026-10-21T19:45:09Z) - Approximation Property of Dropout Neural Networks: Sobolev Rates and Confidence Bounds [1.0152838128195467]
定数深さとサイズ$widetilde O_n,d(p-9varepsilon-maxd/n,2 log (1/)$。
この構成は、有界な局所ワーク、成功した近似事象の局所化、およびマルチスケールのテイラー分解を組み合わせたものである。
論文 参考訳（メタデータ） (2026-09-30T19:19:07Z) - Scalable Minimum-Volume Simplex Estimation with Non-asymptotic Analysis [3.008906408145323]
既存の推定器は、サンプルごとの立方体処理か、または$O(NK)$ストレージを必要とする。
DeepMVSAは神経暗黙の形で最小限の原理を再表現する。
最大$N=108$の合成観測実験は、予測された精度とスケーリングと一致している。
論文 参考訳（メタデータ） (2026-09-22T02:13:14Z) - Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
Lag $j$はスケール$r_j$の予測に影響を与え、$n_T,j=T-j+1$の予測ラウンドに入る。
すべての要約可能なエンベロープに対して、局所化された混合は$cR_T(r)leq C_T(r)$を証明する。
指数関数やエンベロープの場合、有限サンプル条件の下では、トープリッツ・デサインの逆は$cR_T(r)geq c_T(r)$である。
論文 参考訳（メタデータ） (2026-08-27T01:31:46Z) - A Frame-Spread Lower Bound for Quantum Entropy Estimation under Fixed Rank-One Measurements [0.5076419064097734]
固定階数1の独立な結果から,$d$次元量子状態のフォン・ノイマンエントロピーを推定する。
結果は、コピー間で独立して繰り返される固定された測定、適応的および集合的プロトコル、コピー間で共通の再利用プロトコルがカバーされないことを懸念している。
論文 参考訳（メタデータ） (2026-08-25T15:44:26Z) - Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation [7.764443932311498]
ポイントワイズな1ビット圧縮機は、1ビットを送信しながら期待する全ての実際の入力を再構成する。
我々は、$mathbb R$でバイアスのないすべての公開コイン1ビット符号に対して、ソース平均再構成の2番目のモーメントが$m2+mathcal J(P)2$であることを証明する。
論文 参考訳（メタデータ） (2026-08-20T07:29:09Z) - Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
論文 参考訳（メタデータ） (2025-06-30T13:27:39Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。