Variable metric evolution strategies, such as CMA-ES, are powerful tools for black-box optimization. Despite some theoretical guarantees, our understanding of their optimization dynamics remains incomplete. Theory-guided empirical analysis offers a promising way to address this gap. This study employs drift analysis to evaluate the transient behavior of a simplified (1+1)CMA-ES variant by defining a potential function and examining its induced additive drift.Building on prior work, we investigate how variations in hyperparameters influence drift and assess whether commonly used parameter values are optimal for ensuring convergence. The alternative hypothesis is that tuning the parameters of the algorithm together with the parameters of the potential function can yield larger drift, and hence ultimately a better convergence guarantee. Using a normal form representation, we conduct extensive Monte Carlo simulations over a structured grid of algorithmic states. Our results highlight the role of step size adaptation and covariance matrix update mechanisms in shaping the convergence behavior. By optimizing the weights of the potential function components, we identify configurations that minimize (desired) negative drift and enhance algorithmic stability.These findings contribute to a deeper understanding of CMA-ES convergence dynamics and lay the groundwork for future theoretical guarantees. Ultimately, our study demonstrates the value of combining empirical and theoretical perspectives to enhance the reliability of evolution strategies in black-box optimization.

Drift analysis is a great tool for proving that optimization algorithms work the way we think they do, and for analyzing them, potentially in great detail. In this talk, I will discuss drift analysis for evolution strategies. These algorithms exhibit linear convergence on a wide range of problems, which corresponds to a linear decrease of the logarithmic distance of the best-so-far sample from the optimum, giving rise to simple additive drift. That behavior is enabled by online adaptation of the step size, which decays at the same rate as the distance to the optimum. Moreover, modern evolution strategies like CMA-ES adapt not only the step size, but rather the full covariance matrix of their sampling distribution. The mechanism enables convergence at a problem-independent rate that depends only on the dimension of the search space. The primary challenge of proving the convergence of CMA-ES lies in establishing the stability of the adaptation process, which was recently achieved by analyzing the invariant Markov chain that describes the parameter adaptation process. Yet, a drift-based analysis is still desirable because it can yield much more fine-grained results. For instance, it can provide details about the transient adaptation phase, which often takes up the lion's share of the time for solving the problem. To achieve this, we need a potential function that appropriately penalizes unsuitable parameter configurations, or more precisely, configurations the algorithm tends to move away from. Designing a potential function that captures the dynamics of covariance matrix adaptation is an ongoing challenge. I will present our recent research efforts towards this goal and emphasize why relatively simple additive drift offers a powerful framework for achieving it.

We present a novel method for constructing a close-to-optimal potential function for drift analysis of evolution strategies and other numerical optimization algorithms. It is based on a piecewise linear ansatz for the potential function, defined by potential values on a discrete grid of states together with a corresponding interpolation scheme. We compute or approximate the algorithm dynamics on the grid and then construct a linear program from expected progress and (weighted) state transitions. The solution of the optimization problem gives rise to parameters of the potential function maximizing (additive) drift. Under mild assumptions, the proceeding yields an arbitrarily close approximation of the optimal potential function at the expense of growing computational demands. As a proof of concept we apply the method to the (1+1) evolution strategy on the two-dimensional sphere function.

We design a class of variable metric evolution strategies well suited for high-dimensional problems. We target problems with many variables, not (necessarily) with many objectives. The construction combines two independent developments: efficient algorithms for scaling covariance matrix adaptation to high dimensions, and evolution strategies for multi-objective optimization. In order to design a specific instance of the class we first develop a (1+1) version of the limited memory matrix adaptation evolution strategy and then use an established standard construction to turn a population thereof into a state-of-the-art multi-objective optimizer with indicator-based selection. The method compares favorably to adaptation of the full covariance matrix.

