Laboratory of Structural Methods of Data Analysis in Predictive
Modeling Moscow Institute of Physics and Technology
ENG
Логин:
Пароль:

Structural optimization

Описание направления:

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

 

Сотрудники программы специализируются на разработке эффективных проблемно-ориентированных методов оптимизации с гарантированными оценками сложности.

Публикации:

Cтохастический промежуточный градиентный метод для задач выпуклой оптимизации

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

Преподаватели: Гасников Александр Владимирович, Двуреченский Павел , 27 декабря 2014

Стохастические градиентные методы с неточным оракулом

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

Преподаватели: Нестеров Юрий Евгеньевич, Гасников Александр Владимирович, Двуреченский Павел , 27 декабря 2014

Stochastic Intermediate Gradient Method for Convex Problems with Inexact Stochastic Oracle

In this paper we introduce new methods for convex optimization problems with inexact stochastic oracle. First method is an extension of the intermediate gradient method proposed by Devolder, Glineur and Nesterov for problems with inexact oracle. Our new method can be applied to the problems with composite structure, stochastic inexact oracle and allows using non-Euclidean setup. We prove estimates for mean rate of convergence and probabilities of large deviations from this rate. Also we introduce two modifications of this method for strongly convex problems. For the first modification we prove mean rate of convergence estimates and for the second we prove estimates for large deviations from the mean rate of convergence. All the rates give the complexity estimates for proposed methods which up to multiplicative constant coincide with lower complexity bound for the considered class of convex composite optimization problems with stochastic inexact oracle.

Преподаватели: Гасников Александр Владимирович, Двуреченский Павел , 27 декабря 2014

Stochastic Intermediate Gradient Method for Convex Problems with Inexact Stochastic Oracle

In this paper we propose new method for convex optimization problems with inexact stochastic oracle. This method is an extension of the intermediate gradient method proposed by O. Devolder, F. Glineur, and Yu. Nesterov for problems with inexact oracle.
Our new method can be applied to the problems with composite structure, stochastic inexact oracle and allows using non-Euclidean setup. Also it allows to play on the tradeoff between the rate of convergence and oracle error accumulation depending on the problem parameters.

Преподаватели: Гасников Александр Владимирович, Двуреченский Павел , 27 декабря 2014

Gradient-free optimization methods with ball randomization

In such applications as bi-level optimization and huge-scale optimization we can encounter a situation when we can not calculate subgradient of a convex function which is minimized. In such situations we can use stochastic approximation of the gradient using finite difference. In a recent work by Yu. Nesterov a normal randomization is considered. In this work we consider the case of randomization with vectors uniformly distributed over a unit sphere. We provide complexity bounds for simple random search for smooth convex function and strongly convex smooth convex function. Also we consider the case when the value of the function is calculated with independent stochastic error with zero mean and bounded by known value.

Преподаватели: Гасников Александр Владимирович, Двуреченский Павел , Анастасия Лагуновская, 27 декабря 2014

Прошедшие мероприятия:

07.11.2014
МФТИ, 303 КПМ

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

19.05.2014

20.05.2014

21.05.2014

22.05.2014

Invited Plenary Talk (title TBA)

SIAM (Society for Industrial and Applied Mathematics)

15.05.2014

16.05.2014

Advances in Optimization and Statistics

Institute of Information Transmission Problems of RAS (Kharkevich Institute)

15.05.2014
IITP RAS

6. International Workshop "Advances in Optimization and Statistics"

11.04.2014
МФТИ, 303 КПМ

Intermediate gradient method for convex problems with stochastic inexact oracle

Члены лаборатории:
Dorn Yuriy
Должность: Младший научный сотрудник
Spokoiny Vladimir
Должность: Руководитель
Polyak Boris
Должность: Ведущий научный сотрудник
Shpirko Sergei
Должность: Ведущий научный сотрудник
Gasnikov Alexander
Должность: Ведущий научный сотрудник
Kabatiansky Grigory
Должность: Ведущий научный сотрудник
Dvurechensky Pavel
Должность: Ведущий научный сотрудник
Maximov Yury
Должность: Младший научный сотрудник
Gagloev Alexander
Должность: Младший научный сотрудник
Nazin Alexander
Должность: Ведущий научный сотрудник