Аннотация:
В докладе пойдет речь о недавних работах Ю.Е. Нестерова с соавторами и работах
$$$$
Devolder O. Stochastic first order methods in smooth convex optimization. CORE Discussion Paper 2011/7. 2011.
$$$$
Ghadimi S., Lan G. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization, II: shrinking procedures and optimal algorithms // SIAM Journal on Optimization. 2013. V. 23(4), P. 2061–2089.
$$$$
на основе которых будут предложены, по-видимому, не улучшаемые оценки числа итераций, необходимых для численного решения задач выпуклой оптимизации во всех случаях (гладкий/негладкий, сильно выпуклый/выпуклый, стохастический/нестохастический, с точным оракулом/с неточным оракулом, с известными априорно характеристиками оптимизируемой функции (типа констант Липшица, сильной выпуклости)/неизвестными, которые должны адаптивно определяться). "Алгебра" в названии доклада отражает следующее: специализированные методы (алгоритмы), заточенные под свои семейства задач, на которых они оптимальны, можно в определенном смысле сочетать друг с другом так, что с точностью до логарифмических поправок получаются методы, оптимальные в пересечении этих классов.
