---
# System prepended metadata

title: 制御点行列の収束性

---

# 制御点行列の収束性

## 目的

制御点に関する更新則：

\begin{align}
\boldsymbol{P}^{(k+1)} = \boldsymbol{P}^{(k)} - \alpha^{(k)} \left(\boldsymbol{Z}^{(k)\top} \boldsymbol{Z}^{(k)} \right)^{-1} \boldsymbol{Z}^{(k)\top} \boldsymbol{G}^{(k)} 
\tag{1}
\end{align}

によって生成される点列 $\{\boldsymbol{P}^{(k)}\}$ の収束性を調べたい．

## 目標

パレートセットを表現する最適な制御点行列を $\boldsymbol{P}^\star$ とする．このとき，(1) によって生成される制御点行列の点列 $\{\boldsymbol{P}^{(k)}\}$ について以下が成立することを示したい：

\begin{align}
\left\|\boldsymbol{P}^{(k+1)} - \boldsymbol{P}^\star\right\|_F^2 \leq 
\gamma \left\|\boldsymbol{P}^{(k)} - \boldsymbol{P}^\star\right\|_F^2.
\end{align}

ここで，$\gamma$ は $0< \gamma< 1$ なる定数．

つまり，制御点行列の更新によって最適解との誤差が非増加であることを示したい．

## 通常の勾配降下法における点列の収束性

微分可能な凸関数 $f:\mathbb{R}^n\to\mathbb{R}$ の最適解を求める勾配降下法を考える：
\begin{align}
\boldsymbol{x}^{k+1} = \boldsymbol{x}^{k} - \alpha \nabla f(\boldsymbol{x}^{k}).
\end{align}
この手法によって生成される点列 $\{\boldsymbol{x}^{k}\}$ に対して，

\begin{align}
\left\| \boldsymbol{x}^{k+1} - \boldsymbol{x}^\star \right\|_2^2 \leq \gamma \left\| \boldsymbol{x}^{k} - \boldsymbol{x}^\star \right\|_2^2, \quad (0< \gamma < 1)
\end{align}

が成立する．

### 必要な仮定

- $f$ の $\mu$-強凸性 (i.e., $f(y) \geq f(x) + \left< \nabla f(x), y - x \right> + \frac{\mu}{2} \|y-x\|^2$)
- $f$ の $L$-平滑性 (i.e., $\| \nabla f(y) - \nabla f(x)\| \leq L \|x - y \|$)
- ステップサイズ：$0 < \alpha < \frac{1}{L}$

### 証明

以下のように計算できる：

\begin{align}
\left\| \boldsymbol{x}^{k+1} - \boldsymbol{x}^\star \right\|_2^2 
&\leq \left\| \boldsymbol{x}^{k} - \boldsymbol{x}^\star - \alpha\nabla f(\boldsymbol{x}^k) \right\|_2^2 \\
&=\left\| \boldsymbol{x}^{k} - \boldsymbol{x}^\star \right\|_2^2 - 2\alpha \left< \boldsymbol{x}^{k} - \boldsymbol{x}^\star, \nabla f(\boldsymbol{x}^k)) \right> +\left\| \alpha\nabla f(\boldsymbol{x}) \right\|_2^2 \\
&\overset{(a)}{\leq} \left\| \boldsymbol{x}^{k} - \boldsymbol{x}^\star \right\|_2^2 - 2\alpha \left\{ \left( f(\boldsymbol{x}^{k}) - f(\boldsymbol{x}^{\star}) \right) + \frac{\mu}{2} \|\boldsymbol{x}^{k} - \boldsymbol{x}^{\star}\|_2^2 \right\} + \left\| \alpha\nabla f(\boldsymbol{x}) \right\|_2^2 \\
&= (1 - \alpha \mu) \left\| \boldsymbol{x}^{k} - \boldsymbol{x}^\star \right\|_2^2 - 2\alpha (f(\boldsymbol{x}^{k}) - f(\boldsymbol{x}^{\star})) + \alpha^2 \left\| \nabla f(\boldsymbol{x}) \right\|_2^2 \\
&\overset{(b)}{\leq} (1 - \alpha \mu) \left\| \boldsymbol{x}^{k} - \boldsymbol{x}^\star \right\|_2^2 - 2\alpha (f(\boldsymbol{x}^{k}) - f(\boldsymbol{x}^{\star})) + \alpha^2 L \left( f(\boldsymbol{x}) - f(\boldsymbol{x}^\star) \right) \\
&=(1 - \alpha \mu) \left\| \boldsymbol{x}^{k} - \boldsymbol{x}^\star \right\|_2^2 - \underbrace{2\alpha (1-\alpha L)(f(\boldsymbol{x}^{k}) - f(\boldsymbol{x}^{\star}))}_{\geq 0}.
\end{align}

ここで，($a$) は $f$ の $\mu$-強凸性を，($b$) は $f$ の $L$-平滑性を用いた ($\nabla f(\boldsymbol{x}^\star) = \boldsymbol{0}$ に注意する)．

よって，

$$
\left\| \boldsymbol{x}^{k+1} - \boldsymbol{x}^\star \right\|_2^2 \leq (1 - \alpha \mu) \left\| \boldsymbol{x}^{k} - \boldsymbol{x}^\star \right\|_2^2
$$

が成り立つ．また，これを繰り返し用いることによって，

$$
\left\| \boldsymbol{x}^{k+1} - \boldsymbol{x}^\star \right\|_2^2 \leq (1 - \alpha \mu)^{k+1} \left\| \boldsymbol{x}^{0} - \boldsymbol{x}^\star \right\|_2^2
$$

が成り立つ．


## 制御点行列の更新則で同様の議論ができるか？

以下の点で難しさがある：

- 制御点に関する最適性条件なるものがない (通常の最適化における $\nabla f(\boldsymbol{x}^\star) = \boldsymbol{0}$ に相当するもの)
- 制御点に関する性質を上手く使えない
    - 最適化すべき関数 $f$ の凸性や平滑性が使えない


## 発散せず収束することを示せないか？

- 最適解に収束するかはともかく，どこかに収束することは示せないか？
- 各反復 ($k=1,2,\dots$) で得られる制御点行列は有界で訓練データ集合に対して
$$
\| b(t|P^{(k)}) - x^{(k)}(t) \|_2 < \varepsilon (k) \quad (\forall t\in T^{(k)})
$$を満たす．ここで，$T^{(k)}$ は第 $k$ 反復目におけるデータ集合．
- 示したいのは，以下のような関係：
$$
\lim_{k\to\infty} \mathrm{dist}(P^{(k)}, \overline{P}) = 0.
$$
- $\overline{P}$ は集積点の気持ち．
- 適当な部分列を取る必要があるかもしれない

### データを十分に大きくとる

- 訓練データ $T_1, T_2$ とし，それぞれの要素は十分に大きいとする．これらのデータを用いて得られるベジエ単体を $b_1, b_2$ とする．このとき，$\|b_1 - b_2 \| \leq \varepsilon$ が成り立つ．つまり，データ数を十分に大きくとれば，得られるベジエ単体は大きく違わないことを意味する．
- 上のようなことが言えないか？
- これが言えると，コーシー列であることは言えそう：
$$
\lim_{m,n\to\infty} \|P^{(m)} - P^{(n)}\| = 0.
$$

データ $\{(t_1,x_1),\dots,(t_N, x_N)\}\subseteq \Delta^{M-1}\times\mathbb{R}^L$ で得られるベジエ単体を記述する制御点行列は以下の線形方程式の解として与えられる：
$$
(Z(t)^\top Z(t))P = Z(t)X
$$









