OpenRaiser/Intern-Atlas huggingface dataset:
Proving Soundness of Extensional Normal-Form Bisimilarities
Venue: arXiv cs.LO 2019
Year: 2019

Normal-form bisimilarity is a simple, easy-to-use behavioral equivalence that relates terms in $λ$-calculi by decomposing their normal forms into bisimilar subterms. Moreover, it typically allows for powerful up-to techniques, such as bisimulation up to context, which simplify bisimulation proofs even further. However, proving soundness of these relations becomes complicated in the presence of $η$-expansion and usually relies on ad hoc proof methods which depend on the language. In this paper we propose a more systematic proof method to show that an extensional normal-form bisimilarity along with its corresponding up to context technique are sound. We illustrate our technique with three calculi: the call-by-value $λ$-calculus, the call-by-value $λ$-calculus with the delimited-control operators shift and reset, and the call-by-value $λ$-calculus with the abortive control operators call/cc and abort. In the first two cases, there was previously no sound up to context technique validating the $η$-law, whereas no theory of normal-form bisimulations for a calculus with call/cc and abort has been presented before. Our results have been fully formalized in the Coq proof assistant.
Improved Approximation Schemes for the Restricted Shortest Path Problem
Venue: arXiv cs.DS 2019
Year: 2019

The Restricted Shortest Path (RSP) problem, also known as the Delay-Constrained Least-Cost (DCLC) problem, is an NP-hard bicriteria optimization problem on graphs with $n$ vertices and $m$ edges. In a graph where each edge is assigned a cost and a delay, the goal is to find a min-cost path which does not exceed a delay bound. In this paper, we present improved approximation schemes for RSP on several graph classes. For planar graphs, undirected graphs with positive integer resource (= delay) values, and graphs with $m \in Ω(n \log n)$, we obtain $(1 + \varepsilon)$-approximations in time $O(mn/\varepsilon)$. For general graphs and directed acyclic graphs, we match the results by Xue et al. (2008, [10]) and Ergun et al. (2002, [1]), respectively, but with arguably simpler algorithms.
A Denotational Semantics for SPARC TSO
Venue: arXiv cs.PL 2019
Year: 2019

The SPARC TSO weak memory model is defined axiomatically, with a non-compositional formulation that makes modular reasoning about programs difficult. Our denotational approach uses pomsets to provide a compositional semantics capturing exactly the behaviours permitted by SPARC TSO. It uses buffered states and an inductive definition of execution to assign an input-output meaning to pomsets. We show that our denotational account is sound and complete relative to the axiomatic account, that is, that it captures exactly the behaviours permitted by the axiomatic account. Our compositional approach facilitates the study of SPARC TSO and supports modular analysis of program behaviour.
Performance of Balanced Fairness in Resource Pools: A Recursive Approach
Venue: arXiv cs.NI 2019
Year: 2019

Understanding the performance of a pool of servers is crucial for proper dimensioning. One of the main challenges is to take into account the complex interactions between servers that are pooled to process jobs. In particular, a job can generally not be processed by any server of the cluster due to various constraints like data locality. In this paper, we represent these constraints by some assignment graph between jobs and servers. We present a recursive approach to computing performance metrics like mean response times when the server capacities are shared according to balanced fairness. While the computational cost of these formulas can be exponential in the number of servers in the worst case, we illustrate their practical interest by introducing broad classes of pool structures that can be exactly analyzed in polynomial time. This extends considerably the class of models for which explicit performance metrics are accessible.
Long-Term Online Smoothing Prediction Using Expert Advice
Venue: arXiv cs.LG 2019
Year: 2019

