User menu

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

Variable Metric Random Pursuit

Primary tabs

Stich, Sebastian [UCL] Muller, C. L. [Simons Center for Data Analysis, Simons Foundation, New York, USA] Gartner, B. [Institute of Theoretical Computer Science, ETH Zurich, Zurich, Switzerland]

We consider unconstrained randomized optimization of smooth convex objective functions in the gradient-free setting. We analyze Random Pursuit (RP) algorithms with fixed (F-RP) and variable metric (V-RP). The algorithms only use zeroth-order information about the objective function and compute an approximate solution by repeated optimization over randomly chosen one-dimensional subspaces. The distribution of search directions is dictated by the chosen metric. Variable Met- ric RP uses novel variants of a randomized zeroth-order Hessian approximation scheme recently introduced by Leventhal and Lewis (Optimization 60(3):329–345, 2011. doi:10.1080/02331930903100141). We here present (1) a refined analysis of the expected single step progress of RP algorithms and their global convergence on (strictly) convex functions and (2) novel convergence bounds for V-RP on strongly convex functions. We also quantify how well the employed metric needs to match the local geometry of the function in order for the RP algorithms to converge with the best possible rate. Our theoretical results are accompanied by numerical experi- ments, comparing V-RP with the derivative-free schemes CMA-ES, Implicit Filtering, Nelder–Mead, NEWUOA, Pattern-Search and Nesterov’s gradient-free algorithms.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès interdit
Publication date 2016
Language Anglais
Journal information "Mathematical Programming, Series A" - Vol. 156, no. 1, p. 549-579 (2016)
Peer reviewed yes
Publisher Springer-Verlag (Berlin Heidelberg)
issn 0025-5610
e-issn 1436-4646
Publication status Publié
Affiliations UCL - SSH/LIDAM/CORE - Center for operations research and econometrics
UCL - SST/ICTM/INMA - Pôle en ingénierie mathématique
Keywords Gradient-free optimization ; Convex optimization ; Variable metric ; Line search
Links
  1. Adamczak, R., Litvak, A.E., Pajor, A., Tomczak-Jaegermann, N.: Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles. J. AMS 23, 535–561 (2010). doi: 10.1090/S0894-0347-09-00650-X
  2. Armijo Larry, Minimization of functions having Lipschitz continuous first partial derivatives, 10.2140/pjm.1966.16.1
  3. Brockhoff Dimo, Auger Anne, Hansen Nikolaus, Arnold Dirk V., Hohm Tim, Mirrored Sampling and Sequential Selection for Evolution Strategies, Parallel Problem Solving from Nature, PPSN XI (2010) ISBN:9783642158438 p.11-21, 10.1007/978-3-642-15844-5_2
  4. BROYDEN C. G., The Convergence of a Class of Double-rank Minimization Algorithms 1. General Considerations, 10.1093/imamat/6.1.76
  5. Davidon William C., Variable Metric Method for Minimization, 10.1137/0801001
  6. Fletcher R., A new approach to variable metric algorithms, 10.1093/comjnl/13.3.317
  7. Goldfarb Donald, A family of variable-metric methods derived by variational means, 10.1090/s0025-5718-1970-0258249-6
  8. Goldstein A. A., On Steepest Descent, 10.1137/0303013
  9. Hansen Nikolaus, Ostermeier Andreas, Completely Derandomized Self-Adaptation in Evolution Strategies, 10.1162/106365601750190398
  10. Heijmans Risto, When does the expectation of a ratio equal the ratio of expectations?, 10.1007/bf02927114
  11. Horn Roger A., Johnson Charles R., Matrix analysis, ISBN:9780511810817, 10.1017/cbo9780511810817
  12. Hu T. C., Klee Victor, Larman David, Optimization of Globally Convex Functions, 10.1137/0327055
  13. Jägersküpper Jens, Lower Bounds for Hit-and-Run Direct Search, Stochastic Algorithms: Foundations and Applications ISBN:9783540748700 p.118-129, 10.1007/978-3-540-74871-7_11
  14. Kelley C. T., Implicit Filtering, ISBN:9781611971897, 10.1137/1.9781611971903
  15. Kjellstrom G., Taxen L., Stochastic optimization in system design, 10.1109/tcs.1981.1085030
  16. Leventhal D., Lewis A.S., Randomized Hessian estimation and directional search, 10.1080/02331930903100141
  17. Marti K., Controlled random search procedures for global optimization, Lecture Notes in Control and Information Sciences ISBN:3540166599 p.457-474, 10.1007/bfb0007122
  18. Mathai, A.M., Provost, S.B.: Quadratic forms in random variables: theory and applications. No. 126. In: Statistics: Textbooks and Monographs. New York, Dekker (1992)
  19. Müller Christian L., Sbalzarini Ivo F., Gaussian Adaptation Revisited – An Entropic View on Covariance Matrix Adaptation, Applications of Evolutionary Computation (2010) ISBN:9783642122385 p.432-441, 10.1007/978-3-642-12239-2_45
  20. Nelder J. A., Mead R., A Simplex Method for Function Minimization, 10.1093/comjnl/7.4.308
  21. Nesterov, Y.: Random Gradient-Free Minimization of Convex Functions. Technical report, ECORE (2011)
  22. Powell M. J. D., The NEWUOA software for unconstrained optimization without derivatives, Nonconvex Optimization and Its Applications (2006) ISBN:9780387300634 p.255-297, 10.1007/0-387-30065-1_16
  23. Puntanen Simo, Styan George P. H., Isotalo Jarkko, Matrix Tricks for Linear Statistical Models, ISBN:9783642104725, 10.1007/978-3-642-10473-2
  24. Rosenbrock H. H., An Automatic Method for Finding the Greatest or Least Value of a Function, 10.1093/comjnl/3.3.175
  25. Schumer M., Steiglitz K., Adaptive step size random search, 10.1109/tac.1968.1098903
  26. Shanno D. F., Conditioning of quasi-Newton methods for function minimization, 10.1090/s0025-5718-1970-0274029-x
  27. Stich, S.U.: Convex optimization with random pursuit. ETH Zurich (2014). doi: 10.3929/ethz-a-010377352
  28. Stich Sebastian U., Müller Christian L., On Spectral Invariance of Randomized Hessian and Covariance Matrix Adaptation Schemes, Lecture Notes in Computer Science (2012) ISBN:9783642329364 p.448-457, 10.1007/978-3-642-32937-1_45
  29. Stich S. U., Müller C. L., Gärtner B., Optimization of Convex Functions with Random Pursuit, 10.1137/110853613
  30. Stich, S.U., Müller, C.L., Gärtner, B.: Supporting online material for: variable metric random pursuit. arXiv:1210.5114 (2014)
  31. Wedderburn, J.H.M.: Lectures on Matrices. (Colloquium Publications) AMS, New York (1938)
  32. Wolfe Philip, Convergence Conditions for Ascent Methods, 10.1137/1011036
  33. Wolfe Philip, Convergence Conditions for Ascent Methods. II: Some Corrections, 10.1137/1013035
Bibliographic reference Stich, Sebastian ; Muller, C. L. ; Gartner, B.. Variable Metric Random Pursuit. In: Mathematical Programming, Series A, Vol. 156, no. 1, p. 549-579 (2016)
Permanent URL http://hdl.handle.net/2078.1/175747