論文の概要: A General Framework for Metropolis-Adjusted Dikin Walks: Dimension-Square Mixing on Polytopes and Log-Det Walks on Spectrahedra
- arxiv url: http://arxiv.org/abs/2608.25273v1
- Date: Wed, 26 Aug 2026 01:18:00 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-27 14:15:15.505999
- Title: A General Framework for Metropolis-Adjusted Dikin Walks: Dimension-Square Mixing on Polytopes and Log-Det Walks on Spectrahedra
- Title（参考訳）: メトロポリス調整ダイキンウォークの一般的な枠組み:ポリトープ上の次元とスペクトルヘドラ上の対数歩行を混合する
- Abstract要約: 提案した2次形式と逆2次形式を両立させることにより、正確なメトロポリス調整ダイキンウォークを解析する。
n$不等式と$L$-Lipschitzポテンシャルで与えられるポリトープの場合、これは正規化されたリー-シドフォード・ウォークに対して、$widetilde O((d2+dL2R2)log(w/)$の温度開始混合をもたらす。
- 参考スコア（独自算出の注目度）: 12.89814955033651
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We analyze exact-metric, Metropolis-adjusted Dikin walks by keeping the proposal determinant and reverse quadratic form together. Their leading uncentered terms cancel in the complete logarithmic acceptance ratio, leaving centered fluctuations that can be controlled with second-order tools. For a polytope given by $n$ inequalities and a convex $L$-Lipschitz potential, this yields warm-start mixing in $\widetilde O((d^{2}+dL^{2}R^{2})\log(w/δ))$ steps for the regularized Lee--Sidford walk. For a spectrahedron with $n\times n$ blocks, the log-det walk mixes in $\widetilde O((ψ^\star nd+dL^{2}R^{2})\log(w/δ))$ steps, where $ψ^\star$ measures matrix leverage. The two analyses share an acceptance-to-mixing reduction. A proposal-comparison argument transfers the polytope bound to an appropriately padded $O(1/d)$-accurate metric computed from high-precision Lewis weights. For spectrahedra, given $\widehatψ\geψ^\star$, a direct-or-two-seed TensorSRHT construction gives an exact-arithmetic implementation with $ψ^\star$ replaced by $\widehatψ$ in the mixing bound.
- Abstract（参考訳）: 提案した2次形式と逆2次形式を両立させることにより、正確なメトロポリス調整ダイキンウォークを解析する。
彼らの主要な非中心的項は完全な対数受容比でキャンセルされ、2階ツールで制御できる中心的ゆらぎが残る。
n$不等式と凸$L$-Lipschitzポテンシャルで与えられるポリトープの場合、これは正規化されたリー-シドフォードウォークのステップを$\widetilde O((d^{2}+dL^{2}R^{2})\log(w/δ) で温開始混合する。
n$ブロックが$n\times n$ブロックを持つ spectrahedron に対して、log-det walk は $\widetilde O(()^\star nd+dL^{2}R^{2})\log(w/δ)$ steps で混合される。
2つの分析は、受け入れと混合の削減を共有している。
提案-比較引数は、高精度ルイス重みから計算された適切なパッド付き$O(1/d)$-正確な計量にポリトープを束縛する。
spectrahedra に対して、$\widehat ^\star$ が与えられたとき、直列または二列の TensorSRHT 構造は、混合境界において $ ^\star$ を $\widehat $ に置き換えた正確な算術的な実装を与える。
関連論文リスト
- On two proofs of $d^2$ mixing of weighted Dikin walks [6.216428054339837]
重み付きダイキンウォークの混合時間について検討し,ポリトープの指数分布と有極正セミド有限錐体(PSD)の混合時間について検討した。
このフレームワークをLee-Sidford、Lewis-weight、Johnのメトリクスに適用すると、ポリトープからサンプリングするために$widetilde O(d4)$mixboundが得られる。
論文 参考訳（メタデータ） (2026-08-28T17:43:58Z) - Shallow ReLU$^s$ Networks in $L^p$-Type and Sobolev Spaces: Approximation and Path-Norm Controlled Generalization [12.871748162999062]
特に、$_d$が均一測度で$1le p2$のとき、近似率は$O!left(m-fracp(2s+2d+1)-2d2dpright)$ for $1le p*$と$O!left(m-fracp(4s+3d-1)-2d+24dpright)$ for $p*p2$である。
non (複数形 nons)
論文 参考訳（メタデータ） (2026-05-18T14:27:49Z) - Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。
我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
論文 参考訳（メタデータ） (2026-03-20T01:53:44Z) - Heavy-Tailed Linear Bandits: Huber Regression with One-Pass Update [62.96781471194877]
ヘビーテール付きバンディットには、ヘビーテール付きノイズ、トランケーション、中央値の2つの基本戦略が導入されている。
本稿では,オンラインミラー降下フレームワークに基づくEmphone-passアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-03-01T09:41:45Z) - Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk [12.842909157175582]
我々は、$d$-dimensional log-concave distribution $pi(theta) propto exp(-f(theta))$ for $L$-Lipschitz $f$を考える。
本稿では,各繰り返しにおける障壁関数のヘシアンに対するスペクトル近似を計算するインプロバストサンプリングフレームワークを提案する。
論文 参考訳（メタデータ） (2024-10-08T05:32:51Z) - On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。
我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。
収束率は$frac1Tsum_k=1Tと類似していると考えられる。
論文 参考訳（メタデータ） (2024-02-01T07:21:32Z) - Algorithms for mean-field variational inference via polyhedral optimization in the Wasserstein space [10.292118864147097]
ワッサーシュタイン空間上の有限次元多面体部分集合の理論を開発し、一階法による函数の最適化を行う。
我々の主な応用は平均場変動推論の問題であり、これは分布の$pi$ over $mathbbRd$を製品測度$pistar$で近似しようとするものである。
解析の副産物として,MFVIのための勾配に基づくアルゴリズムの最初のエンドツーエンド解析を求める。
論文 参考訳（メタデータ） (2023-12-05T16:02:04Z) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳（メタデータ） (2021-01-29T18:57:52Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov
Decision Processes [91.38793800392108]
本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。
上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。
我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
論文 参考訳（メタデータ） (2020-12-15T18:56:46Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。