OpenRaiser/Intern-Atlas huggingface dataset:
Stability and Optimization Error of Stochastic Gradient Descent for Pairwise Learning
Venue: arXiv cs.LG 2019
Year: 2019

In this paper we study the stability and its trade-off with optimization error for stochastic gradient descent (SGD) algorithms in the pairwise learning setting. Pairwise learning refers to a learning task which involves a loss function depending on pairs of instances among which notable examples are bipartite ranking, metric learning, area under ROC (AUC) maximization and minimum error entropy (MEE) principle. Our contribution is twofold. Firstly, we establish the stability results of SGD for pairwise learning in the convex, strongly convex and non-convex settings, from which generalization bounds can be naturally derived. Secondly, we establish the trade-off between stability and optimization error of SGD algorithms for pairwise learning. This is achieved by lower-bounding the sum of stability and optimization error by the minimax statistical error over a prescribed class of pairwise loss functions. From this fundamental trade-off, we obtain lower bounds for the optimization error of SGD algorithms and the excess expected risk over a class of pairwise losses. In addition, we illustrate our stability results by giving some specific examples of AUC maximization, metric learning and MEE.
Communication trade-offs for synchronized distributed SGD with large step size
Venue: arXiv cs.LG 2019
Year: 2019

Synchronous mini-batch SGD is state-of-the-art for large-scale distributed machine learning. However, in practice, its convergence is bottlenecked by slow communication rounds between worker nodes. A natural solution to reduce communication is to use the \emph{`local-SGD'} model in which the workers train their model independently and synchronize every once in a while. This algorithm improves the computation-communication trade-off but its convergence is not understood very well. We propose a non-asymptotic error analysis, which enables comparison to \emph{one-shot averaging} i.e., a single communication round among independent workers, and \emph{mini-batch averaging} i.e., communicating at every step. We also provide adaptive lower bounds on the communication frequency for large step-sizes ($ t^{-α} $, $ α\in (1/2 , 1 ) $) and show that \emph{Local-SGD} reduces communication by a factor of $O\Big(\frac{\sqrt{T}}{P^{3/2}}\Big)$, with $T$ the total number of gradients and $P$ machines.
Ephemeral Data Handling in Microservices - Technical Report
Venue: arXiv cs.PL 2019
Year: 2019

In modern application areas for software systems --- like eHealth, the Internet-of-Things, and Edge Computing --- data is encoded in heterogeneous, tree-shaped data-formats, it must be processed in real-time, and it must be ephemeral, i.e., not persist in the system. While it is preferable to use a query language to express complex data-handling logic, their typical execution engine, a database external from the main application, is unfit in scenarios of ephemeral data-handling. A better option is represented by integrated query frameworks, which benefit from existing development support tools (e.g., syntax and type checkers) and execute within the application memory. In this paper, we propose one such framework that, for the first time, targets tree-shaped, document-oriented queries. We formalise an instantiation of MQuery, a sound variant of the widely-used MongoDB query language, which we implemented in the Jolie language. Jolie programs are microservices, the building blocks of modern software systems. Moreover, since Jolie supports native tree data-structures and automatic management of heterogeneous data-encodings, we can provide a uniform way to use MQuery on any data-format supported by the language. We present a non-trivial use case from eHealth, use it to concretely evaluate our model, and to illustrate our formalism.
Palindromes in two-dimensional Words
Venue: arXiv cs.DM 2019
Year: 2019

A two-dimensional ($2$D) word is a $2$D palindrome if it is equal to its reverse and it is an HV-palindrome if all its columns and rows are $1$D palindromes. We study some combinatorial and structural properties of HV-palindromes and its comparison with $2$D palindromes. We investigate the maximum number number of distinct non-empty HV-palindromic sub-arrays in any finite $2$D word, thus, proving the conjecture given by Anisiua et al. We also find the least number of HV-palindromes in an infinite $2$D word over a finite alphabet size $q$.
Interpolation and the Array Property Fragment
Venue: arXiv cs.LO 2019
Year: 2019

Interpolation based software model checkers have been successfully employed to automatically prove programs correct. Their power comes from interpolating SMT solvers that check the feasibility of potential counterexamples and compute candidate invariants, otherwise. This approach works well for quantifier-free theories, like equality theory or linear arithmetic. For quantified formulas, there are SMT solvers that can decide expressive fragments of quantified formulas, e. g., EPR, the array property fragment, and the finite almost uninterpreted fragment. However, these solvers do not support interpolation. It is already known that in general EPR does not allow for interpolation. In this paper, we show the same result for the array property fragment.
Multiterminal Secret Key Agreement with Nearly No Discussion
Venue: arXiv cs.IT 2019
Year: 2019

We consider the secret key agreement problem under the multiterminal source model proposed by Csiszár and Narayan. A single-letter characterization of the secrecy capacity is desired but remains unknown except in the extreme case with unlimited public discussion and without wiretapper's side information. Taking the problem to the opposite extreme by requiring the public discussion rate to be zero asymptotically, we obtain the desired characterization under surprisingly general setting with wiretapper's side information, silent users, trusted and untrusted helpers. An immediate consequence of the result is that the capacity with nearly no discussion is the same as the capacity with no discussion, resolving a previous conjecture in the affirmative. The idea of the proof is to characterize the capacity in the special case with neither wiretapper's side information nor untrusted helpers using a multivariate extension of Gács-Körner common information, and then extend the result to the general setting by a change of scenario that turns untrusted helpers into trusted helpers. We further show how to evaluate the capacity explicitly for finite linear sources and discuss how the current result can be extended to improve and unify existing bounds on the capacity for strictly positive discussion rates.
Genet: A Quickly Scalable Fat-Tree Overlay for Personal Volunteer Computing using WebRTC
Venue: arXiv cs.DC 2019
Year: 2019

WebRTC enables browsers to exchange data directly but the number of possible concurrent connections to a single source is limited. We overcome the limitation by organizing participants in a fat-tree overlay: when the maximum number of connections of a tree node is reached, the new participants connect to the node's children. Our design quickly scales when a large number of participants join in a short amount of time, by relying on a novel scheme that only requires local information to route connection messages: the destination is derived from the hash value of the combined identifiers of the message's source and of the node that is holding the message. The scheme provides deterministic routing of a sequence of connection messages from a single source and probabilistic balancing of newer connections among the leaves. We show that this design puts at least 83% of nodes at the same depth as a deterministic algorithm, can connect a thousand browser windows in 21-55 seconds in a local network, and can be deployed for volunteer computing to tap into 320 cores in less than 30 seconds on a local network to increase the total throughput on the Collatz application by two orders of magnitude compared to a single core.
Compressive Multidimensional Harmonic Retrieval with Prior Knowledge
Venue: arXiv cs.IT 2019
Year: 2019

This paper concerns the problem of estimating multidimensional (MD) frequencies using prior knowledge of the signal spectral sparsity from partial time samples. In many applications, such as radar, wireless communications, and super-resolution imaging, some structural information about the signal spectrum might be known beforehand. Suppose that the frequencies lie in given intervals, the goal is to improve the frequency estimation performance by using the prior information. We study the MD Vandermonde decomposition of block Toeplitz matrices in which the frequencies are restricted to given intervals. We then propose to solve the frequency-selective atomic norm minimization by converting them into semidefinite program based on the MD Vandermonde decomposition. Numerical simulation results are presented to illustrate the good performance of the proposed method.
Threshold shift method for reliability-based design optimization
Venue: arXiv cs.NA 2019
Year: 2019

We present a novel approach, referred to as the 'threshold shift method' (TSM), for reliability based design optimization (RBDO). The proposed approach is similar in spirit with the sequential optimization and reliability analysis (SORA) method where the RBDO problem is decoupled into an optimization and a reliability analysis problem. However, unlike SORA that utilizes shift-vector to shift the design variables within a constraint (independently), in TSM we propose to shift the threshold of the constraints. We argue that modifying a constraint, either by shifting the design variables (SORA) or by shifting the threshold of the constraints (TSM), influences the other constraints of the system. Therefore, we propose to determine the thresholds for all the constraints by solving a single optimization problem. Additionally, the proposed TSM is equipped with an active-constraint determination scheme. To make the method scalable, a practical algorithm for TSM that utilizes two surrogate models is proposed. Unlike the conventional RBDO methods, the proposed approach has the ability to handle highly non-linear probabilistic constraints. The performance of the proposed approach is examined on six benchmark problems selected from the literature. The proposed approach yields excellent results outperforming other popular methods in literature. As for the computational efficiency, the proposed approach is found to be highly efficient, indicating it's future application to other real-life problems.
$d$-MABE: Distributed Multilevel Attribute-Based EMR Management and Applications
Venue: arXiv cs.CR 2019
Year: 2019

Current systems used by medical institutions for the management and transfer of Electronic Medical Records (EMR) can be vulnerable to security and privacy threats. In addition, these centralized systems often lack interoperability and give patients limited or no access to their own EMRs. In this paper, we propose a novel distributed data sharing scheme that applies the security benefits of blockchain to handle these concerns. With blockchain, we incorporate smart contracts and a distributed storage system to alleviate the dependence on the record-generating institutions to manage and share patient records. To preserve privacy of patient records, we implement our smart contracts as a method to allow patients to verify attributes prior to granting access rights. Our proposed scheme also facilitates selective sharing of medical records among staff members that belong to different levels of a hierarchical institution. We provide extensive security, privacy, and evaluation analyses to show that our proposed scheme is both efficient and practical.
Distributed Detection of Cliques in Dynamic Networks
Venue: arXiv cs.DC 2019
Year: 2019

This paper provides an in-depth study of the fundamental problems of finding small subgraphs in distributed dynamic networks. While some problems are trivially easy to handle, such as detecting a triangle that emerges after an edge insertion, we show that, perhaps somewhat surprisingly, other problems exhibit a wide range of complexities in terms of the trade-offs between their round and bandwidth complexities. In the case of triangles, which are only affected by the topology of the immediate neighborhood, some end results are: \begin{itemize} \item The bandwidth complexity of $1$-round dynamic triangle detection or listing is $Θ(1)$. \item The bandwidth complexity of $1$-round dynamic triangle membership listing is $Θ(1)$ for node/edge deletions, $Θ(n^{1/2})$ for edge insertions, and $Θ(n)$ for node insertions. \item The bandwidth complexity of $1$-round dynamic triangle membership detection is $Θ(1)$ for node/edge deletions, $O(\log n)$ for edge insertions, and $Θ(n)$ for node insertions. \end{itemize} Most of our upper and lower bounds are \emph{tight}. Additionally, we provide almost always tight upper and lower bounds for larger cliques.
Blurring the Line Between Structure and Learning to Optimize and Adapt Receptive Fields
Venue: arXiv cs.CV 2019
Year: 2019

The visual world is vast and varied, but its variations divide into structured and unstructured factors. We compose free-form filters and structured Gaussian filters, optimized end-to-end, to factorize deep representations and learn both local features and their degree of locality. Our semi-structured composition is strictly more expressive than free-form filtering, and changes in its structured parameters would require changes in free-form architecture. In effect this optimizes over receptive field size and shape, tuning locality to the data and task. Dynamic inference, in which the Gaussian structure varies with the input, adapts receptive field size to compensate for local scale variation. Optimizing receptive field size improves semantic segmentation accuracy on Cityscapes by 1-2 points for strong dilated and skip architectures and by up to 10 points for suboptimal designs. Adapting receptive fields by dynamic Gaussian structure further improves results, equaling the accuracy of free-form deformation while improving efficiency.
Probing What Different NLP Tasks Teach Machines about Function Word Comprehension
Venue: arXiv cs.CL 2019
Year: 2019

We introduce a set of nine challenge tasks that test for the understanding of function words. These tasks are created by structurally mutating sentences from existing datasets to target the comprehension of specific types of function words (e.g., prepositions, wh-words). Using these probing tasks, we explore the effects of various pretraining objectives for sentence encoders (e.g., language modeling, CCG supertagging and natural language inference (NLI)) on the learned representations. Our results show that pretraining on language modeling performs the best on average across our probing tasks, supporting its widespread use for pretraining state-of-the-art NLP models, and CCG supertagging and NLI pretraining perform comparably. Overall, no pretraining objective dominates across the board, and our function word probing tasks highlight several intuitive differences between pretraining objectives, e.g., that NLI helps the comprehension of negation.
Machine Learning For Distributed Acoustic Sensors, Classic versus Image and Deep Neural Networks Approach
Venue: arXiv cs.LG 2019
Year: 2019

Distributed Acoustic Sensing (DAS) using fiber optic cables is a promising new technology for pipeline monitoring and protection. In this work, we applied and compared two approaches for event detection using DAS: Classic machine learning approach and the approach based on image processing and deep learning. Although with both approaches acceptable performance can be achieved, the preliminary results show that image based deep learning is more promising approach, offering six times lower event detection delay and twelve times lower execution time.
Approximation Algorithms for Min-Distance Problems
Venue: arXiv cs.DS 2019
Year: 2019

We study fundamental graph parameters such as the Diameter and Radius in directed graphs, when distances are measured using a somewhat unorthodox but natural measure: the distance between $u$ and $v$ is the minimum of the shortest path distances from $u$ to $v$ and from $v$ to $u$. The center node in a graph under this measure can for instance represent the optimal location for a hospital to ensure the fastest medical care for everyone, as one can either go to the hospital, or a doctor can be sent to help. By computing All-Pairs Shortest Paths, all pairwise distances and thus the parameters we study can be computed exactly in $\tilde{O}(mn)$ time for directed graphs on $n$ vertices, $m$ edges and nonnegative edge weights. Furthermore, this time bound is tight under the Strong Exponential Time Hypothesis [Roditty-Vassilevska W. STOC 2013] so it is natural to study how well these parameters can be approximated in $O(mn^{1-ε})$ time for constant $ε>0$. Abboud, Vassilevska Williams, and Wang [SODA 2016] gave a polynomial factor approximation for Diameter and Radius, as well as a constant factor approximation for both problems in the special case where the graph is a DAG. We greatly improve upon these bounds by providing the first constant factor approximations for Diameter, Radius and the related Eccentricities problem in general graphs. Additionally, we provide a hierarchy of algorithms for Diameter that gives a time/accuracy trade-off.
Control from Signal Temporal Logic Specifications with Smooth Cumulative Quantitative Semantics
Venue: arXiv cs.SY 2019
Year: 2019

We present a framework to synthesize control policies for nonlinear dynamical systems from complex temporal constraints specified in a rich temporal logic called Signal Temporal Logic (STL). We propose a novel smooth and differentiable STL quantitative semantics called cumulative robustness, and efficiently compute control policies through a series of smooth optimization problems that are solved using gradient ascent algorithms. Furthermore, we demonstrate how these techniques can be incorporated in a model predictive control framework in order to synthesize control policies over long time horizons. The advantages of combining the cumulative robustness function with smooth optimization methods as well as model predictive control are illustrated in case studies.
The minimum cost query problem on matroids with uncertainty areas
Venue: arXiv cs.DS 2019
Year: 2019

We study the minimum weight basis problem on matroid when elements' weights are uncertain. For each element we only know a set of possible values (an uncertainty area) that contains its real weight. In some cases there exist bases that are uniformly optimal, that is, they are minimum weight bases for every possible weight function obeying the uncertainty areas. In other cases, computing such a basis is not possible unless we perform some queries for the exact value of some elements. Our main result is a polynomial time algorithm for the following problem. Given a matroid with uncertainty areas and a query cost function on its elements, find the set of elements of minimum total cost that we need to simultaneously query such that, no matter their revelation, the resulting instance admits a uniformly optimal base. We also provide combinatorial characterizations of all uniformly optimal bases, when one exists; and of all sets of queries that can be performed so that after revealing the corresponding weights the resulting instance admits a uniformly optimal base.
Interactive user interface based on Convolutional Auto-encoders for annotating CT-scans
Venue: arXiv cs.HC 2019
Year: 2019

High resolution computed tomography (HRCT) is the most important imaging modality for interstitial lung diseases, where the radiologists are interested in identifying certain patterns, and their volumetric and regional distribution. The use of machine learning can assist the radiologists with both these tasks by performing semantic segmentation. In this paper, we propose an interactive annotation-tool for semantic segmentation that assists the radiologist in labeling CT scans. The annotation tool is evaluated by six radiologists and radiology residents classifying healthy lung and reticular pattern i HRCT images. The usability of the system is evaluated with a System Usability Score (SUS) and interaction information from the readers that used the tool for annotating the CT volumes. It was discovered that the experienced usability and how the users interactied with the system differed between the users. A higher SUS-score was given by users that prioritized learning speed over model accuracy and spent less time with manual labeling and instead utilized the suggestions provided by the GUI. An analysis of the annotation variations between the readers show substantial agreement (Cohen's kappa=0.69) for classification of healthy and affected lung parenchyma in pulmonary fibrosis. The inter-reader variation is a challenge for the definition of ground truth.
XR: Enabling training mode in the human brain XR: Enabling training mode in the human brain
Venue: arXiv cs.GR 2019
Year: 2019

The face of simulation-based training has greatly evolved, with the most recent tools giving the ability to create virtual environments that rival realism. At first glance, it might appear that what the training sector needs is the most realistic simulators possible, but traditional simulators are not necessarily the most efficient or practical training tools. With all that these new technologies have to offer; the challenge is to go back to the core of training needs and identify the right vector of sensory cues that will most effectively enable training mode in the human brain. Bigger and Pricier doesn't necessarily mean better. Simulation with cross-reality content (XR), which by definition encompasses virtual reality (VR), mixed reality (MR), and augmented reality (AR), is the most practical solution for deploying any kind of simulation-based training. The authors of this paper (a teacher and a technology expert) share their experiences and expose XR-specific best practices to maximize learning transfer. ABOUT THE AUTHORS Sebastien Loze : Starting his career in the modeling and simulation community more than 15 years ago, S{é}bastien has focused on learning about the latest simulation innovations and sharing information on how experts have solved their challenges. He worked on the COTS integration at CAE and the Presagis focusing on Simulation and Visualization products. More recently, Sebastien put together simulation and training teams and strategies for emerging companies like CM Labs and D-BOX. He is now the Simulations Industry Manager at Epic Games, focusing on helping companies develop real-time solutions for simulation-based training. Philippe Lepinard: Former military helicopter pilot and simulation officer, Philippe L{é}pinard is now an associate professor at the University of Paris-Est Cr{é}teil (UPEC). His research is focusing on playful learning and training through simulation. He is one of the founding members of the French simulation association.