Теория сложности ограничивает производительность градиентного спуска

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

Август 206,

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

Многие аспекты современных прикладных исследований основаны на важном алгоритме, называемом градиентным спуском. Это процедура, обычно используемая для поиска наибольших или наименьших значений конкретной математической функции – процесс, известный как оптимизация функции. Его можно использовать для расчета чего угодно, от наиболее прибыльного способа производства продукта до наилучшего способа распределения рабочих смен.

Тем не менее, несмотря на такую ​​широкую полезность, исследователи так и не до конца понимали, с какими ситуациями алгоритм борется больше всего. Теперь это объясняется в новой работе

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

«Это своего рода жесткость наихудшего случая, о которой стоит знать», – сказал Пол Голдберг из Оксфордский университет, соавтор работы вместе с Джон Фернли и Рахул Савани из Ливерпульского университета и Александрос Холлендер из Оксфорда. Результат получил награду за лучшую работу. в июне в годовом Симпозиум по теории вычислений .

Вы можете представить себе функцию как пейзаж, где высота земля равна значению функции («прибыль») в этом конкретном месте. Градиентный спуск ищет локальный минимум функции, ища направление наискорейшего подъема в заданном месте и ища спуск от него. Наклон ландшафта называется градиентным, отсюда и название градиентный спуск.

Градиентный спуск – важный инструмент современных прикладных исследований, но есть много общих проблем, для которых он не работает. Но до этого исследования не было исчерпывающего понимания того, что именно вызывает борьбу с градиентным спуском и когда – вопросы, на которые помогала ответить другая область информатики, известная как теория вычислительной сложности.

«О большой работе по градиентному спуску речь не шла. с теорией сложности », – сказал Костис Даскалакис из Массачусетского технологического института.

Вычислительная сложность – это изучение ресурсов, часто времени вычислений, необходимых для решения или проверки решений для различных вычислений. проблемы. Исследователи сортируют задачи по разным классам, причем все задачи в одном классе имеют общие вычислительные характеристики.

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

Этот вопрос относится к классу сложности под названием TFNP, сокращенно от «Недетерминированный многочлен полной функции». Это совокупность всех вычислительных задач, для которых есть гарантированные решения и решения которых можно быстро проверить на правильность. Исследователи сосредоточились на пересечении двух подмножеств проблем в TFNP. Первое подмножество называется PLS (полиномиальный локальный поиск). Это набор задач, связанных с поиском минимального или максимального значения функции в определенной области. На эти проблемы гарантированно найдутся ответы, которые можно будет найти с помощью относительно простых рассуждений.

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

Второе подмножество задач – это PPAD (аргументы полиномиальной четности на ориентированных графах). У этих проблем есть решения, которые возникают в результате более сложного процесса, называемого теоремой Брауэра о неподвижной точке. Теорема гласит, что для любой непрерывной функции гарантированно найдется одна точка, которую функция оставляет неизменной – как известно, фиксированная точка. Это верно в повседневной жизни. Если вы перемешаете стакан с водой, теорема гарантирует, что обязательно должна быть одна частица воды, которая окажется в том же месте, откуда она началась.

Само пересечение классов PLS и PPAD образует класс известных проблем. как PLS int PPAD. Он содержит множество естественных проблем, имеющих отношение к исследователям сложности. Однако до сих пор исследователям не удавалось найти естественную проблему, которая была бы завершена для PLS int PPAD – это означает, что это пример самых сложных возможных проблем, которые попадают в класс.

До этого документа единственный известный PLS int Задача PPAD-complete была довольно искусственной конструкцией – проблему иногда называли «Либо-решение». Эта проблема объединила полную проблему из PLS и полную проблему из PPAD, образуя то, с чем исследователь вряд ли столкнется вне этого контекста. В новой статье исследователи доказали, что градиентный спуск так же сложен, как и решение Either-Solution, что делает сам градиент PLS int PPAD-complete.

« это то, что мы, как вид, должны попытаться глубоко понять во всех его многочисленных формах. И я думаю, что этого должно быть достаточно, чтобы быть в восторге от этого результата », – сказал Тим Рафгарден из Колумбийского университета

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

«Существует слегка юмористический стереотип о вычислительной сложности, который гласит, что в конечном итоге мы часто делаем задачу, которую часто решаем на практике, и доказывая, что это на самом деле очень сложно, – сказал Голдберг. Но результат действительно означает, что прикладным исследователям не следует ожидать, что градиентный спуск предоставит точные решения для некоторых проблем, где точность важна.

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

Например, градиентный спуск часто используется в машинном обучении способами, не требующими особой точности. Но исследователь машинного обучения может захотеть удвоить точность эксперимента. В этом случае новый результат подразумевает, что им, возможно, придется в четыре раза увеличить время работы своего алгоритма градиентного спуска. Это не идеально, но и не мешает.

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

«[It] тормозит то, во что [they], возможно, может стрелять», – сказал Даскалакис. .

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

Но это не значит, что быстрого алгоритма градиентного спуска не существует. Может. Но результат действительно означает, что любой такой алгоритм немедленно подразумевал бы существование быстрых алгоритмов для всех других проблем в PLS int PPAD – гораздо более высокий план, чем просто поиск быстрого алгоритма для самого градиентного спуска.

«Многие проблемы, которые могут быть некоторый прогресс в математике может дать трещину », – сказал Даскалакис. «Вот почему нам нравится иметь очень естественную задачу, такую ​​как градиентный спуск, которая отражает сложность всего пересечения».

Leave a comment

Your email address will not be published. Required fields are marked *

5 × four =