Александр Владимирович Гасников
Концентрация равномерной меры на сфере и приложение к безградиентным методам выпуклой оптимизации
А. В. Гасников планирует провести 2 занятия.
Доступны 2 видеозаписи курса.
В некоторых многомерных задачах теории вероятностей важную роль играет эффект концентрации меры. А именно, с ростом размерности оказывается, что случайная величина "в подавляющем большинстве случаев" принимает примерно одно и то же значение. Об этом не раз рассказывалось на ЛШСМ. Популярно об этом написано в замечательной книге В.А. Зорича "Математический анализ задач естествознания". Но как правило, в вводных текстах и курсах про концентрацию меры разбираются довольно простые (игрушечные) примеры.
В данном мини-курсе мы представим (и даже схематично докажем) нетривиальный пример задачи на концентрацию равномерной меры на поверхности евклидовой сферы. А именно, мы зафиксируем вектор u и для случайного вектора v на сфере будем рассматривать величину |v|p⟨u,v⟩— произведение p- нормы v и скалярного произведения u с v. Будет показано, что такая функция сконцентрирована около своего среднего значения (медианы)- это означает, что для большинства векторов, задающих точку на сфере, значение этой функции близко к среднему значению. Данное наблюдение позволяет практически бесплатно получать оценку на среднее значение этой функции на сфере.
В свою очередь, последняя величина играет важную роль в решении задачи, о которой ранее в ЛШСМ рассказывал В.Ю. Протасов "Как по значениям функции найти ее минимум?" С помощью полученной оценки среднего значения описанной выше функции будет показано, что для задач гладкой выпуклой оптимизации, у которых разреженное решение (много нулевых компонент в решении) можно получать оценки на число вычислений значения функции существенно лучшие, чем известные нижние оценки (А.С. Немировский, 1979). Противоречия тут нет, потому что было сделано дополнительное предположение о разреженной структуре решения (нижние оценки были получены без этого предположения).
Данный мини-курс про концентрацию меры и оптимизацию можно понимать, как идейное продолжение двух мини-курсов про оптимизацию и про концентрацию меры, прочитанных в прошлом году. Однако, слушать его можно независимо. От слушателей предполагается знакомство с основами дифференциального и интегрального исчисления и знание основ теории вероятностей. Впрочем, все конкретные необходимые факты планируется напоминать.
Organization Committee e-mail:
dubna@mccme.ru