For the prediction with experts' advice setting, we construct forecasting algorithms that suffer loss not much more than any expert in the pool. In contrast to the standard approach, we investigate the case of long-term forecasting of time series and consider two scenarios. In the first one, at each step $t$ the learner has to combine the point forecasts of the experts issued for the time interval $[t+1, t+d]$ ahead. Our approach implies that at each time step experts issue point forecasts for arbitrary many steps ahead and then the learner (algorithm) combines these forecasts and the forecasts made earlier into one vector forecast for steps $[t+1,t+d]$. By combining past and the current long-term forecasts we obtain a smoothing mechanism that protects our algorithm from temporary trend changes, noise and outliers. In the second scenario, at each step $t$ experts issue a prediction function, and the learner has to combine these functions into the single one, which will be used for long-term time-series prediction. For each scenario, we develop an algorithm for combining experts forecasts and prove $O(\ln T)$ adversarial regret upper bound for both algorithms.
Crafting Adversarial Examples For Speech Paralinguistics Applications
Venue: arXiv cs.LG 2019
Year: 2019

Computational paralinguistic analysis is increasingly being used in a wide range of cyber applications, including security-sensitive applications such as speaker verification, deceptive speech detection, and medical diagnostics. While state-of-the-art machine learning techniques, such as deep neural networks, can provide robust and accurate speech analysis, they are susceptible to adversarial attacks. In this work, we propose an end-to-end scheme to generate adversarial examples for computational paralinguistic applications by perturbing directly the raw waveform of an audio recording rather than specific acoustic features. Our experiments show that the proposed adversarial perturbation can lead to a significant performance drop of state-of-the-art deep neural networks, while only minimally impairing the audio quality.
One-Bit ExpanderSketch for One-Bit Compressed Sensing
Venue: arXiv cs.IT 2019
Year: 2019

Is it possible to obliviously construct a set of hyperplanes H such that you can approximate a unit vector x when you are given the side on which the vector lies with respect to every h in H? In the sparse recovery literature, where x is approximately k-sparse, this problem is called one-bit compressed sensing and has received a fair amount of attention the last decade. In this paper we obtain the first scheme that achieves almost optimal measurements and sublinear decoding time for one-bit compressed sensing in the non-uniform case. For a large range of parameters, we improve the state of the art in both the number of measurements and the decoding time.
Persuasion with limited communication capacity
Venue: arXiv cs.IT 2019
Year: 2019

We consider a Bayesian persuasion problem where the persuader and the decision maker communicate through an imperfect channel that has a fixed and limited number of messages and is subject to exogenous noise. We provide an upper bound on the payoffs the persuader can secure by communicating through the channel. We also show that the bound is tight, i.e., if the persuasion problem consists of a large number of independent copies of the same base problem, then the persuader can achieve this bound arbitrarily closely by using strategies that tie all the problems together. We characterize this optimal payoff as a function of the information-theoretic capacity of the communication channel.
Neuromorphic computing with multi-memristive synapses
Venue: arXiv cs.ET 2019
Year: 2019

Neuromorphic computing has emerged as a promising avenue towards building the next generation of intelligent computing systems. It has been proposed that memristive devices, which exhibit history-dependent conductivity modulation, could efficiently represent the synaptic weights in artificial neural networks. However, precise modulation of the device conductance over a wide dynamic range, necessary to maintain high network accuracy, is proving to be challenging. To address this, we present a multi-memristive synaptic architecture with an efficient global counter-based arbitration scheme. We focus on phase change memory devices, develop a comprehensive model and demonstrate via simulations the effectiveness of the concept for both spiking and non-spiking neural networks. Moreover, we present experimental results involving over a million phase change memory devices for unsupervised learning of temporal correlations using a spiking neural network. The work presents a significant step towards the realization of large-scale and energy-efficient neuromorphic computing systems.
Online Clustering of Contextual Cascading Bandits
Venue: arXiv cs.LG 2019
Year: 2019

