2025-11-17T11:43:13.229047

Average-case thresholds for exact regularization of linear programs

Friedlander, Kubal, Plan et al.
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.
academic

Durchschnittsfallschwellen für exakte Regularisierung linearer Programme

Grundinformationen

  • Paper-ID: 2510.13083
  • Titel: Average-case thresholds for exact regularization of linear programs
  • Autoren: Michael P. Friedlander, Sharvaj Kubal, Yaniv Plan, Matthew S. Scott
  • Klassifikation: math.OC cs.NA math.NA math.PR
  • Veröffentlichungsdatum: 15. Oktober 2025
  • Paper-Link: https://arxiv.org/abs/2510.13083

Zusammenfassung

Kleine Regularisierer können die Lösungen linearer Programme exakt bewahren. Dieses Paper liefert die erste Durchschnittsfallanalyse der exakten Regularisierung: Unter standardisierten Gaußschen Kostenvektoren und fester Nebenbedingungsmenge werden Schranken für die Erfolgswahrscheinlichkeit der exakten Regularisierung in Abhängigkeit von der Regularisierungsstärke etabliert. Versagen wird durch das Gaußmaß innerer Kegel charakterisiert, kontrolliert durch neue zweiseitige Schranken verschobener Kegelmaße. Die Ergebnisse offenbaren dimensionsabhängige Skalierungsgesetze und verbinden die exakte Regularisierung linearer Programme durch Normalenkegelfächer und deren Gaußsche (Raumwinkel-)Maße mit der Polyedergeometrie. Berechenbare Schranken werden in mehreren typischen Einstellungen erhalten, einschließlich regularisierter optimaler Transport. Numerische Experimente bestätigen die vorhergesagten Skalierungen und Schwellen.

Forschungshintergrund und Motivation

Problemdefinition

Das Kernproblem dieser Arbeit ist das Phänomen der exakten Regularisierung: Für das lineare Programm (P0)min⁡{−g⋅x∣Ax≤b}\text{(P0)} \quad \min \{-g \cdot x | Ax \leq b\} und seine regularisierte Version (Pε)min⁡{−g⋅x+εψ(x)∣Ax≤b}\text{(P}_\varepsilon\text{)} \quad \min \{-g \cdot x + \varepsilon\psi(x) | Ax \leq b\} bleibt die Lösung des regularisierten Problems eine Lösung des ursprünglichen Problems, wenn der Regularisierungsparameter ε\varepsilon hinreichend klein ist, d.h. Sol(Pε)⊆Sol(P0)\text{Sol}(\text{P}_\varepsilon) \subseteq \text{Sol}(\text{P}_0).

Forschungsmotivation

  1. Rechnerische Herausforderungen: Lineare Programme können nicht-eindeutige Lösungen und extreme Empfindlichkeit gegenüber Datenstörungen aufweisen; Regularisierung kann diese Probleme abschwächen
  2. Theoretische Lücke: Bestehende deterministische Analysen erfordern die Lösung des ursprünglichen Problems, um die exakte Regularisierungsschwelle εˉ\bar{\varepsilon} zu bestimmen
  3. Praktische Anforderungen: In Anwendungen wie optimalem Transport bewahrt quadratische Regularisierung die Sparsität besser als Entropieregularisierung
  4. Geometrische Einsichten: Probabilistische Analyse offenbart tiefe Verbindungen zwischen exakter Regularisierung und Polyedergeometrie

Einschränkungen bestehender Methoden

  • Die deterministische Theorie von Mangasarian und Meyer erfordert gleichzeitige Lösung von P0 und des Auswahlproblems P_ψ
  • Die Schranken von González-Sanz und Nutz sind im Durchschnittfall zu locker (um Faktor n verbessert)
  • Fehlende Analyse dimensionsabhängiger Skalierungsgesetze

