Найден первый полностью полиномиальный алгоритм обучения ReLU-комбинаций

Исследователи представили первый PAC-алгоритм, который за полиномиальное время учит положительные линейные комбинации k ReLU при гауссовых входах и L2-потере. В отличие от прежних методов, ему не нужны сверхполиномиальное время или жёсткие условия обусловленности.

• Алгоритм полиномиален по размерности, k и обратной ошибке
• Прежние методы требовали сверхполиномиального времени или сильной обусловленности
• Результат теоретический: практическая реализуемость не показана
• Открыт вопрос переноса на знаковые комбинации и глубокие сети