論文の概要: KL Before and After Mixing: A Round-Complexity Separation in Parallel Sampling
- arxiv url: http://arxiv.org/abs/2610.13924v1
- Date: Fri, 09 Oct 2026 17:54:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-13 04:06:29.718806
- Title: KL Before and After Mixing: A Round-Complexity Separation in Parallel Sampling
- Title（参考訳）: 混合前後KL:並列サンプリングにおけるラウンド複雑分離
- Abstract要約: ターゲットの$p$と、スケジュールの$U$の出力法である$q_U$に対して、平均的な発散である$mathbbE_U D_rmKL(p|mathbbE_U_U)$と、出力法的な発散である$D_mathrmKL(p|mathbbE_U_U)$を比較する。
この目標に対して、カウント状態再帰は、すべての因果ランダム化ポリシーに対する全てのラウンドキャップにおいて、正確に最小出力のばらつきを与える。
- 参考スコア（独自算出の注目度）: 12.892650354721342
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A parallel sampler can choose at random which coordinates to generate together. For a target $p$ and the output law $q_U$ of a schedule $U$ drawn afresh for each output, we compare the schedule-averaged divergence $\mathbb{E}_U D_{\mathrm{KL}}(p\|q_U)$ with the output-law divergence $D_{\mathrm{KL}}(p\|\mathbb{E}_U q_U)$, in nats. Rounds commit independent draws from exact conditional marginals frozen at the round's start, each output's schedule is drawn before sampling from a finite mixture of schedules, and every scheduled round is charged. For the uniform distribution on binary strings of even length $n$ with $n/2$ ones, the least expected number of rounds at a fixed tolerance $\varepsilon>0$ is $Θ_\varepsilon((\log n)^2)$ under the first criterion but $(e^{-\varepsilon}+o(1))\log_2\ln n$ under the second, and the double-logarithmic order is attainable with the same round count on every run. For this target, a count-state recursion gives the exact least output divergence at every round cap over all causal randomized policies. The separation extends to weighted fixed-count targets with bounded weight ratios and quota fractions bounded away from zero and one, without permutation symmetry, and to the full-support Beta$(1,1)$--Bernoulli target, where the sharp expected cost under the output-law criterion is $(e^{-\varepsilon}/2+o(1))\log_2\log_2n$, attained with rare $n$-round runs. Prior work implies the order of the schedule-averaged cost on the balanced target and its $O_\varepsilon((\log n)^2)$ upper bounds on both extensions.
- Abstract（参考訳）: 並列サンプリング器は、どの座標を一緒に生成するかをランダムに選択することができる。
対象の$p$ と、各出力に対する描画 afresh の出力法$q_U$ に対して、平均発散値 $\mathbb{E}_U D_{\mathrm{KL}}(p\|q_U)$ と、出力-法則発散値 $D_{\mathrm{KL}}(p\|\mathbb{E}_U q_U)$ を比較する。
ラウンドはラウンド開始時に凍結された正確な条件付き辺縁から独立して引き出され、各出力のスケジュールは有限のスケジュールからサンプリングする前に引き出され、全てのスケジュールされたラウンドはチャージされる。
偶数長さ$n$と$n/2$の2次弦上の一様分布に対して、固定許容値$\varepsilon>0$ における最小のラウンド数は、第一基準の下で $ _\varepsilon((\log n)^2)$ であるが、第二基準下で $(e^{-\varepsilon}+o(1))\log_2\ln n$ であり、二重対数順序は全てのランで同じラウンド数で達成可能である。
この目標に対して、カウント状態再帰は、すべての因果ランダム化ポリシーに対して、全てのラウンドキャップにおいて、正確に最小出力のばらつきを与える。
この分離は、有界な重み比と商分を 0 と 1 から有界に有界に有り、置換対称性を持たず、完全支持のベータ$(1,1)$-ベルヌーリ目標に拡張され、出力法規準の下での厳しい期待コストは $(e^{-\varepsilon}/2+o(1))\log_2\log_2n$ となり、希少な$n$ラウンドランで達成される。
以前の作業は、バランスの取れたターゲット上の平均的なコストと、両方の拡張の上限である$O_\varepsilon((\log n)^2)$の順序を意味する。
関連論文リスト
- High-dimensional online calibration from harmonic weights [26.94938196315732]
任意の凸集合$YsubseteqmathbbRd$上での多次元予測のオンライン校正について検討する。
我々のアルゴリズムは単純で、各ラウンドで調和的に滑らかな過去の結果に対して調和的に重み付けされた分布を出力する。
論文 参考訳（メタデータ） (2026-10-06T04:36:12Z) - Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise [55.29259818039367]
オンライン凸最適化を1ラウンドに1つの偏りのない下位段階と、未知の有限条件の雑音モーメントであるp$th, $1ple2$で検討する。
長さ$n$の固定区間$I$に対して、学習者は最適な全水平静的レートを含む1+log(T/n)$を達成する。
論文 参考訳（メタデータ） (2026-09-30T21:03:03Z) - 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) - Quantum Change Interval: Exact Asymptotics for Minimum Error Localization [8.906035369693457]
我々は、あるソースが1つの間隔で$lvertrangle$と$lvert0rangle$を出力する復帰量子変化間隔について研究する。
Toeplitz 比較と Flner 変換を用いて行列を解析し,励起数と間隔包による正確な分解を行った。
論文 参考訳（メタデータ） (2026-08-25T13:30:26Z) - 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) - Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。
各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。
第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Sampling from Log-Concave Distributions with Infinity-Distance
Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
本稿では,dis distributionO(varepsilon)$close から$ infinity-distance に点を出力するアルゴリズムを提案する。
また、ディキンウォークの「ソフトパイ」バージョンも提示する。
論文 参考訳（メタデータ） (2021-11-07T13:44:50Z) - Learning Mixtures of Spherical Gaussians via Fourier Analysis [0.5381004207943596]
標本と計算複雑性の有界性は、$omega(1) leq d leq O(log k)$のとき以前には分かっていなかった。
これらの著者はまた、半径$d$ in $d$ dimensions, if $d$ is $Theta(sqrtd)$ in $d$ dimensions, if $d$が少なくとも$poly(k, frac1delta)$であるとき、ガウスのランダム混合の複雑さのサンプルを示す。
論文 参考訳（メタデータ） (2020-04-13T08:06:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。