Statistical Mechanics of Optimal Convex Inference in High Dimensions
Statistical Mechanics of Optimal Convex Inference in High Dimensions
复制标题
DOI：
10.1103/physrevx.6.031034
复制
发表时间：
2016-08-29
影响因子：
12.5
通讯作者：
Ganguli, Surya
中科院分区：
文献类型：
--
作者：
Advani, Madhu;Ganguli, Surya
现代高维数据分析中的一个基本问题是有效地推断一组P个未知模型参数，这些参数控制着N个噪声测量的输入和输出之间的关系。已经提出了各种方法来将输出与输入进行回归，以恢复P参数。在有限的信噪比、有限的测量、先验信息和计算处理要求下，回归精确度的基本限制是什么？我们如何才能以最佳方式将先验信息与测量结果结合起来，以达到这些限制？经典统计学给出了这些问题的精辟答案，因为测量密度α=(N/P)->；无穷大。然而，这些经典的结果与现代高维推理问题无关，而现代高维推理问题发生在有限a处。我们使用复制理论来回答一类推理算法，在统计学文献中称为M-估计。这些算法试图通过解决涉及最小化惩罚数据和模型预测之间的偏差的损失函数和利用关于模型参数的先验信息的正则化的和的优化问题来恢复P模型参数。最大似然(ML)和最大后验概率(MAP)推断等算法作为M-估计量的特例出现。我们的分析揭示了对应于计算上容易处理的凸优化问题的M-估计子类的推理精度的基本极限。这些极限推广了经典的统计定理，如具有先验信息的高维环境下的Cramer-Rao约束。我们进一步发现了对数凹信号和噪声分布的最优M-估计量；我们证明了它可以达到我们对推断精度的高维极限，而ML和MAP不能。有趣的是，在高维情况下，这些优化算法在计算上比ML和MAP更简单，同时性能仍然优于它们。例如，这样的最优M估计算法可以导致数据量减少多达20%，以实现与MAP相同的性能。此外，通过揭示最优M-估计和最优贝叶斯推断在这种情况下的等价性，我们证明了复制理论的一个预测，即当信号和噪声分布是对数凹的时，任何推理过程都不能超过我们的最优M-估计过程。我们的分析还揭示了高维泛化和预测力的本质，压缩感知的信息论限制，二次推理中的相变，以及与凸优化理论和随机矩阵理论中的中心数学对象的联系。
A fundamental problem in modern high-dimensional data analysis involves efficiently inferring a set of P unknown model parameters governing the relationship between the inputs and outputs of N noisy measurements. Various methods have been proposed to regress the outputs against the inputs to recover the P parameters. What are fundamental limits on the accuracy of regression, given finite signal-to-noise ratios, limited measurements, prior information, and computational tractability requirements? How can we optimally combine prior information with measurements to achieve these limits? Classical statistics gives incisive answers to these questions as the measurement density alpha = (N/P) -> infinity. However, these classical results are not relevant to modern high-dimensional inference problems, which instead occur at finite a. We employ replica theory to answer these questions for a class of inference algorithms, known in the statistics literature as M-estimators. These algorithms attempt to recover the P model parameters by solving an optimization problem involving minimizing the sum of a loss function that penalizes deviations between the data and model predictions, and a regularizer that leverages prior information about model parameters. Widely cherished algorithms like maximum likelihood (ML) and maximum-a posteriori (MAP) inference arise as special cases of M-estimators. Our analysis uncovers fundamental limits on the inference accuracy of a subclass of M-estimators corresponding to computationally tractable convex optimization problems. These limits generalize classical statistical theorems like the Cramer-Rao bound to the high-dimensional setting with prior information. We further discover the optimal M-estimator for log-concave signal and noise distributions; we demonstrate that it can achieve our high-dimensional limits on inference accuracy, while ML and MAP cannot. Intriguingly, in high dimensions, these optimal algorithms become computationally simpler than ML and MAP while still outperforming them. For example, such optimal M-estimation algorithms can lead to as much as a 20% reduction in the amount of data to achieve the same performance relative to MAP. Moreover, we demonstrate a prediction of replica theory that no inference procedure whatsoever can outperform our optimal M-estimation procedure when signal and noise distributions are log-concave, by uncovering an equivalence between optimal M-estimation and optimal Bayesian inference in this setting. Our analysis also reveals insights into the nature of generalization and predictive power in high dimensions, information theoretic limits on compressed sensing, phase transitions in quadratic inference, and connections to central mathematical objects in convex optimization theory and random matrix theory.