{"ID":2854939,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.13083","arxiv_id":"2510.13083","title":"Average-case thresholds for exact regularization of linear programs","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2510.13083","url_pdf":"https://arxiv.org/pdf/2510.13083v1","authors":"[\"Michael P. Friedlander\",\"Sharvaj Kubal\",\"Yaniv Plan\",\"Matthew S. Scott\"]","published":"2025-10-15T01:55:01Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"math.NA\",\"math.PR\"]","methods":"[]","has_code":false}