OpenRaiser/Intern-Atlas huggingface dataset:
k-medoids and p-median clustering are solvable in polynomial time for a 2d Pareto front
Venue: arXiv cs.CC 2020
Year: 2020

This paper examines a common extension of k-medoids and k-median clustering in the case of a two-dimensional Pareto front, as generated by bi-objective optimization approaches. A characterization of optimal clusters is provided, which allows to solve the optimization problems to optimality in polynomial time using a common dynamic programming algorithm. More precisely, having $N$ points to cluster in $K$ subsets, the complexity of the algorithm is proven in $O(N^3)$ time and $O(K.N)$ memory space when $K\geqslant 3$, cases $K=2$ having a time complexity in $O(N^2)$. Furthermore, speeding-up the dynamic programming algorithm is possible avoiding useless computations, for a practical speed-up without improving the complexity. Parallelization issues are also discussed, to speed-up the algorithm in practice.
Semi-Dynamic Load Balancing: Efficient Distributed Learning in Non-Dedicated Environments
Venue: arXiv cs.DC 2020
Year: 2020

Machine learning (ML) models are increasingly trained in clusters with non-dedicated workers possessing heterogeneous resources. In such scenarios, model training efficiency can be negatively affected by stragglers -- workers that run much slower than others. Efficient model training requires eliminating such stragglers, yet for modern ML workloads, existing load balancing strategies are inefficient and even infeasible. In this paper, we propose a novel strategy called semi-dynamic load balancing to eliminate stragglers of distributed ML workloads. The key insight is that ML workers shall be load-balanced at iteration boundaries, being non-intrusive to intra-iteration execution. We develop LB-BSP based on such an insight, which is an integrated worker coordination mechanism that adapts workers' load to their instantaneous processing capabilities by right-sizing the sample batches at the synchronization barriers. We have custom-designed the batch sizing algorithm respectively for CPU and GPU clusters based on their own characteristics. LB-BSP has been implemented as a Python module for ML frameworks like TensorFlow and PyTorch. Our EC2 deployment confirms that LB-BSP is practical, effective and light-weight, and is able to accelerating distributed training by up to $54\%$.
Lattice Reduction over Imaginary Quadratic Fields
Venue: arXiv cs.IT 2020
Year: 2020

Complex bases, along with direct-sums defined by rings of imaginary quadratic integers, induce algebraic lattices. In this work, we study such lattices and their reduction algorithms. Firstly, when the lattice is spanned over a two dimensional basis, we show that the algebraic variant of Gauss's algorithm returns a basis that corresponds to the successive minima of the lattice if the chosen ring is Euclidean. Secondly, we extend the celebrated Lenstra-Lenstra-Lovász (LLL) reduction from over real bases to over complex bases. Properties and implementations of the algorithm are examined. In particular, satisfying Lovász's condition requires the ring to be Euclidean. Lastly, we numerically show the time-advantage of using algebraic LLL by considering lattice bases generated from wireless communications and cryptography.
Data augmentation instead of explicit regularization
Venue: arXiv cs.CV 2020
Year: 2020

Contrary to most machine learning models, modern deep artificial neural networks typically include multiple components that contribute to regularization. Despite the fact that some (explicit) regularization techniques, such as weight decay and dropout, require costly fine-tuning of sensitive hyperparameters, the interplay between them and other elements that provide implicit regularization is not well understood yet. Shedding light upon these interactions is key to efficiently using computational resources and may contribute to solving the puzzle of generalization in deep learning. Here, we first provide formal definitions of explicit and implicit regularization that help understand essential differences between techniques. Second, we contrast data augmentation with weight decay and dropout. Our results show that visual object categorization models trained with data augmentation alone achieve the same performance or higher than models trained also with weight decay and dropout, as is common practice. We conclude that the contribution on generalization of weight decay and dropout is not only superfluous when sufficient implicit regularization is provided, but also such techniques can dramatically deteriorate the performance if the hyperparameters are not carefully tuned for the architecture and data set. In contrast, data augmentation systematically provides large generalization gains and does not require hyperparameter re-tuning. In view of our results, we suggest to optimize neural networks without weight decay and dropout to save computational resources, hence carbon emissions, and focus more on data augmentation and other inductive biases to improve performance and robustness.
PAC-Bayes Control: Learning Policies that Provably Generalize to Novel Environments
Venue: arXiv cs.RO 2020
Year: 2020

