Average-case thresholds for exact regularization of linear programs

Basic Information

• Paper ID: 2510.13083
• Title: Average-case thresholds for exact regularization of linear programs
• Authors: Michael P. Friedlander, Sharvaj Kubal, Yaniv Plan, Matthew S. Scott
• Classification: math.OC cs.NA math.NA math.PR
• Publication Date: October 15, 2025
• Paper Link: https://arxiv.org/abs/2510.13083

Abstract

Small regularizers can exactly preserve solutions to linear programs. This paper provides the first average-case analysis of exact regularization: under standard Gaussian cost vectors and fixed constraint sets, we establish bounds on the success probability of exact regularization as a function of regularization strength. Failure is characterized through the Gaussian measure of the inner cone, controlled by novel two-sided bounds on shifted cone measures. The results reveal dimension-dependent scaling laws and connect exact regularization of linear programs to the polyhedral geometry through normal cone fans and the Gaussian (solid angle) measures of their cones. Computable bounds are obtained in several typical settings, including regularized optimal transport. Numerical experiments confirm the predicted scalings and thresholds.

Research Background and Motivation

Problem Definition

The core problem studied in this paper is the exact regularization phenomenon: for the linear program $\text{(P0)} \quad \min \{-g \cdot x | Ax \leq b\}$ and its regularized version $\text{(P}_\varepsilon\text{)} \quad \min \{-g \cdot x + \varepsilon\psi(x) | Ax \leq b\}$ when the regularization parameter $\varepsilon$ is sufficiently small, the solution to the regularized problem remains a solution to the original problem, i.e., $\text{Sol}(\text{P}_\varepsilon) \subseteq \text{Sol}(\text{P}_0)$.

Research Motivation

1. Computational Challenges: Linear programs may have non-unique solutions and extreme sensitivity to data perturbations; regularization can mitigate these issues
2. Theoretical Gap: Existing deterministic analyses require solving the original problem first to determine the exact regularization threshold $\bar{\varepsilon}$
3. Practical Needs: In applications such as optimal transport, quadratic regularization better preserves sparsity than entropy regularization
4. Geometric Insights: Probabilistic analysis reveals deep connections between exact regularization and polyhedral geometry

Limitations of Existing Methods

• Mangasarian and Meyer's deterministic theory requires simultaneously solving P0 and the selection problem P_ψ
• González-Sanz and Nutz's bounds are too loose in the average case (improved by a factor of n)
• Lack of analysis of dimension-dependent scaling laws

Core Contributions

1. Gaussian Measure Bounds for Shifted Cones: Establishes Theorem 1.3, providing two-sided bounds on the Gaussian measure of cone V+w
2. Geometric Characterization: Proves that the exact regularization probability equals the sum of Gaussian measures of inner cones at all vertices (Theorem 1.5)
3. Suite of Inner Cone Bounds: Develops comprehensive bounds through membership conditions (Theorem 2.1) and representation vectors (Theorem 2.5)
4. Marginal Set Analysis: Provides two-sided bounds on marginal sets through face structure (Lemma 3.2, Theorem 3.3)
5. Concrete Applications: Provides optimal bounds (up to constants) for ∞-ball constraints and regularized optimal transport

Methodology Details

Task Definition

Given a polyhedral feasible region $Q = \{x \in \mathbb{R}^n | Ax \leq b\}$ and regularization function $\psi$, analyze the probability of the exact regularization event $\text{ER}(\varepsilon)$ when the cost vector $g \sim N(0, I_n)$.

Core Geometric Framework

Normal Cones and Vertex Structure

For $x \in Q$, the normal cone is defined as: $N(x) := \{v \in \mathbb{R}^n | v \cdot (y-x) \leq 0 \text{ for all } y \in Q\}$

Key properties (Proposition 1.1):

• $N(z)$ is n-dimensional if and only if $z \in \text{Vert}(Q)$
• Normal cones at vertices almost partition the entire space: $\bigcup_{z \in \text{Vert}(Q)} N(z) = \mathbb{R}^n$

Optimality Conditions

• Optimality for P0: $g \in N(z)$
• Optimality for P_ε: $g \in N(z) + \partial(\varepsilon\psi)(z)$

Gaussian Measure Analysis of Shifted Cones

Theorem 1.3 (Core Technical Result): For a cone $V \subseteq \mathbb{R}^d$ and vector $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]$

Proof Techniques:

• Upper bound: Uses Hölder's inequality and weak duality, optimizing over variance parameter $\kappa$
• Lower bound: Jensen's inequality combined with Moreau decomposition

Inner Cone Analysis Methods

Membership Condition Method (Theorem 2.1)

When $\partial(\varepsilon\psi)(z) \cap N(z) \neq \emptyset$, the inner cone simplifies to $N(z) + w$, directly applying Theorem 1.3.

Representation Vector Method (Theorem 2.5)

For cases not satisfying the membership condition, construct a representation vector $\tilde{w} = S_T^{-1}(S_T w)_+$ such that: $M(T, w) = M(T, \tilde{w})$ where $M(T, w) = T \setminus (T + w)$ is the marginal set.

Face Decomposition of Marginal Sets

Lemma 3.1: The marginal set can be decomposed as $\gamma(M(T, w)) \leq \sum_{i=1}^\ell \gamma(P^i)$ where $P^i = \bigcup_{t \in [0,1)} [T^i + tw]$ (when $s_i \cdot w > 0$).

Experimental Setup

Numerical Verification Scenarios

1. Birkhoff Polytope (doubly stochastic matrices) with quadratic regularization
2. ∞-ball with quadratic and linear regularization
3. Dimension range: $n \in [10^3, 10^4]$
4. 20 independent trials for each $(n, \varepsilon)$ pair

