Regressione lineare robusta rispetto a Wasserstein, ottimale in termini di regret

Abstract degli autori

L’ottimizzazione robusta rispetto alla distribuzione (DRO) minimizza il rischio nel caso peggiore in presenza di incertezza distributiva, ma le decisioni che ne derivano possono essere subottimali in termini di rischio in eccesso, o regret. Studiamo questo divario nel caso della regressione multivariata ai minimi quadrati, ipotizzando che la distribuzione sorgente osservata e la distribuzione target sconosciuta differiscano per una perturbazione avversaria di Wasserstein-2 di ampiezza $\varepsilon$. Per prima cosa individuiamo la complessità asintotica del processo decisionale robusto nel limite $\varepsilon \to 0$, caratterizzata da un numero di condizionamento specifico del problema $κ$. In questo regime, un ampio spettro di algoritmi semplici, tra cui la DRO, raggiunge il tasso ottimale per istanza di $O(κ\varepsilon^2)$. Per $\varepsilon > 0$ fissato, dimostriamo che la DRO raggiunge comunque il tasso minimax se il problema ha rango effettivo residuo limitato. D’altra parte, individuiamo casi di fallimento significativi in cui la DRO è dimostrabilmente subottimale di fattori dipendenti dalla dimensione. Dimostriamo però che due procedure alternative, l’ottimizzazione minimax del regret (MRO) e la regolarizzazione con norma spettrale (SNR), raggiungono il tasso minimax. Deriviamo una riformulazione convessa esatta della MRO e un algoritmo prossimale accelerato per la SNR, insieme a garanzie a campione finito ad alta probabilità. Convalidiamo questi risultati teorici con esperimenti numerici che distinguono le prestazioni della MRO e della SNR da quelle della DRO.