A non-linear conjugate gradient in dual space for $L_p$-norm regularized non-linear least squares with application in data assimilation

Abstract

Wanting to minimize a non-linear least squares function penalized with an $L_p$-norm, with $p\in (1,2)$, stemming from a 4DVar formulation of a data assimilation problem, we propose a modification of the non-linear conjugate gradient by making the iterations and the step search in the topological dual space of $L_p$. We prove the convergence of this new algorithm and look at its performance on a data assimilation setup based on the shallow-water equations where the use of such an $L_p$-norm regularization is justified.

Descent algorithms in dual space as mirror descent algorithms

[16] has pointed out the similarities between Banach algorithm that transport the iterates in the dual space or the direction in the primal space and what are referred as proximal algorithms, which are themselves similar to mirror descent algorithms. [17] provides a convergence analysis of these algorithms relying on an hypothesis of strong convexity. In order to show a similar convergence result based on the hypothesis of a p-convex space, we briefly summarize how these algorithms are connected.

The classical gradient descent update $x_{k+1} = x_k - \alpha _k \nabla f_k$ can be retrieved by minimizing

$$\begin{aligned} \mathcal {F}(x) = f_k + \alpha _k \langle \nabla f_k,x \rangle + \frac{1}{2}\Vert x - x_k\Vert _2^2, \end{aligned}$$

looking for a compromise between minimizing the local approximation of f around $x_k$ while not going too far from this point. Mirror descent algorithms consist in using a different distance, instead of $L_2$-norm, to better capture the geometry of the underlying space. Taking the distance $D(x,x_k) = \frac{1}{p} \Vert x - x_k \Vert _p^p$ leads to the Banach descent with transport of the gradient in the primal space. [17] has highlighted the benefits of using the Bregman distance $\Delta _h$ [6] associated with a strictly convex and differentiable function h: $\Delta _h(x,y) = h(y) - h(x) - \langle \nabla h(x), y-x\rangle$. The mirror descent update can then be written as:

$$\begin{aligned} x_{k+1} = \nabla h^* (\nabla h - \alpha _k \nabla f_k), \end{aligned}$$

(28)

with $h^*$ the Fenchel conjugate of f defined by $h^*(y) = \underset{x \in X}{\sup }\ \left( \langle x,y \rangle - h(x) \right)$.

The Banach descent with transport of the iterations in the dual space (9) is equivalent to (28) if $h = \frac{1}{p}\Vert \cdot \Vert _p^p$. We now adapt the result from [17] in the case of a p-convex space.

Theorem 5

Let $f: X \rightarrow \mathbb R$ convex, differentiable and X being p-convex as in Definition 3. The gradient descent in dual space, equivalent to a mirror descent with $h = \frac{1}{p}\Vert \cdot \Vert _p^p$, with a constant step $\alpha$ and a starting point $x_0$ produces iterations $x_1,..., x_N$ such that for all $\bar{x} \in X$:

$$\begin{aligned} {\sum _{k=0}^N \left( f_k - f(\bar{x}) \right) } \le \frac{1}{\alpha } \Delta _h(x_0,\bar{x}) + \underbrace{\frac{1}{q}(\frac{\alpha }{c_p})^{\frac{q}{p}} \sum _{k=0}^N \Vert \nabla f_k\Vert _q^q}_{\text {Regret term}}, \end{aligned}$$

which holds in particular when $\bar{x}$ is the minimum of f.

Proof

Let $k \in \mathbb N$ et $\Phi _k = \frac{1}{\alpha } \Delta _h(x_k,\bar{x})$. By definition of $\Delta _h$, and since $\nabla h(x) = J_p(x)$:

$$\begin{aligned} \begin{aligned} \Phi _{k+1} - \Phi _k&= \frac{1}{\alpha } [ h(\bar{x}) - h(x_{k+1}) - \langle \underbrace{\nabla h(x_{k+1})}_{ x_{k+1}^*}, \bar{x} - x_{k+1} \rangle - h(\bar{x}) + h(x_{k}) \\&\quad + \langle \underbrace{\nabla h(x_{k})}_{x_{k}^*}, \bar{x} - x_{k} \rangle ] \\&= \frac{1}{\alpha } [ h(x_{k}) - h(x_{k+1}) - \langle x_k^* - \alpha \nabla f(x_k), \bar{x} - x_{k+1} \rangle + \langle x_{k}^*, \bar{x} - x_{k} \rangle ] \\&= \frac{1}{\alpha } [ h(x_{k}) - h(x_{k+1}) - \langle J_p(x), x_k - x_{k+1} \rangle + \alpha \langle \nabla f(x_k) , \bar{x} - x_{k+1} \rangle ] \end{aligned} \end{aligned}$$

