User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Random gradient-free minimization of convex functions

Primary tabs

Nesterov, Yurii [UCL] Spokoiny, Vladimir [Weierstrasse Institute for Applied Analysis and Stochastics, University of Berlin, Germany]

In this paper, we prove new complexity bounds for methods of convex optimization based only on computation of the function value. The search directions of our schemes are normally distributed random Gaussian vectors. It appears that such methods usually need at most n times more iterations than the standard gradient methods, where n is the dimension of the space of variables. This conclusion is true for both nonsmooth and smooth problems. For the latter class, we present also an accelerated scheme with the expected rate of convergence O(n2k2), where k is the iteration counter. For stochastic optimization, we propose a zero-order scheme and justify its expected rate of convergence O(nk1/2). We give also some bounds for the rate of convergence of the random gradient-free methods to stationary points of nonconvex functions, for both smooth and nonsmooth cases. Our theoretical results are supported by preliminary computational experiments.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès restreint
Publication date 2017
Language Anglais
Journal information "Foundations of Computational Mathematics" - Vol. 17, no. 2, p. 527-566 (2017)
Peer reviewed yes
Publisher Springer New York LLC ((United States) New York)
issn 1615-3375
e-issn 1615-3383
Publication status Publié
Affiliations UCL - SST/ICTM/INMA - Pôle en ingénierie mathématique
UCL - SSH/LIDAM/CORE - Center for operations research and econometrics
Links
  1. A. Agarwal, O. Dekel, and L. Xiao, Optimal algorithms for online convex optimization with multi-point bandit feedback, in Proceedings of the 23rd Annual Conference on Learning, 2010, pp. 2840.
  2. Agarwal Alekh, Foster Dean P., Hsu Daniel, Kakade Sham M., Rakhlin Alexander, Stochastic Convex Optimization with Bandit Feedback, 10.1137/110850827
  3. Bertsimas Dimitris, Vempala Santosh, Solving convex programs by random walks, 10.1145/1008731.1008733
  4. F. Clarke, Optimization and nonsmooth analysis, Wliley, New York, 1983.
  5. Conn Andrew R., Scheinberg Katya, Vicente Luis N., Introduction to Derivative-Free Optimization, ISBN:9780898716689, 10.1137/1.9780898718768
  6. Dorea C. C. Y., Expected number of steps of a random optimization method, 10.1007/bf00934526
  7. J. Duchi, M.I. Jordan, M.J. Wainwright, and A. Wibisono, Finite sample convergence rate of zero-order stochastic optimization methods, in NIPS, 2012, pp. 1448-1456.
  8. A. D. Flaxman, A.T. Kalai, and B.H. Mcmahan, Online convex optimization in the bandit setting: gradient descent without a gradient, in Proceedings of the 16th annual ACM-SIAM symposium on Discrete Algorithms, 2005, pp. 385-394 .
  9. Kleinberg Robert, Slivkins Aleksandrs, Upfal Eli, Multi-armed bandits in metric spaces, 10.1145/1374376.1374475
  10. Lagarias Jeffrey C., Reeds James A., Wright Margaret H., Wright Paul E., Convergence Properties of the Nelder--Mead Simplex Method in Low Dimensions, 10.1137/s1052623496303470
  11. Lagarias Jeffrey C., Poonen Bjorn, Wright Margaret H., Convergence of the Restricted Nelder--Mead Algorithm in Two Dimensions, 10.1137/110830150
  12. J. Matyas, Random optimization. Automation and Remote Control, 26 (1965), pp. 246-253.
  13. Nelder J. A., Mead R., A Simplex Method for Function Minimization, 10.1093/comjnl/7.4.308
  14. Nemirovski A., Juditsky A., Lan G., Shapiro A., Robust Stochastic Approximation Approach to Stochastic Programming, 10.1137/070704277
  15. A. Nemirovsky and D.Yudin, Problem complexity and method efficiency in optimization, John Wiley and Sons, New York, 1983.
  16. Nesterov Yurii, Introductory Lectures on Convex Optimization, ISBN:9781461346913, 10.1007/978-1-4419-8853-9
  17. Nesterov Yu., Lexicographic differentiation of nonsmooth functions, 10.1007/s10107-005-0633-0
  18. Yu. Nesterov, Random gradient-free minimization of convex functions, CORE Discussion Paper # 2011/1, (2011).
  19. Nesterov Yu., Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems, 10.1137/100802001
  20. B. Polyak, Introduction to Optimization. Optimization Software - Inc., Publications Division, New York, 1987.
  21. Protasov V. Yu., Algorithms for approximate calculation of the minimum of a convex function from its values, 10.1007/bf02312467
  22. Sarma M. S., On the convergence of the Baba and Dorea random optimization methods, 10.1007/bf00939542
Bibliographic reference Nesterov, Yurii ; Spokoiny, Vladimir. Random gradient-free minimization of convex functions. In: Foundations of Computational Mathematics, Vol. 17, no. 2, p. 527-566 (2017)
Permanent URL http://hdl.handle.net/2078.1/181316