In a machine learning setup, the function F could be interpreted as the loss function associated with a sample ξ and the function f could represent the risk, which is defined as the expected loss. Such constrained stochastic optimization problems arise frequently in statistical machine learning applications. Conditional gradient algorithm, also called as Frank-Wolfe algorithm, is an efficient method for solving constrained optimization problems of the form in (1) due to their projection-free nature [Jag13, HJN15, FGM17, LPZZ17, BZK18, RDLS18]. In each step of the conditional gradient method, it is only required to minimize a linear objective over the set Ω. This operation could be implemented efficiently for a variety of sets arising in statistical machine learning, compared to the operation of projecting on to the set Ω, which is required for example by the projected gradient method. Hence, conditional gradient method has regained popularity in the last decade in the optimization and machine learning community.

In this paper we introduce a new problem in the field of production planning which we call the Production Leveling Problem. The task is to assign orders to production periods such that the load in each period and on each production resource is balanced, capacity limits are not exceeded and the orders' priorities are taken into account. Production Leveling is an important intermediate step between long-term planning and the final scheduling of orders within a production period, as it is responsible for selecting good subsets of orders to be scheduled within each period. A formal model of the problem is proposed and NP-hardness is shown by reduction from Bin Backing. As an exact method for solving moderately sized instances we introduce a MIP formulation. For solving large problem instances, metaheuristic local search is investigated. A greedy heuristic and two neighborhood structures for local search are proposed, in order to apply them using Variable Neighborhood Descent and Simulated Annealing. Regarding exact techniques, the main question of research is, up to which size instances are solvable within a fixed amount of time. For the metaheuristic approaches the aim is to show that they produce near-optimal solutions for smaller instances, but also scale well to very large instances. A set of realistic problem instances from an industrial partner is contributed to the literature, as well as random instance generators. The experimental evaluation conveys that the proposed MIP model works well for instances with up to 250 orders. Out of the investigated metaheuristic approaches, Simulated Annealing achieves the best results. It is shown to produce solutions with less than 3% average optimality gap on small instances and to scale well up to thousands of orders and dozens of periods and products. The presented metaheuristic methods are already being used in the industry.

Decision making in the Agriculture domain can be a complex task. The land area allocated to each crop should be fixed every season according to several parameters: prices, demand, harvesting periods, seeds, ground, season etc... The decision to make becomes more difficult when a group of farmers must fix the price and all parameters all together. Generally, optimization models are useful for farmers to find no dominated solutions, but it remains difficult if the farmers have to agree on one solution. We combine two approaches in order to support a group of farmers engaged in this kind of decision making process. We firstly generate a set of no dominated solutions thanks to a centralized optimization model. Based on this set of solution we then used a Group Decision Support System called GRUS for choosing the best solution for the group of farmers. The combined approach allows us to determine the best solution for the group in a consensual way. This combination of approaches is very innovative for the Agriculture. This approach has been tested in laboratory in a previous work. In the current work the same experiment has been conducted with real business (farmers) in order to benefit from their expertise. The two experiments are compared.

In general, a multi-objective optimization problem does not have a single optimal solution but a set of Pareto optimal solutions, which forms the Pareto front in the objective space. Various evolutionary algorithms have been proposed to approximate the Pareto front using a pre-specified number of solutions. Hundreds of solutions are obtained by their single run. The selection of a single final solution from the obtained solutions is assumed to be done by a human decision maker. However, in many cases, the decision maker does not want to examine hundreds of solutions. Thus, it is needed to select a small subset of the obtained solutions. In this paper, we discuss subset selection from a viewpoint of the final decision making. First we briefly explain existing subset selection studies. Next we formulate an expected loss function for subset selection. We also show that the formulated function is the same as the IGD plus indicator. Then we report experimental results where the proposed approach is compared with other indicator-based subset selection methods.

In this work we solve the Dynamic Vehicle Routing Problem (DVRP). DVRP is a modification of the Vehicle Routing Problem, in which the clients' requests (cities) number and location might not be known at the beginning of the working day Additionally, all requests must be served during one working day by a fleet of vehicles with limited capacity. In this work we propose a Monte Carlo method (MCTree), which directly approaches the dynamic nature of arriving requests in the DVRP. The method is also hybridized (MCTree+PSO) with our previous Two-Phase Multi-swarm Particle Swarm Optimization (2MPSO) algorithm. Our method is based on two assumptions. First, that we know a bounding rectangle of the area in which the requests might appear. Second, that the initial requests' sizes and frequency of appearance are representative for the yet unknown clients' requests. In order to solve the DVRP we divide the working day into several time slices in which we solve a static problem. In our Monte Carlo approach we randomly generate the unknown clients' requests with uniform spatial distribution over the bounding rectangle and requests' sizes uniformly sampled from the already known requests' sizes. The solution proposal is constructed with the application of a clustering algorithm and a route construction algorithm. The MCTree method is tested on a well established set of benchmarks proposed by Kilby et al. and is compared with the results achieved by applying our previous 2MPSO algorithm and other literature results. The proposed MCTree approach achieves a better time to quality trade-off then plain heuristic algorithms. Moreover, a hybrid MCTree+PSO approach achieves better time to quality trade-off then 2MPSO for small optimization time limits, making the hybrid a good candidate for handling real world scale goods delivery problems.