To gain a deeper understanding of the behavior and learning dynamics of artificial neural networks, mathematical abstractions and models are valuable. They provide a simplified perspective and facilitate systematic investigations. In this paper, we propose to analyze dynamics of artificial neural activation using stochastic processes, which have not been utilized for this purpose thus far. Our approach involves modeling the activation patterns of nodes in artificial neural networks as stochastic processes. By focusing on the activation frequency, we can leverage techniques used in neuroscience to study neural spike trains. Specifically, we extract the activity of individual artificial neurons during a classification task and model their activation frequency. The underlying process model is an arrival process following a Poisson distribution. We examine the theoretical fit of the observed data generated by various artificial neural networks in image recognition tasks to the proposed model’s key assumptions. Through the stochastic process model, we derive measures describing activation patterns of each network. We analyze randomly initialized, generalizing, and memorizing networks, allowing us to identify consistent differences in learning methods across multiple architectures and training sets. We calculate features describing the distribution of Activation Rate and Fano Factor, which prove to be stable indicators of memorization during learning. These calculated features offer valuable insights into network behavior. The proposed model demonstrates promising results in describing activation patterns and could serve as a general framework for future investigations. It has potential applications in theoretical simulation studies as well as practical areas such as pruning or transfer learning.

DiBB (for Distributing Black-Box) is a meta-algorithm and framework that addresses the decades-old scalability issue of Black-Box Optimization (BBO), including Evolutionary Computation. Algorithmically, it does so by creating out-of-the-box a Partially Separable (PS) version of any existing black-box algorithm. This is done by leveraging expert knowledge about the task at hand to define blocks of parameters expected to have significant correlation, such as weights entering a same neuron/layer in a neuroevolution application. DiBB distributes the computation to a set of machines without further customization, while still retaining the advanced features of the underlying BBO algorithm, such as scale invariance and step-size adaptation, which are typically lost in recent distributed ES implementations. This is achieved by instantiating a separate instance of the underlying base algorithm for each block, running on a dedicated machine, with DiBB handling communication and constructing complete individuals for evaluation on the original task. DiBB's performance scales constantly with the number of parameter-blocks defined, which should allow for unprecedented applications on large clusters. Our reference implementation (Python, on GitHub and PyPI) demonstrates a 5x speed-up on COCO/BBOB using our new PS-CMA-ES. We also showcase a neuroevolution application (11 590 weights) on the PyBullet Walker2D with our new PS-LM-MA-ES.

Transfer Learning methods aim to reuse previously acquired knowledge about a source task to facilitate learning of a target task. In this paper, we present a Meta Learning approach to find optimal hyperparameters for Transfer Learning processes given previously known metadata about the source task, the target task, and the pre-trained model. We collected metadata and model parameters from more than 15,000 Transfer Learning processes in a dataset, which we use to learn metamodels that predict a Transfer Learning process result in terms of accuracy on the validation sets, given prior information such as the number of epochs, learning rates, optimizers, etc. Using feedforward multilayer perceptrons (MLP), we show that and how our approach finds efficient hyperparameters for Transfer Learning for image classification.

The class of algorithms called Hessian Estimation Evolution Strategies (HE-ESs) update the covariance matrix of their sampling distribution by directly estimating the curvature of the objective function. The approach is practically efficient, as attested by respectable performance on the BBOB testbed, even on rather irregular functions. In this article, we formally prove two strong guarantees for the (1 + 4)-HE-ES, a minimal elitist member of the family: stability of the covariance matrix update, and as a consequence, linear convergence on all convex quadratic problems at a rate that is independent of the problem instance.

Modern model-based reinforcement learning methods for high-dimensional inputs often incorporate an unsupervised learning step for dimensionality reduction. The training objective of these unsupervised learning methods often leverages only static inputs such as reconstructing observations. These representations are combined with predictor functions for simulating rollouts to navigate the environment. We advance this idea by taking advantage of the fact that we navigate dynamic environments with visual stimulus and create a representation that is specifically designed with control and actions in mind. We propose to learn a feature map that is maximally predictable for a predictor function. This results in representations that are well suited for the task of planning, where the predictor is used as a forward model. To this end, we introduce a new way of learning this representation along with the prediction function, a system we dub Latent Representation Prediction Network (LARP). The prediction function is used as a forward model for a search on a graph in a viewpoint-matching task, and the representation learned to maximize predictability is found to outperform other representations. The sample efficiency and overall performance of our approach are shown to rival standard reinforcement learning methods, and our learned representation transfers successfully to unseen environments.

