Bayesian optimization is a broadly applied methodology to optimize the expensive blackbox function. Despite its success, it still faces the challenge from the high-dimensional search space. To alleviate this problem, we propose a novel Bayesian optimization framework, which finds a low-dimensional space to perform Bayesian optimization through a semi-supervised, iterative, and embedding learning-based method (SILBO). SILBO incorporates both labeled and unlabeled points acquired from the acquisition function of Bayesian optimization to guide the learning of embedding space. To accelerate the learning procedure, we present a randomized method for generating the projection matrix. Furthermore, to map from the low-dimensional space to the high-dimensional original space, we propose two mapping strategies: SILBO-BU and SILBO-TD according to the evaluation overhead of the objective function. Experimental results on both synthetic function and hyperparameter optimization tasks demonstrate that SILBO outperforms the existing state-of-the-art high-dimensional Bayesian optimization methods.

We study the problem of differentially private constrained maximization of decomposable submodular functions. A submodular function is decomposable if it takes the form of a sum of submodular functions. The special case of maximizing a monotone, decomposable submodular function under cardinality constraints is known as the Combinatorial Public Projects (CPP) problem [Papadimitriou et al., 2008]. Previous work by Gupta et al. [2010] gave a differentially private algorithm for the CPP problem. We extend this work by designing differentially private algorithms for both monotone and non-monotone decomposable submodular maximization under general matroid constraints, with competitive utility guarantees. We complement our theoretical bounds with experiments demonstrating empirical performance, which improves over the differentially private algorithms for the general case of submodular maximization and is close to the performance of non-private algorithms.

The k-center problem is a fundamental problem we often face when considering complex service systems. Typical challenges include the placement of warehouses in logistics or positioning of servers for content delivery networks. We previously have proposed Dragoon as an effective algorithm to approach the k-center problem. This paper evaluates Dragoon with a focus on potential worst case behavior in comparison to other techniques. We use an evolutionary algorithm to generate instances of the k-center problem that are especially challenging for Dragoon. Ultimately, our experiments confirm the previous good results of Dragoon, however, we also can reliably find scenarios where it is clearly outperformed by other approaches.

Averting the effects of anthropogenic climate change requires a transition from fossil fuels to low-carbon technology. A way to achieve this is to decarbonize the electricity grid. However, further efforts must be made in other fields such as transport and heating for full decarbonization. This would reduce carbon emissions due to electricity generation, and also help to decarbonize other sources such as automotive and heating by enabling a low-carbon alternative. Carbon taxes have been shown to be an efficient way to aid in this transition. In this paper, we demonstrate how to to find optimal carbon tax policies through a genetic algorithm approach, using the electricity market agent-based model ElecSim. To achieve this, we use the NSGA-II genetic algorithm to minimize average electricity price and relative carbon intensity of the electricity mix. We demonstrate that it is possible to find a range of carbon taxes to suit differing objectives. Our results show that we are able to minimize electricity cost to below \textsterling10/MWh as well as carbon intensity to zero in every case. In terms of the optimal carbon tax strategy, we found that an increasing strategy between 2020 and 2035 was preferable. Each of the Pareto-front optimal tax strategies are at least above \textsterling81/tCO2 for every year. The mean carbon tax strategy was \textsterling240/tCO2.

We study a model for adversarial classification based on distributionally robust chance constraints. We show that under Wasserstein ambiguity, the model aims to minimize the conditional value-at-risk of the distance to misclassification, and we explore links to previous adversarial classification models and maximum margin classifiers. We also provide a reformulation of the distributionally robust model for linear classifiers, and show it is equivalent to minimizing a regularized ramp loss. Numerical experiments show that, despite the nonconvexity, standard descent methods appear to converge to the global minimizer for this problem. Inspired by this observation, we show that, for a certain benign distribution, the regularized ramp loss minimization problem has a single stationary point, at the global minimizer.