Kernbeiträge

  1. Gaußmaßschranken verschobener Kegel: Etablierung von Theorem 1.3 mit zweiseitigen Schranken für das Gaußmaß von Kegeln V+w
  2. Geometrische Charakterisierung: Beweis, dass die Wahrscheinlichkeit exakter Regularisierung gleich der Summe der Gaußmaße innerer Kegel an allen Ecken ist (Theorem 1.5)
  3. Umfassende Schranken für innere Kegel: Entwicklung vollständiger Schranken durch Zugehörigkeitsbedingungen (Theorem 2.1) und Darstellungsvektoren (Theorem 2.5)
  4. Randmengenanalyse: Zweiseitige Schranken für Randmengen durch Flächenstruktur (Lemma 3.2, Theorem 3.3)
  5. Konkrete Anwendungen: Optimale Schranken (bis auf Konstanten) für ∞-Ballnebenbedingungen und regularisierten optimalen Transport

Methodische Details

Aufgabendefinition

Gegeben ein Polyeder Q={x∈Rn∣Ax≤b}Q = \{x \in \mathbb{R}^n | Ax \leq b\} und eine Regularisierungsfunktion ψ\psi, wird die Wahrscheinlichkeit des Ereignisses exakter Regularisierung ER(ε)\text{ER}(\varepsilon) analysiert, wenn der Kostenvektor g∼N(0,In)g \sim N(0, I_n) ist.

Zentrales geometrisches Gerüst

Normalenkegel und Eckenstruktur

Für x∈Qx \in Q ist der Normalenkegel definiert als: N(x):={v∈Rn∣v⋅(y−x)≤0 fu¨r alle y∈Q}N(x) := \{v \in \mathbb{R}^n | v \cdot (y-x) \leq 0 \text{ für alle } y \in Q\}

Schlüsseleigenschaften (Proposition 1.1):

  • N(z)N(z) ist nn-dimensional genau dann, wenn z∈Vert(Q)z \in \text{Vert}(Q)
  • Die Normalenkegel an Ecken partitionieren den Raum fast vollständig: ⋃z∈Vert(Q)N(z)=Rn\bigcup_{z \in \text{Vert}(Q)} N(z) = \mathbb{R}^n

Optimalitätsbedingungen

  • Optimalität von P0: g∈N(z)g \in N(z)
  • Optimalität von P_ε: g∈N(z)+∂(εψ)(z)g \in N(z) + \partial(\varepsilon\psi)(z)

Gaußmaßanalyse verschobener Kegel

