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

The gist: We introduce a principled learning to optimize (L2O) framework for solving fixed-point problems involving general nonexpansive mappings by deliberately injecting summable perturbations into standard Krasnosel’skii–Mann iteration to improve its average-case performance over a specific distribution of problems while retaining its convergence guarantees.

Learning to Optimize (L2O) Framework

The paper introduces an L2O framework for learning fixed points of general nonexpansive mappings, inspired by Martin et al. (2025) and building on well-known quasi-Fej´er monotonicity results for inexact KM iterations. This framework uses machine learning (ML) to automate the design of solution methods tailored to problem instances observed during training. Instead of hand-crafting acceleration schemes based on complex analyses of their worst-case rates, this paradigm uses NN parametrizations to learn the structure underlying specific families of parametric problems. The goal is formalized as minimizing MetaLoss(Sθ, Tθ, x) subject to asymptotic regularity and convergence desiderata.

Characterization of Convergent Iterations

Under a metric sub-regularity assumption, the authors prove that the proposed parametrization encompasses only iterations that converge linearly—up to a vanishing bias term—in a neighborhood of a fixed point, and that it includes all iterations that do so at a sufficiently fast rate. Proposition 3 shows that different feasible solutions Sθ(Tθ, x) for (7) can be obtained by perturbing the KM iteration with a summable augmentation term v ∈ l 1 n. The authors show that not all iterations Sθ complying with (5) and (6) correspond to a specific choice of v ∈ l 1 n in (8).

Application to Operator Splitting Methods

The results enable learning perturbations to several operator splitting methods, such as the Davis–Yin splitting. Theorem 7 demonstrates that introducing summable perturbations in the updates of (14) preserves the convergence guarantees of (13). This means that for monotone inclusion problems, the iteration defined by (14) converges to a solution if the sequence v defined by (16) is summable. The framework extends naturally to augmenting any algorithm that can be derived as a special case of the Davis–Yin splitting.

Validation and Experimental Results

The theoretical results are validated by numerical experiments on a best approximation problem using an L2O-augmented Douglas–Rachford (DR) splitting algorithm. In the experiment, the authors introduce a trainable perturbation v t z in (19c), resulting in iterations (20a)-(20c). The training involves minimizing the sample average approximation of the residuals using Adam to minimize empirical weighted sum of residuals. Figure 1 shows that the proposed method learns to slide along the surface of the sphere, achieving modest accuracy solutions after a small number of iterations only. Figure 2 reports the average distance between the solution and shadow iterates computed over 1024 independent realizations of p ∼ P.

Conclusion

We have proposed learning parametrized summable perturbations to standard KM iterations to enhance their average-case performance on a set of training problems through automatic differentiation while guaranteeing convergence by design. We have formally analyzed the expressiveness of the proposed parametrization under a mild regularity assumption, and we have showcased the broad applicability and potential of our framework by augmenting several widely-used operator splitting methods. Important avenues for future research include extensions to stochastic fixed-point iterations and applications to equilibrium-seeking algorithms in multi-player games.

--- Page 1 ---

