On April 27, 2023 at 14:00 EEST, Andrei Sipoș (University of Bucharest & IMAR & ILDS) will give a talk in the Logic Seminar.
Title: The computational content of super strongly nonexpansive mappings and uniformly monotone operators
Abstract:
Strongly nonexpansive mappings are a core concept in convex optimization. Recently, they have begun to be studied from a quantitative viewpoint: U. Kohlenbach has identified in [1] the notion of a ‘modulus’ of strong nonexpansiveness, which leads to computational interpretations of the main results involving this class of mappings (e.g. rates of convergence, rates of metastability). This forms part of the greater research program of ‘proof mining’, initiated by G. Kreisel and highly developed by U. Kohlenbach and his collaborators, which aims to apply proof-theoretic tools to extract computational content from ordinary proofs in mainstream mathematics. The quantitative study of strongly nonexpansive mappings has later led to finding rates of asymptotic regularity for the problem of ‘inconsistent feasibility’ [2, 5], where one essential ingredient has been a computational counterpart of the concept of rectangularity, recently identified in [3] as a ‘modulus of uniform rectangularity’.
Last year, Liu, Moursi and Vanderwerff [4] have introduced the class of ‘super strongly nonexpansive mappings’, and have shown that this class is tightly linked to that of uniformly monotone operators. What we do is to provide a modulus of super strong nonexpansiveness, give examples of it in the cases e.g. averaged mappings and contractions for large distances and connect it to the modulus of uniform monotonicity. In the case where the modulus is supercoercive, we give a refined analysis, identifying a second modulus for supercoercivity, specifying the necessary computational connections and generalizing quantitative inconsistent feasibility.
The results in this talk (and additional references) may be found in the paper [6].
References:
[1] U. Kohlenbach, On the quantitative asymptotic behavior of strongly nonexpansive mappings in Banach and geodesic spaces. Israel Journal of Mathematics 216, no. 1, 215–246, 2016.
[2] U. Kohlenbach, A polynomial rate of asymptotic regularity for compositions of projections in Hilbert space. Foundations of Computational Mathematics 19, no. 1, 83–99, 2019.
[3] U. Kohlenbach, N. Pischke, Proof theory and non-smooth analysis. Philosophical Transactions of the Royal Society A 381, Issue 2248, 20220015 [21 pp.], 2023.
[4] L. Liu, W. M. Moursi, J. Vanderwerff, Strongly nonexpansive mappings revisited: uniform monotonicity and operator splitting. arXiv:2205.09040 [math.OC], 2022.
[5] A. Sipoș, Quantitative inconsistent feasibility for averaged mappings. Optimization Letters 16, no. 6, 1915–1925, 2022.
[6] A. Sipoș, The computational content of super strongly nonexpansive mappings and uniformly monotone operators. arXiv:2303.02768 [math.OC], 2023.
The talk will take place physically at FMI (Academiei 14), Hall 214 “Google”.