Неравенство Талаграна и локальные меры сложности в теории статистического обучения

Доклад посвящен современному подходу к получению оценкок обобщающей способности (generalization error) и избыточного риска (excess risk) метода минимизации эмпирического риска в теории статистического обучения, основанному на использовании неравенства Талаграна. Данный подход, часто называемый в литературе “локальным”, был развит в серии работ P. Massart, V. Koltchinskii, P. Bartlett, S. Mendelson и O. Bousquet начиная с 2000 года. Классический подход к этим задачам, развитый В. Н. Вапником и А. Я. Червоненкисом в начале 1970 годов, основан на рассмотрении равномерных отклонений эмпирического риска от среднего риска по всему рассматриваемому классу отображений и в общих предположениях ведет к оценкам порядка $O(n^{-1/2})$, где $n$ — размер обучающей выборки. Локальный подход, пользуясь неравенством Талаграна, сужает подмножество, по которому берется супремум, и во многих интересных случаях ведет к оценкам порядка $o(n^{-1/2})$ (и даже $O(n^{-1})$) при наложении дополнительных нестрогих ограничений на рассматриваемые задачи. В докладе будут рассмотрены основные результаты локального подхода, включая оценки, основанные на локальной Радемахеровской сложности (Local Rademacher Complexity).