Fugu-MT 論文翻訳(概要): On the Pseudo-Mixing of Kac's Walk

論文の概要: On the Pseudo-Mixing of Kac's Walk

arxiv url: http://arxiv.org/abs/2608.17374v1
Date: Tue, 18 Aug 2026 05:08:44 GMT
ステータス: 翻訳完了
システム内更新日: 2026-08-19 21:40:53.222941
Title: On the Pseudo-Mixing of Kac's Walk
Title（参考訳）: カッツウォークの擬似ミキシングについて
Abstract要約: 最初の$k$列がヴァッサーシュタイン距離を$O(n(k+log n)log n)$ステップで混合していることが証明され、オリヴェイラの予想が解かれる。応用として、この擬似混合推定を用いて、通常の目標次元を持つ高速ジョンソン・リンデンシュトラウス変換の有効性を証明できることを示す。
参考スコア（独自算出の注目度）: 8.182894251434183
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Motivated by a conjecture of Vaikuntanathan and Zamir, we study the pseudo-mixing of Kac's walk on $\mathrm{SO}(n)$: whether short trajectories are indistinguishable from Haar measure by low-complexity tests. We prove that the first $k$ columns mix in Wasserstein distance in $O(n(k+\log n)\log n)$ steps for fixed accuracy, resolving a conjecture of Oliveira. Combining this with a representation-theoretic variance bound, we show that if $T=ω(nk(k+\log n)\log n)$, then every degree-$k$ polynomial normalized to have unit Haar variance has expectation under the $T$-step law within $o(1)$ of its Haar expectation. As an application, we show that this pseudo-mixing estimate can be used to prove the effectiveness of a fast Johnson--Lindenstrauss transform with the usual target dimension.
Abstract（参考訳）: Vaikuntanathan と Zamir の予想に触発され、Kac のウォークの擬混合を $\mathrm{SO}(n)$: 短軌跡がハール測度と区別できないかどうかを低複素性試験で調べる。最初の$k$列がヴァッサーシュタイン距離を$O(n(k+\log n)\log n)$ステップで混合していることが証明され、オリヴェイラの予想が解かれる。これを表現論的分散境界と組み合わせると、$T=ω(nk(k+\log n)\log n)$ とすると、すべての次数-$k$多項式が、単位ハール分散を持つように正規化される。応用として、この擬似混合推定を用いて、通常の目標次元を持つ高速ジョンソン-リンデンシュトラウス変換の有効性を証明できることを示す。

関連論文リスト

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)
Tight Sample Bounds for Renyi and Min-Entropy Estimation [4.866431869728017]
サンプルからエントロピーを推定することは、情報理論とプロパティテストにおいて基礎となる。定数加法精度に対する最小エントロピー推定が標本複雑性$(klog k)$であることを証明する。
論文参考訳（メタデータ） (2026-07-18T21:01:38Z)
Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文参考訳（メタデータ） (2026-07-08T17:49:40Z)
Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach [2.956729394666618]
シャドウトモグラフィーの高精度化過程における試料の複雑さについて検討した。我々は、$O(mathrmpolylog(d))$$のコピー数に一度に作用するアダプティブな測定値を使用する。
論文参考訳（メタデータ） (2026-02-04T19:00:00Z)
Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
論文参考訳（メタデータ） (2024-11-20T02:46:15Z)
Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文参考訳（メタデータ） (2024-06-25T06:07:20Z)
Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity [6.812247730094931]
任意の$ngeq 2k-1$に対して、サンプルの複雑さとランタイムの複雑さをどうやって達成するかを示す(1/zeta)O(k)$。また、既知の$eOmega(k)$の下位境界を拡張して、より広い範囲の$zeta$と一致させる。
論文参考訳（メタデータ） (2023-09-25T09:50:15Z)
Classical shadows of fermions with particle number symmetry [0.0]
我々は、$mathcalO(k2eta)$classic complexityを持つ任意の$k$-RDMに対する推定器を提供する。ハーフフィリングの最悪の場合、我々の手法はサンプルの複雑さに4k$の利点をもたらす。
論文参考訳（メタデータ） (2022-08-18T17:11:12Z)
Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文参考訳（メタデータ） (2022-03-28T23:53:48Z)
Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
論文参考訳（メタデータ） (2020-06-12T10:21:40Z)
Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文参考訳（メタデータ） (2020-06-04T17:51:00Z)
Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。我々はCIFARに関する実験結果を示し,その理論を検証した。
論文参考訳（メタデータ） (2020-02-08T22:02:14Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。