論文の概要: Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation
- arxiv url: http://arxiv.org/abs/2609.27860v1
- Date: Thu, 20 Aug 2026 07:29:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-28 05:09:55.995877
- Title: Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation
- Title（参考訳）: Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation
- Abstract要約: ポイントワイズな1ビット圧縮機は、1ビットを送信しながら期待する全ての実際の入力を再構成する。
我々は、$mathbb R$でバイアスのないすべての公開コイン1ビット符号に対して、ソース平均再構成の2番目のモーメントが$m2+mathcal J(P)2$であることを証明する。
- 参考スコア（独自算出の注目度）: 7.764443932311498
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A pointwise-unbiased one-bit compressor reconstructs every real input in expectation while transmitting one bit. For a scalar source $P$ with CDF $F$, mean $m$, and $\mathcal J(P)=\int_{\mathbb R}\sqrt{F(r)(1-F(r))}\,dr$, we prove that the infimum of the source-averaged reconstruction second moment over all public-coin one-bit codes unbiased on $\mathbb R$ is $m^2+\mathcal J(P)^2$. For regular full-support sources, a distribution-centered random-threshold code attains this value; a converse over arbitrary randomized binary encoders and an equality analysis characterize every attaining code up to null sets, bit relabeling, and public-seed refinement. For the Gaussian location family $\mathcal N(μ,σ^2)$ with $|μ|\le cσ$, the equal prior on the endpoint means is least favorable and the minimax value is $σ^2Λ_c^2$. Exact Gaussian minimax optimality forces a critical heavy tail: at the endpoint means, absolute moments are finite exactly for $p<3$, and $\Pr(W>t)=Θ(t^{-3}/\sqrt{\log t})$. A Cauchy-mixture robustification inflates the second moment by at most $1/(1-η)$ while making every positive-order absolute moment finite. Finite-support public randomness with finite decoder means cannot achieve exact unbiasedness on $\mathbb R$, but a bounded-output approximation using exactly $R$ shared random bits has explicit bias and second-moment bounds converging to the minimax constant. Finally, coordinate allocation communicates exactly $B$ bits per Gaussian-gradient query. On Kim's continuous quadratic hard family, the expected optimization guarantee matches the lower bound in its dependence on $(σ,d,B,\varepsilon)$, and a finite-variance high-probability bound incurs only a logarithmic confidence factor.
- Abstract（参考訳）: ポイントワイズな1ビット圧縮機は、1ビットを送信しながら期待する全ての実際の入力を再構成する。
CDF $F$, mean $m$, and $\mathcal J(P)=\int_{\mathbb R}\sqrt{F(r)(1-F(r))}\,dr$ の場合、$\mathbb R$は$m^2+\mathcal J(P)^2$である。
任意のランダム化されたバイナリエンコーダを逆転する分布中心のランダムスレッショルドコードと等式解析は、すべての到達したコードをヌルセット、ビットレバーベリング、パブリックシードの精細化まで特徴付ける。
ガウス的位置族 $\mathcal N(μ,σ^2)$ と $|μ|\le cσ$ に対して、終点上の等式は最優先であり、ミニマックス値は $σ^2\_c^2$ である。
終点平均において絶対モーメントはちょうど$p<3$と$\Pr(W>t)=\(t^{-3}/\sqrt{\log t})$に対して有限である。
コーシー混合の強固化は、任意の正の次数の絶対モーメントを有限にしながら、少なくとも1/(1-η)$で第二モーメントを膨らませる。
有限デコーダによる有限支持な公開ランダム性は、$\mathbb R$ の正確な非バイアス性を達成することはできないが、正確な$R$共有ランダムビットを用いた有界出力近似は、極小定数に収束する第二モーメント境界を持つ。
最後に、座標割り当てはガウス階調クエリ毎に正確に$B$bitsの通信を行う。
キムの連続二次ハードファミリーでは、期待される最適化保証は、$(σ,d,B,\varepsilon)$への依存の低い境界と一致する。
関連論文リスト
- Tight Sampling Complexity with stochastic gradient oracles in Fixed Dimensions [5.603202398374589]
ポテンシャルは$$-strongly convexと$L$-smoothであり、原点に関する半径$-1/2$の球に未知のモードがある。
Nstar_textTV=!left(log(1+)+ frac2right), ] $:=frac L$は条件数である。
論文 参考訳（メタデータ） (2026-09-11T08:44:06Z) - Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs [0.0]
非空コンパクト集合 $mathcal X の部分集合 Rd$ 上で、決定論的目的関数 $f$ を最小化するための期待された改善 (EI) ポリシーについて検討する。
論文 参考訳（メタデータ） (2026-07-31T10:18:54Z) - Solving Stochastic Fixed-Point Equations with High Probability [22.376855234542813]
オラクルの不動点方程式 $mathbfT(mathbfx) = mathbfx$ をノルム空間上で研究する。
本稿では,2次スムーズなバナッハ空間に対する分散還元段階Halpern法であるVR-GHALを紹介する。
論文 参考訳（メタデータ） (2026-07-10T04:59:20Z) - Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
論文 参考訳（メタデータ） (2025-06-30T13:27:39Z) - Nonparametric MLE for Gaussian Location Mixtures: Certified Computation and Generic Behavior [28.71736321665378]
一次元のガウス的位置混合に対する非パラメトリック最大度推定器$widehatpi$について検討する。
We provide a algorithm that for small enough $varepsilon>0$ computes a $varepsilon$-approximation of $widehatpi in Wasserstein distance。
また、$k$-atomicと条件付けられた$widehatpi$の分布は、関連する2k-1$次元パラメータ空間上の密度を許容することを示す。
論文 参考訳（メタデータ） (2025-03-26T03:36:36Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - 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) - AI without networks [0.0]
我々は、生成モデリングを取り入れたAIのためのネットワークフリーフレームワークを開発する。
我々は、この枠組みを、民族学、制御理論、数学の3つの異なる分野の例で示す。
また、生成AIによる倫理的法的課題に対処するために、この枠組みに基づいて容易に計算された信用割当手法を提案する。
論文 参考訳（メタデータ） (2021-06-07T05:50:02Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。