OpenRaiser/Intern-Atlas huggingface dataset:
The importance of space and time in neuromorphic cognitive agents
Venue: arXiv cs.NE 2019
Year: 2019

Artificial neural networks and computational neuroscience models have made tremendous progress, allowing computers to achieve impressive results in artificial intelligence (AI) applications, such as image recognition, natural language processing, or autonomous driving. Despite this remarkable progress, biological neural systems consume orders of magnitude less energy than today's artificial neural networks and are much more agile and adaptive. This efficiency and adaptivity gap is partially explained by the computing substrate of biological neural processing systems that is fundamentally different from the way today's computers are built. Biological systems use in-memory computing elements operating in a massively parallel way rather than time-multiplexed computing units that are reused in a sequential fashion. Moreover, activity of biological neurons follows continuous-time dynamics in real, physical time, instead of operating on discrete temporal cycles abstracted away from real-time. Here, we present neuromorphic processing devices that emulate the biological style of processing by using parallel instances of mixed-signal analog/digital circuits that operate in real time. We argue that this approach brings significant advantages in efficiency of computation. We show examples of embodied neuromorphic agents that use such devices to interact with the environment and exhibit autonomous learning.
Logarithmic Regret for parameter-free Online Logistic Regression
Venue: arXiv cs.LG 2019
Year: 2019

We consider online optimization procedures in the context of logistic regression, focusing on the Extended Kalman Filter (EKF). We introduce a second-order algorithm close to the EKF, named Semi-Online Step (SOS), for which we prove a O(log(n)) regret in the adversarial setting, paving the way to similar results for the EKF. This regret bound on SOS is the first for such parameter-free algorithm in the adversarial logistic regression. We prove for the EKF in constant dynamics a O(log(n)) regret in expectation and in the well-specified logistic regression model.
PubSub-SGX: Exploiting Trusted Execution Environments for Privacy-Preserving Publish/Subscribe Systems
Venue: arXiv cs.DC 2019
Year: 2019

This paper presents PUBSUB-SGX, a content-based publish-subscribe system that exploits trusted execution environments (TEEs), such as Intel SGX, to guarantee confidentiality and integrity of data as well as anonymity and privacy of publishers and subscribers. We describe the technical details of our Python implementation, as well as the required system support introduced to deploy our system in a container-based runtime. Our evaluation results show that our approach is sound, while at the same time highlighting the performance and scalability trade-offs. In particular, by supporting just-in-time compilation inside of TEEs, Python programs inside of TEEs are in general faster than when executed natively using standard CPython.
Achieving Secrecy Capacity of Minimum Storage Regenerating Codes for all Feasible $(n, k, d)$ Parameter Values
Venue: arXiv cs.IT 2019
Year: 2019

This paper addresses the problem of constructing secure exact-repair regenerating codes at the MSR point for all feasible values of the parameters. The setting involves a passive eavesdropper who is allowed to observe the stored contents of, and the downloads into, an $l$-subset of the $n$ nodes of a distributed storage system (DSS). The objective is to achieve perfect secrecy between the eavesdropped symbols and the file stored on the DSS. Previous secure code constructions (most notably that by Rawat et al.) tackle the problem only for the restricted case wherein the number, $d$, of helper nodes aiding in the recovery of a failed node is equal to $n-1$. This paper builds on Rawat's work, by combining Gabidulin pre-coding and an MSR construction by Ye and Barg to prove the achievability of secrecy capacity at the MSR point for all allowed values of $d$.
Learning Vertex Convolutional Networks for Graph Classification
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we develop a new aligned vertex convolutional network model to learn multi-scale local-level vertex features for graph classification. Our idea is to transform the graphs of arbitrary sizes into fixed-sized aligned vertex grid structures, and define a new vertex convolution operation by adopting a set of fixed-sized one-dimensional convolution filters on the grid structure. We show that the proposed model not only integrates the precise structural correspondence information between graphs but also minimises the loss of structural information residing on local-level vertices. Experiments on standard graph datasets demonstrate the effectiveness of the proposed model.
Fused Lasso for Feature Selection using Structural Information
Venue: arXiv cs.LG 2019
Year: 2019

Feature selection has been proven a powerful preprocessing step for high-dimensional data analysis. However, most state-of-the-art methods tend to overlook the structural correlation information between pairwise samples, which may encapsulate useful information for refining the performance of feature selection. Moreover, they usually consider candidate feature relevancy equivalent to selected feature relevancy, and some less relevant features may be misinterpreted as salient features. To overcome these issues, we propose a new feature selection method using structural correlation between pairwise samples. Our idea is based on converting the original vectorial features into structure-based feature graph representations to incorporate structural relationship between samples, and defining a new evaluation measure to compute the joint significance of pairwise feature combinations in relation to the target feature graph. Furthermore, we formulate the corresponding feature subset selection problem into a least square regression model associated with a fused lasso regularizer to simultaneously maximize the joint relevancy and minimize the redundancy of the selected features. To effectively solve the optimization problem, an iterative algorithm is developed to identify the most discriminative features. Experiments demonstrate the effectiveness of the proposed approach.
An Automatic Speedup Theorem for Distributed Problems
Venue: arXiv cs.DC 2019
Year: 2019

