RUS  ENG
Полная версия
ВИДЕОТЕКА

Летняя школа «Современная математика» имени Виталия Арнольда, 2018
26 июля 2018 г. 15:30, г. Дубна, Московская область, г. Дубна, дом отдыха «Ратмино»


Концентрация равномерной меры на сфере и приложение к безградиентным методам выпуклой оптимизации, занятие 1

А. В. Гасников



Аннотация: В некоторых многомерных задачах теории вероятностей важную роль играет эффект концентрации меры. А именно, с ростом размерности оказывается, что случайная величина «в подавляющем большинстве случаев» принимает примерно одно и то же значение. Об этом не раз рассказывалось на ЛШСМ. Популярно об этом написано в замечательной книге В.А. Зорича «Математический анализ задач естествознания». Но как правило, в вводных текстах и курсах про концентрацию меры разбираются довольно простые (игрушечные) примеры. В данном мини-курсе мы представим (и даже схематично докажем) нетривиальный пример задачи на концентрацию равномерной меры на поверхности евклидовой сферы. А именно, мы зафиксируем вектор $u$ и для случайного вектора $v$ на сфере будем рассматривать величину $|v|_p\langle u,v \rangle$ — произведение $p$-нормы $v$ и скалярного произведения $u$ с $v$. Будет показано, что такая функция сконцентрирована около своего среднего значения (медианы) — это означает, что для большинства векторов, задающих точку на сфере, значение этой функции близко к среднему значению. Данное наблюдение позволяет практически бесплатно получать оценку на среднее значение этой функции на сфере. В свою очередь, последняя величина играет важную роль в решении задачи, о которой ранее в ЛШСМ рассказывал В.Ю. Протасов — «Как по значениям функции найти ее минимум?» С помощью полученной оценки среднего значения описанной выше функции будет показано, что для задач гладкой выпуклой оптимизации, у которых разреженное решение (много нулевых компонент в решении) можно получать оценки на число вычислений значения функции существенно лучшие, чем известные нижние оценки (А.С. Немировский, 1979). Противоречия тут нет, потому что было сделано дополнительное предположение о разреженной структуре решения (нижние оценки были получены без этого предположения).

Website: https://www.mccme.ru/dubna/2018/courses/gasnikov.html
Цикл лекций


© МИАН, 2024