We consider a new setting of online clustering of contextual cascading bandits, an online learning problem where the underlying cluster structure over users is unknown and needs to be learned from a random prefix feedback. More precisely, a learning agent recommends an ordered list of items to a user, who checks the list and stops at the first satisfactory item, if any. We propose an algorithm of CLUB-cascade for this setting and prove a $T$-step regret bound of order $\tilde{O}(\sqrt{T})$. Previous work corresponds to the degenerate case of only one cluster, and our general regret bound in this special case also significantly improves theirs. We conduct experiments on both synthetic and real data, and demonstrate the effectiveness of our algorithm and the advantage of incorporating online clustering method.
Attended End-to-end Architecture for Age Estimation from Facial Expression Videos
Venue: arXiv cs.CV 2019
Year: 2019

The main challenges of age estimation from facial expression videos lie not only in the modeling of the static facial appearance, but also in the capturing of the temporal facial dynamics. Traditional techniques to this problem focus on constructing handcrafted features to explore the discriminative information contained in facial appearance and dynamics separately. This relies on sophisticated feature-refinement and framework-design. In this paper, we present an end-to-end architecture for age estimation, called Spatially-Indexed Attention Model (SIAM), which is able to simultaneously learn both the appearance and dynamics of age from raw videos of facial expressions. Specifically, we employ convolutional neural networks to extract effective latent appearance representations and feed them into recurrent networks to model the temporal dynamics. More importantly, we propose to leverage attention models for salience detection in both the spatial domain for each single image and the temporal domain for the whole video as well. We design a specific spatially-indexed attention mechanism among the convolutional layers to extract the salient facial regions in each individual image, and a temporal attention layer to assign attention weights to each frame. This two-pronged approach not only improves the performance by allowing the model to focus on informative frames and facial areas, but it also offers an interpretable correspondence between the spatial facial regions as well as temporal frames, and the task of age estimation. We demonstrate the strong performance of our model in experiments on a large, gender-balanced database with 400 subjects with ages spanning from 8 to 76 years. Experiments reveal that our model exhibits significant superiority over the state-of-the-art methods given sufficient training data.
Action Branching Architectures for Deep Reinforcement Learning
Venue: arXiv cs.LG 2019
Year: 2019

Discrete-action algorithms have been central to numerous recent successes of deep reinforcement learning. However, applying these algorithms to high-dimensional action tasks requires tackling the combinatorial increase of the number of possible actions with the number of action dimensions. This problem is further exacerbated for continuous-action tasks that require fine control of actions via discretization. In this paper, we propose a novel neural architecture featuring a shared decision module followed by several network branches, one for each action dimension. This approach achieves a linear increase of the number of network outputs with the number of degrees of freedom by allowing a level of independence for each individual action dimension. To illustrate the approach, we present a novel agent, called Branching Dueling Q-Network (BDQ), as a branching variant of the Dueling Double Deep Q-Network (Dueling DDQN). We evaluate the performance of our agent on a set of challenging continuous control tasks. The empirical results show that the proposed agent scales gracefully to environments with increasing action dimensionality and indicate the significance of the shared decision module in coordination of the distributed action branches. Furthermore, we show that the proposed agent performs competitively against a state-of-the-art continuous control algorithm, Deep Deterministic Policy Gradient (DDPG).
Joint Transmit and Circuit Power Minimization in Massive MIMO with Downlink SINR Constraints: When to Turn on Massive MIMO?
Venue: arXiv cs.IT 2019
Year: 2019

In this work, we consider the downlink of a multi-cell multiple-input multiple-output (MIMO) system and find the jointly optimal number of base station (BS) antennas and transmission powers that minimize the power consumption while satisfying each user's effective signal-to-interference-and-noise-ratio (SINR) constraint and the BSs' power constraints. Different from prior work, we consider a power consumption model that takes both transmitted and hardware-consumed power into account. We formulate the joint optimization problem for both single-cell and multi-cell systems. Closed-form expressions for the optimal number of BS antennas and transmission powers are derived for the single-cell case. The analysis for the multi-cell case reveals that increasing the number of BS antennas in any cell always improves the performance of the overall system in terms of both feasibility and total radiated power. A key contribution of this work is to show that the joint optimization problem can be relaxed as a geometric programming problem that can be solved efficiently. The solution can be utilized in practice to turn on and off antennas depending on the traffic load variations. Substantial power savings are demonstrated by simulation.
Performance Measures in Electric Power Networks under Line Contingencies
Venue: arXiv cs.SY 2019
Year: 2019