In stochastic optimization, particularly in evolutionary computation and reinforcement learning, the optimization of a function f : Ω → R is often addressed through optimizing a so-called relaxation θ ϵ Θ → Eθ(f) of f, where Θ resembles the parameters of a family of probability measures on Ω. We investigate the structure of such relaxations by means of measure theory and Fourier analysis, enabling us to shed light on the success of many associated stochastic optimization methods. The main structural traits we derive and that allow fast and reliable optimization of relaxations are the consistency of optimal values of f, Lipschitzness of gradients, and convexity. We emphasize settings where f itself is not differentiable or convex, e.g., in the presence of (stochastic) disturbance.

We establish global convergence of the (1 + 1) evolution strategy, that is, convergence to a critical point independent of the initial state. More precisely, we show the existence of a critical limit point, using a suitable extension of the notion of a critical point to measurable functions. At its core, the analysis is based on a novel progress guarantee for elitist, rank-based evolutionary algorithms. By applying it to the (1 + 1) evolution strategy we are able to provide an accurate characterization of whether global convergence is guaranteed with full probability, or whether premature convergence is possible. We illustrate our results on a number of example applications ranging from smooth (non-convex) cases over different types of saddle points and ridge functions to discontinuous and extremely rugged problems.

Convex quadratic objective functions are an important base case in state-of-the-art benchmark collections for single-objective optimization on continuous domains. Although often considered rather simple, they represent the highly relevant challenges of non-separability and ill-conditioning. In the multi-objective case, quadratic benchmark problems are under-represented. In this paper we analyze the specific challenges that can be posed by quadratic functions in the bi-objective case. Our construction yields a full factorial design of 54 different problem classes. We perform experiments with well-established algorithms to demonstrate the insights that can be supported by this function class. We find huge performance differences, which can be clearly attributed to two root causes: non-separability and alignment of the Pareto set with the coordinate system.

We present a dual subspace ascent algorithm for support vector machine training that respects a budget constraint limiting the number of support vectors. Budget methods are effective for reducing the training time of kernel SVM while retaining high accuracy. To date, budget training is available only for primal (SGD-based) solvers. Dual subspace ascent methods like sequential minimal optimization are attractive for their good adaptation to the problem structure, their fast convergence rate, and their practical speed. By incorporating a budget constraint into a dual algorithm, our method enjoys the best of both worlds. We demonstrate considerable speed-ups over primal budget training methods.

The covariance matrix adaptation evolution strategy (CMA-ES) is a popular method to deal with nonconvex and/or stochastic optimization problems when gradient information is not available. Being based on the CMA-ES, the recently proposed matrix adaptation evolution strategy (MA-ES) establishes the rather surprising result that the covariance matrix and all associated operations (e.g., potentially unstable eigen decomposition) can be replaced by an iteratively updated transformation matrix without any loss of performance. In order to further simplify MAES and reduce its O(n2) time and storage complexity to O(mn) with m ≪ n such as m ∈ O(1) or m∈O(log(n)), we present the limited-memory MA-ES for efficient zeroth order large-scale optimization. The algorithm demonstrates state-of-the-art performance on a set of established large-scale benchmarks.

This paper explores the use of the standard approach for proving runtime bounds in discrete domains---often referred to as drift analysis---in the context of optimization on a continuous domain. Using this framework we analyze the (1+1) Evolution Strategy with one-fifth success rule on the sphere function. To deal with potential functions that are not lower-bounded, we formulate novel drift theorems. We then use the theorems to prove bounds on the expected hitting time to reach a certain target fitness in finite dimension d. The bounds are akin to linear convergence. We then study the dependency of the different terms on d proving a convergence rate dependency of Θ(1/d). Our results constitute the first non-asymptotic analysis for the algorithm considered as well as the first explicit application of drift analysis to a randomized search heuristic with continuous domain.