This article applies the principle of Occam's Razor to non-parametric model building of statistical data, by finding a model with the minimal number of bits, leading to an exceptionally effective regularization method for probability density estimators. The idea comes from the fact that likelihood maximization also minimizes the number of bits required to encode a dataset. However, traditional methods overlook that the optimization of model parameters may also inadvertently play the part in encoding data points. The article shows how to extend the bit counting to the model parameters as well, providing the first true measure of complexity for parametric models. Minimizing the total bit requirement of a model of a dataset favors smaller derivatives, smoother probability density function estimates and most importantly, a phase space with fewer relevant parameters. In fact, it is able prune parameters and detect features with small probability at the same time. It is also shown, how it can be applied to any smooth, non-parametric probability density estimator.

Federated learning is a distributed paradigm that aims at training models using samples distributed across multiple users in a network while keeping the samples on users' devices with the aim of efficiency and protecting users privacy. In such settings, the training data is often statistically heterogeneous and manifests various distribution shifts across users, which degrades the performance of the learnt model. The primary goal of this paper is to develop a robust federated learning algorithm that achieves satisfactory performance against distribution shifts in users' samples. To achieve this goal, we first consider a structured affine distribution shift in users' data that captures the device-dependent data heterogeneity in federated settings. This perturbation model is applicable to various federated learning problems such as image classification where the images undergo device-dependent imperfections, e.g. different intensity, contrast, and brightness. To address affine distribution shifts across users, we propose a Federated Learning framework Robust to Affine distribution shifts (FLRA) that is provably robust against affine Wasserstein shifts to the distribution of observed samples. To solve the FLRA's distributed minimax problem, we propose a fast and efficient optimization method and provide convergence guarantees via a gradient Descent Ascent (GDA) method. We further prove generalization error bounds for the learnt classifier to show proper generalization from empirical distribution of samples to the true underlying distribution. We perform several numerical experiments to empirically support FLRA. We show that an affine distribution shift indeed suffices to significantly decrease the performance of the learnt classifier in a new test user, and our proposed algorithm achieves a significant gain in comparison to standard federated learning and adversarial training methods.

Recent advances have shown that implicit bias of gradient descent on over-parameterized models enables the recovery of low-rank matrices from linear measurements, even with no prior knowledge on the intrinsic rank. In contrast, for robust low-rank matrix recovery from grossly corrupted measurements, over-parameterization leads to overfitting without prior knowledge on both the intrinsic rank and sparsity of corruption. This paper shows that with a double over-parameterization for both the low-rank matrix and sparse corruption, gradient descent with discrepant learning rates provably recovers the underlying matrix even without prior knowledge on neither rank of the matrix nor sparsity of the corruption. We further extend our approach for the robust recovery of natural images by over-parameterizing images with deep convolutional networks. Experiments show that our method handles different test images and varying corruption levels with a single learning pipeline where the network width and termination conditions do not need to be adjusted on a case-by-case basis. Underlying the success is again the implicit bias with discrepant learning rates on different over-parameterized parameters, which may bear on broader applications.

Variational representations of distances and divergences between high-dimensional probability distributions offer significant theoretical insights and practical advantages in numerous research areas. Recently, they have gained popularity in machine learning as a tractable and scalable approach for training probabilistic models and statistically differentiate between data distributions. Their advantages include: 1) They can be estimated from data. 2) Such representations can leverage the ability of neural networks to efficiently approximate optimal solutions in function spaces. However, a systematic and practical approach to improving the tightness of such variational formulas, and accordingly accelerate statistical learning and estimation from data, is currently lacking. Here we develop a systematic methodology for building new, tighter variational representations of divergences. Our approach relies on improved objective functionals constructed via an auxiliary optimization problem. Furthermore, the calculation of the functional Hessian of objective functionals unveils the local curvature differences around the common optimal variational solution; this allows us to quantify and order relative tightness gains between different variational representations. Finally, numerical simulations utilizing neural network optimization demonstrate that tighter representations can result in significantly faster learning and more accurate estimation of divergences in both synthetic and real datasets (of more than 700 dimensions), often accelerated by nearly an order of magnitude.

We develop a distributed second order optimization algorithm that is communication-efficient as well as robust against Byzantine failures of the worker machines. We propose COMRADE (COMunication-efficient and Robust Approximate Distributed nEwton), an iterative second order algorithm, where the worker machines communicate only once per iteration with the center machine. This is in sharp contrast with the state-of-the-art distributed second order algorithms like GIANT [34] and DINGO[7], where the worker machines send (functions of) local gradient and Hessian sequentially; thus ending up communicating twice with the center machine per iteration. Moreover, we show that the worker machines can further compress the local information before sending it to the center. In addition, we employ a simple norm based thresholding rule to filter-out the Byzantine worker machines. We establish the linear-quadratic rate of convergence of COMRADE and establish that the communication savings and Byzantine resilience result in only a small statistical error rate for arbitrary convex loss functions. To the best of our knowledge, this is the first work that addresses the issue of Byzantine resilience in second order distributed optimization. Furthermore, we validate our theoretical results with extensive experiments on synthetic and benchmark LIBSVM [5] data-sets and demonstrate convergence guarantees.