Error bounds, PL condition, and quadratic growth for weakly convex functions, and linear convergences of proximal point methods

技術要約：弱凸関数における誤差境界、PL条件、および二次成長、ならびに近接点法の線形収束について

問題設定
多くの実用的な最適化問題、特に機械学習や信号処理の分野においては、強凸性が欠如している。一次アルゴリズムは強凸性の下で線形収束を達成することが知られているが、近年の研究では、滑らかな凸関数に対してより弱い正則性条件（例：Polyak-Lojasiewicz不等式、誤差境界、二次成長）の下でも線形収束が保証され得ることが示されている。しかし、これらの条件間の関係性は、非滑らかな非凸関数の設定においては十分に理解されていなかった。具体的には、弱凸関数（ある $\rho \geq 0$ に対して $f + \frac{\rho}{2}\|\cdot\|^2$ が凸である関数）は、現代的なモデル（例：非滑らかな深層ネットワーク、凸関数と滑らかな関数の合成）を包含しているが、これらの正則性条件を繋ぐ統一された枠組みを欠いていた。さらに、近接点法（Proximal Point Method: PPM）の線形収束に関する既存の証明の多くは、制限的な仮定（例：一意の最小化子、逆劣微分係数の局所リプシッツ連続性）や複雑な議論に依存していた。

手法
本論文は、非滑らかな解析のツール、具体的には勾配（slope）の概念、エケランドの変分原理、および距離推定補題を用いて、正則性条件間の関係を分析する。著者らは、部分集合 $[f \leq f^\star + \nu]$ において、以下の5つの主要な条件を定義する：

1. 強凸性 (SC)
2. 制限付きセカント不等式 (RSI)
3. 劣微分誤差境界 (EB)
4. Polyak-Lojasiewicz (PL) 不等式
5. 二次成長 (QG)

著者らは、滑らかな設定と非滑らかな設定の間の溝を埋めるために、勾配 $|\nabla f|(x) = \text{dist}(0, \hat{\partial}f(x))$ （ここで $\hat{\partial}f$ はフレシェ劣微分）を利用する。彼らは、これらの条件間の論理的含意および同値性を確立し、特に二次成長定数 $\mu_q$ が弱凸パラメータ $\rho$ を超えるケースに焦点を当てる。

これらの同値性に基づき、本論文は近接点法 (PPM) を分析する：
$$x_{k+1} = \text{prox}_{c_k f}(x_k) = \arg\min_x \left( f(x) + \frac{1}{2c_k}\|x - x_k\|^2 \right)$$
著者らは、凸および弱凸の両方の設定において、PPMの線形収束のためのモジュール化された証明を提供する。また、問題を近似的に解く不完全近接点法 (Inexact PPM: iPPM) にも分析を拡張し、停止基準に関する微妙な差異や実行可能性（反復点が $f$ のドメイン内に留まること）に対処する。

主な貢献

1. 弱凸関数のための正則性条件の統一：
   本論文は、$\rho$-弱凸関数のための正則性条件の階層と同値性を確立する。

   • 一般的な含意の連鎖： $(SC) \implies (RSI) \implies (EB) \iff (PL) \implies (QG)$。
   • $\mu_q > \rho$ の下での同値性： もし $\rho$-弱凸関数が定数 $\mu_q > \rho$ を伴う二次成長を満たすならば、これら4つの条件 $(RSI), (EB), (PL), (QG)$ はすべて同値である。
   • 著者らは、これらの条件間の明示的な係数変換を導出し（論文の表1にまとめられている）、実務者が一つの条件から別の条件へ定数を変換できるようにしている。

2. PPMの線形収束証明の簡略化：
   本論文は、凸および弱凸関数の両方に対するPPMの線形収束のための、シンプルかつモジュール化された証明を提示する。

   • 凸の場合： 同値な正則性条件（PL, EB, RSI, QG）のいずれかの下で、PPMは関数値および解集合への距離の両方において線形収束を達成する。この証明は、一意の最小化子や逆劣微分の局所リプシッツ連続性といった要求を排除することで、従来の仮定を緩和している。
   • 弱凸の場合： 初期値がQGを $\mu_q > \rho$ で満たす部分集合内であり、かつステップサイズが $1/c_k > \rho$ を満たす場合に、結果は $\rho$-弱凸関数へと拡張される。

3. 不完全近接点法 (iPPM) の分析：
   著者らは、iPPMにおける不完全性と実行可能性のニュアンスを明確にする。標準的な停止基準（Rockafellarの基準AおよびB）の下で、関数が解集合の近傍でQGを満たす場合、iPPMの線形収束を確立する。その証明は、先行文献からの主要な不等式と、モジュール化された正則性条件の枠組みを組み合わせたものである。

結果

• 理論的： 定理3.1は、弱凸関数の場合、$\mu_q > \rho$ であれば正則性条件の同値性が成立することを確認している。これは、滑らかな関数または凸関数に限定されていた従来の結果を一般化するものである。
• アルゴリズム的： 定理4.2および4.3は、PPMが正則性定数（例：$\omega_k = \frac{1}{1+c_k\mu_p}$）に依存するレートで線形収束することを示している。定理5.3はこれをiPPMへと拡張し、不完全性が制御されている限り（誤差の総和が有限である限り）、漸近的に線形収束レートが保持されることを示している。
• 数値的： Linear SVM、Lasso、およびElastic-Net問題を用いた実験により、PPMの理論的な線形収束が確認された。実験にはYALMIPモデリングパッケージとMOSEKソルバーが使用され、コスト値のギャップと解集合への距離の両方において高速な収束が示された。

意義および主張
本論文は、正則性条件の理解を、滑らかな／凸な設定から、より広いクラスである非滑らかな弱凸関数へと一般化することを主張している。これらの条件間のつながりを明らかにすることで、著者らは反復アルゴリズムの分析を簡素化する統一された枠組みを提供している。

具体的には、以下のことを主張している：

• $\mu_q > \rho$ の下での条件の同値性（RSI, EB, PL, QG）は柔軟な分析を可能にする。すなわち、一つの条件を確立すれば、他の条件を通じて収束結果を導き出すことができる。
• PPMの線形収束の証明は、既存の文献よりもシンプルかつ透明であり、一意の最小化子のような制限的な仮定を回避している。
• これらの結果は、弱凸性が普及している大規模な円錐計画法や機械学習アプリケーションにおける非滑らかな最適化のアルゴリズム開発を促進する。

著者らは、これらの条件の同値性が滑らかな、あるいは凸な関数については既知であったものの、これを弱凸な設定へと拡張し、PPM（不完全版を含む）のクリーンな証明を提供することが主要な新規性であると述べている。本論文は、詳細な証明、係数変換、および不完全PPMの拡張分析を加えた、会議論文の拡張版として提示されている。