In this paper, we propose an algorithm developed to detect the curbstone and its surroundings. This work is a part of the user-centered development of an assistance system currently being developed to support the older pedestrians crossing the road. For the development of this algorithm, an end-to-end learning approach was chosen. The convolutional neural network was selected to process raw pixels from a mono camera and the network was trained on a dataset to detect the curb. The use of end-to-end learning with a convolutional neural network proved remarkably powerful in distinguishing the curbstone. In order to train the network, images of curb and their surroundings were essential. For this purpose, a new dataset was created where multiple requirements, for example, different approach angles to the curbstone, weather and light conditions etc, were considered. As this system is currently being developed for Berlin (Germany), an analysis was carried out to determine the types and frequencies of pavements in Berlin pathways. Based on this analysis and the requirements, a dataset was created which comprises the images of the pavements, for example, cobblestone, concrete slabs etc, in diverse sets of weather and light conditions. This dataset was developed using the videos taken at 10 frames per second from a mono camera. For the collection of dataset and for testing purposes, a prototype in the form of a walker was built which has sensors, Leddar and camera mounted on it. This paper gives an overview of the development of the algorithm and describes the procedures, such as district analysis of Berlin and data collection, needed to develop the algorithm.

End-to-end learning refers to training a possibly complex learning system by applying gradient-based learning to the system as a whole. End-to-end learning systems are specifically designed so that all modules are differentiable. In effect, not only a central learning machine, but also all “peripheral” modules like representation learning and memory formation are covered by a holistic learning process. The power of end-to-end learning has been demonstrated on many tasks, like playing a whole array of Atari video games with a single architecture. While pushing for solutions to more challenging tasks, network architectures keep growing more and more complex. In this paper we ask the question whether and to what extent end-to-end learning is a future-proof technique in the sense of \emphscaling to complex and diverse data processing architectures. We point out potential inefficiencies, and we argue in particular that end-to-end learning does not make optimal use of the modular design of present neural networks. Our surprisingly simple experiments demonstrate these inefficiencies, up to the complete breakdown of learning.

We present a comparison of step size adaptation methods for evolution strategies, covering recent developments in the field. Following recent work by Hansen et al. we formulate a concise list of performance criteria: a) fast convergence of the mean, b) near-optimal fixed point of the normalized step size dynamics, and c) invariance to adding constant dimensions of the objective function. Our results show that algorithms violating these principles tend to underestimate the step size or are unreliable when the function does not fit to the algorithm's tuned hyperparameters. In contrast, we find that cumulative step size adaptation (CSA) and two-point adaptation (TPA) provide reliable estimates of the optimal step size. We further find that removing the evolution path of CSA still leads to a reliable algorithm without the computational requirements of CSA.

We present a novel technique for texture synthesis and style transfer based on convolutional neural networks (CNNs). Our method learns feed-forward image generators that correspond to specification of styles and textures in terms of high-level describable attributes such as 'striped', 'dotted', or 'veined'. Two key conceptual advantages over template-based approaches are that attributes can be analyzed and activated individually, while a template image necessarily represents a simultaneous specification of many attributes, and that attributes can combine aspects of many texture templates allowing flexibility in the generation process. Once the attribute-wise networks are trained, applications to texture synthesis and style transfer are fast, allowing for real-time video processing.

A unified view on multi-class support vector machines (SVMs) is presented, covering most prominent variants including the one- vs-all approach and the algorithms proposed by Weston & Watkins, Crammer & Singer, Lee, Lin, & Wahba, and Liu & Yuan. The unification leads to a template for the quadratic training problems and new multi-class SVM formulations. Within our framework, we provide a comparative analysis of the various notions of multi-class margin and margin-based loss. In particular, we demonstrate limitations of the loss function considered, for instance, in the Crammer & Singer machine. We analyze Fisher consistency of multi- class loss functions and universal consistency of the various machines. On the one hand, we give examples of SVMs that are, in a particular hyperparameter regime, universally consistent without being based on a Fisher consistent loss. These include the canonical extension of SVMs to multiple classes as proposed by Weston & Watkins and Vapnik as well as the one-vs-all approach. On the other hand, it is demonstrated that machines based on Fisher consistent loss functions can fail to identify proper decision boundaries in low-dimensional feature spaces. We compared the performance of nine different multi-class SVMs in a thorough empirical study. Our results suggest to use the Weston & Watkins SVM, which can be trained comparatively fast and gives good accuracies on benchmark functions. If training time is a major concern, the one-vs-all approach is the method of choice.

