Average-case thresholds for exact regularization of linear programs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914093850427392 |
|---|---|
| author | Friedlander, Michael P. Kubal, Sharvaj Plan, Yaniv Scott, Matthew S. |
| author_facet | Friedlander, Michael P. Kubal, Sharvaj Plan, Yaniv Scott, Matthew S. |
| contents | Small regularizers can preserve linear programming solutions exactly. This paper provides the first average-case analysis of exact regularization: with a standard Gaussian cost vector and fixed constraint set, bounds are established for the probability that exact regularization succeeds as a function of regularization strength. Failure is characterized via the Gaussian measure of inner cones, controlled by novel two-sided bounds on the measure of shifted cones. Results reveal dimension-dependent scaling laws and connect exact regularization of linear programs to their polyhedral geometry via the normal fan and the Gaussian (solid-angle) measure of its cones. Computable bounds are obtained in several canonical settings, including regularized optimal transport. Numerical experiments corroborate the predicted scalings and thresholds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_13083 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Average-case thresholds for exact regularization of linear programs Friedlander, Michael P. Kubal, Sharvaj Plan, Yaniv Scott, Matthew S. Optimization and Control Numerical Analysis Probability 52A38, 60D05, 90C05, 90C31, 90C46 Small regularizers can preserve linear programming solutions exactly. This paper provides the first average-case analysis of exact regularization: with a standard Gaussian cost vector and fixed constraint set, bounds are established for the probability that exact regularization succeeds as a function of regularization strength. Failure is characterized via the Gaussian measure of inner cones, controlled by novel two-sided bounds on the measure of shifted cones. Results reveal dimension-dependent scaling laws and connect exact regularization of linear programs to their polyhedral geometry via the normal fan and the Gaussian (solid-angle) measure of its cones. Computable bounds are obtained in several canonical settings, including regularized optimal transport. Numerical experiments corroborate the predicted scalings and thresholds. |
| title | Average-case thresholds for exact regularization of linear programs |
| topic | Optimization and Control Numerical Analysis Probability 52A38, 60D05, 90C05, 90C31, 90C46 |
| url | https://arxiv.org/abs/2510.13083 |