论文标题
稀疏PCA中的自由能井和重叠间隙属性
Free Energy Wells and Overlap Gap Property in Sparse PCA
论文作者
论文摘要
我们研究了“硬”制度中稀疏PCA（主要成分分析）问题的变体，其中推理任务是可能的，但尚无多项式时间算法。先前的工作，基于低度的似然比，在整个硬性方案中为最佳（次指数）运行时猜想了精确的表达式。取而代之的是，统计物理学启发了观点，我们在自然界的自由能井的深度上显示了与该问题自然相关的各种吉布斯措施的界限。这些自由能井意味着遇到时间的下限，证实了低度猜想的时间：我们表明，一类天然MCMC（Markov Chain Monte Carlo）方法（具有最差的案例初始化）无法以低于猜想的运行时解决稀疏PCA。这些下限适用于两个调谐参数的广泛值：温度和稀疏性畸形。最后，我们证明，重叠间隙属性（OGP）是一种结构性属性，暗示某些本地搜索算法失败，它占据了硬性状态的重要部分。
We study a variant of the sparse PCA (principal component analysis) problem in the "hard" regime, where the inference task is possible yet no polynomial-time algorithm is known to exist. Prior work, based on the low-degree likelihood ratio, has conjectured a precise expression for the best possible (sub-exponential) runtime throughout the hard regime. Following instead a statistical physics inspired point of view, we show bounds on the depth of free energy wells for various Gibbs measures naturally associated to the problem. These free energy wells imply hitting time lower bounds that corroborate the low-degree conjecture: we show that a class of natural MCMC (Markov chain Monte Carlo) methods (with worst-case initialization) cannot solve sparse PCA with less than the conjectured runtime. These lower bounds apply to a wide range of values for two tuning parameters: temperature and sparsity misparametrization. Finally, we prove that the Overlap Gap Property (OGP), a structural property that implies failure of certain local search algorithms, holds in a significant part of the hard regime.
