Consider a problem of minimizing the mathematical expectation of a convex loss function
on a given convex compact set of a finite-dimensional real space $E$ with a norm $\|\cdot\|$. The oracle produces unbiased stochastic subgradients of the loss function at current points with a
uniformly bounded second moment of dual norm in $E^*$. The goal is to modify the well-known
method of Mirror Descent (MD) proposed in 1979 by A.S. Nemirovskii and D.B. Yudin [1] and
generalized the famous gradient method from the Euclidean case to an arbitrary primal-dual
pair of spaces $(E,E^*)$; see also [2] and the references therein. In this paper (cf. [3]):
- The idea of a new, so-called inertial MD method is demonstrated on the example of a
deterministic optimization problem with continuous time; in particular, in the Euclidean
case the heavy ball method [4] is realized; it is noted that the new method does not use
additional averaging;
- The discrete algorithm of the inertial MD is described; the theorem on the upper bound
on the regret is proved (i.e., the difference between the current mean loss value and the
minimum value) for the problem of stochastic optimization;
- An illustrative computational example is given.
In the conclusion, we discuss future work on both deterministic and stochastic algorithms
of inertial mirror descent.
References
[1] Nemirovskii, A. S. and Yudin, D. B., Slozhnost’ zadach i effektivnost’ metodov optimizatsii,
Moscow: Nauka, 1979 (in Russian). Translated under the title Problem Complexity and
Method Efficiency in Optimization, Chichester: Wiley, 1983.
[2] Juditsky, A. B., Nazin, A. V., Tsybakov, A. B., and N. Vayatis, N.: Recursive aggregation
of estimators by the mirror descent algorithm with averaging // Problems of Information
Transmission, 41(4):368–384, 2005. Translated from Problemy Peredachi Informatsii, No.4,
2005, pp.78–96.
[3] Nazin, A. V.: Algorithms of Inertial Mirror Descent in Convex Problems of Stochastic
Optimization // Automation and Remote Control. 2017. Submitted.
[4] Polyak, B. T.: Some methods of speeding up the convergence of iteration methods //
USSR Computational Mathematics and Mathematical Physics, 4(5):1–17, 1964.