数理工学のススメ

敵対的オンライン凸最適化とオンライン近接勾配法のリグレット上界

2018/3/19 大学院レベル最適化, 機械学習

オンライン学習の一種である敵対的オンライン凸最適化の問題設定とアルゴリズムの性能評価指標（リグレット）を解説し，オンライン近接勾配法

$x_{t} = \underset{x \in R^{d}}{a r g m i n} {⟨ p_{t - 1}, x ⟩ + g (x) + \frac{η_{t}}{2} ‖ x - x_{t - 1} ‖^{2}}$

のリグレット上界を証明をします．

自然対数の底の無限級数表示の確率による証明

2018/3/18 高校レベル確率, 解析

自然対数の底（オイラー数，ネイピア数）に関する以下の有名な等式（無限級数表示）を，確率や期待値を使って証明します：

$lim_{n \to \infty} (1 + \frac{1}{n})^{n} = \sum_{k = 0}^{\infty} \frac{1}{k!} .$

ミニマックス定理の意味とゲーム理論的証明

2018/3/17 大学3〜4年レベル最適化

最適化理論のミニマックス定理を，ゲーム理論を使って証明します：

関数 $f : X \times Y \to R$ が「ある仮定」を満たすとき，

$min_{x \in X} max_{y \in Y} f (x, y) = max_{y \in Y} min_{x \in X} f (x, y) .$

最大値の期待値・裾確率の不等式の応用例と証明

2018/1/30 大学3〜4年レベル確率

確率変数の最大値に関する2つの不等式とその応用例を紹介し，証明をします：

実数値確率変数 $X_{1}, \dots, X_{n}$ のモーメント母関数を $G_{1}, \dots, G_{n}$ とすると，任意の $t > 0$ と $a$ に対し，

$E [max_{i = 1, \dots, n} X_{i}] \leq \frac{1}{t} \log (\sum_{i = 1}^{n} G_{i} (t)),$

$P (max_{i = 1, \dots, n} X_{i} > a) \leq e^{- a t} \sum_{i = 1}^{n} G_{i} (t) .$

ARモデルとユール–ウォーカー方程式

2018/1/28 大学3〜4年レベル統計, 統計検定

時系列データの分析に用いられるARモデル（AutoRegressive model，自己回帰モデル）と，ARモデルの推定に用いられる「ユール–ウォーカー方程式」について解説します．

劣モジュラ関数最小化の藤重–ウルフ法

2018/1/27 大学院レベル最適化

劣モジュラ関数最小化のための藤重–ウルフ法を解説します．アルゴリズムの導出に必要な藤重の定理を証明します：

基多面体上の最小ノルム点問題 $min_{x \in B (f)} ‖ x ‖^{2}$ の最適解を $x^{*}$ とする．集合 $S = {i \in [n] ∣ x_{i}^{*} < 0}$ は劣モジュラ関数最小化問題 $min_{A \subseteq [n]} f (A)$ の最適解である．