Classes of performance measures expressed in terms of ${\cal H}_2$-norms have been recently introduced to quantify the response of coupled dynamical systems to external perturbations. So far, investigations of these performance measures have been restricted to nodal perturbations. Here, we go beyond these earlier works and consider the equally important, but so far neglected case of line perturbations. We consider a network-reduced power system, where a Kron reduction has eliminated passive buses. Identifying the effect that a line fault in the physical network has on the Kron-reduced network, we find that performance measures depend on whether the faulted line connects two passive, two active buses or one active to one passive bus. In all cases, performance measures depend quadratically on the original load on the faulted line times a topology dependent factor. Our theoretical formalism being restricted to Dirac-$δ$ perturbations, we investigate numerically the validity of our results for finite-time line faults. We find good agreement with theoretical predictions for longer fault durations in systems with more inertia.
Learning from Longitudinal Face Demonstration - Where Tractable Deep Modeling Meets Inverse Reinforcement Learning
Venue: arXiv cs.CV 2019
Year: 2019

This paper presents a novel Subject-dependent Deep Aging Path (SDAP), which inherits the merits of both Generative Probabilistic Modeling and Inverse Reinforcement Learning to model the facial structures and the longitudinal face aging process of a given subject. The proposed SDAP is optimized using tractable log-likelihood objective functions with Convolutional Neural Networks (CNNs) based deep feature extraction. Instead of applying a fixed aging development path for all input faces and subjects, SDAP is able to provide the most appropriate aging development path for individual subject that optimizes the reward aging formulation. Unlike previous methods that can take only one image as the input, SDAP further allows multiple images as inputs, i.e. all information of a subject at either the same or different ages, to produce the optimal aging path for the given subject. Finally, SDAP allows efficiently synthesizing in-the-wild aging faces. The proposed model is experimented in both tasks of face aging synthesis and cross-age face verification. The experimental results consistently show SDAP achieves the state-of-the-art performance on numerous face aging databases, i.e. FG-NET, MORPH, AginG Faces in the Wild (AGFW), and Cross-Age Celebrity Dataset (CACD). Furthermore, we also evaluate the performance of SDAP on large-scale Megaface challenge to demonstrate the advantages of the proposed solution.
Context-Awareness Enhances 5G Multi-Access Edge Computing Reliability
Venue: arXiv cs.NI 2019
Year: 2019

The fifth generation (5G) mobile telecommunication network is expected to support Multi- Access Edge Computing (MEC), which intends to distribute computation tasks and services from the central cloud to the edge clouds. Towards ultra-responsive, ultra-reliable and ultra-low-latency MEC services, the current mobile network security architecture should enable a more decentralized approach for authentication and authorization processes. This paper proposes a novel decentralized authentication architecture that supports flexible and low-cost local authentication with the awareness of context information of network elements such as user equipment and virtual network functions. Based on a Markov model for backhaul link quality, as well as a random walk mobility model with mixed mobility classes and traffic scenarios, numerical simulations have demonstrated that the proposed approach is able to achieve a flexible balance between the network operating cost and the MEC reliability.
Distributed Algorithms Made Secure: A Graph Theoretic Approach
Venue: arXiv cs.DS 2019
Year: 2019

