論文の概要: Beyond the $d^{2.5}$-mixing bound for Dikin walks on polytopes

• arxiv url: http://arxiv.org/abs/2607.13943v1
• Date: Wed, 15 Jul 2026 15:29:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-16 16:39:12.823591
• Title: Beyond the $d^{2.5}$-mixing bound for Dikin walks on polytopes
• Title（参考訳）: ポリトープ上のダイキンウォークの$d^{2.5}$-mixing束を超えて
• Abstract要約: 2009年、カナンとナラヤナンはポリトープから一様にサンプリングするダイキンウォークを導入した。 2017年、Chen、Dwivedi、Wainwright、Yuはルイスウェイトバリアを使ってこれを$d2.5$に改善した。 ポリトープ上の指数的サンプリングのために、スケールしたリー-シドフォード計量を持つダイキンウォークが、dd2.25$反復の温かいスタートから混合されることを証明した。
• 参考スコア（独自算出の注目度）: 5.744814240870601
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Inspired by interior-point methods (IPM) for structured convex optimization, Kannan and Narayanan introduced the Dikin walk for sampling uniformly from polytopes in 2009. As in IPMs, the Dikin walk is affine-invariant, and its convergence is governed by the barrier geometry used to define its local proposal. They showed that the Dikin walk with the logarithmic barrier for a polytope in $\mathbb{R}^{d}$ with $m$ linear inequalities mixes in $md$ iterations. In 2017, Chen, Dwivedi, Wainwright, and Yu improved this to $d^{2.5}$ using a Lewis-weight barrier, and conjectured that the correct mixing time should be $d^{2}$. We make progress toward this conjecture by improving the previous $d^{2.5}$-mixing bound. For exponential sampling over a polytope, we prove that the Dikin walk with a scaled Lee--Sidford metric mixes from a warm start in $d^{2.25}$ iterations. This also yields an improved cold-start complexity via a known annealing framework. The main technical ingredient is improved average self-concordance of the Lee--Sidford metric, which gives high acceptance probability for the Metropolis filter along a random Dikin proposal. While previous analyses were effectively limited to second-order control due to technical difficulties, we develop a principled higher-order analysis. The proof combines a selective higher-order expansion of recursive bottleneck terms, a moving orthonormal-frame calculus for higher derivatives of the Lewis weights, and Wiener-chaos decompositions via multiple stochastic integrals to control the resulting Gaussian polynomials.
• Abstract（参考訳）: コンベックス最適化のためのインテリアポイント法(IPM)にインスパイアされ、2009年にカナンとナラヤナンはポリトープから一様にサンプリングするダイキンウォークを導入した。 IPM と同様に、ダイキン・ウォークはアフィン不変であり、その収束は局所的な提案を定義するために用いられる障壁幾何学によって制御される。 彼らは、ジキンウォークが$\mathbb{R}^{d}$のポリトープの対数障壁を持ち、$m$線型不等式が$md$反復で混合されることを示した。 2017年、Chen, Dwivedi, Wainwright, Yu らはこれをルイス級障壁を用いて$d^{2.5}$に改善し、正しい混合時間は$d^{2}$と予測した。 我々は、以前の$d^{2.5}$-mixing境界を改善することにより、この予想に向けて前進する。 ポリトープ上の指数的サンプリングのために、スケールしたリー-シドフォード計量を持つダイキンウォークが、d^{2.25}$反復の温かい開始から混合されることを証明した。 これにより、既知のアニールフレームワークを通じて、コールドスタートの複雑さも向上する。 主な技術的要素はリー-シドフォード計量の平均自己一致性の改善であり、これはランダムなダイキンの提案に沿ってメトロポリスフィルタの高い受理確率を与える。 従来の解析は技術的困難により2次制御に事実上制限されていたが,高次解析の原理を考案した。 この証明は、再帰的ボトルネック項の選択的高次展開、ルイス重み付けの高次微分に対する運動正則フレーム計算、および結果のガウス多項式を制御するために複数の確率積分によるウィーナー・カオス分解を組み合わせたものである。