Covariance matrix adaptation (CMA) mechanisms are core building blocks of modern evolution strategies. Despite sharing a common principle, the exact implementation of CMA varies considerably between different algorithms. In this paper, we investigate the benefits of an exponential parametrization of the covariance matrix in the CMA-ES. This technique was first proposed for the xNES algorithm. It results in a multiplicative update formula for the covariance matrix. We show that the exponential parameterization and the multiplicative update are compatible with all mechanisms of CMA-ES. The resulting algorithm, xCMA-ES, performs at least on par with plain CMA-ES. Its advantages show in particular with updates that actively decrease the sampling variance in specific directions, i.e., for active constraint handling.

A particular strength of many evolution strategies is their invariance against strictly monotonic and therefore rank-preserving transformations of the objective function. Their view onto a continuous fitness landscape is therefore completely determined by the shapes of the level sets. Most modern algorithms can cope well with diverse shapes as long as these are sufficiently smooth. In contrast, the sharp angles found in level sets of ridge functions can cause premature convergence to a non-optimal point. We propose a simple and generic family of transformation of the fitness function to avoid this effect. This allows general purpose evolution strategies to solve even extremely sharp ridge problems.

Coordinate descent (CD) algorithms have become the method of choice for solving a number of machine learning tasks. They are particularly popular for training linear models, including linear support vector machine classification, LASSO regression, and logistic regression. We propose an extension of the CD algorithm, called the adaptive coordinate frequencies (ACF) method. This modified CD scheme does not treat all coordinates equally, in that it does not pick all coordinates equally often for optimization. Instead the relative frequencies of coordinates are subject to online adaptation. The resulting optimization scheme can result in significant speed-ups. We demonstrate the usefulness of our approach on a number of large scale machine learning problems.

We propose a generic method for turning a modern, non-elitist evolution strategy with fully adaptive covariance matrix into an asynchronous algorithm. This algorithm can process the result of an evaluation of the fitness function anytime and update its search strategy, without the need to synchronize with the rest of the population. The asynchronous update builds on the recent developments of natural evolution strategies and information geometric optimization.

Deep belief networks (DBNs) can approximate any distribution over fixed-length binary vectors. However, DBNs are frequently applied to model real-valued data, and so far little is known about their representational power in this case. We analyze the approximation properties of DBNs with two layers of binary hidden units and visible units with conditional distributions from the exponential family. It is shown that these DBNs can, under mild assumptions, model any additive mixture of distributions from the exponential family with independent variables. An arbitrarily good approximation in terms of Kullback-Leibler divergence of an m-dimensional mixture distribution with n components can be achieved by a DBN with m visible variables and n and n+1 hidden variables in the first and second hidden layer, respectively. Furthermore, relevant infinite mixtures can be approximated arbitrarily well by a DBN with a finite number of neurons. This includes the important special case of an infinite mixture of Gaussian distributions with fixed variance restricted to a compact domain, which in turn can approximate any strictly positive density over this domain.

A major limitation in applying evolution strategies to black box optimization is the possibility of convergence into bad local optima. Many techniques address this problem, mostly through restarting the search. However, deciding the new start location is nontrivial since neither a good location nor a good scale for sampling a random restart position are known. A black box search algorithm can nonetheless obtain some information about this location and scale from past exploration. The method proposed here makes explicit use of such experience, through the construction of an archive of novel solutions during the run. Upon convergence, the most "novel" individual found so far is used to position the new start in the least explored region of the search space, actively looking for a new basin of attraction. We demonstrate the working principle of the method on two multi-modal test problems.

The family of natural evolution strategies (NES) offers a principled approach to real-valued evolutionary optimization. NES follows the natural gradient of the expected fitness on the parameters of its search distribution. While general in its formulation, previous research has focused on multivariate Gaussian search distributions. Here we exhibit problem classes for which other search distributions are more appropriate, and then derive corresponding NES-variants.

The family of natural evolution strategies (NES) offers a principled approach to real-valued evolutionary optimization by following the natural gradient of the expected fitness. Like the well-known CMA-ES, the most competitive algorithm in the field, NES comes with important invariance properties. In this paper, we introduce a number of elegant and efficient improvements of the basic NES algorithm. First, we propose to parameterize the positive definite covariance matrix using the exponential map, which allows the covariance matrix to be updated in a vector space. This new technique makes the algorithm completely invariant under linear transformations of the underlying search space, which was previously achieved only in the limit of small step sizes. Second, we compute all updates in the natural coordinate system, such that the natural gradient coincides with the vanilla gradient. This way we avoid the computation of the inverse Fisher information matrix, which is the main computational bottleneck of the original NES algorithm. Our new algorithm, exponential NES (xNES), is significantly simpler than its predecessors. We show that the various update rules in CMA-ES are closely related to the natural gradient updates of xNES. However, xNES is more principled than CMA-ES, as all the update rules needed for covariance matrix adaptation are derived from a single principle. We empirically assess the performance of the new algorithm on standard benchmark functions