Evaluation Metrics

• Exact regularization failure probability $P(\text{ER}^c(\varepsilon))$
• Expected regularization threshold $E[\bar{\varepsilon}]$
• Comparison of theoretical bounds with empirical observations

Experimental Results

Quadratic Regularization on Birkhoff Polytope

Theoretical Predictions:

• Failure probability bound: $P(\text{ER}^c(\varepsilon)) \leq \frac{1}{2}\varepsilon^2\sqrt{n} + \varepsilon n^{3/4}$
• Expected threshold lower bound: $E[\bar{\varepsilon}] \geq \frac{1-e^{-4n}}{2n^{3/4}}$

Experimental Verification:

• Empirical failure probability at the level curve $\varepsilon n^{3/4} = 2$ is approximately 0.5, consistent with theoretical bound of 0.875
• Scaling relationships appear as straight lines on logarithmic scale, confirming dimension dependence

∞-ball Constraint Analysis

Quadratic Regularization:

• Theoretical bound: $P(\text{ER}^c(\varepsilon)) \leq \varepsilon n + \frac{1}{2}\varepsilon^2 n$
• When $\varepsilon < n^{-1}$, the first term dominates, and the bound is optimal within constant factor $\sqrt{2\pi e}$

Linear Regularization:

• Marginal method yields tighter bounds: $P(\text{ER}^c(\varepsilon)) \leq \frac{1}{\sqrt{2\pi}}\varepsilon\|p\|_1 \exp(\varepsilon\sqrt{n-1}\|p\|)$
• More effective for nearly sparse vectors $p$ (quantified by ratio $\|p\|_1/(\sqrt{n}\|p\|)$)

Lower Bound Verification

Proposition 4.1 establishes lower bounds on the ∞-ball: $P(\text{ER}^c(\varepsilon)) \geq 1 - \exp\left(-\sqrt{\frac{2}{\pi e}}n\varepsilon\right)$ For $\varepsilon \leq \sqrt{(\pi e)/2} \cdot \frac{1}{2n}$, we have $P(\text{ER}^c(\varepsilon)) \geq \frac{1}{\sqrt{2\pi e}}n\varepsilon$.

Related Work

Deterministic Exact Regularization Theory

• Mangasarian and Meyer 1979: Establish fundamental conditions
• Friedlander and Tseng 2008: Characterization for general convex programs
• Characterize threshold $\bar{\varepsilon}$ through dual selection problem $\text{P}_\psi$

Regularized Optimal Transport

• Cuturi 2013: Sinkhorn algorithm for entropy regularization
• González-Sanz and Nutz 2024: Exactness of quadratic regularization
• This paper improves their bound $E[\bar{\varepsilon}] \geq c/(4n^2)$ to $E[\bar{\varepsilon}] \geq 1/(4n)$

Exact Regularization in Sparse and Low-rank Recovery

• Require prior structural assumptions, applicable to different regimes

Conclusions and Discussion

Main Conclusions

1. Dimension Scaling Laws: Exact regularization thresholds exhibit clear dimension dependence, such as $\propto n^{-3/4}$ (Birkhoff polytope) and $\propto n^{-1}$ (∞-ball)
2. Geometric Connection: Establishes deep connections between exact regularization and polyhedral geometry through Gaussian measures of normal cone fans
3. Soft Phase Transition: Exhibits a clear phase transition threshold; high success probability for small $\varepsilon$, high failure probability for large $\varepsilon$

Limitations

1. Polyhedral Restriction: Analysis limited to polyhedral feasible regions
2. Gaussian Assumption: Cost vector must be Gaussian distributed
3. Computational Complexity: Some bounds require computing normal cones of all vertices

Future Directions

1. Solution Distance Bounds: Probabilistic bounds on $\text{dist}(x_\varepsilon, \text{Sol}(\text{P}_0))$ when exact regularization fails
2. Support Monotonicity: Quantify probability of support monotonicity in quadratically constrained regularized LPs
3. General Conic Programs: Extend to quadratic and semidefinite constraints

In-Depth Evaluation

Strengths

1. Theoretical Innovation: First average-case analysis of exact regularization, filling an important theoretical gap
2. Technical Depth: Two-sided bounds on Gaussian measures of shifted cones are core technical contributions
3. Practical Value: Provides computable bounds for applications such as regularized optimal transport
4. Geometric Insights: Reveals deep connections between exact regularization and polyhedral geometry
5. Experimental Validation: Numerical experiments thoroughly verify theoretical predictions

Weaknesses

1. Scope of Applicability: Limited to polyhedral constraints and Gaussian cost vectors
2. Constant Optimization: Constants in some bounds may not be sufficiently tight
3. Computational Complexity: Computing normal cones of all vertices may be difficult in practical applications

Impact

1. Theoretical Contribution: Provides new tools for random linear programming theory
2. Application Value: Offers practical guidance for optimal transport and sparse optimization
3. Methodological: Shifted cone analysis techniques can be generalized to other problems

Applicable Scenarios

1. Linear programming applications requiring understanding of regularization effects
2. Regularization parameter selection in optimal transport
3. Robustness analysis of high-dimensional linear programs
4. Exact recovery guarantees in sparse optimization

References

This paper cites 36 related references, primarily including:

• Classical convex optimization theory (Rockafellar, Hiriart-Urruty & Lemaréchal)
• Exact regularization theory (Mangasarian & Meyer, Friedlander & Tseng)
• Optimal transport (Cuturi, González-Sanz & Nutz)
• High-dimensional probability (Vershynin, Ledoux & Talagrand)