Ученые нашли алгоритмический предел в обучении нейросетей на многомерных данных

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

Авторы рассматривают простую задачу обучения с учителем, где признаки представляют собой стандартные гауссовские векторы в d-мерном пространстве, а отклик зависит от проекции этих векторов на неизвестное k-мерное подпространство. Модель обучается с помощью эмпирической минимизации риска, при этом используется m-мерная проекция данных (например, нейросеть с m нейронами).

Для анализа задачи ученые разработали инкрементальный алгоритм аппроксимирующего распространения сообщений (IAMP). Он позволяет точно охарактеризовать ошибку обучения, которую достигает алгоритм, а также соотношение между ошибкой на обучающей и тестовой выборках. Анализ проводится в асимптотике больших размерностей, когда n и d стремятся к бесконечности с фиксированным отношением.

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

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

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