Strong self-concordance and sampling
Strong self-concordance and sampling
复制标题
较强的自一致性和抽样能力
DOI：
10.1145/3357713.3384272
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Vempala, Santosh
中科院分区：
文献类型：
--
作者：
Laddha, Aditi;Lee, Yin Tat;Vempala, Santosh
在Dikin行走的激励下，我们发展了高维采样的内点理论。具体来说，我们引入了势垒强自和谐和对称性的概念。这些性质意味着用对称参数为ν的强自调和势垒定义的Dikin游走在Õ（nν）步中从一个温暖的开始混合在一个凸体上。对于许多天然势垒，ν大致被ν所限定，ν是标准的自洽参数。我们也证明了这些性质适用于李-西福德势垒。作为结果，我们得到了在Õ（n2）步中混合的第一次行走对于一个任意的多面体在t (n)。其他势垒的强自我一致性导致了一个有趣的（和意想不到的）联系——对于普遍和熵势垒，它是由KLS猜想所暗示的。
Motivated by the Dikin walk, we develop aspects of the interior-point theory for sampling in high dimension. Specifically, we introduce the notions of strong self-concordance and symmetry for a barrier. These properties imply that the Dikin walk defined using a strongly self-concordant barrier with symmetry parameter ν mixes in Õ(nν) steps from a warm start for a convex body in ℝn. For many natural barriers, ν is roughly bounded by ν, the standard self-concordance parameter. We also show that these properties hold for the Lee-Sidford barrier. As a consequence, we obtain the first walk that mixes in Õ(n2) steps for an arbitrary polytope in ℝn. Strong self-concordance for other barriers leads to an interesting (and unexpected) connection — for the universal and entropic barriers, it is implied by the KLS conjecture.
登录
查看更多内容
影响因子：
2.7
作者：
Lovász, L
通讯作者：
Lovász, L
熵势垒：一种简单且最优的通用自和谐势垒
DOI：
--
发表时间：
2014
期刊：
Annual Conference Computational Learning Theory
影响因子：
--
作者：
Sébastien Bubeck;Ronen Eldan
通讯作者：
Ronen Eldan
约翰的步行
影响因子：
1.2
作者：
Adam Gustafson;Hariharan Narayanan
通讯作者：
Hariharan Narayanan
DOI：
10.1002/(sici)1098-2418(199708)11:1
发表时间：
1997
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
R. Kannan;L. Lovász;M. Simonovits
通讯作者：
R. Kannan;L. Lovász;M. Simonovits
影响因子：
1
作者：
L. Lovász;S. Vempala
通讯作者：
L. Lovász;S. Vempala