Steinwart was the first to prove universal consistency of support vector machine classification. His proof analyzed the ‘standard’ support vector machine classifier, which is restricted to binary classification problems. In contrast, recent analysis has resulted in the common belief that several extensions of SVM classification to more than two classes are inconsistent. Countering this belief, we proof the universal consistency of the multi-class support vector machine by Crammer and Singer. Our proof extends Steinwart’s techniques to the multi-class case.

Adapting the hyperparameters of support vector machines (SVMs) is a challenging model selection problem, especially when flexible kernels are to be adapted and data are scarce. We present a coherent framework for regularized model selection of 1-norm soft margin SVMs for binary classification. It is proposed to use gradient-ascent on a likelihood function of the hyperparameters. The likelihood function is based on logistic regression for robustly estimating the class conditional probabilities and can be computed efficiently. Overfitting is an important issue in SVM model selection and can be addressed in our framework by incorporating suitable prior distributions over the hyperparameters. We show empirically that gradient-based optimization of the likelihood function is able to adapt multiple kernel parameters and leads to better models than four concurrent state-of-the-art methods.

Iterative learning algorithms that approximate the solution of support vector machines (SVMs) have two potential advantages. First, they allow online and active learning. Second, for large data sets, computing the exact SVM solution may be too time-consuming, and an efficient approximation can be preferable. The powerful LASVM iteratively approaches the exact SVM solution using sequential minimal optimization (SMO). It allows efficient online and active learning. Here, this algorithm is considerably improved in speed and accuracy by replacing the working set selection in the SMO steps. A second-order working set selection strategy, which greedily aims at maximizing the progress in each single step, is incorporated.

Oligo kernels for biological sequence classification have a high discriminative power. A new parameterization for the K-mer oligo kernel is presented, where all oligomers of length K are weighted individually. The task specific choice of these parameters increases the classification performance and reveals information about discriminative features. For adapting the multiple kernel parameters based on cross-validation the covariance matrix adaptation evolution strategy is proposed. It is applied to optimize the trimer oligo kernels for the detection of bacterial gene starts. The resulting kernels lead to higher classification rates, and the adapted parameters reveal the importance of particular triplets for classification, for example of those occurring in the Shine-Dalgarno Sequence.

Biological data mining using kernel methods can be improved by a task-specific choice of the kernel function. Oligo kernels for genomic sequence analysis have proven to have a high discriminative power and to provide interpretable results. Oligo kernels that consider subsequences of different lengths can be combined and parameterized to increase their flexibility. For adapting these parameters efficiently, gradient-based optimization of the kernel-target alignment is proposed. The power of this new, general model selection procedure and the benefits of fitting kernels to problem classes are demonstrated by adapting oligo kernels for bacterial gene start detection.

Support vector machines are trained by solving constrained quadratic optimization problems. This is usually done with an iterative decomposition algorithm operating on a small working set of variables in every iteration. The training time strongly depends on the selection of these variables. We propose the maximum-gain working set selection algorithm for large scale quadratic programming. It is based on the idea to greedily maximize the progress in each single iteration. The algorithm takes second order information from cached kernel matrix entries into account. We prove the convergence to an optimal solution of a variant termed hybrid maximum-gain working set selection. This method is empirically compared to the prominent most violating pair selection and the latest algorithm using second order information. For large training sets our new selection scheme is significantly faster.

Gradient-based optimizing of gaussian kernel functions is considered. The gradient for the adaptation of scaling and rotation of the input space is computed to achieve invariance against linear transformations. This is done by using the exponential map as a parameterization of the kernel parameter manifold. By restricting the optimization to a constant trace subspace, the kernel size can be controlled. This is, for example, useful to prevent overfitting when minimizing radius-margin generalization performance measures. The concepts are demonstrated by training hard margin support vector machines on toy data.