← Back to all news
arXiv Machine Learning

A regret minimization approach to fixed-point iterations

The paper introduces a conversion scheme that transforms regret-minimizing algorithms into fixed-point iterations, providing convergence guarantees derived from regret bounds. This framework generalizes the classical Krasnoselskii–Mann iterations, recovering them when applying Online Gradient Descent. By converting AdaGrad-based regret minimizers, the authors obtain new fixed-point iterations with adaptive guarantees, and numerical experiments show these AdaGrad-based iterations converge faster than traditional Krasnoselskii–Mann iterations.

Related stories

arXiv Machine Learning
Oct 12

Learning to accelerate Krasnosel'skii-Mann fixed-point iterations with guarantees

The paper presents a learning-to-optimize (L2O) framework that injects summable perturbations into Krasnosel'skii-Mann iterations to accelerate solving fixed-point problems with nonexpansive mappings. It proves that, under metric sub-regularity, the parametrized iterations achieve local linear convergence with a vanishing bias and include all fast-converging iterations. The framework is applied to enhance operator splitting methods, such as Douglas‑Rachford, and is validated on a best‑approximation problem.

By Andrea Martin, Giuseppe Belgioioso
safety
More like this →
arXiv Machine Learning
Jun 18

Stochastic Adaptive Gradient Descent Without Descent

arXiv:2509. 14969v2 Announce Type: replace Abstract: We introduce a new adaptive step-size strategy for convex optimization with stochastic gradient that exploits the local geometry of the objective function only by means of a first-order stochastic oracle and without any hyper-parameter tuning.

By Jean-Fran\c{c}ois Aujol, J\'er\'emie Bigot, Camille Castera
More like this →
arXiv AI
Sep 21

Matrix AdaGrad: Row-wise and Column-wise Adaptive Subgradient Methods

The paper introduces Row-wise Matrix AdaGrad and Column-wise Matrix AdaGrad, two adaptive subgradient methods that extend AdaGrad to matrix-valued parameters by using row-wise and column-wise proximal functions. It presents a general Online Mirror Descent framework that derives these optimizers through online regret minimization, providing regret guarantees that can be tighter than entry-wise AdaGrad for structured gradients. Experiments on matrix factorization and deep neural-network training show that aligning adaptive scaling with matrix structure improves optimization stability, allows larger learning rates, and supports greater network depth.

By Wenpeng Zhang, Runsheng Yu, Peilin Zhao
More like this →
arXiv Statistics ML
Oct 12

Provable Parameter-Free Fixed-Point Algorithms with Linear Convergence Rates

The paper introduces two parameter‑free Halpern fixed‑point algorithms that automatically exploit hidden contractivity without needing a prior estimate of the contraction factor. Both methods achieve explicit linear convergence rates for the fixed‑point residual and distance to the unique fixed point, with one variant using a line‑search to locally estimate the contraction factor. Extensions include parameter‑free Nesterov‑type variants and a Tikhonov‑regularized approach for cocoercive equations, yielding an iteration complexity of \(\mathcal{O}(\epsilon^{-1}\log(\epsilon^{-1}))\).

By Quoc Tran-Dinh, Pham Ngoc Anh, Ha Manh Tien
More like this →
arXiv Machine Learning
Aug 18

Online Convex Optimization with Dueling Feedback

arXiv:2608. 15050v1 Announce Type: new Abstract: We study online convex optimization with dueling (pairwise comparison) feedback, where the learner observes only a binary preference between two queried points.

By Yiyang Lu, Hareshkumar Jadav, Mohammad Pedramfar, Ranveer Singh, Vaneet Aggarwal
safety
More like this →