Average-case thresholds for exact regularization of linear programs

基本信息

• 论文ID: 2510.13083
• 标题: Average-case thresholds for exact regularization of linear programs
• 作者: Michael P. Friedlander, Sharvaj Kubal, Yaniv Plan, Matthew S. Scott
• 分类: math.OC cs.NA math.NA math.PR
• 发表时间: 2025年10月15日
• 论文链接: https://arxiv.org/abs/2510.13083

摘要

小的正则化器可以精确保持线性规划解。本文提供了精确正则化的首个平均情况分析：在标准高斯成本向量和固定约束集的情况下，建立了精确正则化成功概率关于正则化强度的界限。失败通过内锥的高斯测度来刻画，由移位锥测度的新双边界限控制。结果揭示了维度依赖的缩放律，并通过法锥扇和其锥的高斯（立体角）测度将线性规划的精确正则化与其多面体几何联系起来。在几个典型设置中获得了可计算界限，包括正则化最优传输。数值实验证实了预测的缩放和阈值。

研究背景与动机

问题定义

本文研究的核心问题是精确正则化现象：对于线性规划问题 $\text{(P0)} \quad \min \{-g \cdot x | Ax \leq b\}$ 及其正则化版本 $\text{(P}_\varepsilon\text{)} \quad \min \{-g \cdot x + \varepsilon\psi(x) | Ax \leq b\}$ 当正则化参数$\varepsilon$足够小时，正则化问题的解仍然是原问题的解，即$\text{Sol}(\text{P}_\varepsilon) \subseteq \text{Sol}(\text{P}_0)$。

研究动机

1. 计算挑战：线性规划可能存在非唯一解和对数据扰动的极端敏感性，正则化可以缓解这些问题
2. 理论空白：现有的确定性分析需要先解决原问题才能确定精确正则化阈值$\bar{\varepsilon}$
3. 实际需求：在最优传输等应用中，二次正则化比熵正则化更能保持稀疏性
4. 几何洞察：通过概率分析揭示精确正则化与多面体几何的深层联系

现有方法局限性

• Mangasarian和Meyer的确定性理论需要同时求解P0和选择问题P_ψ
• González-Sanz和Nutz的界限在平均情况下过于宽松（改进了n倍）
• 缺乏维度依赖的缩放律分析

核心贡献

1. 移位锥的高斯测度界限：建立了Theorem 1.3，提供了锥V+w的高斯测度双边界限
2. 几何刻画：证明了精确正则化概率等于所有顶点处内锥高斯测度之和（Theorem 1.5）
3. 内锥界限套件：通过成员条件（Theorem 2.1）和表示向量（Theorem 2.5）发展了全面的界限
4. 边缘集分析：通过面结构提供边缘集的双边界限（Lemma 3.2，Theorem 3.3）
5. 具体应用：为∞-球约束和正则化最优传输提供了最优界限（up to常数）

方法详解

任务定义

给定多面体可行域$Q = \{x \in \mathbb{R}^n | Ax \leq b\}$和正则化函数$\psi$，分析当成本向量$g \sim N(0, I_n)$时，精确正则化事件$\text{ER}(\varepsilon)$的概率。

核心几何框架

法锥和顶点结构

对于$x \in Q$，法锥定义为： $N(x) := \{v \in \mathbb{R}^n | v \cdot (y-x) \leq 0 \text{ for all } y \in Q\}$

关键性质（Proposition 1.1）：

• $N(z)$是$n$维的当且仅当$z \in \text{Vert}(Q)$
• 顶点处的法锥几乎分割整个空间：$\bigcup_{z \in \text{Vert}(Q)} N(z) = \mathbb{R}^n$

最优性条件

• P0的最优性：$g \in N(z)$
• P_ε的最优性：$g \in N(z) + \partial(\varepsilon\psi)(z)$

移位锥的高斯测度分析

Theorem 1.3（核心技术结果）：对于锥$V \subseteq \mathbb{R}^d$和向量$w \in \mathbb{R}^d$， $\gamma(V + w) \in \left[\gamma(V) \exp\left(-\frac{1}{2}\|w\|^2 - \text{dist}(w, -V^*)\sqrt{d}\right), \gamma(V) \exp\left(-\frac{1}{2}\|\Pi_{V^*}w\|^2 + \text{dist}(w, V^*)\sqrt{d}\right)\right]$

证明技巧：

• 上界：使用Hölder不等式和弱对偶性，通过优化方差参数$\kappa$
• 下界：Jensen不等式结合Moreau分解

内锥分析方法

成员条件方法（Theorem 2.1）

当$\partial(\varepsilon\psi)(z) \cap N(z) \neq \emptyset$时，内锥简化为$N(z) + w$，直接应用Theorem 1.3。

表示向量方法（Theorem 2.5）

对于不满足成员条件的情况，构造表示向量$\tilde{w} = S_T^{-1}(S_T w)_+$，使得： $M(T, w) = M(T, \tilde{w})$ 其中$M(T, w) = T \setminus (T + w)$是边缘集。

边缘集的面分解

Lemma 3.1：边缘集可以分解为 $\gamma(M(T, w)) \leq \sum_{i=1}^\ell \gamma(P^i)$ 其中$P^i = \bigcup_{t \in [0,1)} [T^i + tw]$（当$s_i \cdot w > 0$时）。

