Riemannian conditional gradient methods for composite optimization problems

The conditional gradient (CG) method, also known as the Frank-Wolfe algorithm, is a first-order iterative method, widely used for solving constrained nonlinear optimization problems. Developed by Frank and Wolfe in 1956 [1], the CG method addresses the problem of minimizing a convex function over a convex constraint set, particularly when the constraint set is difficult, in the sense that the projection onto it is computationally demanding.

The convergence rate of $\mathcal{O}(1/k)$, where $k$ denotes the number of iterations, for the conditional gradient method has been presented in several studies [2, 3]. Recent advancements in the field have focused on accelerating the method [4, 5]. The versatility of this method is also clear, since many applications can be found in the literature (see, for instance, [6, 7]). Furthermore, the CG method has recently been extended to multiobjective optimization [8, 9, 10].

Meanwhile, composite optimization problems, where the objective function can be decomposed into the sum of two functions, have become increasingly important in modern optimization theory and applications. Specifically, the objectives of these problems take the form $F(x):=f(x)+g(x)$, where $f$ is a smooth function and $g$ is a possibly non-smooth and convex function. This structure arises naturally in many areas, including machine learning and signal processing, where $f$ often represents a data fidelity term and $g$ serves as a regularization term to promote desired properties such as sparsity or low rank [11, 12, 13].

To deal with such problems efficiently, various methods have been developed. Classical approaches include proximal gradient methods [14, 15, 16], which address the non-smooth term $g$ using proximal operators, and accelerated variants such as FISTA [17]. Other methods, such as the alternating direction method of multipliers (ADMM) [18], decompose the problem further to enable parallel and distributed computation. For problems with specific structures or manifold constraints, methods like the Riemannian proximal gradient have been proposed in [19, 20], extending proximal techniques to non-Euclidean settings. Recently, the CG method in Riemannian manifolds has been proposed in [21], and the CG method for composite functions, called the generalized conditional gradient (GCG) method, has also been discussed in many works [9, 22, 23, 24].

In this paper, we propose GCG methods on Riemannian manifolds, with general retractions and vector transport. We also focus on three types of step-size strategies: adaptive, diminishing, and those based on the Armijo condition. We provide a detailed discussion on the implementation of subproblem solutions for each strategy. For each step-size approach, we analyze the convergence of the method. Specifically, for the adaptive and diminishing step-size strategies, we establish a convergence rate of $\mathcal{O}(1/k)$, where $k$ represents the number of iterations. For the Armijo step size strategy, we derive an iteration complexity of $\mathcal{O}(1/\epsilon^{2})$, where $\epsilon$ represents the desired accuracy in the optimality condition.

This paper is organized as follows. In Section 2, we review fundamental concepts and results related to Riemannian optimization. In Section 3, we introduce the generalized conditional gradient method on Riemannian manifolds with three different types of step size. Section 4 presents the convergence analysis, while Section 5 focuses on the discussion of the subproblem. Section 6 explores the accelerated version of the proposed method. Numerical experiments are presented in Section 7 to demonstrate the effectiveness of our approach. Finally, in Section 8, we conclude the paper and suggest potential directions for future research.

