证明了非凸广义线性模型在高维下的精确渐近行为,验证了物理学家的预测。
Asymptotics of Non-Convex Generalized Linear Models in High-Dimensions: A proof of the replica formula
- 结合极小极大定理与近似消息传递算法,严格推导非凸模型渐近解。
- 在ε污染数据下,证明Tukey损失优于Huber损失,负正则化更优。
- 为复杂优化问题提供理论工具,适合研究高维统计与机器学习者。
近年来,高维广义线性模型(GLMs)在高斯数据下的优化行为分析成为统计学与概率论的核心议题。尽管凸情形(如LASSO、岭回归、逻辑回归)已通过多种方法深入研究,但非凸情形仍远未被充分理解,尽管其具有重要意义。统计物理中的非严格框架曾对高维优化问题给出惊人预测,但其在非凸情况下的严格有效性始终是基础性挑战。本文通过构建系统性框架,严格证明了非凸GLMs的副本对称公式,并精确定义其适用条件。令人惊奇的是,严格结果与物理学家的猜想及所谓的复制子条件完全一致。方法原创性在于融合两个强大理论工具:利用高斯极小极大定理获得精确下界,同时证明近似消息传递(AMP)算法可达到该下界。通过三个重要应用展示了该框架价值:(i) 在ε污染数据模型下,证明Tukey损失优于常用的Huber损失;(ii) 确立高维非凸回归中负正则化的最优性;(iii) 揭示线性化AMP算法的性能极限。本工作严谨验证了非凸设置下统计物理预测的正确性,旨在为超越凸性的复杂优化景观分析开辟新路径。
原文摘要 · Abstract (English)
The analytic characterization of the high-dimensional behavior of optimization for Generalized Linear Models (GLMs) with Gaussian data has been a central focus in statistics and probability in recent years. While convex cases, such as the LASSO, ridge regression, and logistic regression, have been extensively studied using a variety of techniques, the non-convex case remains far less understood despite its significance. A non-rigorous statistical physics framework has provided remarkable predictions for the behavior of high-dimensional optimization problems, but rigorously establishing their validity for non-convex problems has remained a fundamental challenge. In this work, we address this challenge by developing a systematic framework that rigorously proves replica-symmetric formulas for non-convex GLMs and precisely determines the conditions under which these formulas are valid. Remarkably, the rigorous replica-symmetric predictions align exactly with the conjectures made by physicists, and the so-called replicon condition. The originality of our approach lies in connecting two powerful theoretical tools: the Gaussian Min-Max Theorem, which we use to provide precise lower bounds, and Approximate Message Passing (AMP), which is shown to achieve these bounds algorithmically. We demonstrate the utility of this framework through significant applications: (i) by proving the optimality of the Tukey loss over the more commonly used Huber loss under a $\varepsilon$ contaminated data model, (ii) establishing the optimality of negative regularization in high-dimensional non-convex regression and (iii) characterizing the performance limits of linearized AMP algorithms. By rigorously validating statistical physics predictions in non-convex settings, we aim to open new pathways for analyzing increasingly complex optimization landscapes beyond the convex regime.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。