Direct Acceleration of Stochastic Root-Finding Without Variance Reduction and Regularization
Di cosa parla
Un metodo alternativo per accelerare algoritmi che cercano radici (trovare un valore che annulla una funzione) o punti fissi (un valore che resta invariato sotto una trasformazione) è stato adattato al caso in cui i calcoli sono rumorosi perché basati su dati casuali. Diversamente dalle versioni precedenti, questo approccio ottiene accelerazione senza ricorrere a tecniche che riducono la variabilità dei risultati o ad aumentare la quantità di dati usata per ogni passo.
Cosa permette di osservare
Fa riflettere su se sia possibile velocizzare metodi che operano su dati rumorosi senza complicare il processo aumentando i dati o introducendo fasi di correzione, e invita a confrontare diverse strategie di accelerazione in scenari pratici con rumore.
Dalla fonte
Acceleration for deterministic root-finding problems has been extensively studied in recent years; specifically, the anchor-based, or Halpern-type methods achieve optimal convergence rates with respect to the operator norm. However, acceleration via these methods does not directly carry over to stochastic setting due to accumulation of errors, unless one enforces diminishing variance via increasing batch sizes or variance reduction techniques. In this work, we show that another class of acceleration, namely the dual-anchor mechanism, extends to the stochastic setting without such error accumulation, in contrast to anchor-based algorithms. Consequently, we cleanly achieve $O(\epsilon^{-3})$ complexity with iteration-independent batch size, without any variance reduction or double-loop recursive regularization, for stochastic root-finding (resp. fixed-point) problems with cocoercivity (re…