The min-max optimization problem, also known as the saddle point problem, is a classical optimization problem which is also studied in the context of zero-sum games. Given a class of objective functions, the goal is to find a value for the argument which leads to a small objective value even for the worst case function in the given class. Min-max optimization problems have recently become very popular in a wide range of signal and data processing applications such as fair beamforming, training generative adversarial networks (GANs), and robust machine learning, to just name a few. The overarching goal of this article is to provide a survey of recent advances for an important subclass of min-max problem, where the minimization and maximization problems can be non-convex and/or non-concave. In particular, we will first present a number of applications to showcase the importance of such min-max problems; then we discuss key theoretical challenges, and provide a selective review of some exciting recent theoretical and algorithmic advances in tackling non-convex min-max problems. Finally, we will point out open questions and future research directions.

We study the problem of policy repair for learning-based control policies in safety-critical settings. We consider an architecture where a high-performance learning-based control policy (e.g. one trained as a neural network) is paired with a model-based safety controller. The safety controller is endowed with the abilities to predict whether the trained policy will lead the system to an unsafe state, and take over control when necessary. While this architecture can provide added safety assurances, intermittent and frequent switching between the trained policy and the safety controller can result in undesirable behaviors and reduced performance. We propose to reduce or even eliminate control switching by `repairing' the trained policy based on runtime data produced by the safety controller in a way that deviates minimally from the original policy. The key idea behind our approach is the formulation of a trajectory optimization problem that allows the joint reasoning of policy update and safety constraints. Experimental results demonstrate that our approach is effective even when the system model in the safety controller is unknown and only approximated.

In this work, we attempt to solve the integer-weight knapsack problem using the D-Wave 2000Q adiabatic quantum computer. The knapsack problem is a well-known NP-complete problem in computer science, with applications in economics, business, finance, etc. We attempt to solve a number of small knapsack problems whose optimal solutions are known; we find that adiabatic quantum optimization fails to produce solutions corresponding to optimal filling of the knapsack in all problem instances. We compare results obtained on the quantum hardware to the classical simulated annealing algorithm and two solvers employing a hybrid branch-and-bound algorithm. The simulated annealing algorithm also fails to produce the optimal filling of the knapsack, though solutions obtained by simulated and quantum annealing are no more similar to each other than to the correct solution. We discuss potential causes for this observed failure of adiabatic quantum optimization.

Jigsaw puzzle solving, the problem of constructing a coherent whole from a set of non-overlapping unordered fragments, is fundamental to numerous applications, and yet most of the literature has focused thus far on less realistic puzzles whose pieces are identical squares. Here we formalize a new type of jigsaw puzzle where the pieces are general convex polygons generated by cutting through a global polygonal shape with an arbitrary number of straight cuts, a generation model inspired by the celebrated Lazy caterer's sequence. We analyze the theoretical properties of such puzzles, including the inherent challenges in solving them once pieces are contaminated with geometrical noise. To cope with such difficulties and obtain tractable solutions, we abstract the problem as a multi-body spring-mass dynamical system endowed with hierarchical loop constraints and a layered reconstruction process. We define evaluation metrics and present experimental results to indicate that such puzzles are solvable completely automatically.

In the power and energy systems area, a progressive increase of literature contributions containing applications of metaheuristic algorithms is occurring. In many cases, these applications are merely aimed at proposing the testing of an existing metaheuristic algorithm on a specific problem, claiming that the proposed method is better than other methods based on weak comparisons. This 'rush to heuristics' does not happen in the evolutionary computation domain, where the rules for setting up rigorous comparisons are stricter, but are typical of the domains of application of the metaheuristics. This paper considers the applications to power and energy systems, and aims at providing a comprehensive view of the main issues concerning the use of metaheuristics for global optimization problems. A set of underlying principles that characterize the metaheuristic algorithms is presented. The customization of metaheuristic algorithms to fit the constraints of specific problems is discussed. Some weaknesses and pitfalls found in literature contributions are identified, and specific guidelines are provided on how to prepare sound contributions on the application of metaheuristic algorithms to specific problems.

Grassmann manifold based sparse spectral clustering is a classification technique that  consists in learning a latent representation of data, formed by a subspace basis, which  is sparse. In order to learn a latent representation, spectral clustering is formulated in  terms of a loss minimization problem over a smooth manifold known as Grassmannian.  Such minimization problem cannot be tackled by one of traditional gradient-based learning  algorithms, which are only suitable to perform optimization in absence of constraints among  parameters. It is, therefore, necessary to develop specific optimization/learning algorithms  that are able to look for a local minimum of a loss function under smooth constraints in  an efficient way. Such need calls for manifold optimization methods. In this paper, we  extend classical gradient-based learning algorithms on   at parameter spaces (from classical  gradient descent to adaptive momentum) to curved spaces (smooth manifolds) by means  of tools from manifold calculus. We compare clustering performances of these methods  and known methods from the scientific literature. The obtained results confirm that the  proposed learning algorithms prove lighter in computational complexity than existing ones  without detriment in clustering efficacy.

Promotions and discounts have become key components of modern e-commerce platforms. For online travel platforms (OTPs), popular promotions include room upgrades, free meals and transportation services. By offering these promotions, customers can get more value for their money, while both the OTP and its travel partners may grow their loyal customer base. However, the promotions usually incur a cost that, if uncontrolled, can become unsustainable. Consequently, for a promotion to be viable, its associated costs must be balanced by incremental revenue within set financial constraints. Personalized treatment assignment can be used to satisfy such constraints. This paper introduces a novel uplift modeling technique, relying on the Knapsack Problem formulation, that dynamically optimizes the incremental treatment outcome subject to the required Return on Investment (ROI) constraints. The technique leverages Retrospective Estimation, a modeling approach that relies solely on data from positive outcome examples. The method also addresses training data bias, long term effects, and seasonality challenges via online-dynamic calibration. This approach was tested via offline experiments and online randomized controlled trials at Booking .com - a leading OTP with millions of customers worldwide, resulting in a significant increase in the target outcome while staying within the required financial constraints and outperforming other approaches.

We design layerwise objectives as functionals whose analytic minimizers sufficiently express the exact ground-truth network in terms of its parameters and nonlinearities. Following this objective landscape, learning a preReLU-TLRN from finite samples can be formulated as convex programming with nonparametric function estimation: For each layer, we first formulate the corresponding empirical risk minimization (ERM) as convex quadratic programming (QP), then we show the solution space of the QP can be equivalently determined by a set of linear inequalities, which can then be efficiently solved by linear programming (LP). Experiments show the robustness and sample efficiency of our methods.

When solving an equation, using the result to encode a message, transmitting the coded message to another device, decoding the message at the other end, saving the message onto a hard drive, or using it to create a visual rendering; inaccuracies are often the system's enemy and have to be fought against. Furthermore, if and when any of these computational operations is repeated, we expect the results to be unchanged. We view an unrepeatable result as a sign of a "bug" that either has to be fixed, tamed, or at least well understood and tolerated. Reduced precision and reliability is often considered as a price in the tradeoff with computational efficiency. The central thesis of this perspective article is that for machine learning (ML) specifically, and artificial intelligence (AI) more generally, probabilistic operations are fundamentally important building blocks, which the field is growing to rely on. We anticipate that stochasticity will therefore feature more prominently, and as a fundamental principle, in the future of machine intelligence.

Simulation is increasingly being used for generating large labelled datasets in many machine learning problems. Recent methods have focused on adjusting simulator parameters with the goal of maximising accuracy on a validation task, usually relying on REINFORCE-like gradient estimators. However these approaches are very expensive as they treat the entire data generation, model training, and validation pipeline as a black-box and require multiple costly objective evaluations at each iteration. We propose an efficient alternative for optimal synthetic data generation, based on a novel differentiable approximation of the objective. This allows us to optimize the simulator, which may be non-differentiable, requiring only one objective evaluation at each iteration with a little overhead. We demonstrate on a state-of-the-art photorealistic renderer that the proposed method finds the optimal data distribution faster (up to $50\times$), with significantly reduced training data generation (up to $30\times$) and better accuracy ($+8.7\%$) on real-world test datasets than previous methods.