This section summarizes essential definitions, results, and concepts fundamental to Riemannian optimization [25]. The transpose of a matrix $A$ is denoted by $A^{T}$, and the identity matrix with dimension $\ell$ is written as $I_{\ell}$. A Riemannian manifold $\mathcal{M}$ is a smooth manifold equipped with a Riemannian metric, which is a smoothly varying inner product $\langle\eta_{x},\sigma_{x}\rangle_{x}\in\mathbb{R}$, defined on the tangent space at each point $x\in\mathcal{M}$, where $\eta_{x}$ and $\sigma_{x}$ are tangent vectors in the tangent space $T_{x}\mathcal{M}$. The tangent space at a point $x$ on the manifold $\mathcal{M}$ is denoted by $T_{x}\mathcal{M}$, while the tangent bundle of $\mathcal{M}$ is denoted as $T\mathcal{M}:=\{(x,d)\mid d\in T_{x}\mathcal{M},x\in\mathcal{M}\}$. The norm of a tangent vector $\eta\in T_{x}\mathcal{M}$ is defined by $\|\eta\|_{x}:=\sqrt{\langle\eta,\eta\rangle_{x}}$. When the norm and the inner product are written as $\|\cdot\|$ and $\langle\cdot,\cdot\rangle$, without the subscript, then they are the Euclidean ones. For a map $F\colon\mathcal{M}\rightarrow\mathcal{N}$ between two manifolds $\mathcal{M}$ and $\mathcal{N}$, the derivative of $F$ at a point $x\in\mathcal{M}$, denoted by $\mathrm{D}F(x)$, is a linear map $\mathrm{D}F(x)\colon T_{x}\mathcal{M}\rightarrow T_{F(x)}\mathcal{N}$ that maps tangent vectors from the tangent space of $\mathcal{M}$ at $x$ to the tangent space of $\mathcal{N}$ at $F(x)$. The Riemannian gradient $\operatorname{grad}f(x)$ of a smooth function $f\colon\mathcal{M}\rightarrow\mathbb{R}$ at a point $x\in\mathcal{M}$ is defined as the unique tangent vector at $x$ that satisfies the equation $\langle\operatorname{grad}f(x),\eta\rangle_{x}=\mathrm{D}f(x)[\eta]$ for every tangent vector $\eta\in T_{x}\mathcal{M}$. We also define the Whitney sum of the tangent bundle as $T\mathcal{M}\oplus T\mathcal{M}:=\left\{(\xi,d)\mid\xi,d\in T_{x}\mathcal{M},x\in\mathcal{M}\right\}$.

In Riemannian optimization, a retraction is employed to map points from the tangent space of a manifold back onto the manifold.

Depending on the problem and the specific properties of the manifold, different types of retractions can be utilized. Many Riemannian optimization algorithms employ a retraction that generalizes the exponential map on $\mathcal{M}$. For instance, assume that we have an iterative method generating iterates $\{x^{k}\}$. In Euclidean spaces, the update takes the form $x^{k+1}=x^{k}+t_{k}d^{k}$, while in the Riemannian case it is generalized as

where $d^{k}$ is a descent direction and $t_{k}$ is a step size.

Another essential concept is the vector transport, which is critical in Riemannian optimization to maintain the intrinsic geometry of the manifold during computations.

The adjoint operator of a vector transport $\mathcal{T}$, denoted by $\mathcal{T}^{\sharp}$, is a vector transport satisfying:

where $y=R_{x}(\eta_{x})$. The inverse operator of a vector transport, denoted by $\mathcal{T}_{\eta_{x}}^{-1}$, is a vector transport satisfying:

where id is the identity operator.

Note that a map $\mathcal{T}$ defined by $\mathcal{T}_{d}(\xi):=\mathrm{P}_{\gamma_{x,d}}^{1\leftarrow 0}(\xi)$ is also a vector transport, where $\mathrm{P}_{\gamma_{x,d}}^{1\leftarrow 0}$ is the parallel transport along the geodesic $\gamma_{x,d}(t):=\operatorname{Exp}_{x}(td)$ connecting $\gamma_{x,d}(0)=x$ and $\gamma_{x,d}(1)=\operatorname{Exp}_{x}(d)$ with the exponential map Exp as a retraction. Parallel transport is a specific case of vector transport that preserves the length and angle of vectors as they are transported along geodesics, thereby preserving the intrinsic Riemannian metric of the manifold exactly. In contrast, vector transport is a more general operation that allows for the movement of vectors between tangent spaces in a way that approximately preserves geometric properties, and it may not necessarily follow geodesics or maintain exact parallelism. If there is a unique geodesic between any two points in $\mathcal{X}\subset\mathcal{M}$, then the exponential map has an inverse $\operatorname{Exp}_{x}^{-1}\colon\mathcal{X}\rightarrow T_{x}\mathcal{M}$. This geodesic represents the unique shortest path and the geodesic distance between $x$ and $y$ in $\mathcal{X}$ is given by $\left\|\operatorname{Exp}_{x}^{-1}(y)\right\|_{x}=\left\|\operatorname{Exp}_{y}^{-1}(x)\right\|_{y}$.

Now, we define geodesic convexity sets and functions, $L$-smoothness, and related concepts on Riemannian manifolds as follows:

Considering the definition of geodesic convexity and defining the retraction through $\gamma$, we can easily obtain the following result.

A similar concept is defined below.

In this paper, we consider the following Riemannian optimization problem:

