論文の概要: On two proofs of $d^2$ mixing of weighted Dikin walks

• arxiv url: http://arxiv.org/abs/2608.28566v1
• Date: Fri, 28 Aug 2026 17:43:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-31 17:16:04.423301
• Title: On two proofs of $d^2$ mixing of weighted Dikin walks
• Title（参考訳）: 重み付きダイキンウォークの$d^2$混合の2つの証明について
• Abstract要約: 重み付きダイキンウォークの混合時間について検討し,ポリトープの指数分布と有極正セミド有限錐体(PSD)の混合時間について検討した。 このフレームワークをLee-Sidford、Lewis-weight、Johnのメトリクスに適用すると、ポリトープからサンプリングするために$widetilde O(d4)$mixboundが得られる。
• 参考スコア（独自算出の注目度）: 6.216428054339837
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the mixing time of weighted Dikin walks for sampling from exponential distributions on polytopes and truncated positive-semidefinite (PSD) cones. Our first result gives a general total-variation mixing bound under strong self-concordance, $\barν$-symmetry, and mixed-trace regularity on the local metric. The key idea is to control the Metropolis--Hastings acceptance probability on a high-probability region rather than at every point. Applying this framework to the Lee--Sidford, Lewis-weight, and John metrics yields an $\widetilde O(d^2)$ mixing bound for sampling from polytopes, while applying it to a hybrid barrier yields an $\widetilde O(d^4)$ mixing bound for sampling from truncated PSD cones. Our second result establishes stronger $χ^2$-divergence guarantees and pointwise acceptance control using a new fourth-order bootstrap condition. For a suitably scaled Lee--Sidford metric, this yields an $\widetilde O(d^2)$ mixing bound in $χ^2$-divergence, improving on the previous $\widetilde O(d^{9/4})$ bound.
• Abstract（参考訳）: 重み付きダイキンウォークの混合時間について検討し,ポリトープの指数分布と有極正セミド有限錐体(PSD)の混合時間について検討した。 最初の結果は、強い自己一致、$\barν$-対称性、局所計量上の混合トラス正則の下での一般的な全変分混合を与える。 鍵となる考え方は、全ての点でではなく、高確率領域におけるメトロポリス・ハスティングの受容確率を制御することである。 このフレームワークをLee-Sidford、Lewis-weight、Johnのメトリクスに適用すると、ポリトープからサンプリングするために$\widetilde O(d^2)$の混合バウンドが得られ、ハイブリッドバリアに適用すると、トランカットされたPSDコーンからサンプリングするために$\widetilde O(d^4)$の混合バウンドが得られる。 2つ目の結果は、新しい4階ブートストラップ条件を用いて、より強力な$ ^2$-divergence保証とポイントワイドの受け入れ制御を確立する。 適切なスケールのLee-Sidford計量に対して、これは$\widetilde O(d^2)$ mixed bound in $ ^2$-divergence となり、以前の$\widetilde O(d^{9/4})$ bound で改善される。

関連論文リスト

• A General Framework for Metropolis-Adjusted Dikin Walks: Dimension-Square Mixing on Polytopes and Log-Det Walks on Spectrahedra [12.89814955033651]
  提案した2次形式と逆2次形式を両立させることにより、正確なメトロポリス調整ダイキンウォークを解析する。 n$不等式と$L$-Lipschitzポテンシャルで与えられるポリトープの場合、これは正規化されたリー-シドフォード・ウォークに対して、$widetilde O((d2+dL2R2)log(w/)$の温度開始混合をもたらす。
  論文  参考訳（メタデータ） (2026-08-26T01:18:00Z)
• Beyond the $d^{2.5}$-mixing bound for Dikin walks on polytopes [5.744814240870601]
  2009年、カナンとナラヤナンはポリトープから一様にサンプリングするダイキンウォークを導入した。 2017年、Chen、Dwivedi、Wainwright、Yuはルイスウェイトバリアを使ってこれを$d2.5$に改善した。 ポリトープ上の指数的サンプリングのために、スケールしたリー-シドフォード計量を持つダイキンウォークが、dd2.25$反復の温かいスタートから混合されることを証明した。
  論文  参考訳（メタデータ） (2026-07-15T15:29:25Z)
• High-Probability PL-SGD with Markovian Noise: Optimal Mixing and Tail Dependence [41.64418624570687]
  マルコフ連鎖によって試料が生成された場合,ポリアク・オジャシエヴィチ(PL)条件を満たす目的の1次法について検討した。 ライトテール設定では、標準成長エンベロープスケールの通常のグラディエントD(SGD)に対して、以前の均一時間高確率境界を$widetildeO(t_mix/k)$とする。 我々は、この混合時間に対する線形依存が、持続的2で駆動される二次目的物上の一致する$(2 t_mix/k)$下界によって最適であることを示す。
  論文  参考訳（メタデータ） (2026-06-24T19:00:56Z)
• Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
  我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。 これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
  論文  参考訳（メタデータ） (2026-05-22T15:05:33Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis [3.399289369740637]
  ポリトープ上の対流圏分布から試料を抽出する問題について検討した。 インテリアポイント法とダイキンウォークに基づいて、正規化ダイキンウォークの混合時間を分析する。
  論文  参考訳（メタデータ） (2024-12-15T20:43:51Z)
• Nonlinear Stochastic Gradient Descent and Heavy-tailed Noise: A Unified Framework and High-probability Guarantees [56.80920351680438]
  本研究では,重音の存在下でのオンライン学習における高確率収束について検討する。 ノイズモーメントを仮定することなく、幅広い種類の非線形性を保証する。
  論文  参考訳（メタデータ） (2024-10-17T18:25:28Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• 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)
• 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)

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

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