Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods

Sintesi Tecnica: Limiti di Errore, Condizione PL, Crescita Quadratica per Funzioni Debolmente Convesse e Convergenze Lineari dei Metodi del Punto Prossimale

Enunciato del Problema
Molti problemi di ottimizzazione pratica, in particolare nel machine learning e nell'elaborazione dei segnali, mancano di convessità forte. Sebbene si sappia che gli algoritmi del primo ordine raggiungono la convergenza lineare sotto convessità forte, studi recenti hanno dimostrato che la convergenza lineare può essere garantita anche sotto condizioni di regolarità più deboli (ad esempio, disuguaglianza di Polyak-Lojasiewicz, limiti di errore, crescita quadratica) per funzioni lisce e convesse. Tuttavia, le relazioni tra queste condizioni non erano ben comprese nel contesto delle funzioni non lisce e non convesse. Nello specifico, la classe delle funzioni debolmente convesse (funzioni $f$ tali che $f + \frac{\rho}{2}\|\cdot\|^2$ è convessa per un certo $\rho \geq 0$) comprende molti modelli moderni (ad esempio, reti neurali non lisce, composizioni di funzioni convesse e lisce), ma mancava di un quadro unificato che connettesse queste condizioni di regolarità. Inoltre, le prove esistenti per la convergenza lineare del Metodo del Punto Prossimale (PPM) spesso si basavano su assunzioni restrittive (ad esempio, minimizzatori unici, continuità Lipschitz locale dell'inverso del subdifferenziale) o argomentazioni complesse.

Metodologia
Il lavoro impiega strumenti dell'analisi non liscia, specificamente la nozione di pendenza (slope), il principio di variazione di Ekeland e i lemmi di stima della distanza, per analizzare le relazioni tra le condizioni di regolarità. Gli autori definiscono cinque condizioni chiave su un insieme di sottolivello $[f \leq f^\star + \nu]$:

1. Convessità Forte (SC)
2. Disuguaglianza Seccante Restretta (RSI)
3. Limite di Errore del Subdifferenziale (EB)
4. Disuguaglianza di Polyak-Lojasiewicz (PL)
5. Crescita Quadratica (QG)

Gli autori utilizzano la pendenza $|\nabla f|(x) = \text{dist}(0, \hat{\partial}f(x))$ (dove $\hat{\partial}f$ è il subdifferenziale di Fréchet) per colmare il divario tra l'ambito liscio e quello non liscio. Stabiliscono implicazioni logiche ed equivalenze tra queste condizioni, concentrandosi in particolare sul caso in cui la costante di crescita quadratica $\mu_q$ eccede il parametro di convessità debole $\rho$.

Sulla base di queste equivalenze, il documento analizza il Metodo del Punto Prossimale (PPM):
$$x_{k+1} = \text{prox}_{c_k f}(x_k) = \arg\min_x \left( f(x) + \frac{1}{2c_k}\|x - x_k\|^2 \right)$$
Gli autori forniscono una prova modulare per la convergenza lineare sia in contesti convessi che debolmente convessi. Estendono inoltre l'analisi al PPM Inesatto (iPPM), dove i sottoproblemi sono risolti approssimativamente, affrontando le sottigliezze relative ai criteri di arresto e alla fattibilità (garantendo che le iterazioni rimangano nel dominio di $f$).

Contributi Chiave

1. Unificazione delle Condizioni di Regolarità per Funzioni Debolmente Convesse:
   Il documento stabilisce la gerarchia e l'equivalenza delle condizioni di regolarità per funzioni $\rho$-debolmente convesse.

   • Catena di Implicazione Generale: $(SC) \implies (RSI) \implies (EB) \iff (PL) \implies (QG)$.
   • Equivalenza sotto $\mu_q > \rho$: Se una funzione $\rho$-debolmente convessa soddisfa la Crescita Quadratica con una costante $\mu_q > \rho$, allora tutte e quattro le condizioni $(RSI), (EB), (PL)$e$(QG)$ sono equivalenti.
   • Gli autori derivano conversioni esplicite dei coefficienti tra queste condizioni (riassunte nella Tabella 1 del documento), consentendo ai professionisti di tradurre le costanti da una condizione all'altra.

