Избыточный риск стабильных обучающих алгоритмов. Егор Клочков

Наиболее точные из известных оценок обобщения с высокой вероятностью для равномерно устойчивых алгоритмов (Фельдман, Вондрак, NeurIPS 2018, COLT, 2019), (Буске, Клочков, Животовский, COLT, 2020) содержат неизбежный член ошибки выборки порядка Θ (1 / √n). Применительно к оценкам избыточного риска это приводит к неоптимальным результатам в нескольких стандартных задачах выпуклой оптимизации. На вебинаре Егор показал как этого члена можно избежать, если выполняется так называемое условие Бернштейна, и оценки избыточного риска порядка O (1 / n) станут возможны благодаря равномерной устойчивости. Используя этот результат, Егор показал оценки избыточного риска порядка O (log n / n) для сильно выпуклых и липшицевых потерь, действительную для любого эмпирического метода минимизации риска. Это решает вопрос поставленный Шалев-Шварцем, Шамиром, Сребро и Шридхарана (COLT, 2009). Доклад основан на совместной работе с Никитой Животовским и Оливье Буске. Спикер: Егор Клочков, Кембриджский Университет, Кембридж, Великобрит