A regret minimization approach to fixed-point iterations
This work provides a novel framework for fixed-point iterations with adaptive guarantees, potentially benefiting optimization and machine learning applications.
The authors tackled the problem of finding fixed points of non-self operators by converting regret-minimizing algorithms into fixed-point iterations with convergence guarantees, resulting in AdaGrad-based iterations that demonstrated faster convergence than classical methods in numerical experiments.
We propose a conversion scheme that turns regret minimizing algorithms into fixed point iterations, with convergence guarantees following from regret bounds. The resulting iterations can be seen as a grand extension of the classical Krasnoselskii--Mann iterations, as the latter are recovered by converting the Online Gradient Descent algorithm. This approach yields new simple iterations for finding fixed points of non-self operators. We also focus on converting algorithms from the AdaGrad family of regret minimizers, and thus obtain fixed point iterations with adaptive guarantees of a new kind. Numerical experiments on various problems demonstrate faster convergence of AdaGrad-based fixed point iterations over Krasnoselskii--Mann iterations.