On the Convex Interpolation for Linear Operators

Nizar Bousselmi, Zhicheng Deng, Jie Lu, François Glineur, Julien M. Hendrickx · 2025

Read On the Convex Interpolation for Linear Operators by Nizar Bousselmi, Zhicheng Deng, Jie Lu, François Glineur, Julien M. Hendrickx (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-16360.txt.

Introduction

Nizar Bousselmi and four co-authors study interpolation conditions for linear operators, the finite tests that say whether a set of observed inputs and outputs could come from a given class of operators. Such conditions underpin worst-case performance analysis of optimization methods.

The authors first show a limit. With only convex constraints on scalar products, one can characterize just those classes whose singular values or eigenvalues lie in a fixed subset of the real line. They then give new interpolation conditions for operators with bounded smallest and largest singular values, and for values lying in unions of subsets. The conditions are used to analyze the gradient method and the Chambolle-Pock method, producing new numerical worst-case guarantees for both.

Catalog record

CREATORNizar Bousselmi, Zhicheng Deng, Jie Lu, François Glineur, Julien M. Hendrickx
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-16360

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Convex Interpolation for Linear Operators Nizar Bousselmi, Zhicheng Deng, Jie Lu, François Glineur, Julien M. Hendrickx Abstract The worst-case performance of an optimization method on a problem class can be analyzed using a finite description of the problem class, known as interpolation conditions. In this work, we study interpolation conditions for linear operators given scalar products between discrete inputs and outputs. First, we show that if only convex constraints on the scalar products of inputs and outputs are allowed, it is only possible to characterize classes of linear operators or symmetric linear operator whose all singular values or eigenvalues belong to some subset of ℝ \mathbb{R} . Then, we propose new interpolation conditions for linear operators with minimal and maximal singular values and linear operators whose eigenvalues or singular values belong to unions of subsets. Finally, we illustrate the new interpolation conditions through the analysis of the Gradient and Chambolle-Pock methods. It allows to obtain new numerical worst-case guarantees on these methods. keywords Linear operator, Convex interpolation, Worst-case analysis, Performance estimation problem † † equal-contributors: These authors contributed equally to this work. † † equal-contributors: These authors contributed equally to this work. 1 Introduction One recent way to analyze the worst-case performance of a given optimization method on a given function class is the well-developed Performance Estimation Problem (PEP) framework Drori and Teboulle 2014 ; Taylor et al. 2017 . It formulates the problem of computing the worst-case performance of the method on the class as an optimization problem and then solves it. The framework relies on interpolation conditions of the function classes considered Rubbens and Hendrickx 2024 ; Goujaud et al. 2023 (such interpolation conditions can serve larger purposes). Worst-case guarantees are built up by combining inequalities between specific points of the domain characterizing the function class. In some sense, interpolation conditions of a function class are the best description of this class. Analyzing the performance of optimization methods on problems of the form \min_{x}g(Mx) or \min_{x}f(x)+g(Mx) where f\in\mathcal{F} , g\in\mathcal{G} , and M\in\mathcal{M} with PEP requires interpolation conditions for the function classes \mathcal{F} and \mathcal{G} and linear operator class \mathcal{M} (see Taylor et al. 2017 ; Bousselmi et al. 2024a for more details). We will focus on the interpolation of linear operators defined as follows. Definition 1.1 (Operator interpolability) . Given a class of linear operators \mathcal{M} , the sets of pairs \{(x_{i},y_{i})\}_{i\in[N_{1}]} and \{(u_{j},v_{j})\}_{j\in[N_{2}]} are \mathcal{M} -interpolable if \exists M\in\mathcal{M}~:\begin{cases}y_{i}=Mx_{i},&\forall i\in[N_{1}]\\ v_{j}=M^{T}u_{j},&\forall j\in[N_{2}]\end{cases} (1) \chreplaced [id=D,comment=]While given sets of points \{(x_{i},y_{i})\}_{i\in[N_{1}]} and \{(u_{j},v_{j})\}_{j\in[N_{2}]} , this question can often easily be solved by computing M explicitly, the PEP methodology requires an explicit description of the whose sets of points for which the desired interpolable property holds. Interpolation conditions are necessary and sufficient constraints on the set of points \{(x_{i},y_{i})\}_{i\in[N_{1}]} and \{(u_{j},v_{j})\}_{j\in[N_{2}]} guaranteeing their interpolability. A previous work Bousselmi et al. 2024a , developed interpolation conditions for the classes of linear operators with singular values in [0,L] , \mathcal{L}_{[0,L]} , and for symmetric linear operators with eigenvalues in [\mu,L] , \mathcal{S}_{[\mu,L]} , with \mu\leq L . Formally, given subset S\subseteq\mathbb{R} , we denote \displaystyle\mathcal{L}_{S} \displaystyle=\{M:\sigma_{i}(M)\in S,~\forall i\} (2) \displaystyle\mathcal{S}_{S} \displaystyle=\{M\text{ is symmetric }:\lambda_{i}(M)\in S,~\forall i\} (3) where \sigma_{i}(M) and \lambda_{i}(M) are the singular values and eigenvalues of M . Given the sets of pairs \{(x_{i},y_{i})\}_{i\in[N_{1}]} and \{(u_{j},v_{j})\}_{j\in[N_{2}]} where x_{i},u_{j}\in\mathbb{R}^{n},v_{j},y_{i}\in\mathbb{R}^{m} , we denote X=(x_{1}~\cdots~x_{N_{1}}) , Y=(y_{1}~\cdots~y_{N_{1}}) , U=(u_{1}~\cdots~u_{N_{2}}) , V=(v_{1}~\cdots~v_{N_{2}}) . Interpolation conditions for \mathcal{L}_{[0,L]} and \mathcal{S}_{[\mu,L]} -interpolability are the following Bousselmi et al. 2024a (there also exist interpolation conditions for skew-symmetric linear operators ( Bousselmi et al. 2024a , Corollary 3.2) ). Theorem 1.1 ( \mathcal{L}_{[0,L]} -interpolation conditions, Theorem 3.1 of Bousselmi et al. 2024a ) . Given L\geq 0 . The sets of pairs \{(x_{i},y_{i})\}_{i\in[N_{1}]} and \{(u_{j},v_{j})\}_{j\in[N_{2}]} are \mathcal{L}_{[0,L]} -interpolable if, and only if, \displaystyle\begin{split}\begin{cases}X^{T}V=Y^{T}U,\\ Y^{T}Y\preceq L^{2}X^{T}X,\\ V^{T}V\preceq L^{2}\>U^{T}U.\end{cases}\end{split} (4) Theorem 1.2 ( \mathcal{S}_{[\mu,L]} -interpolation conditions, Theorem 3.3 of Bousselmi et al. 2024a ) . Given \mu\leq L . The set \{(x_{i},y_{i})\}_{i\in[N_{1}]} is \mathcal{S}_{[\mu,L]} -interpolable if, and only if, \displaystyle\begin{split}\begin{cases}X^{T}Y=Y^{T}X,\\ (Y-\mu X)^{T}(LX-Y)\succeq 0.\end{cases}\end{split} (5) Thanks to these interpolation conditions and PEP, new worst-case guarantees were obtained on the Gradient and Chambolle-Pock methods ( Bousselmi et al. 2024a , Section 4) , Condat-Vũ methods Bousselmi et al. 2024b , decentralized optimization Colla 2024 , min-max optimization Vasin et al. 2025 ; Krivchenko et al. 2024 and parametric quadratic optimization Ranjan and Stellato 2024 . Worst-case analysis and Gram representation Both classical worst-case analysis of optimization methods and PEP require algebraic characterizations of function classes Nesterov et al. 2018 ; Rubbens et al. 2023 , to obtain \chreplaced [id=D,comment=]guaranteed tight and unimprovable bounds. In this work, we focus on the PEP methodology. It appears that in a lot of cases, the problem of computing the worst-case performance of a given method on a given class of functions can be formulated as a convex problem Taylor et al. 2017 . A necessary condition for the PEP to be efficiently exploitable is that the interpolation conditions must be convex on the scalar products between points. We discuss interpolation conditions for linear operators. This convexity must hold on the elements of the following pair of Gram matrices when considering classes of general linear operators: (G,H)=\left(\mathrm{Gram}\begin{pmatrix}X&V\end{pmatrix},\mathrm{Gram}\begin{pmatrix}Y&U\end{pmatrix}\right)\triangleq\left(\begin{pmatrix}X&V\end{pmatrix}^{T}\begin{pmatrix}X&V\end{pmatrix},\begin{pmatrix}Y&U\end{pmatrix}^{T}\begin{pmatrix}Y&U\end{pmatrix}\right) (6) and the following Gram matrix when considering classes of (square) symmetric linear operators G=\mathrm{Gram}\begin{pmatrix}X&Y&U&V\end{pmatrix}\triangleq\begin{pmatrix}X&Y&U&V\end{pmatrix}^{T}\begin{pmatrix}X&Y&U&V\end{pmatrix} (7) \chreplaced [id=D,comment=] i.e. , all the scalar products whose existence is compatible with the dimensions. For instance, Theorem 1.1 (resp. 1.2 ) can be written as convex semi-definite constraints on G and H (resp. G ). In this work, we focus on interpolation conditions which are convex on the above Gram matrices G and H . We tackle the following two questions related to operator interpolability: 1. Which classes of linear operators can be represented by convex interpolation conditions on products between the points of the sets \{(x_{i},y_{i})\}_{i\in[N_{1}]} and \{(u_{j},v_{j})\}_{j\in[N_{2}]} ? 2. Is there a tractable form of interpolation conditions for \mathcal{L}_{[\mu,L]} when \mu>0 ? We here propose answers to these questions. Contributions and outline of the paper In Section 2 , we show that when restricted to convex constraints on the Gram matrices of the inputs and outputs, we can only characterize classes of linear and symmetric linear operators of the forms ( 2 ) and ( 3 ) (i.e., classes of linear operators for which the singular values or eigenvalues belong to a given set) (Theorem 2.4 ). For example, it is impossible to characterize the class of symmetric linear operators for which the sum of singular values is equal to a given number with convex constraints on the scalar products. In Section 3 , we present interpolation conditions for the class of linear operators \mathcal{L}_{[\mu,L]} (Theorem 1.1 ). To obtain them, we rely on the polar decomposition that allows to express any linear operator as a product of a unitary and a symmetric linear operator for which we already knew interpolation conditions. In Section 4 , we propose interpolation conditions for linear operators whose singular values or eigenvalues belong to a union of subsets, extending thus Theorem 1.2 and 1.1 , and approaching the limitations derived in Section 2 . In Section 5 , we illustrate the application of our new interpolation conditions to analyze the worst-case

Read the complete text