where $\mathcal{X}\subseteq\mathcal{M}$ is a compact geodesically convex set and $F\colon\mathcal{M}\rightarrow\mathbb{R}$ is a composite function with $f\colon\mathcal{M}\rightarrow\mathbb{R}$ being continuously differentiable and $g\colon\mathcal{M}\rightarrow\mathbb{R}$ being a closed, geodesically convex and lower semicontinuous (possibly nonsmooth) function. Here, we can also consider $F$ as an extended-valued function. All the analyses would still apply, but we omit the infinity for simplicity. Also, we make the following assumption.

As discussed in [26, Section 10.2], for general retractions, over some domain of $\mathcal{M}\times\mathcal{M}$ which contains all pairs $(x,x)$, the map $(x,y)\mapsto R_{x}^{-1}(y)$ can be defined smoothly jointly in $x$ and $y$. In this sense, we can say that the above assumption is reasonable.

Now, let us recall the CG method in the Euclidean space. Consider minimizing a convex function $\tilde{f}\colon\mathbb{R}^{n}\rightarrow\mathbb{R}$ over a convex compact set $\mathcal{X}\subseteq\mathbb{R}^{n}$. At each iteration $k$, the method solves a linear approximation of the original problem by finding a direction $s^{k}$ that minimizes the linearized objective function over the constraint set $\mathcal{X}$, i.e., $s^{k}=\arg\min_{s\in\mathcal{X}}\langle\nabla\tilde{f}(x^{k}),s\rangle.$ Then, it updates the current point $x^{k}$ using a step size $\lambda_{k}$ along the direction $s^{k}-x^{k}$, i.e., $x^{k+1}=x^{k}+\lambda_{k}(s^{k}-x^{k}).$ For composite functions of the form $\tilde{f}(x)=\tilde{h}(x)+\tilde{g}(x)$, where $\tilde{h}$ is smooth and $\tilde{g}$ is convex, the CG method can be adapted to handle the non-smooth term $\tilde{g}$. The update step becomes:

In this case, $s\mapsto\langle\nabla\tilde{h}(x^{k}),s\rangle+\tilde{g}(s)$ is the new objective function for the subproblem, which remains convex due to the convexity of $\tilde{g}$, compacity of $\mathcal{X}$ and the linearity of $\langle\nabla\tilde{h}(x^{k}),\cdot\rangle$. The convexity of $\mathcal{X}$ ensures that this subproblem also has a solution. The step size $\lambda_{k}$ can be chosen using various strategies. The CG method is particularly useful when the constraint set $\mathcal{X}$ is not an easy set, making projection-based methods computationally expensive.

The exponential map, the parallel transport, and specific step size are used in the Riemannian CG method proposed in [21]. Now we extend this approach to a more general framework for composite optimization problems, without specifying the retraction and the vector transport.

Our method is presented in Algorithm 1. In Step 1, we need to solve the subproblem (4), which, similarly to the Euclidean case, is related to the linear approximation of the objective functions. In Step 2, we compute the step size based on some strategies that we will mention later. In Step 3, we update the iterate by using some retraction. Note that if $u=x^{k}$ in (4), then $\left\langle\mathrm{grad}f(x^{k}),R^{-1}_{x^{k}}(u)\right\rangle_{x^{k}}+g(u)-g(x^{k})=0$, which implies that $\theta(x^{k})\leq 0$. And since $d(x^{k})=R^{-1}_{x^{k}}(p(x^{k}))$, the subproblem is equivalent to

In the subsequent sections, we will examine the convergence properties of the sequence generated by the Algorithm 1, specifically focusing on three distinct and rigorously defined strategies for step size determination, which is also discussed in [8], as elaborated below.  

Step 0. Set $\lambda_{k_{0}}=1$ and initialize $\ell\leftarrow 0$.

Step 1. If

then set $\lambda_{k}:=\lambda_{k_{\ell}}$ and return to the main algorithm.

Step 2. Find $\lambda_{k_{\ell+1}}\in\left[\omega_{1}\lambda_{k_{\ell}},\omega_{2}\lambda_{k_{\ell}}\right]$, set $\ell\leftarrow\ell+1$, and go to Step 1.

In this section, we will provide the convergence analysis for three types of step sizes. The following assumption will be used in the convergence results.

Since $\mathcal{X}$ is a compact set, we can assume without loss of generality that $\mathcal{X}=\mathrm{dom}(g)$ is a compact set, its diameter is finite and can be defined by

Additionally, we can derive the following proposition.

Now we present a result associated to general sequences of real numbers, which will be useful for our study of convergence and iteration complexity bounds for the CG method.