論文の概要: Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation
- arxiv url: http://arxiv.org/abs/2610.24890v1
- Date: Sat, 17 Oct 2026 22:12:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-22 15:33:48.705756
- Title: Query-Dependent Reading for Quantized Inner-Product Estimation: A Minimax Separation
- Title（参考訳）: 内部積推定のためのクエリ依存読み出し:ミニマックス分離
- Abstract要約: 記憶と読書の予算が異なる場合の内積推定の定量化について検討する。
性能は、プロトコルのランダム性よりも平均された$x,y$以上の最悪の平均2乗誤差の$d$で測定される。
- 参考スコア（独自算出の注目度）: 13.325950960279322
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study quantization for inner-product estimation when storage and reading have separate budgets. In the static bit-probe model [Yao, 1981], an encoder stores $w$ bits about $x$ before seeing a query $y$, and a reader probes at most $r<w$ bits to estimate $x^\top y$. Both vectors lie in the $d$-dimensional Euclidean unit ball. Protocols may be randomized, and computation is unrestricted. Performance is measured by $d$ times the worst-case mean-squared error over $x,y$, averaged over protocol randomness. First, we show that query-independent reading cannot benefit from extra storage. Any such reader is equivalent to fully reading an $r$-bit message, even when later reads depend on previously returned bits. At fixed positive rates $W=w/d$ and $R=r/d$, the normalized minimax error converges to $1/(4^R-1)$, independent of $W$. The upper bound was already known [Ordentlich and Polyanskiy, 2025]. We prove the matching lower bound for arbitrary scalar decoders, extending the result for unbiased compressors [Safaryan et al., 2020]. Then, we show that query-dependent reading makes extra storage useful. We construct a two-batch protocol using Gaussian projections and random thresholds, with asymptotic normalized error at most $(π+o(1))/[4R\log(W/R)]$ as $W/R\to\infty$. At fixed $R$, this error vanishes as storage grows, giving an unbounded advantage over query-independent reading. We also prove a finite-dimensional lower bound for arbitrary encoders, decoders, and fully branching readers. In the doubly sparse regime $W/R\to\infty$ and $R\log(W/R)\to0$, it gives normalized error at least $(1-o(1))/[2R\log(W/R)]$. Thus, our protocol is optimal within a factor of $π/2$ in the leading constant.
- Abstract（参考訳）: 記憶と読書の予算が異なる場合の内積推定の定量化について検討する。
静的ビットプローブモデル [Yao, 1981] では、エンコーダはクエリー$y$を見る前に$w$約$x$を格納し、リーダーは最大$r<w$ bitsで$x^\top y$を推定する。
どちらのベクトルも$d$次元ユークリッド単位球に含まれる。
プロトコルはランダム化され、計算は制限されない。
性能は、プロトコルのランダム性よりも平均された$x,y$以上の最悪の平均2乗誤差の$d$で測定される。
まず、クエリ非依存の読み出しは、余分なストレージの恩恵を受けないことを示す。
そのような読み手は、後に返されたビットに依存する場合であっても、$r$-bitメッセージを完全に読み取るのと同じである。
固定正率$W=w/d$と$R=r/d$では、正規化されたミニマックス誤差は$W$とは独立に$/(4^R-1)$に収束する。
上部の境界は既に知られていた[Ordentlich and Polyanskiy, 2025]。
任意のスカラーデコーダの一致した下界を証明し、非バイアス圧縮機 [Safaryan et al , 2020] の結果を拡張した。
そして、クエリ依存の読み出しにより、余分なストレージが有用であることを示す。
ガウス射影とランダムしきい値を用いて2バッチプロトコルを構築し、漸近正規化誤差を最大$(π+o(1))/[4R\log(W/R)]$ as $W/R\to\infty$とする。
固定の$R$で、ストレージが増加するにつれてこのエラーは消え、クエリ非依存の読み込みに対して非バウンドな優位性を与える。
また、任意のエンコーダ、デコーダ、完全に分岐する読者に対して有限次元の下界を証明する。
二重スパース状態の$W/R\to\infty$と$R\log(W/R)\to0$では、正規化誤差が少なくとも$(1-o(1))/[2R\log(W/R)]$を与える。
したがって、このプロトコルは先頭定数において$π/2$の係数で最適である。
関連論文リスト
- Mutual Information Constrained Chernoff Bottleneck [10.026496861838448]
我々は、このチャーノフ情報を最大化するエンコーダを求める、相互に制約されたチャーノフボトルネックについて検討する。
最適値 $C(R)$ は、$R = H(V)$ まで厳密に増加し、$V$ は$X$ の記号を等等比でマージする。
一般化されたブラフト-アリモトアルゴリズムと非線形方程式によるチェルノフパラメータ$s$を用いてエンコーダを更新する交互アルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-09-29T16:53:00Z) - Ordered-Angle Coding for Exact Multiuser Unanimity Testing [0.0]
我々は、シリアル量子アーキテクチャにおいて、$n$変換のみのユーザ間でバイナリユニニミティテストのための順序角符号化を導入する。
加法的代数にはベルの絡み合いは必要ないが、すべての正直な試行において、旅行者は局所的に極大に混合される。
論文 参考訳（メタデータ） (2026-09-04T18:28:01Z) - 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) - High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。
我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
論文 参考訳（メタデータ） (2026-02-01T17:05:31Z) - Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
この仮定は、収束とより微細な結果には必要ないことが初めて示される。
標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。
数値実験の結果,乗法雑音とマルコフ記憶の組み合わせにより,$beta_theta$が大きくなる可能性が示唆された。
論文 参考訳（メタデータ） (2024-05-28T05:11:05Z) - Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
本稿では,プライバシのシャッフルモデルにおけるプライベートベクトル平均推定の問題について検討する。
我々は,$tildemathcalOleft(min(nvarepsilon2,d)right)$ message per users を用いて,最適なエラーを実現する新しいマルチメッセージプロトコルを提案する。
論文 参考訳（メタデータ） (2024-04-16T00:56:36Z) - Robust Testing in High-Dimensional Sparse Models [0.0]
2つの異なる観測モデルの下で高次元スパース信号ベクトルのノルムを頑健にテストする問題を考察する。
回帰係数のノルムを確実に検定するアルゴリズムは、少なくとも$n=Omegaleft(min(slog d,1/gamma4)right)サンプルを必要とする。
論文 参考訳（メタデータ） (2022-05-16T07:47:22Z) - Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。
任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
論文 参考訳（メタデータ） (2022-01-24T17:33:19Z) - Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。
規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
論文 参考訳（メタデータ） (2021-05-31T16:10:49Z) - On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。
目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
論文 参考訳（メタデータ） (2020-09-21T04:13:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。