Optimization
Recovery-to-Efficiency: A New Robustness Concept for Multi-objective Optimization under Uncertainty
Talbi, El-Ghazali, Todosijevic, Raca
This paper presents a new robustness concept for uncertain multi-objective optimization problems. More precisely, in the paper the so-called recovery-to-efficiency robustness concept is proposed and investigated. Several approaches for generating recovery-to-efficiency robust sets in the context of multi-objective optimization are proposed as well. An extensive experimental analysis is performed to disclose differences among robust sets obtained using different concepts as well as to deduce some interesting observations. For testing purposes, instances from the bi-objective knapsack problem are considered.
Mapping the landscape of Artificial Intelligence applications against COVID-19
Bullock, Joseph (United Nations Global Pulse, New York, NY, USA) | Luccioni, Alexandra (Institute for Data Science, Durham University, Durham, United Kingdom) | Hoffman Pham, Katherine (Mila Quebec Artificial Intelligence Institute, Universite de Montreal, Montreal, Quebec, Canada) | Sin Nga Lam, Cynthia (United Nations Global Pulse, New York, NY, USA) | Luengo-Oroz, Miguel (NYU Stern School of Business, New York, NY, USA)
COVID-19, the disease caused by the SARS-CoV-2 virus, has been declared a pandemic by the World Health Organization, which has reported over 18 million confirmed cases as of August 5, 2020. In this review, we present an overview of recent studies using Machine Learning and, more broadly, Artificial Intelligence, to tackle many aspects of the COVID-19 crisis. We have identified applications that address challenges posed by COVID-19 at different scales, including: molecular, by identifying new or existing drugs for treatment; clinical, by supporting diagnosis and evaluating prognosis based on medical imaging and non-invasive measures; and societal, by tracking both the epidemic and the accompanying infodemic using multiple data sources. We also review datasets, tools, and resources needed to facilitate Artificial Intelligence research, and discuss strategic considerations related to the operational implementation of multidisciplinary partnerships and open science. We highlight the need for international cooperation to maximize the potential of AI in this and future pandemics.
Exploring Constraint Handling Techniques in Real-world Problems on MOEA/D with Limited Budget of Evaluations
Vaz, Felipe, Lavinas, Yuri, Aranha, Claus, Ladeira, Marcelo
Finding good solutions for Multi-objective Optimization (MOPs) Problems is considered a hard problem, especially when considering MOPs with constraints. Thus, most of the works in the context of MOPs do not explore in-depth how different constraints affect the performance of MOP solvers. Here, we focus on exploring the effects of different Constraint Handling Techniques (CHTs) on MOEA/D, a commonly used MOP solver when solving complex real-world MOPs. Moreover, we introduce a simple and effective CHT focusing on the exploration of the decision space, the Three Stage Penalty. We explore each of these CHTs in MOEA/D on two simulated MOPs and six analytic MOPs (eight in total). The results of this work indicate that while the best CHT is problem-dependent, our new proposed Three Stage Penalty achieves competitive results and remarkable performance in terms of hypervolume values in the hard simulated car design MOP.
Algorithms for Advanced Hyper-Parameter Optimization/Tuning - KDnuggets
Most Professional Machine Learning practitioners follow the ML Pipeline as a standard, to keep their work efficient and to keep the flow of work. A pipeline is created to allow data flow from its raw format to some useful information. All sub-fields in this pipeline's modules are equally important for us to produce quality results, and one of them is Hyper-Parameter Tuning. Most of us know the best way to proceed with Hyper-Parameter Tuning is to use the GridSearchCV or RandomSearchCV from the sklearn module. But apart from these algorithms, there are many other Advanced methods for Hyper-Parameter Tuning.
Introduction to Core-sets: an Updated Survey
In optimization or machine learning problems we are given a set of items, usually points in some metric space, and the goal is to minimize or maximize an objective function over some space of candidate solutions. For example, in clustering problems, the input is a set of points in some metric space, and a common goal is to compute a set of centers in some other space (points, lines) that will minimize the sum of distances to these points. In database queries, we may need to compute such a some for a specific query set of k centers. However, traditional algorithms cannot handle modern systems that require parallel real-time computations of infinite distributed streams from sensors such as GPS, audio or video that arrive to a cloud, or networks of weaker devices such as smartphones or robots. Core-set is a "small data" summarization of the input "big data", where every possible query has approximately the same answer on both data sets. Generic techniques enable efficient coreset maintenance of streaming, distributed and dynamic data. Traditional algorithms can then be applied on these coresets to maintain the approximated optimal solutions. The challenge is to design coresets with provable tradeoff between their size and approximation error. This survey summarizes such constructions in a retrospective way, that aims to unified and simplify the state-of-the-art. Bringing big data to the enterprise, 2012) are generated by cheap and numerous information-sensing mobile devices, remote sensing, software logs, cameras, microphones, RFID readers and wireless sensor networks (Segaran & Hammerbacher, 2009; Hellerstein, 2008; Funke & Laue, 2007). These require clustering algorithms that, unlike traditional algorithms, (a) learn unbounded streaming data that cannot fit into main memory, (b) run in parallel on distributed data among thousands of machines, (c) use low communication between the machines (d) apply real-time computations on the device, (e) handle privacy and security issues. A common approach is to reinvent computer science for handling these new computational models, and develop new algorithms "from scratch" independently of existing solutions.
Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS
Kivva, Bohdan, Potechin, Aaron
In this paper we show that simple semidefinite programs inspired by degree $4$ SOS can exactly solve the tensor nuclear norm, tensor decomposition, and tensor completion problems on tensors with random asymmetric components. More precisely, for tensor nuclear norm and tensor decomposition, we show that w.h.p. these semidefinite programs can exactly find the nuclear norm and components of an $(n\times n\times n)$-tensor $\mathcal{T}$ with $m\leq n^{3/2}/polylog(n)$ random asymmetric components. For tensor completion, we show that w.h.p. the semidefinite program introduced by Potechin \& Steurer (2017) can exactly recover an $(n\times n\times n)$-tensor $\mathcal{T}$ with $m$ random asymmetric components from only $n^{3/2}m\, polylog(n)$ randomly observed entries. This gives the first theoretical guarantees for exact tensor completion in the overcomplete regime. This matches the best known results for approximate versions of these problems given by Barak \& Moitra (2015) for tensor completion, and Ma, Shi \& Steurer (2016) for tensor decomposition.
Particle-based Energetic Variational Inference
Wang, Yiwei, Chen, Jiuhai, Liu, Chun, Kang, Lulu
We introduce a new variational inference (VI) framework, called energetic variational inference (EVI). It minimizes the VI object function based on a prescribed energy-dissipation law. Using the EVI framework, we can derive many existing Particle-based Variational Inference (ParVI) methods, including the popular Stein Variational Gradient Descent (SVGD) approach. More importantly, many new ParVI schemes can be created under this framework. For illustration, we propose a new particle-based EVI scheme, which performs the particle-based approximation of the density first and then uses the approximated density in the variational procedure, or "Approximation-then-Variation" for short. Thanks to this order of approximation and variation, the new scheme can maintain the variational structure at the particle level and can significantly decrease the KL-divergence in each iteration. Numerical experiments show the proposed method outperforms some existing ParVI methods in terms of fidelity to the target distribution.
Deep Reinforcement Learning for Stochastic Computation Offloading in Digital Twin Networks
Dai, Yueyue, Zhang, Ke, Maharjan, Sabita, Zhang, Yan
The rapid development of Industrial Internet of Things (IIoT) requires industrial production towards digitalization to improve network efficiency. Digital Twin is a promising technology to empower the digital transformation of IIoT by creating virtual models of physical objects. However, the provision of network efficiency in IIoT is very challenging due to resource-constrained devices, stochastic tasks, and resources heterogeneity. Distributed resources in IIoT networks can be efficiently exploited through computation offloading to reduce energy consumption while enhancing data processing efficiency. In this paper, we first propose a new paradigm Digital Twin Networks (DTN) to build network topology and the stochastic task arrival model in IIoT systems. Then, we formulate the stochastic computation offloading and resource allocation problem to minimize the long-term energy efficiency. As the formulated problem is a stochastic programming problem, we leverage Lyapunov optimization technique to transform the original problem into a deterministic per-time slot problem. Finally, we present Asynchronous Actor-Critic (AAC) algorithm to find the optimal stochastic computation offloading policy. Illustrative results demonstrate that our proposed scheme is able to significantly outperforms the benchmarks.
Federated Composite Optimization
Yuan, Honglin, Zaheer, Manzil, Reddi, Sashank
Federated Learning (FL) is a distributed learning paradigm which scales on-device learning collaboratively and privately. Standard FL algorithms such as Federated Averaging (FedAvg) are primarily geared towards smooth unconstrained settings. In this paper, we study the Federated Composite Optimization (FCO) problem, where the objective function in FL includes an additive (possibly) non-smooth component. Such optimization problems are fundamental to machine learning and arise naturally in the context of regularization (e.g., sparsity, low-rank, monotonicity, and constraint). To tackle this problem, we propose different primal/dual averaging approaches and study their communication and computation complexities. Of particular interest is Federated Dual Averaging (FedDualAvg), a federated variant of the dual averaging algorithm. FedDualAvg uses a novel double averaging procedure, which involves gradient averaging step in standard dual averaging and an average of client updates akin to standard federated averaging. Our theoretical analysis and empirical experiments demonstrate that FedDualAvg outperforms baselines for FCO.
A Survey on the Explainability of Supervised Machine Learning
Burkart, Nadia, Huber, Marco F.
Predictions obtained by, e.g., artificial neural networks have a high accuracy but humans often perceive the models as black boxes. Insights about the decision making are mostly opaque for humans. Particularly understanding the decision making in highly sensitive areas such as healthcare or fifinance, is of paramount importance. The decision-making behind the black boxes requires it to be more transparent, accountable, and understandable for humans. This survey paper provides essential definitions, an overview of the different principles and methodologies of explainable Supervised Machine Learning (SML). We conduct a state-of-the-art survey that reviews past and recent explainable SML approaches and classifies them according to the introduced definitions. Finally, we illustrate principles by means of an explanatory case study and discuss important future directions.