Our goal is to learn control policies for robots that provably generalize well to novel environments given a dataset of example environments. The key technical idea behind our approach is to leverage tools from generalization theory in machine learning by exploiting a precise analogy (which we present in the form of a reduction) between generalization of control policies to novel environments and generalization of hypotheses in the supervised learning setting. In particular, we utilize the Probably Approximately Correct (PAC)-Bayes framework, which allows us to obtain upper bounds that hold with high probability on the expected cost of (stochastic) control policies across novel environments. We propose policy learning algorithms that explicitly seek to minimize this upper bound. The corresponding optimization problem can be solved using convex optimization (Relative Entropy Programming in particular) in the setting where we are optimizing over a finite policy space. In the more general setting of continuously parameterized policies (e.g., neural network policies), we minimize this upper bound using stochastic gradient descent. We present simulated results of our approach applied to learning (1) reactive obstacle avoidance policies and (2) neural network-based grasping policies. We also present hardware results for the Parrot Swing drone navigating through different obstacle environments. Our examples demonstrate the potential of our approach to provide strong generalization guarantees for robotic systems with continuous state and action spaces, complicated (e.g., nonlinear) dynamics, rich sensory inputs (e.g., depth images), and neural network-based policies.
Centrality measures and the role of non-normality for network control energy reduction
Venue: arXiv cs.SY 2020
Year: 2020

Combinations of Gramian-based centrality measures are used for driver node selection in complex networks in order to simultaneously take into account conflicting control energy requirements, like minimizing the average energy needed to steer the state in any direction and the energy needed for the worst direction. The selection strategies that we propose are based on a characterization of the network non-normality, a concept we show is related to the idea of balanced realization.
Aggregation over Metric Spaces: Proposing and Voting in Elections, Budgeting, and Legislation
Venue: arXiv cs.MA 2020
Year: 2020

We present a unifying framework encompassing many social choice settings. Viewing each social choice setting as voting in a suitable metric space, we consider a general model of social choice over metric spaces, in which---similarly to the spatial model of elections---each voter specifies an ideal element of the metric space. The ideal element functions as a vote, where each voter prefers elements that are closer to her ideal element. But it also functions as a proposal, thus making all participants equal not only as voters but also as proposers. We consider Condorcet aggregation and a continuum of solution concepts, ranging from minimizing the sum of distances to minimizing the maximum distance. We study applications of the abstract model to various social choice settings, including single-winner elections, committee elections, participatory budgeting, and participatory legislation. For each setting, we compare each solution concept to known voting rules and study various properties of the resulting voting rules. Our framework provides expressive aggregation for a broad range of social choice settings while remaining simple for voters, and may enable a unified and integrated implementation for all these settings, as well as unified extensions such as sybil-resiliency, proxy voting, and deliberative decision making.
Machine Learning Based Uplink Transmission Power Prediction for LTE and Upcoming 5G Networks using Passive Downlink Indicators
Venue: arXiv cs.NI 2020
Year: 2020

Energy-aware system design is an important optimization task for static and mobile Internet of Things (IoT)-based sensor nodes, especially for highly resource-constrained vehicles such as mobile robotic systems. For 4G/5G-based cellular communication systems, the effective transmission power of uplink data transmissions is of crucial importance for the overall system power consumption. Unfortunately, this information is usually hidden within off-the-shelf modems and mobile handsets and can therefore not be exploited for enabling green communication. Moreover, the dynamic transmission power control behavior of the mobile device is not even explicitly modeled in most of the established simulation frameworks. In this paper, we present a novel machine learning-based approach for forecasting the resulting uplink transmission power used for data transmissions based on the available passive network quality indicators and application-level information. The model is derived from comprehensive field measurements of drive tests performed in a public cellular network and can be parameterized for integrating all measurements a given target platform is able to provide into the prediction process. In a comparison of three different machine learning methods, Random-Forest models thoroughly performed best with a mean average error of 3.166 dB. As the absolute sum of errors converges towards zero and falls below 1 dB after 28 predictions in average, the approach is well-suited for long-term power estimations.
Stagewise Safe Bayesian Optimization with Gaussian Processes
Venue: arXiv cs.LG 2020
Year: 2020

Enforcing safety is a key aspect of many problems pertaining to sequential decision making under uncertainty, which require the decisions made at every step to be both informative of the optimal decision and also safe. For example, we value both efficacy and comfort in medical therapy, and efficiency and safety in robotic control. We consider this problem of optimizing an unknown utility function with absolute feedback or preference feedback subject to unknown safety constraints. We develop an efficient safe Bayesian optimization algorithm, StageOpt, that separates safe region expansion and utility function maximization into two distinct stages. Compared to existing approaches which interleave between expansion and optimization, we show that StageOpt is more efficient and naturally applicable to a broader class of problems. We provide theoretical guarantees for both the satisfaction of safety constraints as well as convergence to the optimal utility value. We evaluate StageOpt on both a variety of synthetic experiments, as well as in clinical practice. We demonstrate that StageOpt is more effective than existing safe optimization approaches, and is able to safely and effectively optimize spinal cord stimulation therapy in our clinical experiments.
Reductive Clustering: An Efficient Linear-time Graph-based Divisive Cluster Analysis Approach
Venue: arXiv cs.AI 2020
Year: 2020

