Abstract
本論文では、過剰パラメータ化された2層ニューラルネットワークに拡張特徴を与えて学習することで、 heta0 = \Theta(1)\ge 1 を満たす、単位球面上で定義された次数k_0の低次数球面多項式を学習する問題を考察する。主結果は、このような低次数多項式の学習におけるサンプル複雑度が大幅に改善される点である。すなわち、任意の回帰リスク \eps \in (0, \Theta(d^{-k_0})] について、確率1-\delta（\delta \in (0,1)）で、GDP（Gradient Descent with Projection：射影付き勾配降下法）という新しい勾配降下法により学習された過剰パラメータ化2層ニューラルネットワークは、n \asymp \Theta\big( \log(4/\delta) \cdot d^{k_0}/\eps \big) のサンプル複雑度を要することを示す。これは、代表的なサンプル複雑度\Theta(d^{k_0} \max\set{\eps^{-2},\log d})と対照的である。さらに、このサンプル複雑度はほぼ改善不能である。なぜなら、学習されたネットワークは、少なくとも1-\deltaの確率で、非パラメトリック回帰リスクに対するオーダー\log({4}/{\delta}) \cdot \Theta(d^{k_0}/{n})のほぼ最適な収束率を与えるからである。一方で、階数\Theta(d^{k_0})の核に対する回帰リスクのミニマックス最適率は\Theta(d^{k_0}/{n})であるため、GDPで学習されたネットワークの非パラメトリック回帰リスクの率はほぼミニマックス最適である。基底となる真の次数k_0が未知の場合には、真の次数を特定し、同じほぼ最適な回帰率を達成する、新規かつ証明可能な適応的次数選択アルゴリズムを提示する。筆者らの知る限り、これは、一般的な活性化関数（ReLU）と低次数球面多項式学習のためのアルゴリズム的保証を用いて、ほぼ最適なリスク上界を得た最初の試みである。GDPの特徴学習能力により、本結果は通常のニューラル・テンサーチャー・カーネル（NTK）の限界を超えている。
