A Survey of Optimization Methods from a Machine Learning Perspective <s> 2) Adaptive <s> In this paper we present a new approach for constructing subgradient schemes for different types of nonsmooth problems with convex structure. Our methods are primal-dual since they are always able to generate a feasible approximation to the optimum of an appropriately formulated dual problem. Besides other advantages, this useful feature provides the methods with a reliable stopping criterion. The proposed schemes differ from the classical approaches (divergent series methods, mirror descent methods) by presence of two control sequences. The first sequence is responsible for aggregating the support functions in the dual space, and the second one establishes a dynamically updated scale between the primal and dual spaces. This additional flexibility allows to guarantee a boundedness of the sequence of primal test points even in the case of unbounded feasible set (however, we always assume the uniform boundedness of subgradients). We present the variants of subgradient schemes for nonsmooth convex minimization, minimax problems, saddle point problems, variational inequalities, and stochastic optimization. In all situations our methods are proved to be optimal from the view point of worst-case black-box lower complexity bounds. <s> BIB001 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 2) Adaptive <s> We review adaptive Markov chain Monte Carlo algorithms (MCMC) as a mean to optimise their performance. Using simple toy examples we review their theoretical underpinnings, and in particular show why adaptive MCMC algorithms might fail when some fundamental properties are not satisfied. This leads to guidelines concerning the design of correct algorithms. We then review criteria and the useful framework of stochastic approximation, which allows one to systematically optimise generally used criteria, but also analyse the properties of adaptive MCMC algorithms. We then propose a series of novel adaptive algorithms which prove to be robust and reliable in practice. These algorithms are applied to artificial and high dimensional scenarios, but also to the classic mine disaster dataset inference problem. <s> BIB002 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 2) Adaptive <s> In this paper we propose a new framework for learning from large scale datasets based on iterative learning from small mini-batches. By adding the right amount of noise to a standard stochastic gradient optimization algorithm we show that the iterates will converge to samples from the true posterior distribution as we anneal the stepsize. This seamless transition between optimization and Bayesian posterior sampling provides an inbuilt protection against overfitting. We also propose a practical method for Monte Carlo estimates of posterior statistics which monitors a "sampling threshold" and collects samples after it has been surpassed. We apply the method to three models: a mixture of Gaussians, logistic regression and ICA with natural gradients. <s> BIB003 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 2) Adaptive <s> Many problems arising in applications result in the need to probe a probability distribution for functions. Examples include Bayesian nonparametric statistics and conditioned diffusion processes. Standard MCMC algorithms typically become arbitrarily slow under the mesh refinement dictated by nonparametric description of the unknown function. We describe an approach to modifying a whole range of MCMC methods, applicable whenever the target measure has density with respect to a Gaussian process or Gaussian random field reference measure, which ensures that their speed of convergence is robust under mesh refinement. ::: ::: Gaussian processes or random fields are fields whose marginal distributions, when evaluated at any finite set of NNpoints, are ℝ^N-valued Gaussians. The algorithmic approach that we describe is applicable not only when the desired probability measure has density with respect to a Gaussian process or Gaussian random field reference measure, but also to some useful non-Gaussian reference measures constructed through random truncation. In the applications of interest the data is often sparse and the prior specification is an essential part of the overall modelling strategy. These Gaussian-based reference measures are a very flexible modelling tool, finding wide-ranging application. Examples are shown in density estimation, data assimilation in fluid mechanics, subsurface geophysics and image registration. ::: ::: The key design principle is to formulate the MCMC method so that it is, in principle, applicable for functions; this may be achieved by use of proposals based on carefully chosen time-discretizations of stochastic dynamical systems which exactly preserve the Gaussian reference measure. Taking this approach leads to many new algorithms which can be implemented via minor modification of existing algorithms, yet which show enormous speed-up on a wide range of applied problems. <s> BIB004 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 2) Adaptive <s> Dynamics-based sampling methods, such as Hybrid Monte Carlo (HMC) and Langevin dynamics (LD), are commonly used to sample target distributions. Recently, such approaches have been combined with stochastic gradient techniques to increase sampling efficiency when dealing with large datasets. An outstanding problem with this approach is that the stochastic gradient introduces an unknown amount of noise which can prevent proper sampling after discretization. To remedy this problem, we show that one can leverage a small number of additional variables to stabilize momentum fluctuations induced by the unknown noise. Our method is inspired by the idea of a thermostat in statistical physics and is justified by a general theory. <s> BIB005 </s> A Survey of Optimization Methods from a Machine Learning Perspective <s> 2) Adaptive <s> Stan is a probabilistic programming language for specifying statistical models. A Stan program imperatively defines a log probability function over parameters conditioned on specified data and constants. As of version 2.14.0, Stan provides full Bayesian inference for continuous-variable models through Markov chain Monte Carlo methods such as the No-U-Turn sampler, an adaptive form of Hamiltonian Monte Carlo sampling. Penalized maximum likelihood estimates are calculated using optimization methods such as the limited memory Broyden-Fletcher-Goldfarb-Shanno algorithm. Stan is also a platform for computing log densities and their gradients and Hessians, which can be used in alternative algorithms such as variational Bayes, expectation propagation, and marginal inference using approximate integration. To this end, Stan is set up so that the densities, gradients, and Hessians, along with intermediate quantities of the algorithm such as acceptance probabilities, are easily accessible. Stan can be called from the command line using the cmdstan package, through R using the rstan package, and through Python using the pystan package. All three interfaces support sampling and optimization-based inference with diagnostics and posterior analysis. rstan and pystan also provide access to log probabilities, gradients, Hessians, parameter transforms, and specialized plotting. <s> BIB006
Step Size ǫ: The performance of HMC is highly sensitive to the step size ǫ in leapfrog integrator. If the ǫ is too small, the update will slow, and the calculation cost will be high; if the ǫ is too large, the rejection rate will be high, resulting in useless updates. To set ǫ reasonably and adaptively, a vanishing adaptation of the dual averaging algorithm can be used in HMC BIB001 , BIB002 . Specifically, a statistic H t = δ − α t is adopted in dual averaging method, where δ is the desired average acceptance probability, and α t is the current Metropolis-Hasting acceptance probability for iteration t. The statistic H t 's expectation h(ǫ) is defined as where ǫ t is the step size for iteration t in the leapfrog integrator. To satisfy h(ǫ) ≡ E t [H t |ǫ t ] = 0, we can derive the update formula of ǫ, i.e., ǫ t+1 = ǫ t − η t H t . Tuning ǫ by vanishing adaptation algorithm guarantees that the average acceptance probability of Metropolis verges to a fixed value. The hyper-parameters in the HMC include not only the step size ǫ and the length of iteration steps L, but also the mass M , etc. Optimizing these hyper-parameters can help improve sampling performance  , BIB006 , BIB004 . It is convenient and efficient to tune the hyper-parameters automatically without cumbersome adjustments based on data and variables in the MCMC. These adaptive tuning methods can be applied to other MCMC algorithms to improve the performance of the samplers. In addition to second-order SGHMC, stochastic gradient Langevin dynamics (SGLD) BIB003 is a first-order Langevin dynamic technique combined with stochastic optimization. Efficient variants of both SGLD and SGHMC are still active  , BIB005 .