Theorem 1.3 (zentrales technisches Ergebnis): Für einen Kegel V⊆RdV \subseteq \mathbb{R}^d und einen Vektor w∈Rdw \in \mathbb{R}^d gilt: γ(V+w)∈[γ(V)exp⁡(−12∥w∥2−dist(w,−V∗)d),γ(V)exp⁡(−12∥ΠV∗w∥2+dist(w,V∗)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]

Beweistechniken:

  • Obere Schranke: Hölder-Ungleichung und schwache Dualität, Optimierung des Varianzparameters κ\kappa
  • Untere Schranke: Jensen-Ungleichung kombiniert mit Moreau-Zerlegung

Methoden der Innenkegel-Analyse

Zugehörigkeitsbedingungen-Methode (Theorem 2.1)

Wenn ∂(εψ)(z)∩N(z)≠∅\partial(\varepsilon\psi)(z) \cap N(z) \neq \emptyset, vereinfacht sich der Innenkegel zu N(z)+wN(z) + w, und Theorem 1.3 wird direkt angewendet.

Darstellungsvektoren-Methode (Theorem 2.5)

Für Fälle, die die Zugehörigkeitsbedingung nicht erfüllen, wird ein Darstellungsvektor w~=ST−1(STw)+\tilde{w} = S_T^{-1}(S_T w)_+ konstruiert, so dass: M(T,w)=M(T,w~)M(T, w) = M(T, \tilde{w}) wobei M(T,w)=T∖(T+w)M(T, w) = T \setminus (T + w) die Randmenge ist.

Flächenzerlegung der Randmenge

Lemma 3.1: Die Randmenge kann zerlegt werden als: γ(M(T,w))≤∑i=1ℓγ(Pi)\gamma(M(T, w)) \leq \sum_{i=1}^\ell \gamma(P^i) wobei Pi=⋃t∈[0,1)[Ti+tw]P^i = \bigcup_{t \in [0,1)} [T^i + tw] (wenn si⋅w>0s_i \cdot w > 0).

Experimentelle Einrichtung

Numerische Verifikationsszenarien

  1. Birkhoff-Polytop (doppelt stochastische Matrizen) mit quadratischer Regularisierung
  2. ∞-Ball mit quadratischer und linearer Regularisierung
  3. Dimensionsbereich: n∈[103,104]n \in [10^3, 10^4]
  4. 20 unabhängige Versuche pro (n,ε)(n, \varepsilon)-Paar

Bewertungsmetriken

  • Fehlerwahrscheinlichkeit exakter Regularisierung P(ERc(ε))P(\text{ER}^c(\varepsilon))
  • Erwartete Regularisierungsschwelle E[εˉ]E[\bar{\varepsilon}]
  • Vergleich theoretischer Schranken mit empirischen Beobachtungen

Experimentelle Ergebnisse

Quadratische Regularisierung auf Birkhoff-Polytop

Theoretische Vorhersagen:

  • Fehlerwahrscheinlichkeitsschranke: P(ERc(ε))≤12ε2n+εn3/4P(\text{ER}^c(\varepsilon)) \leq \frac{1}{2}\varepsilon^2\sqrt{n} + \varepsilon n^{3/4}
  • Untere Schranke der erwarteten Schwelle: E[εˉ]≥1−e−4n2n3/4E[\bar{\varepsilon}] \geq \frac{1-e^{-4n}}{2n^{3/4}}

Experimentelle Verifikation:

  • Die empirische Fehlerwahrscheinlichkeit bei der horizontalen Kurve εn3/4=2\varepsilon n^{3/4} = 2 beträgt etwa 0,5, konsistent mit der theoretischen Schranke von 0,875
  • Die Skalierungsbeziehung zeigt sich auf logarithmischer Skala als Gerade, was die Dimensionsabhängigkeit bestätigt

Analyse der ∞-Ballnebenbedingung

Quadratische Regularisierung:

  • Theoretische Schranke: P(ERc(ε))≤εn+12ε2nP(\text{ER}^c(\varepsilon)) \leq \varepsilon n + \frac{1}{2}\varepsilon^2 n
  • Für ε<n−1\varepsilon < n^{-1} dominiert der erste Term; die Schranke ist optimal bis auf einen konstanten Faktor 2πe\sqrt{2\pi e}

Lineare Regularisierung:

  • Die Randmethode ergibt tightere Schranken: P(ERc(ε))≤12πε∥p∥1exp⁡(εn−1∥p∥)P(\text{ER}^c(\varepsilon)) \leq \frac{1}{\sqrt{2\pi}}\varepsilon\|p\|_1 \exp(\varepsilon\sqrt{n-1}\|p\|)
  • Effektiver für fast-spärliche Vektoren pp (quantifiziert durch das Verhältnis ∥p∥1/(n∥p∥)\|p\|_1/(\sqrt{n}\|p\|))

Verifikation unterer Schranken

Proposition 4.1 beweist untere Schranken auf dem ∞-Ball: P(ERc(ε))≥1−exp⁡(−2πenε)P(\text{ER}^c(\varepsilon)) \geq 1 - \exp\left(-\sqrt{\frac{2}{\pi e}}n\varepsilon\right) Für ε≤(πe)/2⋅12n\varepsilon \leq \sqrt{(\pi e)/2} \cdot \frac{1}{2n} gilt P(ERc(ε))≥12πenεP(\text{ER}^c(\varepsilon)) \geq \frac{1}{\sqrt{2\pi e}}n\varepsilon.

Verwandte Arbeiten

Deterministische Theorie exakter Regularisierung

  • Mangasarian und Meyer 1979: Etablierung grundlegender Bedingungen
  • Friedlander und Tseng 2008: Charakterisierung für allgemeine konvexe Programme
  • Charakterisierung der Schwelle εˉ\bar{\varepsilon} durch das duale Auswahlproblem Pψ\text{P}_\psi

Regularisierter optimaler Transport

  • Cuturi 2013: Sinkhorn-Algorithmus mit Entropieregularisierung
  • González-Sanz und Nutz 2024: Exaktheit quadratischer Regularisierung
  • Diese Arbeit verbessert ihre Schranke E[εˉ]≥c/(4n2)E[\bar{\varepsilon}] \geq c/(4n^2) zu E[εˉ]≥1/(4n)E[\bar{\varepsilon}] \geq 1/(4n)

Exakte Regularisierung in Sparsity- und Low-Rank-Wiederherstellung

  • Erfordert Annahmen über Vorstruktur; anwendbar in verschiedenen Regimen

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Dimensionsskalierungsgesetze: Exakte Regularisierungsschwellen zeigen klare Dimensionsabhängigkeit, wie ∝n−3/4\propto n^{-3/4} (Birkhoff-Polytop) und ∝n−1\propto n^{-1} (∞-Ball)
  2. Geometrische Verbindung: Tiefe Verbindung zwischen exakter Regularisierung und Polyedergeometrie durch Gaußmaße von Normalenkegelfächern
  3. Weiche Phasenübergang: Existenz klarer Phasenübergangsschwellen mit hoher Erfolgswahrscheinlichkeit bei kleinem ε\varepsilon und hoher Fehlerwahrscheinlichkeit bei großem ε\varepsilon

Einschränkungen

  1. Polyederbeschränkung: Analyse beschränkt auf polyedrische Nebenbedingungsmengen
  2. Gaußannahme: Kostenvektor muss Gaußverteilt sein
  3. Rechenkomplexität: Einige Schranken erfordern Berechnung der Normalenkegel aller Ecken

Zukünftige Richtungen

  1. Lösungsabstandsschranken: Probabilistische Schranken für dist(xε,Sol(P0))\text{dist}(x_\varepsilon, \text{Sol}(\text{P}_0)) bei Versagen exakter Regularisierung
  2. Trägermonotonie: Quantifizierung der Wahrscheinlichkeit von Trägermonotonie in quadratisch-beschränkten regularisierten LPs
  3. Allgemeine Kegelprogram: Erweiterung auf quadratisch- und semidefinit-beschränkte Programme

Tiefgreifende Bewertung

Stärken

  1. Theoretische Innovation: Erste Durchschnittsfallanalyse exakter Regularisierung; füllt wichtige theoretische Lücke
  2. Technische Tiefe: Zweiseitige Schranken für Gaußmaße verschobener Kegel sind zentraler technischer Beitrag
  3. Praktischer Wert: Liefert berechenbare Schranken für Anwendungen wie regularisierter optimaler Transport
  4. Geometrische Einsichten: Offenbart tiefe Verbindungen zwischen exakter Regularisierung und Polyedergeometrie
  5. Experimentelle Verifikation: Numerische Experimente bestätigen theoretische Vorhersagen umfassend

Schwächen

  1. Anwendungsbereich: Beschränkung auf polyedrische Nebenbedingungen und Gaußkostenvektoren
  2. Konstantenoptimierung: Konstanten in einigen Schranken möglicherweise nicht ausreichend tight
  3. Rechenkomplexität: Praktische Berechnung aller Normalenkegel an Ecken kann schwierig sein

Auswirkungen

  1. Theoretischer Beitrag: Neue Werkzeuge für Theorie zufälliger linearer Programme
  2. Anwendungswert: Praktische Orientierung für optimalen Transport und Sparsity-Optimierung
  3. Methodologie: Verschobene-Kegel-Analysetechniken verallgemeinerbar auf andere Probleme

Anwendungsszenarien

  1. Lineare Programmierungsanwendungen, die Verständnis der Regularisierungseffekte erfordern
  2. Parameterauswahl für Regularisierung im optimalen Transport
  3. Robustheitsanalyse hochdimensionaler linearer Programme
  4. Exakte Wiederherstellungsgarantien in Sparsity-Optimierung

Literaturverzeichnis

Das Paper zitiert 36 relevante Arbeiten, hauptsächlich umfassend:

  • Klassische konvexe Optimierungstheorie (Rockafellar, Hiriart-Urruty & Lemaréchal)
  • Theorie exakter Regularisierung (Mangasarian & Meyer, Friedlander & Tseng)
  • Optimaler Transport (Cuturi, González-Sanz & Nutz)
  • Hochdimensionale Wahrscheinlichkeit (Vershynin, Ledoux & Talagrand)