text: This paper studies the complexity of solving two classes of non-cooperative games in a distributed manner in which the players communicate with a set of system nodes over noisy communication channels. The complexity of solving each game class is defined as the minimum number of iterations required to find a Nash equilibrium (NE) of any game in that class with @math accuracy. First, we consider the class @math of all @math -player non-cooperative games with a continuous action space that admit at least one NE. Using information-theoretic inequalities, we derive a lower bound on the complexity of solving @math that depends on the Kolmogorov @math -capacity of the constraint set and the total capacity of the communication channels. We also derive a lower bound on the complexity of solving games in @math which depends on the volume and surface area of the constraint set. We next consider the class of all @math -player non-cooperative games with at least one NE such that the players' utility functions satisfy a certain (differential) constraint. We derive lower bounds on the complexity of solving this game class under both Gaussian and non-Gaussian noise models. Our result in the non-Gaussian case is derived by establishing a connection between the Kullback-Leibler distance and Fisher information.
  @cite_14: We consider derivative-free algorithms for stochastic optimization problems that use only noisy function values rather than gradients, analyzing their finite-sample convergence rates. We show that if pairs of function values are available, algorithms that use gradient estimates based on random perturbations suffer a factor of at most √d in convergence rate over traditional stochastic gradient methods, where d is the problem dimension. We complement our algorithmic development with information-theoretic lower bounds on the minimax convergence rate of such problems, which show that our bounds are sharp with respect to all problem-dependent quantities: they cannot be improved by more than constant factors.
  @cite_8: We consider derivative-free algorithms for stochastic and nonstochastic convex optimization problems that use only function values rather than gradients. Focusing on nonasymptotic bounds on convergence rates, we show that if pairs of function values are available, algorithms for @math -dimensional optimization that use gradient estimates based on random perturbations suffer a factor of at most @math in convergence rate over traditional stochastic gradient methods. We establish such results for both smooth and nonsmooth cases, sharpening previous analyses that suggested a worse dimension dependence, and extend our results to the case of multiple ( @math ) evaluations. We complement our algorithmic development with information-theoretic lower bounds on the minimax convergence rate of such problems, establishing the sharpness of our achievable results up to constant (sometimes logarithmic) factors.
  @cite_3: We consider the problem of optimizing convex and concave functions with access to an erroneous zeroth-order oracle. In particular, for a given function x → f (x) we consider optimization when one is given access to absolute error oracles that return values in [f (x) - ∊, f (x) + ∊] or relative error oracles that return value in [(1 - ∊)f (x), (1 + ∊)f (x)], for some ∊ > 0. We show stark information theoretic impossibility results for minimizing convex functions and maximizing concave functions over polytopes in this model.
  @cite_16: We study the intrinsic limitations of sequential convex optimization through the lens of feedback information theory. In the oracle model of optimization, an algorithm queries an oracle for noisy information about the unknown objective function and the goal is to (approximately) minimize every function in a given class using as few queries as possible. We show that, in order for a function to be optimized, the algorithm must be able to accumulate enough information about the objective. This, in turn, puts limits on the speed of optimization under specific assumptions on the oracle and the type of feedback. Our techniques are akin to the ones used in statistical literature to obtain minimax lower bounds on the risks of estimation procedures; the notable difference is that, unlike in the case of i.i.d. data, a sequential optimization algorithm can gather observations in a controlled manner, so that the amount of information at each step is allowed to change in time. In particular, we show that optimization algorithms often obey the law of diminishing returns: the signal-to-noise ratio drops as the optimization algorithm approaches the optimum. To underscore the generality of the tools, we use our approach to derive fundamental lower bounds for a certain active learning problem. Overall, the present work connects the intuitive notions of “information” in optimization, experimental design, estimation, and active learning to the quantitative notion of Shannon information.
  @cite_13: This paper provides lower bounds on the convergence rate of Derivative Free Optimization (DFO) with noisy function evaluations, exposing a fundamental and unavoidable gap between the performance of algorithms with access to gradients and those with access to only function evaluations. However, there are situations in which DFO is unavoidable, and for such situations we propose a new DFO algorithm that is proved to be near optimal for the class of strongly convex objective functions. A distinctive feature of the algorithm is that it uses only Boolean-valued function comparisons, rather than function evaluations. This makes the algorithm useful in an even wider range of applications, such as optimization based on paired comparisons from human subjects, for example. We also show that regardless of whether DFO is based on noisy function evaluations or Boolean-valued function comparisons, the convergence rate is the same.
summary: The paper @cite_16 considered a model in which the algorithm observes noisy versions of the oracle's response and established lower bounds on the complexity of convex optimization problems under first order as well as gradient-only oracles. In @cite_13 , complexity lower bounds were obtained for convex optimization problems with a stochastic zero-order oracle. The paper @cite_14 studied the complexity of convex optimization problems under a zero-order stochastic oracle in which the optimization algorithm submits two queries at each iteration and the oracle responds to both queries. These results were extended to the case in which the algorithm makes queries about multiple points at each iteration in @cite_8 . In @cite_3 , the complexity of convex optimization problems was studied under an erroneous oracle model wherein the oracle's responses to queries are subject to absolute relative errors.