On $O(n)$ Algorithms for Projection onto the Top-$k$-sum Sublevel Set

1. Il Problema

Il lavoro si concentra sul problema della proiezione euclidea sull'insieme di sottolivello della somma dei primi $k$ elementi (top-k-sum). Dati un vettore di input $x_0 \in \mathbb{R}^n$, un intero $k \in \{1, \dots, n\}$ e un budget scalare $r \in \mathbb{R}$, l'obiettivo è risolvere il seguente problema di ottimizzazione convessa forte:

$$\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & \frac{1}{2} \|x - x_0\|_2^2 \\ \text{soggetto a} \quad & x \in B_r^{(k)} := \left\{ x \in \mathbb{R}^n : T^{(k)}(x) := \sum_{i=1}^k \vec{x}_i \leq r \right\} \end{aligned}$$

Dove $\vec{x}$ rappresenta il vettore $x$ ordinato in modo non crescente ($\vec{x}_1 \geq \vec{x}_2 \geq \dots \geq \vec{x}_n$) e $T^{(k)}(x)$ è la somma dei $k$ elementi più grandi.

Contesto e Importanza:
Questo operatore è strettamente legato al Superquantile (noto anche come Conditional Value-at-Risk o CVaR), fondamentale nella gestione del rischio e nell'ottimizzazione robusta. La proiezione su questo insieme è una subroutine critica per metodi iterativi (come il metodo del gradiente proiettato o Lagrangiani aumentati) che risolvono problemi di ottimizzazione composita con vincoli di rischio, comuni in applicazioni critiche per la sicurezza, machine learning (fairness, dati sbilanciati) e design robusto.

2. Metodologia

Gli autori propongono due algoritmi a terminazione finita che operano su un vettore di input già ordinato con complessità $O(n)$, dove la costante moltiplicativa è indipendente da $k$. Questo rappresenta un miglioramento significativo rispetto ai metodi esistenti.

A. Approccio Parametrico-LCP (PLCP)

• Fondamento Teorico: Il metodo si basa sulla struttura delle condizioni di Karush-Kuhn-Tucker (KKT) del problema ordinato, che possono essere formulate come un Problema di Complementarità Lineare Parametrico (PLCP) per una matrice $Z$ (matrice con elementi fuori diagonale non positivi).
• Meccanismo: L'algoritmo penalizza il vincolo di budget nella funzione obiettivo con un parametro $\lambda \geq 0$. Sfruttando la proprietà di monotonia della soluzione del PLCP rispetto a $\lambda$ (garantita dalla struttura della matrice $Z$), l'algoritmo esegue una serie di pivot (aggiustamenti della base) per trovare il valore ottimale di $\lambda$ che soddisfa il vincolo di budget.
• Efficienza: Grazie alla struttura tridiagonale della matrice associata ai vincoli di isotonia, ogni passo di pivot richiede tempo costante $O(1)$. Poiché al massimo sono necessari $n$ pivot, la complessità totale è $O(n)$.

B. Ricerca a Griglia con Arresto Anticipato (ESGS - Early-Stopping Grid-Search)

• Fondamento Teorico: Questo metodo è una variante ottimizzata della ricerca a griglia proposta in lavori precedenti [38]. Analizza le condizioni KKT per identificare le coppie di indici $(k_0, k_1)$ che definiscono la struttura della soluzione (dove $k_0$ e $k_1$ delimitano gli elementi che vengono ridotti, mantenuti uguali o lasciati invariati).
• Meccanismo: Invece di eseguire una ricerca esaustiva su tutte le coppie $(k_0, k_1)$ (che avrebbe complessità $O(k(n-k))$), l'algoritmo sfrutta le proprietà di monotonia delle condizioni KKT. Inizia da una coppia iniziale e si muove lungo un percorso specifico (decrementando $k_0$ o incrementando $k_1$) fino a soddisfare tutte le condizioni.
• Efficienza: La proprietà di monotonia permette di "saltare" grandi porzioni dello spazio di ricerca, garantendo che l'algoritmo termini in al massimo $n$ passi, risultando in complessità $O(n)$.

C. Ordinamento Parziale e Riscaldamento (Warm-start)

Per vettori di input non ordinati, il costo di ordinamento completo è $O(n \log n)$. Gli autori derivano una procedura che utilizza l'ordinamento parziale (basato su heap) integrata direttamente nel processo di risoluzione.

• Se il problema viene risolto in una sequenza di iterazioni (es. in un metodo di discesa del gradiente) dove il vettore di input cambia poco, è possibile riutilizzare la permutazione approssimata dell'iterazione precedente.
• Questo riduce il costo aggiuntivo a $O(\bar{k}_1 \log n)$, dove $\bar{k}_1$ è l'indice critico della soluzione (spesso molto minore di $n$).

3. Contributi Chiave

1. Algoritmi $O(n)$: Introduzione di due algoritmi (PLCP e ESGS) che risolvono esattamente la proiezione su insiemi top-k-sum con complessità lineare rispetto alla dimensione $n$, indipendentemente da $k$.
2. Superiorità rispetto agli stati dell'arte:
   • Rispetto al metodo di ricerca a griglia esistente ($O(k(n-k))$), il miglioramento è drammatico quando $k$ è proporzionale a $n$ (caso comune nelle applicazioni CVaR).
   • Rispetto al metodo di Newton semiliscio (SSN), gli algoritmi proposti sono più veloci e garantiscono una terminazione finita con complessità analitica nota.
   • Rispetto ai solver QP commerciali (es. Gurobi), offrono una velocità di ordini di grandezza superiore per problemi su larga scala.
3. Gestione dell'ordinamento: Sviluppo di una procedura rigorosa per sfruttare l'ordinamento approssimato, riducendo il costo computazionale in contesti iterativi.
4. Implementazione Open Source: Fornitura di un'implementazione in Julia disponibile pubblicamente.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su dataset sintetici con dimensioni fino a $n = 10^7$.

• Prestazioni: Per $n=10^7$ e $k=10^4$, gli algoritmi proposti (ESGS e PLCP) risolvono il problema in meno di 0.05 secondi.
• Confronto:
  • Il metodo SSN (Newton semiliscio) richiede circa 1 secondo.
  • Il metodo di ricerca a griglia e il solver Gurobi richiedono da minuti a ore (o falliscono per timeout).
  • I metodi proposti sono spesso 100-1000 volte più veloci delle alternative competitive.
• Scalabilità: I grafici mostrano un comportamento di scalabilità lineare per i metodi proposti, mentre i metodi basati su ricerca a griglia mostrano una scalatura quadratica.
• Robustezza: ESGS risulta generalmente più veloce di PLCP (di un fattore $\approx 2$) nelle istanze difficili che richiedono molti pivot, mantenendo un vantaggio anche nelle istanze più semplici.

5. Significato e Implicazioni

Questo lavoro risolve un collo di bottiglia computazionale significativo nell'ottimizzazione del rischio e nel machine learning. La capacità di calcolare proiezioni esatte su insiemi top-k-sum in tempo lineare rende fattibile l'uso di metodi di ordine superiore (come Newton o metodi del punto interno) per problemi di ottimizzazione composita su larga scala che coinvolgono vincoli di CVaR.
In particolare, l'efficienza degli algoritmi permette di gestire problemi con milioni di campioni (tipici nell'apprendimento automatico moderno) in tempi reali, abilitando applicazioni precedentemente proibitive in termini di costo computazionale, come il design robusto di sistemi complessi e l'addestramento di modelli resilienti a shift distribuzionali.