【凸解析】平滑性に関する諸性質

これは何？

機械学習や数理最適化に関する論文を読んでいると，アルゴリズムの収束性の議論をするときなどに関数の平滑性 (Smoothness) を仮定することがあります．

先日，友人氏 (@IamTakala) から平滑性に関する性質をまとめた記事 [1] において，[1] -> [0] は成立しないのか，という旨の連絡を受け，凸性を仮定すれば成立することを確認したので，その内容をまとめておこうと思います．記事 [1] の [1] -> [0] がどのような主張かというと，「関数 $g(x) = \frac{L}{2} \|x\|^2 - f(x)$ が凸関数であるとき，関数 $f$ は $L$-平滑である」というものです．

なお，本記事では，ベクトルであっても太字を用いないこととし，$\|\cdot\|$ は適当なノルムを表すものとします．

また，本記事は数理最適化のカレンダー | Advent Calendar 2023 - Qiita の第 11 日目の代理として書かれたものです（何か不都合があれば，@mirucaaura までご連絡頂ければと思います）．

準備

まず，関数 $f$ に関する平滑性は次のように定義されるのであった：

定義 1 (平滑性) 連続的微分可能な関数 $f:\mathbb{R}^n\to\mathbb{R}$ が $L$-平滑 ($L$-smooth) であるとは，任意の $x, y\in\mathbb{R}^n$ に対して， $$ \begin{align} \|\nabla f(x) - f(y) \| \leq L \|x - y \| \end{align} $$ が成り立つことを言う．

上記の平滑性の定義において，関数 $f$ に対する凸性は必要ないことに注意されたい．また，上記の $f$ の平滑性は，$\nabla f(x)$ に関する Lipschitz 連続性と等価であり，$L$ は Lipschitz 定数に他ならない．

次に，関数 $f$ が凸関数であるとき，平滑であることと等価な条件を確認する．証明は [2] などを参照されたい．

命題 1 (平滑性の必要十分条件) [2, 命題 2.3.5] 関数 $f:\mathbb{R}^n\to\mathbb{R}$ を連続的微分可能な凸関数とし，$L>0$ とする．このとき，$f$ が $L$-平滑であるための必要十分条件は次の (1)-(3) である：
(1) $f(y) \leq f(x) + \left<\nabla f(x), y-x\right> + \frac{L}{2} \|x-y\|^2$
(2) $f(y) \geq f(x) + \left<\nabla f(x), y-x\right> + \frac{1}{2L} \|x-y\|^2$
(3) $\left<\nabla f(x) - \nabla f(y), x-y\right> \geq \frac{1}{L} \|\nabla f(x) - \nabla f(y)\|^2$

本題

さて，懸案事項は，凸関数 $f$ が $L$-平滑であるとき，以下のような関係が成立するかどうかである (実際に成立するので命題という形で書いている)：

命題関数 $g(x) = \frac{L}{2} \|x\|^2 - f(x)$ は凸関数であるとする．このとき，$f$ は $L$-平滑，すなわち，任意の $x, y\in\mathbb{R}^n$ に対して， $$ \begin{align} \|\nabla f(x) - f(y) \| \leq L \|x - y \| \end{align} $$ が成り立つ．

証明の方針：凸関数 $f$ が命題の条件を満たすとき，$f$ に対する $L$-平滑性と等価な条件式 (命題 1-(2)) が成立することを確かめる．

証明．まず，関数 $\phi_x:\mathbb{R}^n\to\mathbb{R}$ を次のように定める：

\begin{align} \phi_x(z) := f(z) - \left<\nabla f(x), z\right>. \end{align}

この関数 $\phi_x$ の勾配ベクトルは，

\begin{align} \nabla \phi_x(z) = \nabla f(z) - \nabla f(x) \end{align}

であるから，$z=x$ において最小となる ($\because \nabla \phi_x(x) = \nabla f(x) - \nabla f(x) = 0$)．

いま，命題の条件より，関数 $h(z) := \frac{L}{2} \|z\|^2 - \phi_x(z)$ も凸である．実際，この関数 $h:\mathbb{R}^n\to\mathbb{R}$ は

\begin{align} h(z) = \underbrace{\frac{L}{2} \|z\|^2 - f(z)}_{=g(z)} + \left<\nabla f(x), z\right> \end{align}

であり，凸関数 $g$ に線形項を加えた関数であり，したがって凸である．

さて，関数 $h$ の凸性より，任意の $z, y \in \mathbb{R}^n$ に対して次の不等式が成り立つ：

\begin{align} h(z) \geq h(y) + \left<\nabla h(y), z-y\right>. \end{align}

つまり，任意の $y, z\in\mathbb{R}^n$ に対して，

\begin{align} &\frac{L}{2}\|z\|^2 - \phi_x(z) \geq \frac{L}{2}\|y\|^2 - \phi_x(y) + \left< L y - \nabla \phi_x(y), z-y \right> \\ \iff\quad& \phi_x(z) \leq \phi_x(y) + \left<\nabla \phi_x(y), z-y\right> + \underbrace{\frac{L}{2}\|z\|^2 - \frac{L}{2}\|y\|^2 - \left< Ly, z-y\right>}_{=\frac{L}{2}\|z-y\|^2}. \end{align}

が成り立つ．上式において，左辺の $\phi_x(z)$ は $z=x$ において最小となる．また，右辺全体を $\varphi(z)$ とおくと，$\nabla \varphi(z) = \nabla \phi_x(y) + L(z-y)$ であるから，右辺 $\varphi(z)$ は $z=y-\frac{1}{L}\nabla\phi_x(y)$ で最小となる．したがって，

\begin{align} f(x) - \left< \nabla f(x), x \right> &\leq \phi_x(y) + \left< \nabla \phi_x(y) , -\frac{1}{L} \nabla \phi_x(y) \right> + \frac{L}{2} \left\| -\frac{1}{L} \nabla \phi_x(y) \right\|^2 \\ &= \phi_x(y) - \frac{1}{L} \| \nabla \phi_x(y) \|^2 + \frac{1}{2L} \| \nabla \phi_x(y) \|^2 \\ &= f(y) - \left< \nabla f(x), y\right> - \frac{1}{2L} \| \nabla f(y) - \nabla f(x)\|^2. \end{align}

整理すると，所望の不等式 (命題 2-(2))：

\begin{align} f(y) - f(x) - \left<\nabla f(x), y-x \right> \geq \frac{1}{2L} \| \nabla f(y) - \nabla f(x) \|^2 \end{align}

が得られる．したがって，関数 $g(x) = \frac{L}{2} \|x\|^2 - f(x)$ が凸であるとき，関数 $f$ は $L$-平滑である．（証明終）