楠岡 成雄「Rademacher 複雑度と正則化」§3 Rademacher 複雑度 (1)

公開: 2024/8/23
最終更新: 2024/8/23

楠岡 成雄「Rademacher 複雑度と正則化」
§3 Rademacher 複雑度 (1)

  を可測空間、 を 上の可測関数全体とする。

 定義 3.1.

  1. を の空でない部分集合とする。 を により定義する1。ここで、 は独立同分布な確率変数列で となるものである。
  2. を の空でない部分集合とし、 を 上の確率測度とする。 を により定義する。

 

 命題 3.2.

  1. を の空でない部分集合とする。この時、 に対して また、 とおくと、 である。さらに、 に対して とおくと、 である。
  2. を の空でない部分集合とする。この時、 である。ここで は が存在して、 となる の集合である。
  3. を の空でない部分集合とする。この時、 である。
  4. を の空でない部分集合とする。今、 を が存在して、 となる の集合とする。この時、 である。
  5. を の空でない部分集合とし、 とする。この時、

証明. 1. は よりわかる。

  1. は ならば よりわかる。

  2. は であるので、 よりわかる。

  3. を示す。 ならば が存在して となる。 を、 ならば また ならば で定める。この時、 となるので、 がわかる。よって、 これより 4. がわかる。

  4. を示す。 であるので、 を得る。 であるので 5. を得る。


 

命題 3.3. (Talagrand) は の空でない部分集合とし、 は を満たす可測関数とする。今、 で定める。この時、 が成立する。


証明. は独立同分布な確率変数列で となるものとする。今、 を固定し、 に対して確率変数 を で定める。 は -可測である。この時、 である。任意の 及び に対して で となるものが存在する。

 今、 を とおくと、 となる。この時 は任意なので を得る。よって、 に対して となる。これより主張を得る。


 

 命題 3.4. を 上の確率測度とし、 を の空でない部分集合とする。

  1. に対して また、 とおくと、 である。さらに、 に対して とおくと、 である。
  2. を の空でない部分集合とする。この時、 である。
  3. 今、 を が存在して、 となる の集合とする。この時、 である。
  4. とする。この時、
  5. は を満たす可測関数とする。今、 で定める。この時、 が成立する。
  6. であり、 を の での閉包とする。この時、 である。

証明. 主張 1., 2., 3., 4. は命題 3.2 よりわかる。また、命題 3.2 の 5. より ならば これより主張 5. を得る。

 主張 6. は命題 3.3 よりわかる。主張 7. を示す。 ならば、 が存在して、 となる。 は -値確率変数、 は -値確率変数であり、 は独立で の確率法則は とすると となる。よって部分列 が存在して となる。これより となり、 となる。よって となり、主張 7. を得る。


 


  1. 期待値の中の関数 (確率変数) は全て可測であると仮定する。可測性が成り立つための十分条件について、例えば van der Vaart and Wellner “Weak Convergence and Empirical Processes” (1996, Springer) を参照されたい。↩


※ AMFiL Blog の記事を含む、本ウェブサイトで公開されている全てのコンテンツについての著作権は、一般社団法人数理ファイナンス研究所 (AMFiL) 及びブログ記事の寄稿者に帰属します。いかなる目的であれ、無断での複製、転送、改編、修正、追加等の行為を禁止します。