We propose an efficient linear-time graph-based divisive cluster analysis approach called Reductive Clustering. The approach tries to reveal the hierarchical structural information through reducing the graph into a more concise one repeatedly. With the reductions, the original graph can be divided into subgraphs recursively, and a lite informative dendrogram is constructed based on the divisions. The reduction consists of three steps: selection, connection, and partition. First a subset of vertices of the graph are selected as representatives to build a concise graph. The representatives are re-connected to maintain a consistent structure with the previous graph. If possible, the concise graph is divided into subgraphs, and each subgraph is further reduced recursively until the termination condition is met. We discuss the approach, along with several selection and connection methods, in detail both theoretically and experimentally in this paper. Our implementations run in linear time and achieve outstanding performance on various types of datasets. Experimental results show that they outperform state-of-the-art clustering algorithms with significantly less computing resource requirements.
Generalizing Correspondence Analysis for Applications in Machine Learning
Venue: arXiv cs.LG 2020
Year: 2020

Correspondence analysis (CA) is a multivariate statistical tool used to visualize and interpret data dependencies by finding maximally correlated embeddings of pairs of random variables. CA has found applications in fields ranging from epidemiology to social sciences; however, current methods do not scale to large, high-dimensional datasets. In this paper, we provide a novel interpretation of CA in terms of an information-theoretic quantity called the principal inertia components. We show that estimating the principal inertia components, which consists in solving a functional optimization problem over the space of finite variance functions of two random variable, is equivalent to performing CA. We then leverage this insight to design novel algorithms to perform CA at an unprecedented scale. Particularly, we demonstrate how the principal inertia components can be reliably approximated from data using deep neural networks. Finally, we show how these maximally correlated embeddings of pairs of random variables in CA further play a central role in several learning problems including visualization of classification boundary and training process, and underlying recent multi-view and multi-modal learning methods.
Multi-objective Model-based Policy Search for Data-efficient Learning with Sparse Rewards
Venue: arXiv cs.LG 2020
Year: 2020

The most data-efficient algorithms for reinforcement learning in robotics are model-based policy search algorithms, which alternate between learning a dynamical model of the robot and optimizing a policy to maximize the expected return given the model and its uncertainties. However, the current algorithms lack an effective exploration strategy to deal with sparse or misleading reward scenarios: if they do not experience any state with a positive reward during the initial random exploration, it is very unlikely to solve the problem. Here, we propose a novel model-based policy search algorithm, Multi-DEX, that leverages a learned dynamical model to efficiently explore the task space and solve tasks with sparse rewards in a few episodes. To achieve this, we frame the policy search problem as a multi-objective, model-based policy optimization problem with three objectives: (1) generate maximally novel state trajectories, (2) maximize the expected return and (3) keep the system in state-space regions for which the model is as accurate as possible. We then optimize these objectives using a Pareto-based multi-objective optimization algorithm. The experiments show that Multi-DEX is able to solve sparse reward scenarios (with a simulated robotic arm) in much lower interaction time than VIME, TRPO, GEP-PG, CMA-ES and Black-DROPS.
Bayesian Counterfactual Risk Minimization
Venue: arXiv cs.LG 2020
Year: 2020

We present a Bayesian view of counterfactual risk minimization (CRM) for offline learning from logged bandit feedback. Using PAC-Bayesian analysis, we derive a new generalization bound for the truncated inverse propensity score estimator. We apply the bound to a class of Bayesian policies, which motivates a novel, potentially data-dependent, regularization technique for CRM. Experimental results indicate that this technique outperforms standard $L_2$ regularization, and that it is competitive with variance regularization while being both simpler to implement and more computationally efficient.
Quality of local equilibria in discrete exchange economies
Venue: arXiv cs.GT 2020
Year: 2020

This paper defines the notion of a local equilibrium of quality $(r , s)$, $0 \leq r , s$, in a discrete exchange economy: a partial allocation and item prices that guarantee certain stability properties parametrized by the numbers $r$ and $s$. The quality $( r , s )$ measures the fit between the allocation and the prices: the larger $r$ and $s$ the closer the fit. For $r , s \leq 1$ this notion provides a graceful degradation for the conditional equilibria of [10] which are exactly the local equilibria of quality $( 1 , 1 )$. For $1 < r , s $ the local equilibria of quality $( r , s )$ are {\em more stable} than conditional equilibria. Any local equilibrium of quality $( r , s )$ provides, without any assumption on the type of the agents' valuations, an allocation whose value is at least $\frac{r s} { 1 + r s }$ the optimal fractional allocation. In any economy in which all agents' valuations are $a$-submodular, i.e., exhibit complementarity bounded by $a \: \geq \: 1$, there is a local equilibrium of quality $( \frac{1} {a} , \frac{1}{a} )$. In such an economy any greedy allocation provides a local equilibrium of quality $( 1 , \frac{1}{a} ) $. Walrasian equilibria are not amenable to such graceful degradation.
Rule Algebras for Adhesive Categories
Venue: arXiv cs.LO 2020
Year: 2020