Using the definition of p-convex space and substituting x by $x_k$ and y by $x_k - x_{k+1}$:

$$\begin{aligned} \frac{1}{p} \Vert x_k\Vert _p^p - \frac{1}{p} \Vert x_{k+1}\Vert _p^p - \langle J_p(x_k),x_k - x_{k+1} \rangle \le - \frac{c_p}{p} \Vert x_k - x_{k+1} \Vert _p^p. \end{aligned}$$

Whence

$$\begin{aligned} \Phi _{k+1} - \Phi _k \le \frac{1}{\alpha } [- \frac{c_p}{p} \Vert x_k - x_{k+1} \Vert _p^p + \alpha \langle \nabla f(x_k) , \bar{x} - x_{k+1} \rangle ]. \end{aligned}$$

We then have:

$$\begin{aligned} \begin{aligned} f_k \!-\! f(\bar{x}) \!+\! (\Phi _{k+1} \!-\! \Phi _k)&\le f_k - f(\bar{x}) - \frac{c_p}{\alpha p} \Vert x_k - x_{k+1} \Vert _p^p + \langle \nabla f(x_k) , \bar{x} - x_{k+1} \rangle \\&\le \underbrace{f_k - f(\bar{x}) + \langle \nabla f(x_k) , \bar{x} - x_{k} \rangle }_{\le 0 \text { because f is convex}} - \frac{c_p}{\alpha p} \Vert x_k - x_{k+1} \Vert _p^p \\&+ \langle \nabla f(x_k) , x_k - x_{k+1} \rangle \end{aligned} \end{aligned}$$

Thanks to the Cauchy inequality in Banach space, $\langle \nabla f(x_k), x_k - x_{k+1} \rangle \le \Vert \nabla f_k\Vert _{X^*}\Vert x_k - x_{k+1}\Vert _X$. We now use the Young’s inequality ($ab \le \frac{1}{q}a^q + \frac{1}{p}b^p$, for all $a,b \ge 0$) to write

$$\begin{aligned} \begin{aligned} \Vert \nabla f_k\Vert _q \Vert x_k - x_{k+1}\Vert _p&= (\frac{\alpha }{c_p})^{\frac{1}{p}} \Vert \nabla f_k\Vert _q (\frac{c_p}{\alpha })^{\frac{1}{p}}\Vert x_k - x_{k+1}\Vert _p \\&\le \frac{1}{q}(\frac{\alpha }{c_p})^{\frac{q}{p}}\Vert \nabla f_k\Vert _q^q + \frac{c_p}{\alpha p}\Vert x_k - x_{k+1}\Vert _p^p. \end{aligned} \end{aligned}$$

Thus

$$\begin{aligned} \begin{aligned} f_k - f(\bar{x}) + (\Phi _{k+1} - \Phi _k)&\le - \frac{c_p}{\alpha p} \Vert x_k - x_{k+1} \Vert _p^p + \frac{1}{q}(\frac{\alpha }{c_p})^{\frac{q}{p}}\Vert \nabla f_k\Vert _q^q + \frac{c_p}{\alpha p}\Vert x_k - x_{k+1}\Vert _p^p \\&\le \frac{1}{q}(\frac{\alpha }{c_p})^{\frac{q}{p}}\Vert \nabla f_k\Vert _q^q. \end{aligned} \end{aligned}$$

Summing over k we get:

$$\begin{aligned} {\sum _{k=0}^N \left( f_k - f(\bar{x}) \right) } \le \frac{1}{\alpha } \Delta _h(x_0,\bar{x}) + \frac{1}{q}(\frac{\alpha }{c_p})^{\frac{q}{p}} \sum _{k=0}^N \Vert \nabla f_k\Vert _q^q. \end{aligned}$$