F.S. Stonyakin. Adaptation to inexactness for some gradient-type optimization methods ... P. 210-225

We introduce a notion of inexact model of a convex objective function, which allows for errors both in the function and in its gradient. For this situation, a gradient method with an adaptive adjustment of some parameters of the model is proposed and an estimate for the convergence rate is found. This estimate is optimal on a class of sufficiently smooth problems in the presence of errors. We consider a special class of convex nonsmooth optimization problems. In order to apply the proposed technique to this class, an artificial error should be introduced. We show that the method can be modified for such problems to guarantee a convergence in the function with a nearly optimal rate on the class of convex nonsmooth optimization problems. An adaptive gradient method is proposed for objective functions with some relaxation of the Lipschitz condition for the gradient that satisfy the Polyak–Lojasievicz gradient dominance condition. Here, the objective function and its gradient can be given inexactly. The adaptive choice of the parameters is performed during the operation of the method with respect to both the Lipschitz constant of the gradient and a value corresponding to the error of the gradient and the objective function. The linear convergence of the method is justified up to a value associated with the errors.

Keywords: gradient method, adaptive method, Lipschitz gradient, nonsmooth optimization, gradient dominance condition

Received September 8, 2019

Revised October 21, 2019

Accepted October 28, 2019

Funding Agency: This work was supported by the Russian Science Foundation (project no. 18-71-00048).

Fedor Sergeevich Stonyakin, Cand. Sci. (Phys.-Math.), V.I. Vernadsky Crimean Federal University, Simferopol, Republic of Crimea, 295007 Russia, e-mail: fedyor@mail.ru

REFERENCES

1.   Necoara I., Nesterov Y. Glineur F. Linear convergence of first order methods for non-strongly convex optimization. Math. Program., 2019, vol. 175, pp. 69–107. doi: 10.1007/s10107-018-1232-1 

2.   Tyurin A. I., Gasnikov A. V. Fast gradient descent for convex minimization problems with an oracle issuing $(\delta,L)$-model of the function at the requested point. Comput. Math. Math. Phys., 2019, vol. 59, no. 7, pp. 1085–1097. doi: 10.1134/S0044466919070081 

3.    Stonyakin F. S., Dvinskikh D., Dvurechensky P., Kroshnin A., Kuznetsova O., Agafonov A., Gasnikov A., Tyurin A., Uribe C. A., Pasechnyuk D., Artamonov S. Gradient methods for problems with inexact model of the objective. In: M. Khachay, Y. Kochetov, P. Pardalos (eds.) Mathematical Optimization Theory and Operations Research (MOTOR 2019), Lecture Notes in Computer Science, vol. 11548, Cham: Springer, 2019, pp. 97–114. doi: 10.1007/978-3-030-22629-9_8 

4.   Lu H., Freund R. M., Nesterov Y. Relatively smooth convex optimization by Firstorder methods, and applications. SIAM J. Optim., 2018, vol. 28, no 1, pp. 333–354. doi: 10.1137/16M1099546 

5.   Devolder O., Glineur F., Nesterov Yu. First-order methods of smooth convex optimization with inexact oracle. Math. Program., 2014, vol. 146, no. 1-2, pp. 37–75. doi: 10.1007/s10107-013-0677-5 

6.   Devolder O. Exactness, Inexactness and Stochasticity in First-Order Methods for Large-Scale Convex Optimization, PhD thesis, 2013, 320 p.

7.   Nesterov Yu. Gradient methods for minimizing composite functions. Math. Program., 2013, vol. 140, no. 1, pp. 125–161. doi: 10.1007/s10107-012-0629-5 

8.   Nesterov Yu. E. Algoritmicheskaya vypuklaya optimizatsiya [Algorithmic convex optimization]. Doctor Sci. (Phys.-Math.) Dissertation. Moscow: Mosk. Phys.-Tech. Inst. (State University), 2013, 367 p.

9.   Karimi H., Nutini J., Schmidt M. Linear convergence of gradient and proximal-gradient methods under the Polyak–Lojasiewicz condition. In: B. Berendt etc. (eds.), Machine Learning and Knowledge Discovery in Databases, Lecture Notes in Computer Science, vol. 9851, Cham: Springer, 2016, pp. 795–811. doi: 10.1007/978-3-319-46128-1_50 

10.   Mordukhovich B. Variational analysis and generalized differentiation I, Theory and examples, Part of the Grundlehren der mathematischen Wissenschaften book series, vol 330, Berlin, Heidelberg: Springer-Verlag, 2006, 579 p. doi: 10.1007/3-540-31247-1 

11.   Polyak B. T. Gradient methods for minimizing functionals. Comput. Math. Math. Phys., 1963, vol. 3, no. 4, pp. 643–653. doi: 10.1016/0041-5553(63)90382-3 

12.   Polyak B. T. Vvedenie v optimizaciju [Introduction to Optimization]. Moscow: Nauka Publ., 1983, 384 p.

13.   Stonyakin F. S. An analog of quadratic interpolation for a special class of non-smooth functionals and one of its applications to the adaptive method of mirror descent. Dinamicheskie sistemy, 2019, vol. 9 (37), no. 1, pp. 3–16 (in Russian).

14.   Mordukhovich B. S., Nam N. M. Applications of variational analysis to a generalized Fermat–Torricelli problem. J. Optim. Theory Appl., 2011, vol. 148, no. 3, pp. 431–454. doi: 10.1007/s10957-010-9761-7 

15.   Nemirovsky A. S., Yudin D. B. Slozhnost’ zadach i effektivnost’ metodov optimizatsii [The complexity of tasks and the effectiveness of optimization methods]. Moscow: Nauka Publ., 1979, 384 p.

16.   Nesterov Yu. Universal gradient methods for convex optimization problems. Math. Program. Ser. A, 2015, vol. 152, iss. 1-2, pp. 381–404. doi: 10.1007/s10107-014-0790-0 

17.   D’Aspremont A. Smooth optimization with approximate gradient. SIAM J. Optim., 2008, vol. 19, no 3, pp. 1171–1183. doi: 10.1137/060676386 .

Cite this article as: F.S.Stonyakin, Adaptation to inexactness for some gradient-type optimization methods, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2019, vol. 25, no. 4, pp. 210–225 .