関連論文リスト

• 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)
• 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)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Quadratically Regularized Optimal Transport: Localization Bounds and Affine Case Analysis [4.280045284812897]
  有向ハウスドルフ距離において、QOT の支持は、$varepsilonfrac1d+2$ よりも早くモンジュグラフの周りに集中できないことを示す。 我々は, 自己輸送に問題を低減し, 近年の自己輸送疎結合結果を適用することにより, $varepsilonfrac1d+2$ の急激な点方向管束を導出する。
  論文  参考訳（メタデータ） (2026-05-23T16:21:03Z)
• On Gaussian approximation for entropy-regularized Q-learning with function approximation [30.147231451149064]
  エントロピー規則化非同期Q-ラーニングによって生成されるポリアク・アッパートイテレートの高次元中心定理における収束率を導出する。 我々は、次数$n-1/4$の確率で凸距離に束縛されたガウス近似を$n$の多変数因子まで確立し、ここでは、$n$はアルゴリズムが使用するサンプルの数である。
  論文  参考訳（メタデータ） (2026-05-17T22:23:25Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Dimension-Independent Convergence of Underdamped Langevin Monte Carlo in KL Divergence [50.719298242863744]
  Underdamped Langevin dynamics (ULD) は Gibbs 分布の$propto e-V$ に広く使われているサンプルである。 離散化LDDにおける最初の次元自由なKL分散境界を証明した。
  論文  参考訳（メタデータ） (2026-03-02T22:14:38Z)
• Generalized Gradient Norm Clipping & Non-Euclidean $(L_0,L_1)$-Smoothness [51.302674884611335]
  本研究は、急勾配と条件勾配のアプローチを組み合わせることでノルムクリッピングを一般化するハイブリッド非ユークリッド最適化手法を提案する。 本稿では、ディープラーニングのためのアルゴリズムのインスタンス化について論じ、画像分類と言語モデリングにおけるそれらの特性を実証する。
  論文  参考訳（メタデータ） (2025-06-02T17:34:29Z)
• Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis [3.399289369740637]
  ポリトープ上の対流圏分布から試料を抽出する問題について検討した。 インテリアポイント法とダイキンウォークに基づいて、正規化ダイキンウォークの混合時間を分析する。
  論文  参考訳（メタデータ） (2024-12-15T20:43:51Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity [51.96093077151991]
  我々はAdamの新しい収束保証を導出し、$L$-smooth条件と有界雑音分散仮定のみを導出する。 本証明は,運動量と適応学習率の絡み合いを扱うために,新しい手法を利用する。
  論文  参考訳（メタデータ） (2023-10-27T09:16:58Z)
• When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm? [4.657614491309671]
  本研究では, 磁化ハミルトン・モンテカルロ (HMC) と跳躍フロッグ積分器の混合時間について解析した。 連続HMC力学の離散化における位置と速度変数の結合分布は, ほぼ不変であることを示す。
  論文  参考訳（メタデータ） (2023-04-10T17:35:57Z)
• Restricted Strong Convexity of Deep Learning Models with Smooth Activations [31.003601717265006]
  本研究では,スムーズなアクティベーション機能を持つディープラーニングモデルの最適化問題について検討する。 Restricted Strong Convexity (RSC) に基づく最適化の新しい解析手法を提案する。 深層学習モデルのためのRCCに基づくGDの幾何収束性を確立するための最初の結果である。
  論文  参考訳（メタデータ） (2022-09-29T21:24:26Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。 外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
  論文  参考訳（メタデータ） (2021-11-11T01:19:53Z)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。 我々の理論解析は数値実験によってさらに検証される。
  論文  参考訳（メタデータ） (2021-09-08T18:00:05Z)

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

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