实验设置

数值验证场景

1. Birkhoff多面体（双随机矩阵）上的二次正则化
2. ∞-球上的二次和线性正则化
3. 维度范围：$n \in [10^3, 10^4]$
4. 每个$(n, \varepsilon)$对进行20次独立试验

评价指标

• 精确正则化失败概率$P(\text{ER}^c(\varepsilon))$
• 期望正则化阈值$E[\bar{\varepsilon}]$
• 理论界限与经验观察的对比

实验结果

Birkhoff多面体上的二次正则化

理论预测：

• 失败概率界限：$P(\text{ER}^c(\varepsilon)) \leq \frac{1}{2}\varepsilon^2\sqrt{n} + \varepsilon n^{3/4}$
• 期望阈值下界：$E[\bar{\varepsilon}] \geq \frac{1-e^{-4n}}{2n^{3/4}}$

实验验证：

• 水平曲线$\varepsilon n^{3/4} = 2$处的经验失败概率约为0.5，与理论界限0.875一致
• 缩放关系在对数尺度上表现为直线，证实了维度依赖性

∞-球约束分析

二次正则化：

• 理论界限：$P(\text{ER}^c(\varepsilon)) \leq \varepsilon n + \frac{1}{2}\varepsilon^2 n$
• 当$\varepsilon < n^{-1}$时，第一项占主导，界限在常数因子$\sqrt{2\pi e}$内最优

线性正则化：

• 边缘方法给出更紧界限：$P(\text{ER}^c(\varepsilon)) \leq \frac{1}{\sqrt{2\pi}}\varepsilon\|p\|_1 \exp(\varepsilon\sqrt{n-1}\|p\|)$
• 对几乎稀疏向量$p$（由比率$\|p\|_1/(\sqrt{n}\|p\|)$量化）更有效

下界验证

Proposition 4.1证明了∞-球上的下界： $P(\text{ER}^c(\varepsilon)) \geq 1 - \exp\left(-\sqrt{\frac{2}{\pi e}}n\varepsilon\right)$ 对于$\varepsilon \leq \sqrt{(\pi e)/2} \cdot \frac{1}{2n}$，有$P(\text{ER}^c(\varepsilon)) \geq \frac{1}{\sqrt{2\pi e}}n\varepsilon$。

相关工作

确定性精确正则化理论

• Mangasarian和Meyer 1979：建立基本条件
• Friedlander和Tseng 2008：一般凸规划的刻画
• 通过对偶选择问题$\text{P}_\psi$刻画阈值$\bar{\varepsilon}$

正则化最优传输

• Cuturi 2013：熵正则化的Sinkhorn算法
• González-Sanz和Nutz 2024：二次正则化的精确性
• 本文改进了他们的界限$E[\bar{\varepsilon}] \geq c/(4n^2)$到$E[\bar{\varepsilon}] \geq 1/(4n)$

稀疏和低秩恢复中的精确正则化

• 要求先验结构假设，适用于不同的regime

结论与讨论

主要结论

1. 维度缩放律：精确正则化阈值具有明确的维度依赖性，如$\propto n^{-3/4}$（Birkhoff多面体）和$\propto n^{-1}$（∞-球）
2. 几何联系：通过法锥扇的高斯测度建立了精确正则化与多面体几何的深层联系
3. 软相变：存在明确的相变阈值，小$\varepsilon$时高概率成功，大$\varepsilon$时高概率失败

局限性

1. 多面体限制：分析局限于多面体可行域
2. 高斯假设：成本向量必须是高斯分布
3. 计算复杂性：某些界限需要计算所有顶点的法锥

未来方向

1. 解距离界限：当精确正则化失败时，$\text{dist}(x_\varepsilon, \text{Sol}(\text{P}_0))$的概率界限
2. 支撑单调性：量化二次约束正则化LP中支撑单调性的概率
3. 一般锥规划：扩展到二次和半定约束

深度评价

优点

1. 理论创新：首次提供精确正则化的平均情况分析，填补重要理论空白
2. 技术深度：移位锥高斯测度的双边界限是核心技术贡献
3. 实用价值：为正则化最优传输等应用提供可计算界限
4. 几何洞察：揭示了精确正则化与多面体几何的深层联系
5. 实验验证：数值实验充分验证了理论预测

不足

1. 适用范围：限制于多面体约束和高斯成本向量
2. 常数优化：某些界限中的常数可能不够紧
3. 计算复杂性：实际应用中计算所有顶点法锥可能困难

影响力

1. 理论贡献：为随机线性规划理论提供新工具
2. 应用价值：对最优传输和稀疏优化具有实际指导意义
3. 方法论：移位锥分析技术可推广到其他问题

适用场景

1. 需要理解正则化效果的线性规划应用
2. 最优传输中的正则化参数选择
3. 高维线性规划的鲁棒性分析
4. 稀疏优化中的精确恢复保证

参考文献

本文引用了36篇相关文献，主要包括：

• 经典凸优化理论（Rockafellar, Hiriart-Urruty & Lemaréchal）
• 精确正则化理论（Mangasarian & Meyer, Friedlander & Tseng）
• 最优传输（Cuturi, González-Sanz & Nutz）
• 高维概率（Vershynin, Ledoux & Talagrand）