2. Prove Semplificate della Convergenza Lineare per il PPM:
   Il documento presenta una prova semplice e modulare per la convergenza lineare del PPM sia per funzioni convesse che debolmente convesse.

   • Caso Convesso: Sotto qualsiasi delle condizioni di regolarità equivalenti (PL, EB, RSI, QG), il PPM raggiunge la convergenza lineare sia per i valori della funzione che per la distanza dall'insieme dei minimi. La prova rilassa le assunzioni precedenti, eliminando la necessità di un minimizzatore unico o della continuità Lipschitz locale dell'inverso del subdifferenziale.
   • Caso Debolmente Convesso: I risultati sono estesi alle funzioni $\rho$-debolmente convesse, a condizione che l'inizializzazione sia all'interno di un insieme di sottolivello che soddisfi la QG con $\mu_q > \rho$ e che i passi soddisfino $1/c_k > \rho$.

3. Analisi del PPM Inesatto (iPPM):
   Gli autori chiariscono le sfumature dell'inesattezza e della fattibilità nel iPP. Stabiliscono la convergenza lineare per l'iPPM sotto standard criteri di arresto (criteri A e B di Rockafellar), a condizione che la funzione soddisfi la QG in un vicinato dell'insieme dei minimi. La prova combina una chiave disuguaglianza dalla letteratura precedente con il framework di regolarità modulare.

Risultati

• Teorici: Il Teorema 3.1 conferma che, per le funzioni debolmente convesse, l'equivalenza delle condizioni di regolarità è valida se $\mu_q > \rho$. Questo generalizza i risultati precedenti limitati a funzioni lisce o convesse.
• Algoritmici: I Teoremi 4.2 e 4.3 dimostrano che il PPM converge linearmente con tassi dipendenti dalle costanti di regolarità (ad esempio, $\omega_k = \frac{1}{1+c_k\mu_p}$). Il Teorema 5.3 estende questo al PPM inesatto, mostrando che finché l'inesattezza è controllata (la somma degli errori è finita), il tasso di convergenza lineare è preservato asintoticamente.
• Numerici: Gli esperimenti su problemi di Linear SVM, Lasso ed Elastic-Net confermano la convergenza lineare teorica del PPM. Gli esperimenti utilizzano il pacchetto di modellazione YALMIP e il solver MOSEK, mostrando una convergenza rapida sia nei gap di valore di costo che nella distanza dall'insieme dei minimi.

Significatività e Rivendicazioni
Il documento sostiene di generalizzare la comprensione delle condizioni di regolarità dal contesto liscio/convesso alla classe più ampia di funzioni debolmente convesse non lisce. Chiarendo le connessioni tra queste condizioni, gli autori forniscono un quadro unificato che semplifica l'analisi degli algoritmi iterativi.

Nello specifico, il documento afferma che:

• L'equivalenza delle condizioni (RSI, EB, PL, QG) sotto $\mu_q > \rho$ permette un'analisi flessibile; una condizione può essere stabilita per derivare i risultati di convergenza tramite le altre.
• Le prove della convergenza lineare del PPM sono più semplici e trasparenti rispetto alla letteratura esistente, evitando assunzioni restrittive come i minimizzatori unici.
• I risultati facilitano lo sviluppo di algoritmi per l'ottimizzazione non liscia, particolarmente nelle applicazioni di ottimizzazione conica su larga scala e nel machine learning dove la convessità debole è prevalente.

Gli autori osservano che, sebbene l'equivalenza di queste condizioni fosse nota per funzioni lisce o convesse, l'estensione a funzioni debolmente convesse non lisce e la fornitura di una prova pulita per il PPM (inclusi i casi inesatti) costituisce la principale novità. Il lavoro è presentato come una versione estesa di un articolo di conferenza, con l'aggiunta di prove dettagliate, conversioni di coefficienti e un'analisi estesa del PPM inesatto.