Online Convex Optimization with Sublinear Noisy Probes

Sintesi Tecnica: Ottimizzazione Convessa Online con Saggi Noiosi Sublineari

Formulazione del Problema
Questo articolo investiga l'Ottimizzazione Convessa Online (OCO) su un insieme convesso $K \subseteq \mathbb{R}^d$. Nel setting standard, un apprendente seleziona una decisione $x_t \in K$ ad ogni round $t$, incorre in una perdita convessa $f_t(x_t)$ scelta da un avversario e riceve un feedback completo (la funzione $f_t$ o i suoi subgradienti). L'obiettivo è minimizzare il regret rispetto alla migliore decisione fissa a posteriori.

Gli autori introducono un modello di saggio (probing) unificato che generalizza due recenti linee di ricerca: le query del miglior esperto sublineare nel setting degli esperti [Russo et al., 2024] e il feedback di confronto a coppie in OCO [Bhaskara et al., 2023b]. In questo framework, l'apprendente dispone di un budget di $k \le T$ saggi a coppie (pairwise probes). In un round di saggio, prima di selezionare $x_t$, l'apprendante può interrogare due punti $\{y_{t,1}, y_{t,2}\} \subseteq K$ e ricevere un'indicazione di quale punto incorra nella perdita minore. Fondamentalmente, questi saggi sono noiosi (noisy): con probabilità $\delta$, l'oracolo restituisce il punto con la perdita maggiore (la risposta "sbagliata"), e con probabilità $1-\delta$ restituisce il minimizzatore corretto. Il parametro di rumore $\delta \in [0, 1]$ è ignoto all'apprendente.

Il protocollo assume un avversario oblivo che si impegna preventivamente sulla sequenza di funzioni di perdita $\{f_t\}_{t=1}^T$ prima che l'apprendente decida se effettuare un saggio in un determinato round. Questo vincolo è vitale; se l'avversario potesse adattarsi alla decisione di saggio, il saggio potrebbe essere reso inutile (ad esempio, impostando le perdite a 0 nei round di saggio), degradando il limite del regret a $\Theta(\sqrt{T-k})$.

Metodologia
L'algoritmo proposto è una versione adattiva e aumentata dai saggi del Continuous Exponential Weights (CEW). L'intuizione tecnica centrale si basa su un effetto di riduzione della varianza combinato con un'analisi del secondo ordine (basata sulla varianza) dell'algoritmo CEW.

1. Riduzione della Varianza tramite Saggio:
   In un round di saggio, l'algoritmo campiona due punti indipendentemente dalla densità di distribuzione corrente $p_t$. Giocando il punto con la perdita osservata minore (o quello suggerito dal saggio), la perdita attesa diminuisce di un ammontare proporzionale alla varianza della funzione di perdita sotto $p_t$, denotata $v_t = \text{Var}_{x \sim p_t}[f_t(x)]$. Specificamente, per saggi senza rumore, la perdita attesa è ridotta da $v_t$.

2. Gestione dei Saggi Noiosi (Meta-Learner):
   Poiché $\delta$ è ignoto, l'algoritmo impiega un Meta-Learner leggero (specificamente AdaHedge) per decidere se "seguire" il suggerimento del saggio o "invertirlo". Il Meta-Learner opera su due azioni: $F$ (follow/segui) e $I$ (invert/inverti). Esso aggiorna i propri pesi in base alle perdite incorse da queste due azioni ipotetiche nei round di saggio. Ciò consente all'algoritmo di fidarsi adattivamente del saggio quando è informativo ($\delta$ lontano da $1/2$) e di ignorarlo quando non lo è.

3. Decomposizione del Regret:
   L'analisi del regret decompone la perdita totale in due componenti:

   • Round non di saggio: L'algoritmo segue lo standard aggiornamento CEW. Il regret è limitato usando un'analisi del secondo ordine (seguendo de Rooij et al., 2014) che mette in relazione il regret di base con la varianza cumulativa $V_T = \sum v_t$.
   • Round di saggio: La perdita è limitata dalla perdita della migliore delle due azioni del Meta-Learner ($F$ o $I$), più un termine di regret per il Meta-Learner stesso. L'analisi mostra che la "migliore" azione ottiene una riduzione della perdita proporzionale a $|1-2\delta|v_t$.

Risultati Chiave
L'articolo stabilisce che un budget sublineare di saggi a coppie noiosi può migliorare provabilmente il regret nel caso peggiore nel regime di full-feedback di OCO.

• Per Perdite Convesse Generali: Per perdite convesse generali limitate in $[0, 1]$ su un insieme convesso $K \subseteq \mathbb{R}^d$, il regret atteso è:
  $$\text{Reg}_T \le O\left( \min\left\{ \sqrt{dT \ln T}, \frac{dT \ln T}{k |1 - 2\delta|} \right\} \right)$$
  Questo limite è stretto (fino a fattori logaritmici in $T$) rispetto all'orizzonte $T$, al budget di saggio $k$ e al parametro di rumore $\delta$. Il regret degrada fluidamente quando $\delta \to 1/2$ (lancio di moneta).

• Predizione con Esperti: Nel caso speciale del setting degli esperti (perdite lineari sui vertici del simplesso $\Delta^{d-1}$), il limite migliora in:
  $$\text{Reg}_T \le O\left( \min\left\{ \sqrt{T \ln d}, \frac{T \ln d}{k |1 - 2\delta|} \right\} \right)$$
  Questi tassi sono completamente stretti in tutti i parametri, inclusa la dimensione $d$.

Significatività e Contributi
Gli autori rivendicano diversi contributi significativi:

1. Unificazione: Il lavoro unifica il modello di saggio del "miglior esperto" discreto e il modello di "confronto a coppie" continuo in un unico framework, dimostrando che i saggi a coppie sono informativi quanto i saggi del miglior esperto per ottenere tassi di regret ottimali.
2. Robustezza al Rumore: A differenza di lavori precedenti che spesso assumono modelli di rumore privi di rumore o specifici, questo framework gestisce livelli di rumore ignoti $\delta$ e ottiene una dipendenza ottimale da $|1-2\delta|$.
3. Novità Tecnica: L'analisi evita la strumentazione della privacy differenziale e le assunzioni riguardanti le norme dei gradienti o la curvatura (che erano richieste in lavori precedenti come Bhaskara et al., 2023b). Invezione, sfrutta un argomento di riduzione basato sulla varianza.
4. Ottimalità: L'articolo fornisce limiti inferiori corrispondenti (nell'Appendice A) mostrando che i tassi derivati sono stretti per il setting degli esperti e stretti in $T, k, \delta$ per insiemi convessi generali.

Gli autori notano che, sebbene le garanzie teoriche siano forti, l'algoritmo principale richiede il calcolo di integrali su insiemi convessi, il che può essere computazionalmente difficile in generale. Identificano lo sviluppo di algoritmi efficienti che raggiungano garanzie comparabili come una direzione aperta.