We explore why many recently proposed robust estimation problems are efficiently solvable, even though the underlying optimization problems are non-convex. We study the loss landscape of these robust estimation problems, and identify the existence of "generalized quasi-gradients". Whenever these quasi-gradients exist, a large family of low-regret algorithms are guaranteed to approximate the global minimum; this includes the commonly-used filtering algorithm. For robust mean estimation of distributions under bounded covariance, we show that any first-order stationary point of the associated optimization problem is an {approximate global minimum} if and only if the corruption level $\epsilon < 1/3$. Consequently, any optimization algorithm that aproaches a stationary point yields an efficient robust estimator with breakdown point $1/3$. With careful initialization and step size, we improve this to $1/2$, which is optimal. For other tasks, including linear regression and joint mean and covariance estimation, the loss landscape is more rugged: there are stationary points arbitrarily far from the global minimum. Nevertheless, we show that generalized quasi-gradients exist and construct efficient algorithms. These algorithms are simpler than previous ones in the literature, and for linear regression we improve the estimation error from $O(\sqrt{\epsilon})$ to the optimal rate of $O(\epsilon)$ for small $\epsilon$ assuming certified hypercontractivity. For mean estimation with near-identity covariance, we show that a simple gradient descent algorithm achieves breakdown point $1/3$ and iteration complexity $\tilde{O}(d/\epsilon^2)$.

Routing of multiple vehicles is an important and difficult problem with applications in the logistic domain [1], especially in the area of customer servicing [2]. In postal services, after-sales services, and in business to business delivery or pick up services one or more vehicles have to be efficiently routed towards customers. If customers can request services over time, the problem becomes dynamic: besides a set of fixed customers, new requests can appear at any point in time. Of course, it is desirable that as many customers as possible are serviced while the tour of any vehicle is kept short. However, it is usually infeasible (due to human resources, labor regulations, or other constraints) to service all customer requests. And clearly, the less customers are left unserviced, the longer the tours become. Thus, the problem is inherently multi-objective. Any efficient solution (smallest maximum tour across all vehicles) is a compromise between the desire to service as many customers as possible (e.g.

The Traveling-Salesperson-Problem (TSP) is arguably one of the best-known NP-hard combinatorial optimization problems. The two sophisticated heuristic solvers LKH and EAX and respective (restart) variants manage to calculate close-to optimal or even optimal solutions, also for large instances with several thousand nodes in reasonable time. In this work we extend existing benchmarking studies by addressing anytime behaviour of inexact TSP solvers based on empirical runtime distributions leading to an increased understanding of solver behaviour and the respective relation to problem hardness. It turns out that performance ranking of solvers is highly dependent on the focused approximation quality. Insights on intersection points of performances offer huge potential for the construction of hybridized solvers depending on instance features. Moreover, instance features tailored to anytime performance and corresponding performance indicators will highly improve automated algorithm selection models by including comprehensive information on solver quality.

The increasing demand for democratizing machine learning algorithms for general software developers calls for hyperparameter optimization (HPO) solutions at low cost. Many machine learning algorithms have hyperparameters, which can cause a large variation in the training cost. But this effect is largely ignored in existing HPO methods, which are incapable to properly control cost during the optimization process. To address this problem, we develop a cost effective HPO solution. The core of our solution is a new randomized direct-search method. We prove a convergence rate of $O(\frac{\sqrt{d}}{\sqrt{K}})$ and provide an analysis on how it can be used to control evaluation cost under reasonable assumptions. Extensive evaluation using a latest AutoML benchmark shows a strong any time performance of the proposed HPO method when tuning cost-related hyperparameters.

This work proposes an iterative sparse-regularized regression method to recover governing equations of nonlinear dynamical systems from noisy state measurements. The method is inspired by the Sparse Identification of Nonlinear Dynamics (SINDy) approach of {\it [Brunton et al., PNAS, 113 (15) (2016) 3932-3937]}, which relies on two main assumptions: the state variables are known {\it a priori} and the governing equations lend themselves to sparse, linear expansions in a (nonlinear) basis of the state variables. The aim of this work is to improve the accuracy and robustness of SINDy in the presence of state measurement noise. To this end, a reweighted $\ell_1$-regularized least squares solver is developed, wherein the regularization parameter is selected from the corner point of a Pareto curve. The idea behind using weighted $\ell_1$-norm for regularization -- instead of the standard $\ell_1$-norm -- is to better promote sparsity in the recovery of the governing equations and, in turn, mitigate the effect of noise in the state variables. We also present a method to recover single physical constraints from state measurements. Through several examples of well-known nonlinear dynamical systems, we demonstrate empirically the accuracy and robustness of the reweighted $\ell_1$-regularized least squares strategy with respect to state measurement noise, thus illustrating its viability for a wide range of potential applications.