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