Quando è sostenibile l’inseguimento? Una soglia di fattibilità con budget di movimento per il regret dinamico

Abstract degli autori

Il regret dinamico misura le prestazioni di un algoritmo online rispetto a un comparatore in movimento, e le analisi standard presuppongono che l’algoritmo possa muoversi liberamente a ogni round. Studiamo cosa accade quando non può farlo: all’algoritmo viene imposto un budget rigido $S$ per il movimento totale $\sum_t \|x_t - x_{t-1}\|$. Il nostro risultato principale è che un budget di movimento crea una barriera di fattibilità. Su un dominio di diametro $D$ con perdite convesse $G$-Lipschitz, per ogni lunghezza del percorso del comparatore $P_T \in [D, DT]$ mostriamo che un avversario deterministico può imporre un regret $R_d = Ω(GDT)$ a qualsiasi algoritmo che rispetti il budget, ogni volta che $S \le c P_T$ per una costante universale $c>0$. Questa barriera è causata dal budget, non da un ambiente volatile: a $D$ fissato, si applica quando $P_T = o(T)$, nel qual caso il tasso minimax senza vincoli $Θ(G\sqrt{D(D+P_T)T})$ è sublineare, perciò le stesse istanze sono apprendibili con un budget illimitato e non apprendibili quando il budget è vincolato. Viceversa, la discesa del gradiente online proiettata, con un passo che tiene conto del budget, rispetta il vincolo di budget e raggiunge $o(GDT)$ quando $S = ω(D + P_T)$. La scala critica del movimento è quindi $D+P_T$: il regret lineare è inevitabile al di sotto di un multiplo costante sufficientemente piccolo di $P_T$, mentre il regret sublineare è ottenibile quando $S/(D+P_T)\to\infty$ nel regime apprendibile. La costruzione si basa su una distinzione che rendiamo esplicita: ciò che rende costoso seguire un comparatore con un budget di movimento è la distanza che costringe l’algoritmo a percorrere, non la lunghezza del suo percorso. Al di sopra della soglia forniamo un limite superiore dipendente dal budget e indichiamo come problema aperto il tasso minimax ottimale in questa regione, anziché sostenere che valga una legge di prodotto. Gli esperimenti confermano la posizione prevista della transizione e il decadimento $1/S$.