MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization

Technische Samenvatting: MoSSP voor niet-convexe, met DC-geregulariseerde geconstrueerde optimalisatie

Probleemformulering
Dit artikel behandelt een gestructureerde klasse van niet-convexe, geconstrueerde stochastische optimalisatieproblemen met Difference-of-Convex (DC)-regularisatie. Het probleem wordt geformuleerd als:
$$\min_{x \in \mathbb{R}^n} F(x) = \mathbb{E}_{\xi}[f(x, \xi)] + h(x) - g(x) \quad \text{zodat} \quad c(x) = 0,$$
waarbij $f$ een stochastische gladde verliesfunctie is, $h$ en $g$ proper, gesloten, convexe functies zijn (met $g$ potentieel niet-glad), en $c(x)=0$ niet-convexe gelijkheidsrestricties voorstelt. De toelaatbare verzameling wordt verondersteld niet-convex te zijn. Een belangrijke uitdaging in deze setting is dat de samengestelde regularisator $h-g$ over het algemeen niet-prox-vriendelijk is (d.w.z. de proximale operator van het verschil is niet in gesloten vorm beschikbaar), en dat de restricties niet-convex zijn, wat het behoud van haalbaarheid bemoeilijkt. Bovendien zijn exacte gradiënten van $f$ vaak niet toegankelijk, wat het gebruik van stochastische gradiënten noodzakelijk maakt.

Methodologie: MoSSP
Om deze uitdagingen aan te pakken, stellen de auteurs MoSSP (Momentum-based Single-loop Stochastic Penalty) voor, een single-loop raamwerk dat de rekenkundige last van double-loop-algoritmen (die vereisen dat innerlijke subproblemen bij benadering worden opgelost) vermijdt. De methodologie rust op drie kerncomponenten:

1. Straf en Gladding: De niet-convexe restricties worden behandeld via een kwadratische strafmethode, waardoor het probleem wordt omgezet in een reeks ongeconstrueerde DC-problemen met toenemende strafparameters $\rho_k$. Om de niet-gladheid van de DC-structuur aan te pakken, hanteren de auteurs de Difference-of-Moreau-Envelopes (DME)-techniek. In plaats van het gehele doelwit te glad te maken, construeren zij een gladde surrogaat $F_{\rho, \mu}(z) = M_{\mu}\psi_{\rho}(z) - M_{\mu}g(z)$, waarbij $\psi_{\rho} = f + \frac{\rho}{2}\|c(x)\|^2 + h$. Dit maakt het gebruik van gradiëntgebaseerde updates mogelijk terwijl de kritieke eigenschappen van de DC-structuur behouden blijven.
2. Single-loop Updates: Het algoritme onderhoudt twee variabelen, $x_k$ en $z_k$.
   • $x_k$ wordt bijgewerkt via een stochastische proximaal-gradiëntstap op het convexe deel van de gladde surrogaat, wat effectief de proximale afbeelding van $\psi_{\rho}$ schat.
   • $z_k$ wordt bijgewerkt via een gradiënt-type stap met gebruik van het verschil tussen de proximale afbeeldingen van $g$ en de geschatte $\psi_{\rho}$.
3. Momentumvarianten: Het raamwerk integreert twee momentumstrategieën om stochastische variantie te controleren en convergentiesnelheden te verbeteren:
   • MoSSP-P: Gebruikt Polyak-momentum (heavy-ball) voor de stochastische gradiëntschatter.
   • MoSSP-R: Gebruikt recursief momentum (STORM) voor variantiereductie, wat een correctieterm op basis van enkele steekproeven incorporateert.

Belangrijkste Bijdragen
Het artikel claimt de volgende bijdragen:

• Eerste Single-loop Complexiteit voor Geconstrueerde DC: Naar beste weten van de auteurs is dit de eerste systematische complexiteitsstudie van single-loop stochastische methoden voor niet-convexe, functioneel geconstrueerde optimalisatie die DC-structuur omvat.
• Bewezen Complexiteitsgaranties:
  • MoSSP-P bereikt een oracle-complexiteit van $O(\epsilon^{-4})$ voor het vinden van een stochastisch $\epsilon$-KKT-punt (onder milde voorwaarden) of een stochastisch $\epsilon-stationair punt.
  • MoSSP-R, met recursief momentum en een aanname van gemiddelde kwadratische gladheid, verbetert dit tot $O(\epsilon^{-3})$. Dit komt overeen met de bekende ondergrens voor ongeconstrueerde stochastische optimalisatie met variantiereductie en de best bekende snelheden voor niet-convexe, geconstrueerde stochastische optimalisatie zonder DC-structuur.
• Nieuwe Theoretische Analyse: De auteurs ontwikkelen een DC-bewuste complexiteitsanalyse die stochastische fouten expliciet karakteriseert binnen het kritischheidsmaat. Zij construeren een specifieke potentiaalfunctie om de controle van gladmakings-, momentum- en strafparameters te coördineren, zodat de DC-structuur de complexiteitsorde niet verslechtert in vergelijking met ongeconstrueerde settings.
• Omgaan met Niet-gladde DC: In tegenstelling tot eerdere werken die vaak gladde concave componenten veronderstellen of double-loop-schema's vereisen, behandelt MoSSP gevallen waarbij het concave deel $g$ niet-glad is en de restricties niet-convex zijn.

Experimentele Resultaten
De auteurs evalueren MoSSP-P en MoSSP-R op een met gelijkheidsrestricties geconstrueerd binair classificatieprobleem met DC-regularisatie (met $\ell_1 - \ell_2$-sparsiteit) over drie LIBSVM-datasets (a9a, phishing, australian). Zij vergelijken met double-loop-baselines: SPDC (stochastisch DC-algoritme) en SALM (stochastische augmented Lagrangiaan-methode), beide uitgerust met Polyak- of recursief momentum.

• Convergentiesnelheid: Op grootschalige datasets (a9a, phishing) convergeren MoSSP-varianten aanzienlijk sneller in termen van vermindering van de doelwaarde en vermindering van restrictie-overtredingen in vergelijking met de double-loop-baselines.
• Haalbaarheid: MoSSP vermindert restrictie-overtredingen snel van initiële niveaus (bijv. 100) naar $10^{-3}$ met minder gradiëntevaluaties. Daarentegen blijven baselines vaak gedurende langere tijd op hogere overtredingsniveaus ($10^{-2}$ of hoger).
• Robuustheid: Het voorgestelde raamwerk toont robuustheid ten opzichte van de keuze van de momentumtechniek, met concurrerende uiteindelijke doelwaarden en restrictie-overtredingen over verschillende datasets.

Betekenis en Claims
Het artikel positioneert MoSSP als een belangrijke stap voorwaarts in stochastische optimalisatie voor gestructureerde niet-convexe problemen. De auteurs benadrukken dat hun single-loop-ontwerp de behoefte aan uitgebreide hyperparameterafstelling en precieze eindingscriteria voor innerlijke loops elimineert, zoals vereist door double-loop-methoden. Cruciaal is dat zij claimen dat hun analyse bewijst dat de aanwezigheid van de DC-structuur en niet-convexe restricties de oracle-complexiteitsorde niet inherent verslechtert in vergelijking met eenvoudigere ongeconstrueerde of convex-geconstrueerde stochastische problemen. De door MoSSP-R bereikte $O(\epsilon^{-3})$-snelheid wordt geïdentificeerd als overeenkomend met state-of-the-art grenzen voor niet-convexe, geconstrueerde optimalisatie, wat aantoont dat het single-loop-strafraamwerk complexe DC-regularisaties effectief kan hanteren zonder theoretische efficiëntie op te offeren.