Математики определили фундаментальные ограничения методов отбраковки выбросов в обучении

Группа исследователей представила математическое описание фундаментальных ограничений для методов сертификации отбраковки выбросов в задачах устойчивого обучения половинных пространств. В работе, опубликованной на arXiv, показано, что степень полиномиального сертификата напрямую связана с объемом скрываемых искажений.

Центральным результатом стала точная формулировка принципа разрешения: максимальная масса зашумления, которая может остаться незамеченной при использовании сертификата степени 2t, равна функции Кристоффеля от чистой маргинальной границы. Это позволяет рассматривать устойчивое обучение с точки зрения алгебраических ограничений, а не информационно-теоретических пределов.

Авторы вывели три ключевых следствия. Первое — компромисс между маржей и степенью: чтобы сертифицировать «плотный блин» с ошибкой epsilon, требуется степень сертификата Omega(log(1/epsilon)) или маржа Omega(sqrt(log(1/epsilon))/sqrt(d)). Это объясняет, почему ранее полученная граница Shen (2025) по марже в логарифмическом масштабе является вынужденной.

Второе следствие — барьер для сертификатов степени 2. Продемонстрирован явный пример, где сертификат степени 2 не может убрать более eta^{1/2} искажений, в то время как сертификат степени 4 преодолевает это ограничение. Таким образом, неэффективность метода на малых степенях заложена в самой структуре задачи, а не в анализе.

Третье — предложен алгоритм степени 2t, который отслеживает фронтальную границу eta^{1-1/2t} и восстанавливает результат Shen при t=1. Улучшение показано с явной константой, ограниченной плотностью «блина», и его оптимальность подтверждена барьером степени 2.

Результаты работы важны для разработки более эффективных методов машинного обучения, устойчивых к злонамеренному зашумлению данных, и задают теоретические рамки для оценки вычислительных затрат.