Новый алгоритм сокращает время вычислений на порядки

• Новый алгоритм экспоненциально ускоряет вычисления за счет резкого сокращения количества итераций, необходимых для решения проблемы.
• Он работает гораздо лучше, чем традиционные (последовательные) алгоритмы на больших наборах данных, таких как аналитика социальных сетей и кластеризация генетических данных. 

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

Базовая схема работы этих алгоритмов не менялась (усовершенствовалась) с тех пор, как они были впервые созданы в начале 1970-х годов. Они решают любую конкретную задачу последовательно за n шагов.

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

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

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

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

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

Как это работает?

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

Прорывной алгоритм использует адаптивную выборку | С разрешения исследователей

Точнее, алгоритм требует O (log n) последовательных шагов и достигает аппроксимации, сколь угодно близкой к 1/3. При включении распараллеливания алгоритмы достигают аппроксимации с постоянным коэффициентом экспоненциально быстрее, чем любой существующий метод субмодульной максимизации.

Ссылка:Гарвардский университет SEAS | Гарвардские публикации