Recently, Brandt et al. [STOC'16] proved a lower bound for the distributed Lovász Local Lemma, which has been conjectured to be tight for sufficiently relaxed LLL criteria by Chang and Pettie [FOCS'17]. At the heart of their result lies a speedup technique that, for graphs of girth at least $2t+2$, transforms any $t$-round algorithm for one specific LLL problem into a $(t-1)$-round algorithm for the same problem. We substantially improve on this technique by showing that such a speedup exists for any locally checkable problem $Π$, with the difference that the problem $Π_1$ the inferred $(t-1)$-round algorithm solves is not (necessarily) the same problem as $Π$. Our speedup is automatic in the sense that there is a fixed procedure that transforms a description for $Π$ into a description for $Π_1$ and reversible in the sense that any $(t-1)$-round algorithm for $Π_1$ can be transformed into a $t$-round algorithm for $Π$. In particular, for any locally checkable problem $Π$ with exact deterministic time complexity $T(n, Δ) \leq t$ on graphs with $n$ nodes, maximum node degree $Δ$, and girth at least $2t+2$, there is a sequence of problems $Π_1, Π_2, \dots$ with time complexities $T(n, Δ)-1, T(n, Δ)-2, \dots$, that can be inferred from $Π$. As a first application of our generalized speedup, we solve a long-standing open problem of Naor and Stockmeyer [STOC'93]: we show that weak $2$-coloring in odd-degree graphs cannot be solved in $o(\log^* Δ)$ rounds, thereby providing a matching lower bound to their upper bound.
Shapes from Echoes: Uniqueness from Point-to-Plane Distance Matrices
Venue: arXiv cs.CG 2019
Year: 2019

We study the problem of localizing a configuration of points and planes from the collection of point-to-plane distances. This problem models simultaneous localization and mapping from acoustic echoes as well as the notable "structure from sound" approach to microphone localization with unknown sources. In our earlier work we proposed computational methods for localization from point-to-plane distances and noted that such localization suffers from various ambiguities beyond the usual rigid body motions; in this paper we provide a complete characterization of uniqueness. We enumerate equivalence classes of configurations which lead to the same distance measurements as a function of the number of planes and points, and algebraically characterize the related transformations in both 2D and 3D. Here we only discuss uniqueness; computational tools and heuristics for practical localization from point-to-plane distances using sound will be addressed in a companion paper.
Performance of Non-orthogonal Multiple Access under Finite Blocklength
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we present a finite-block-length comparison between the orthogonal multiple access (OMA) scheme and the non-orthogonal multiple access (NOMA) for the uplink channel. First, we consider the Gaussian channel, and derive the closed form expressions for the rate and outage probability. Then, we extend our results to the quasi-static Rayleigh fading channel. Our analysis is based on the recent results on the characterization of the maximum coding rate at finite block-length and finite block-error probability. The overall system throughput is evaluated as a function of the number of information bits, channel uses and power. We find what would be the respective values of these different parameters that would enable throughput maximization. Furthermore, we analyze the system performance in terms of reliability and throughput when applying the type-I ARQ protocol with limited number of retransmissions. The throughput and outage probability are evaluated for different blocklengths and number of information bits. Our analysis reveals that there is a trade-off between reliability and throughput in the ARQ. While increasing the number of retransmissions boosts reliability by minimizing the probability of reception error, it results in more delay which decreases the throughput. Nevertheless, the results show that NOMA always outperforms OMA in terms of throughput, reliability and latency regardless of the users priority or the number of retransmissions in both Gaussian and fading channels.
Graph Neural Processes: Towards Bayesian Graph Neural Networks
Venue: arXiv cs.LG 2019
Year: 2019

We introduce Graph Neural Processes (GNP), inspired by the recent work in conditional and latent neural processes. A Graph Neural Process is defined as a Conditional Neural Process that operates on arbitrary graph data. It takes features of sparsely observed context points as input, and outputs a distribution over target points. We demonstrate graph neural processes in edge imputation and discuss benefits and drawbacks of the method for other application areas. One major benefit of GNPs is the ability to quantify uncertainty in deep learning on graph structures. An additional benefit of this method is the ability to extend graph neural networks to inputs of dynamic sized graphs.
SeMA: A Design Methodology for Building Secure Android Apps
Venue: arXiv cs.SE 2019
Year: 2019

UX (user experience) designers visually capture the UX of an app via storyboards. This method is also used in Android app development to conceptualize and design apps. Recently, security has become an integral part of Android app UX because mobile apps are used to perform critical activities such as banking, communication, and health. Therefore, securing user information is imperative in mobile apps. In this context, storyboarding tools offer limited capabilities to capture and reason about security requirements of an app. Consequently, security cannot be baked into the app at design time. Hence, vulnerabilities stemming from design flaws can often occur in apps. To address this concern, in this paper, we propose a storyboard based design methodology to enable the specification and verification of security properties of an Android app at design time.
Transfer Learning for Performance Modeling of Configurable Systems: A Causal Analysis
Venue: arXiv cs.AI 2019
Year: 2019

Modern systems (e.g., deep neural networks, big data analytics, and compilers) are highly configurable, which means they expose different performance behavior under different configurations. The fundamental challenge is that one cannot simply measure all configurations due to the sheer size of the configuration space. Transfer learning has been used to reduce the measurement efforts by transferring knowledge about performance behavior of systems across environments. Previously, research has shown that statistical models are indeed transferable across environments. In this work, we investigate identifiability and transportability of causal effects and statistical relations in highly-configurable systems. Our causal analysis agrees with previous exploratory analysis \cite{Jamshidi17} and confirms that the causal effects of configuration options can be carried over across environments with high confidence. We expect that the ability to carry over causal relations will enable effective performance analysis of highly-configurable systems.
A Survey on Graph Processing Accelerators: Challenges and Opportunities
Venue: arXiv cs.DC 2019
Year: 2019

Graph is a well known data structure to represent the associated relationships in a variety of applications, e.g., data science and machine learning. Despite a wealth of existing efforts on developing graph processing systems for improving the performance and/or energy efficiency on traditional architectures, dedicated hardware solutions, also referred to as graph processing accelerators, are essential and emerging to provide the benefits significantly beyond those pure software solutions can offer. In this paper, we conduct a systematical survey regarding the design and implementation of graph processing accelerator. Specifically, we review the relevant techniques in three core components toward a graph processing accelerator: preprocessing, parallel graph computation and runtime scheduling. We also examine the benchmarks and results in existing studies for evaluating a graph processing accelerator. Interestingly, we find that there is not an absolute winner for all three aspects in graph acceleration due to the diverse characteristics of graph processing and complexity of hardware configurations. We finially present to discuss several challenges in details, and to further explore the opportunities for the future research.
Near Optimal Algorithms for Hard Submodular Programs with Discounted Cooperative Costs
Venue: arXiv cs.LG 2019
Year: 2019

In this paper, we investigate a class of submodular problems which in general are very hard. These include minimizing a submodular cost function under combinatorial constraints, which include cuts, matchings, paths, etc., optimizing a submodular function under submodular cover and submodular knapsack constraints, and minimizing a ratio of submodular functions. All these problems appear in several real world problems but have hardness factors of $Ω(\sqrt{n})$ for general submodular cost functions. We show how we can achieve constant approximation factors when we restrict the cost functions to low rank sums of concave over modular functions. A wide variety of machine learning applications are very naturally modeled via this subclass of submodular functions. Our work therefore provides a tighter connection between theory and practice by enabling theoretically satisfying guarantees for a rich class of expressible, natural, and useful submodular cost models. We empirically demonstrate the utility of our models on real world problems of cooperative image matching and sensor placement with cooperative costs.
A Memoization Framework for Scaling Submodular Optimization to Large Scale Problems
Venue: arXiv cs.LG 2019
Year: 2019

We are motivated by large scale submodular optimization problems, where standard algorithms that treat the submodular functions in the \emph{value oracle model} do not scale. In this paper, we present a model called the \emph{precomputational complexity model}, along with a unifying memoization based framework, which looks at the specific form of the given submodular function. A key ingredient in this framework is the notion of a \emph{precomputed statistic}, which is maintained in the course of the algorithms. We show that we can easily integrate this idea into a large class of submodular optimization problems including constrained and unconstrained submodular maximization, minimization, difference of submodular optimization, optimization with submodular constraints and several other related optimization problems. Moreover, memoization can be integrated in both discrete and continuous relaxation flavors of algorithms for these problems. We demonstrate this idea for several commonly occurring submodular functions, and show how the precomputational model provides significant speedups compared to the value oracle model. Finally, we empirically demonstrate this for large scale machine learning problems of data subset selection and summarization.
On the Mortality Problem: from multiplicative matrix equations to linear recurrence sequences and beyond
Venue: arXiv cs.DM 2019
Year: 2019

We consider the following variant of the Mortality Problem: given $k\times k$ matrices $A_1, A_2, \dots,A_{t}$, does there exist nonnegative integers $m_1, m_2, \dots,m_t$ such that the product $A_1^{m_1} A_2^{m_2} \cdots A_{t}^{m_{t}}$ is equal to the zero matrix? It is known that this problem is decidable when $t \leq 2$ for matrices over algebraic numbers but becomes undecidable for sufficiently large $t$ and $k$ even for integral matrices. In this paper, we prove the first decidability results for $t>2$. We show as one of our central results that for $t=3$ this problem in any dimension is Turing equivalent to the well-known Skolem problem for linear recurrence sequences. Our proof relies on the Primary Decomposition Theorem for matrices that was not used to show decidability results in matrix semigroups before. As a corollary we obtain that the above problem is decidable for $t=3$ and $k \leq 3$ for matrices over algebraic numbers and for $t=3$ and $k=4$ for matrices over real algebraic numbers. Another consequence is that the set of triples $(m_1,m_2,m_3)$ for which the equation $A_1^{m_1} A_2^{m_2} A_3^{m_3}$ equals the zero matrix is equal to a finite union of direct products of semilinear sets. For $t=4$ we show that the solution set can be non-semilinear, and thus it seems unlikely that there is a direct connection to the Skolem problem. However we prove that the problem is still decidable for upper-triangular $2 \times 2$ rational matrices by employing powerful tools from transcendence theory such as Baker's theorem and S-unit equations.
Competition with Three-Tier Spectrum Access and Spectrum Monitoring
Venue: arXiv cs.GT 2019
Year: 2019

The Citizens Broadband Radio Service (CBRS) recently adopted in the U.S. enables two tiers of commercial users to share spectrum with a third tier of incumbent users. This sharing can be further assisted by Environmental Sensing Capability operators (ESCs), that monitor the spectrum occupancy to determine when use of the spectrum will not harm incumbents. Two key aspects of this framework that impact how firms may compete are the differences in information provided by different ESCs and the different tiers in which a firm may access the spectrum. We develop a game theoretic model that captures both of these features and analyze it to gain insight into their impact. Specifically, we consider a priority access (PA) tier firm has access to the both licensed band and unlicensed band, and a general authorized access (GAA) tier firm has access only to the unlicensed band. The PA tier and GAA tier firms compete for users. Our analysis reveals that the amount of unlicensed and licensed bandwidth in the CBRS must be chosen judiciously in order to maximize the social welfare. We also show that a limited amount of unlicensed access of PA tier firm is beneficial to the user's surplus as well as to the social welfare.
Reliable Deep Grade Prediction with Uncertainty Estimation
Venue: arXiv cs.AI 2019
Year: 2019

Currently, college-going students are taking longer to graduate than their parental generations. Further, in the United States, the six-year graduation rate has been 59% for decades. Improving the educational quality by training better-prepared students who can successfully graduate in a timely manner is critical. Accurately predicting students' grades in future courses has attracted much attention as it can help identify at-risk students early so that personalized feedback can be provided to them on time by advisors. Prior research on students' grade prediction include shallow linear models; however, students' learning is a highly complex process that involves the accumulation of knowledge across a sequence of courses that can not be sufficiently modeled by these linear models. In addition to that, prior approaches focus on prediction accuracy without considering prediction uncertainty, which is essential for advising and decision making. In this work, we present two types of Bayesian deep learning models for grade prediction. The MLP ignores the temporal dynamics of students' knowledge evolution. Hence, we propose RNN for students' performance prediction. To evaluate the performance of the proposed models, we performed extensive experiments on data collected from a large public university. The experimental results show that the proposed models achieve better performance than prior state-of-the-art approaches. Besides more accurate results, Bayesian deep learning models estimate uncertainty associated with the predictions. We explore how uncertainty estimation can be applied towards developing a reliable educational early warning system. In addition to uncertainty, we also develop an approach to explain the prediction results, which is useful for advisors to provide personalized feedback to students.
Sound Invariant Checking Using Type Modifiers and Object Capabilities
Venue: arXiv cs.PL 2019
Year: 2019

In this paper we use pre existing language support for type modifiers and object capabilities to enable a system for sound runtime verification of invariants. Our system guarantees that class invariants hold for all objects involved in execution. Invariants are specified simply as methods whose execution is statically guaranteed to be deterministic and not access any externally mutable state. We automatically call such invariant methods only when objects are created or the state they refer to may have been mutated. Our design restricts the range of expressible invariants but improves upon the usability and performance of our system compared to prior work. In addition, we soundly support mutation, dynamic dispatch, exceptions, and non determinism, while requiring only a modest amount of annotation. We present a case study showing that our system requires a lower annotation burden compared to Spec#, and performs orders of magnitude less runtime invariant checks compared to the widely used `visible state semantics' protocols of D, Eiffel. We also formalise our approach and prove that such pre existing type modifier and object capability support is sufficient to ensure its soundness.