論文の概要: Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Run

• arxiv url: http://arxiv.org/abs/2608.16878v1
• Date: Mon, 17 Aug 2026 17:57:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-18 19:59:03.833493
• Title: Spectral Gaps of Hit-and-Run and Coordinate Hit-and-Run
• Title（参考訳）: ヒット・アンド・ランとコーディネート・アンド・ランのスペクトルギャップ
• Abstract要約: 我々は、Hit-and-Runが、均一分布の$$$$$$(n2 C_mathsfPIlog(M/varepsilon))$の$$$-divergence$varepsilon$内の分布に収束することを示す。 Kanan, Lovsz and Simonovits (1997) がボールウォークで行ったように、Hit-and-Run の収束を Poincaré/KLS 定数に接続することはオープンな問題であった。
• 参考スコア（独自算出の注目度）: 14.178898919334115
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: For any convex body $\mathcal{K}\subset\mathbb{R}^{n}$ containing a unit ball, the spectral gap of Hit-and-Run is $Ω(1/(n^2 C_{\mathsf{PI}}))$, where $C_{\mathsf{PI}}$ is the Poincaré constant of the uniform distribution $π$ over $\mathcal{K}$. This implies that Hit-and-Run converges to a distribution within $χ^2$-divergence $\varepsilon$ of the uniform distribution $π$ in $O(n^2 C_{\mathsf{PI}}\log(M/\varepsilon))$ steps from any starting distribution $π_0$ with $M=χ^2(π_{0}\,\|\,π)$, thus refining the known bound of $O(n^2 R^2 \log(M/\varepsilon))$ by Lovász and Vempala (2004) in terms of the outer radius $R$; for nearly isotropic bodies, together with progress on the KLS conjecture, the complexity is $O(n^2\log n\log(M/\varepsilon))$, improving the dimension dependence from cubic to nearly quadratic while maintaining logarithmic dependence on the initial distance. It was an open problem to connect the convergence of Hit-and-Run to Poincaré/KLS constants as was done for the Ball walk by Kannan, Lovász and Simonovits (1997). Unlike Hit-and-Run, the Ball walk has an unavoidable linear dependence on (a stronger notion) of the initial warmness. We directly bound the spectral gap of the Hit-and-Run Markov chain by connecting it to functional isoperimetric constants, inspired by the recent analysis of In-and-Out. Rewriting the spectral gap in terms of dual certificates leads to the Babuška--Aziz constant studied in the analysis of PDEs; it is asymptotically bounded by the improved Poincaré constant, which we show can be bounded in terms of the usual Poincaré constant. The proof is based on duality and calculus, unlike known proofs of convergence for Hit-and-Run which are based on bounding the conductance. The same technique can be applied to Coordinate Hit-and-Run, resulting in a much improved mixing time of $O(n^3C_{\mathsf{PI}}\log(M/\varepsilon))$.
• Abstract（参考訳）: 単位球を含む任意の凸体 $\mathcal{K}\subset\mathbb{R}^{n}$ に対して、hit-and-Run のスペクトルギャップは $Ω(1/(n^2 C_{\mathsf{PI}})$ であり、$C_{\mathsf{PI}}$ は均一分布 $π$ over $\mathcal{K}$ のポアンカレ定数である。 このことは、Hit-and-Run が、一様分布の$π$ in $O(n^2 C_{\mathsf{PI}}\log(M/\varepsilon))$ 上の任意の開始分布 $π_0$ with $M=\^2(π_{0}\,\|\,π)$ 内の分布に収束することを意味する。 Kanan, Lovász and Simonovits (1997) がボールウォークで行ったように、Hit-and-Run の収束を Poincaré/KLS 定数に接続することはオープンな問題であった。 ヒット・アンド・ランとは異なり、ボールウォークは、最初の暖かさに対する(より強い概念である)避けられない線形依存を持つ。 ヒット・アンド・ラン・マルコフ連鎖のスペクトルギャップは、近年のイン・アンド・アウト解析に触発されて、関数的等尺定数に接続することで直接有界となる。 二重証明の項でスペクトルギャップを書き換えると、バブシュカ-アジズ定数はPDEの解析において研究され、これは改良されたポアンカレ定数によって漸近的に有界であり、通常のポアンカレ定数の項で有界であることが示される。 この証明は双対性と計算に基づいており、コンダクタンスの境界に基づくヒット・アンド・ランの収束の既知の証明とは異なっている。 同じテクニックがCoordinate Hit-and-Runにも適用でき、結果として$O(n^3C_{\mathsf{PI}}\log(M/\varepsilon)$が大幅に改善される。

関連論文リスト

• Low-Dimensional Embeddings for Gaussian Kernels on Manifolds [0.42970700836450487]
  $mathbb RN$, $t=((d/varepsilon2)log(dR/varepsilon))$ の$d$次元ユークリッド球の点に対して、任意のガウス核距離を保存するのに十分であることを示す。 同様の RFF 埋め込みの下では、ガウス核のパワー距離から作られる重み付き Cech と Rips のフィルターは$(pmvarepsilon_star)$-interleaved という意味で持続的ホモロジーが保存される。
  論文  参考訳（メタデータ） (2026-09-14T08:00:56Z)
• Quantum Change Interval: Exact Asymptotics for Minimum Error Localization [8.906035369693457]
  我々は、あるソースが1つの間隔で$lvertrangle$と$lvert0rangle$を出力する復帰量子変化間隔について研究する。 Toeplitz 比較と Flner 変換を用いて行列を解析し,励起数と間隔包による正確な分解を行った。
  論文  参考訳（メタデータ） (2026-08-25T13:30:26Z)
• Wigner quasi-probability distribution for symmetric multi-quDit systems and their generalized heat kernel [0.0]
  我々はSchr"odinger $U(D)$-spin cat状態の位相空間構造を解析した。 準確率分布である $mathcalF(s)_rho$ と $mathcalF(s')_rho$ に関する一般化熱核を計算する。
  論文  参考訳（メタデータ） (2025-07-20T08:26:28Z)
• Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximation [49.1574468325115]
  時間差分学習(TD(0))は強化学習の基本である。 マルコフデータを混合したバニラTD(0)の最初の高確率有限サンプル解析を行う。
  論文  参考訳（メタデータ） (2025-02-08T22:01:02Z)
• A computational transition for detecting correlated stochastic block models by low-degree polynomials [13.396246336911842]
  2つの相関ブロックモデル $mathcalS(n,tfraclambdan;k,epsilon;s)$ を共通の親ブロックモデル $mathcalS(n,tfraclambdan;k,epsilon)$ からサブサンプリングする。 このモデルを一対の独立した ErdHos'enyi グラフと区別する検出問題に対して、隣接点のエントリのエンブロー度に基づくテストに焦点をあてる。
  論文  参考訳（メタデータ） (2024-09-02T06:14:05Z)
• Efficient Sampling on Riemannian Manifolds via Langevin MCMC [51.825900634131486]
  本稿では,Gibs 分布 $d pi* = eh d vol_g$ over aian manifold $M$ via (geometric) Langevin MCMC。 この結果は、$pi*$ が非指数的であり、$Mh$ が負のリッチ曲率を持つような一般的な設定に適用できる。
  論文  参考訳（メタデータ） (2024-02-15T22:59:14Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• A Normal Map-Based Proximal Stochastic Gradient Method: Convergence and Identification Properties [7.281869462071603]
  近位勾配法 (PSGD) は複合型問題に対する最先端手法の1つである。 本稿では,ロビンソン写像に基づくPSGDの簡易な変種について述べる。
  論文  参考訳（メタデータ） (2023-05-10T01:12:11Z)
• Strong uniform convergence of Laplacians of random geometric and directed kNN graphs on compact manifolds [0.0]
  この作用素の微分ラプラス・ベルトラミ作用素へのほぼ確実に一様収束は、$n$が無限大の傾向にあるときに研究する。 この研究は、過去15年間の既知の結果を拡張した。
  論文  参考訳（メタデータ） (2022-12-20T14:31:06Z)
• 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)
• Stochastic behavior of outcome of Schur-Weyl duality measurement [45.41082277680607]
  我々は、$n$ qubits上のシュル=ワイル双対性に基づく分解によって定義される測定に焦点をあてる。 我々は、$n$が無限大に進むとき、中心極限の一種を含む様々な種類の分布を導出する。
  論文  参考訳（メタデータ） (2021-04-26T15:03:08Z)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)
• From Smooth Wasserstein Distance to Dual Sobolev Norm: Empirical Approximation and Statistical Applications [18.618590805279187]
  我々は$mathsfW_p(sigma)$が$pth次スムーズな双対ソボレフ$mathsfd_p(sigma)$で制御されていることを示す。 我々は、すべての次元において$sqrtnmathsfd_p(sigma)(hatmu_n,mu)$の極限分布を導出する。
  論文  参考訳（メタデータ） (2021-01-11T17:23:24Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。