Learning to accelerate Krasnosel’skii–Mann fixed-point iterations with guarantees⋆ Andrea Martin∗ Giuseppe Belgioioso∗ Division of Decision and Control Systems, KTH Royal Institute of Technology, and Digital Futures, SE-100 44 Stockholm, Sweden (e-mail:

--- Page 2 ---

Abstract: We introduce a principled learning to optimize (L2O) framework for solving fixed-point problems involving general nonexpansive mappings. Our idea is to deliberately inject summable perturbations into a standard Krasnosel’skii–Mann iteration to improve its average-case performance over a specific distribution of problems while retaining its convergence guarantees. Under a metric sub-regularity assumption, we prove that the proposed parametrization includes only iterations that locally achieve linear convergence—up to a vanishing bias term—and that it encompasses all iterations that do so at a sufficiently fast rate. We then demonstrate how our framework can be used to augment several widelyused operator splitting methods to accelerate the solution of structured monotone inclusion problems, and validate our approach on a best approximation problem using an L2O-augmented Douglas–Rachford splitting algorithm. Keywords: Krasnosel’skii–Mann iterations, fixed-point iterations, learning to optimize, amortized optimization, monotone inclusions, convex optimization, neural networks

--- Page 3 ---

3. MAIN RESULTS In this section, we characterize a class of inexact KM iterations in the form (3) that guarantee convergence to a solution of (1), as per Definition 2. Under an additional metric sub-regularity assumption, we then prove that our parametrization encompasses only iterations that converge linearly—up to a vanishing bias term—in a neighborhood of a fixed point, and that it includes all iterations that do so at a sufficiently fast rate. Finally, we show how our results enable learning perturbations to several operator splitting methods to improve their average-case performance while preserving their convergence guarantees.

--- Page 4 ---

Example 4. Let Tθ = 0 be the zero operator. Note that this choice satisfies Assumption 1 as, for every θ ∈ Θ, the operator Tθ is nonexpansive and fixTθ =

--- Page 5 ---

In our experiments, we consider an instance of (17) where C1 is a sphere and C2 is a linear subspace that is nearly parallel to the tangent space to the sphere at any point in C1 ∩ C2. We assume that the points p ∈ R 3 are randomly generated from a uniform distribution P over the cube [0.25, 0.75]3, and define (7a) as the expected weighted sum of the residuals z t+1 − z t over t ∈ N when p ∼ P.

--- Page 6 ---

Fig. 1 Comparison between the evolution of the first 20 shadow iterates x t and y t generated by (19) and (20). The orange point indicates the query point to be projected, and the shaded orange crosses denote the training samples.

--- Page 7 ---

Fig. 2 Evolution of the distance between the solution of (17) and the shadow iterates x t in (19a) and (20a) computed over 1024 independent realizations of p ∼ P.

--- Page 8 ---

REFERENCES Amos, B. et al. (2023). Tutorial on amortized optimization. Foundations and Trends® in Machine Learning, 16(5), 592–732 Banert, S., Rudzusika, J., Oktem, O., and Adler, J. (2024). Accelerated forward-backward optimization using deep learning. SIAM Journal on Optimization, 34(2), 1236–1263 Bauschke, H.H. and Combettes, P.L. (2017). Convex analysis and monotone operator theory in Hilbert spaces Springer Bauschke, H.H., Noll, D., and Phan, H.M. (2015). Linear and strong convergence of algorithms involving averaged nonexpansive operators Journal of Mathematical Analysis and Applications 421(1), 1–20 Belgioioso, G., Yi, P., Grammatico, S., and Pavel, L. (2022). Distributed generalized Nash equilibrium seeking: An operator-theoretic perspective IEEE Control Systems Magazine 42(4), 87–102 Bot, R.I. and Nguyen, D.K. (2023). Fast Krasnosel’ski˘ıMann algorithm with a convergence rate of the fixed point iteration of o 1k SIAM Journal on Numerical Analysis, 61(6), 2813–2843 Briceno-Arias, L.M. and Combettes, P.L. (2013). Monotone operator methods for Nash equilibria in nonpotential games In Computational and Analytical Mathematics: In Honor of Jonathan Borwein’s 60th Birthday, 143–159 Springer Celestini, D., Gammelli, D., Guffanti, T., D’Amico, S., Capello, E., and Pavone, M. (2024). Transformer-based model predictive control: Trajectory optimization via sequence modeling IEEE Robotics and Automation Letters

--- Page 9 ---

Sacks, J. and Boots, B. (2022). Learning to optimize in model predictive control In 2022 International Conference on Robotics and Automation (ICRA), 10549–10556 IEEE Heaton, H., Chen, X., Wang, Z.

1. textbfReal-time Adaptive Learning for Fixed-Point Problems: The L2O Framework Application in Control Systems and Robotics Engine Design EnginesEngine design engines can now automatically learn optimal control laws by augmenting standard Krasnosel’skii–Mann iterations with summable perturbations to improve average-case performance while retaining convergence guarantees. This means the system can achieve high-accuracy solutions faster on a specific distribution of problem parameters, such as varying system states in model predictive control scenarios, without sacrificing formal stability.

2. textbfAccelerated Monotone Inclusion Solvers: Augmenting Splitting Methods for Optimization EnginesOptimization solvers for structured monotone inclusion problems can be accelerated by learning parametrized perturbations to algorithms like the Davis–Yin splitting. This allows the solver to learn augmentations that accelerate convergence, enabling faster computation of solutions in complex multi-variable constraints.

3. textbfGuaranteed Fast Convergence Characterization: Parametrization of Iterations for Linear ConvergenceEngine design can be improved by using neural network parametrizations to characterize iterations that locally achieve linear convergence—up to a vanishing bias term—and that it encompasses all iterations that do so at a sufficiently fast rate. This ensures the learned update rules are theoretically sound for achieving high-speed convergence near fixed points.

We introduce a principled learning to optimize (L2O) framework for solving fixed-point problems involving general nonexpansive mappings. Our idea is to deliberately inject summable perturbations into a standard Krasnosel'skii-Mann iteration to improve its average-case performance over a specific distribution of problems while retaining its convergence guarantees. Under a metric sub-regularity assumption, we prove that the proposed parametrization includes only iterations that locally achieve linear convergence-up to a vanishing bias term-and that it encompasses all iterations that do so at a sufficiently fast rate. We then demonstrate how our framework can be used to augment several widely-used operator splitting methods to accelerate the solution of structured monotone inclusion problems, and validate our approach on a best approximation problem using an L2O-augmented Douglas-Rachford splitting algorithm.