Издательство СО РАН

Издательство СО РАН

Адрес Издательства СО РАН: Россия, 630090, а/я 187
Новосибирск, Морской пр., 2

soran2.gif

Baner_Nauka_Sibiri.jpg


Яндекс.Метрика

Array
(
    [SESS_AUTH] => Array
        (
            [POLICY] => Array
                (
                    [SESSION_TIMEOUT] => 24
                    [SESSION_IP_MASK] => 0.0.0.0
                    [MAX_STORE_NUM] => 10
                    [STORE_IP_MASK] => 0.0.0.0
                    [STORE_TIMEOUT] => 525600
                    [CHECKWORD_TIMEOUT] => 525600
                    [PASSWORD_LENGTH] => 6
                    [PASSWORD_UPPERCASE] => N
                    [PASSWORD_LOWERCASE] => N
                    [PASSWORD_DIGITS] => N
                    [PASSWORD_PUNCTUATION] => N
                    [LOGIN_ATTEMPTS] => 0
                    [PASSWORD_REQUIREMENTS] => Пароль должен быть не менее 6 символов длиной.
                )

        )

    [SESS_IP] => 54.226.226.30
    [SESS_TIME] => 1711663246
    [BX_SESSION_SIGN] => 9b3eeb12a31176bf2731c6c072271eb6
    [fixed_session_id] => ad5267215b9b1a92c5913b5ceb03f135
    [UNIQUE_KEY] => 0a557dc2edc75bf03ea53b9cf5d7ae4a
    [BX_LOGIN_NEED_CAPTCHA_LOGIN] => Array
        (
            [LOGIN] => 
            [POLICY_ATTEMPTS] => 0
        )

)

Поиск по журналу

Сибирский журнал вычислительной математики

2018 год, номер 1

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

П.Е. Двуреченский1,2, А.В. Гасников2,3, А.А. Лагуновская3
1Институт прикладного анализа и стохастики им. К. Вейерштрасса, Моренштрассе, 39, Берлин, Германия, 10117
pavel.dvurechensky@wias-berlin.de
2Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, Большой Каретный пер., 19, строение 1, Москва, 127051
gasnikov.av@mipt.ru
3Московский физико-технический институт, Институтский пер., 9, Долгопрудный, Московская обл., 141700
a.lagunovskaya@phystech.edu
Ключевые слова: стохастическая выпуклая оптимизация, оценки вероятностей больших уклонений, метод зеркального спуска, параллельные алгоритмы, stochastic convex optimization, probability of large deviation, mirror descent, parallel algorithm
Страницы: 47-53

Аннотация

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

DOI: 10.15372/SJNM20180103