This paper addresses the problem of minimizing a convex, Lipschitz function @math over a convex, compact set @math under a stochastic bandit feedback model. In this model, the algorithm is allowed to observe noisy realizations of the function value @math at any query point @math . The quantity of interest is the regret of the algorithm, which is the sum of the function values at algorithm's query points minus the optimal function value. We demonstrate a generalization of the ellipsoid algorithm that incurs @math regret. Since any algorithm has regret at least @math on this problem, our algorithm is optimal in terms of the scaling with @math .
We note that most of the existing approaches to derivative-free optimization outlined in the recent book @cite_3 typically search for a descent or sufficient descent direction and then take a step in this direction. However, most convergence results are asymptotic and do not provide concrete rates even in an optimization error setting. The main emphasis is often on global optimization of non-convex functions, while we are mainly interested in convex functions in this work. Nesterov @cite_13 recently analyzes schemes similar to that of @cite_1 with access to function evaluations, showing @math convergence for non-smooth functions and accelerated schemes for smooth mean cost functions. However, when analyzed in a noisy evaluation setting, his rates suffer from the degradation as those of @cite_1 .
@cite_1 @cite_13 @cite_3
153281708 2149479912 181733065
Bandit convex optimization is a special case of online convex optimization with partial information. In this setting, a player attempts to minimize a sequence of adversarially generated convex loss functions, while only observing the value of each function at a single point. In some cases, the minimax regret of these problems is known to be strictly worse than the minimax regret in the corresponding full information setting. We introduce the multi-point bandit setting, in which the player can query each loss function at multiple points. When the player is allowed to query each function at two points, we prove regret bounds that closely resemble bounds for the full information case. This suggests that knowing the value of each loss function at two points is almost as useful as knowing the value of each function everywhere. When the player is allowed to query each function at d+1 points (d being the dimension of the space), we prove regret bounds that are exactly equivalent to full information bounds for smooth functions. 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 @math O(n2k2), where k is the iteration counter. For stochastic optimization, we propose a zero-order scheme and justify its expected rate of convergence @math 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. The absence of derivatives, often combined with the presence of noise or lack of smoothness, is a major challenge for optimization. This book explains how sampling and model techniques are used in derivative-free methods and how these methods are designed to efficiently and rigorously solve optimization problems. Although readily accessible to readers with a modest background in computational mathematics, it is also intended to be of interest to researchers in the field. Introduction to Derivative-Free Optimization is the first contemporary comprehensive treatment of optimization without derivatives. This book covers most of the relevant classes of algorithms from direct search to model-based approaches. It contains a comprehensive description of the sampling and modeling tools needed for derivative-free optimization; these tools allow the reader to better understand the convergent properties of the algorithms and identify their differences and similarities. Introduction to Derivative-Free Optimization also contains analysis of convergence for modified Nelder Mead and implicit-filtering methods, as well as for model-based methods such as wedge methods and methods based on minimum-norm Frobenius models. Audience: The book is intended for anyone interested in using optimization on problems where derivatives are difficult or impossible to obtain. Such audiences include chemical, mechanical, aeronautical, and electrical engineers, as well as economists, statisticians, operations researchers, management scientists, biological and medical researchers, and computer scientists. It is also appropriate for use in an advanced undergraduate or early graduate-level course on optimization for students having a background in calculus, linear algebra, and numerical analysis. Contents: Preface; Chapter 1: Introduction; Part I: Sampling and modeling; Chapter 2: Sampling and linear models; Chapter 3: Interpolating nonlinear models; Chapter 4: Regression nonlinear models; Chapter 5: Underdetermined interpolating models; Chapter 6: Ensuring well poisedness and suitable derivative-free models; Part II: Frameworks and algorithms; Chapter 7: Directional direct-search methods; Chapter 8: Simplicial direct-search methods; Chapter 9: Line-search methods based on simplex derivatives; Chapter 10: Trust-region methods based on derivative-free models; Chapter 11: Trust-region interpolation-based methods; Part III: Review of other topics; Chapter 12: Review of surrogate model management; Chapter 13: Review of constrained and other extensions to derivative-free optimization; Appendix: Software for derivative-free optimization; Bibliography; Index.