We demonstrate that the most well-known approach to rewriting graphical structures, the Double-Pushout (DPO) approach, possesses a notion of sequential compositions of rules along an overlap that is associative in a natural sense. Notably, our results hold in the general setting of $\mathcal{M}$-adhesive categories. This observation complements the classical Concurrency Theorem of DPO rewriting. We then proceed to define rule algebras in both settings, where the most general categories permissible are the finitary (or finitary restrictions of) $\mathcal{M}$-adhesive categories with $\mathcal{M}$-effective unions. If in addition a given such category possess an $\mathcal{M}$-initial object, the resulting rule algebra is unital (in addition to being associative). We demonstrate that in this setting a canonical representation of the rule algebras is obtainable, which opens the possibility of applying the concept to define and compute the evolution of statistical moments of observables in stochastic DPO rewriting systems.
Building Damage Annotation on Post-Hurricane Satellite Imagery Based on Convolutional Neural Networks
Venue: arXiv cs.CV 2020
Year: 2020

After a hurricane, damage assessment is critical to emergency managers for efficient response and resource allocation. One way to gauge the damage extent is to quantify the number of flooded/damaged buildings, which is traditionally done by ground survey. This process can be labor-intensive and time-consuming. In this paper, we propose to improve the efficiency of building damage assessment by applying image classification algorithms to post-hurricane satellite imagery. At the known building coordinates (available from public data), we extract square-sized images from the satellite imagery to create training, validation, and test datasets. Each square-sized image contains a building to be classified as either 'Flooded/Damaged' (labeled by volunteers in a crowd-sourcing project) or 'Undamaged'. We design and train a convolutional neural network from scratch and compare it with an existing neural network used widely for common object classification. We demonstrate the promise of our damage annotation model (over 97% accuracy) in the case study of building damage assessment in the Greater Houston area affected by 2017 Hurricane Harvey.
Privacy-aware Distributed Hypothesis Testing
Venue: arXiv cs.IT 2020
Year: 2020

A distributed binary hypothesis testing (HT) problem involving two parties, a remote observer and a detector, is studied. The remote observer has access to a discrete memoryless source, and communicates its observations to the detector via a rate-limited noiseless channel. The detector observes another discrete memoryless source, and performs a binary hypothesis test on the joint distribution of its own observations with those of the observer. While the goal of the observer is to maximize the type II error exponent of the test for a given type I error probability constraint, it also wants to keep a private part of its observations as oblivious to the detector as possible. Considering both equivocation and average distortion under a causal disclosure assumption as possible measures of privacy, the trade-off between the communication rate from the observer to the detector, the type II error exponent, and privacy is studied. For the general HT problem, we establish single-letter inner bounds on both the rate-error exponent-equivocation and rate-error exponent-distortion trade-offs. Subsequently, single-letter characterizations for both trade-offs are obtained (i) for testing against conditional independence of the observer's observations from those of the detector, given some additional side-information at the detector; and (ii) when the communication rate constraint over the channel is zero. Finally, we show by providing a counterexample that, the strong converse which holds for distributed HT without a privacy constraint, does not hold when a privacy constraint is imposed. This implies that, in general, the rate-error exponent-equivocation and rate-error exponent-distortion trade-offs are not independent of the type I error probability constraint.
Architecture and performance of Devito, a system for automated stencil computation
Venue: arXiv cs.MS 2020
Year: 2020

Stencil computations are a key part of many high-performance computing applications, such as image processing, convolutional neural networks, and finite-difference solvers for partial differential equations. Devito is a framework capable of generating highly-optimized code given symbolic equations expressed in Python, specialized in, but not limited to, affine (stencil) codes. The lowering process---from mathematical equations down to C++ code---is performed by the Devito compiler through a series of intermediate representations. Several performance optimizations are introduced, including advanced common sub-expressions elimination, tiling and parallelization. Some of these are obtained through well-established stencil optimizers, integrated in the back-end of the Devito compiler. The architecture of the Devito compiler, as well as the performance optimizations that are applied when generating code, are presented. The effectiveness of such performance optimizations is demonstrated using operators drawn from seismic imaging applications.