In the area of distributed graph algorithms a number of network's entities with local views solve some computational task by exchanging messages with their neighbors. Quite unfortunately, an inherent property of most existing distributed algorithms is that throughout the course of their execution, the nodes get to learn not only their own output but rather learn quite a lot on the inputs or outputs of many other entities. This leakage of information might be a major obstacle in settings where the output (or input) of network's individual is a private information. In this paper, we introduce a new framework for \emph{secure distributed graph algorithms} and provide the first \emph{general compiler} that takes any "natural" non-secure distributed algorithm that runs in $r$ rounds, and turns it into a secure algorithm that runs in $\widetilde{O}(r \cdot D \cdot poly(Δ))$ rounds where $Δ$ is the maximum degree in the graph and $D$ is its diameter. The security of the compiled algorithm is information-theoretic but holds only against a semi-honest adversary that controls a single node in the network. This compiler is made possible due to a new combinatorial structure called \emph{private neighborhood trees}: a collection of $n$ trees $T(u_1),\ldots,T(u_n)$, one for each vertex $u_i \in V(G)$, such that each tree $T(u_i)$ spans the neighbors of $u_i$ {\em without going through $u_i$}. Intuitively, each tree $T(u_i)$ allows all neighbors of $u_i$ to exchange a \emph{secret} that is hidden from $u_i$, which is the basic graph infrastructure of the compiler. In a $(d,c)$-private neighborhood trees each tree $T(u_i)$ has depth at most $d$ and each edge $e \in G$ appears in at most $c$ different trees. We show a construction of private neighborhood trees with $d=\widetilde{O}(Δ\cdot D)$ and $c=\widetilde{O}(D)$.
Brain-Computer Interface meets ROS: A robotic approach to mentally drive telepresence robots
Venue: arXiv cs.RO 2019
Year: 2019

This paper shows and evaluates a novel approach to integrate a non-invasive Brain-Computer Interface (BCI) with the Robot Operating System (ROS) to mentally drive a telepresence robot. Controlling a mobile device by using human brain signals might improve the quality of life of people suffering from severe physical disabilities or elderly people who cannot move anymore. Thus, the BCI user is able to actively interact with relatives and friends located in different rooms thanks to a video streaming connection to the robot. To facilitate the control of the robot via BCI, we explore new ROS-based algorithms for navigation and obstacle avoidance, making the system safer and more reliable. In this regard, the robot can exploit two maps of the environment, one for localization and one for navigation, and both can be used also by the BCI user to watch the position of the robot while it is moving. As demonstrated by the experimental results, the user's cognitive workload is reduced, decreasing the number of commands necessary to complete the task and helping him/her to keep attention for longer periods of time.
A General Memory-Bounded Learning Algorithm
Venue: arXiv cs.LG 2019
Year: 2019

Designing bounded-memory algorithms is becoming increasingly important nowadays. Previous works studying bounded-memory algorithms focused on proving impossibility results, while the design of bounded-memory algorithms was left relatively unexplored. To remedy this situation, in this work we design a general bounded-memory learning algorithm, when the underlying distribution is known. The core idea of the algorithm is not to save the exact example received, but only a few important bits that give sufficient information. This algorithm applies to any hypothesis class that has an "anti-mixing" property. This paper complements previous works on unlearnability with bounded memory and provides a step towards a full characterization of bounded-memory learning.
Optimal Energy Consumption with Communication, Computation, Caching and QoI-Guarantee
Venue: arXiv cs.NI 2019
Year: 2019

Energy efficiency is a fundamental requirement of modern data communication systems, and its importance is reflected in much recent work on performance analysis of system energy consumption. However, most works have only focused on communication and computation costs, but do not account for caching costs. Given the increasing interest in cache networks, this is a serious deficiency. {In this paper, we consider the problem of energy consumption in data communication, compression and caching (C$3$) with a Quality of Information (QoI) guarantee in a communication network. {Our goal is to identify the optimal data compression rate and data placement over the network to minimize the overall energy consumption in the network.} he formulated problem is a \emph{Mixed Integer Non-Linear Programming} (MINLP) problem with non-convex functions, which is NP-hard in general. } {We} propose a variant of spatial branch and bound algorithm (V-SBB), that can {provide} the $ε$-global optimal solution to {our problem}. {We numerically show that our C3 optimization framework can improve the energy efficiency up to 88\% compared to any C2 optimization between communication and computation or caching. Furthermore, for our energy consumption problem, V-SBB {provides comparatively better solution than some other MINLP solvers.}}