This work considers the question: what convergence guarantees does the stochastic subgradient method have in the absence of smoothness and convexity? We prove that the stochastic subgradient method, on any semialgebraic locally Lipschitz function, produces limit points that are all first-order stationary. More generally, our result applies to any function with a Whitney stratifiable graph. In particular, this work endows the stochastic subgradient method with rigorous convergence guarantees for a wide class of problems arising in data science---including all popular deep learning architectures.

Apr 24 2018

cs.DS arXiv:1804.08001v1

We design new differentially private algorithms for the Euclidean k-means problem, both in the centralized model and in the local model of differential privacy. In both models, our algorithms achieve significantly improved error rates over the previous state-of-the-art. In addition, in the local model, our algorithm significantly reduces the number of needed interactions. Although the problem has been widely studied in the context of differential privacy, all of the existing constructions achieve only super constant approximation factors. We present, for the first time, efficient private algorithms for the problem with constant multiplicative error.

We give a simple distributed algorithm for computing adjacency matrix eigenvectors for the communication graph in an asynchronous gossip model. We show how to use this algorithm to give state-of-the-art asynchronous community detection algorithms when the communication graph is drawn from the well-studied \emphstochastic block model. Our methods also apply to a natural alternative model of randomized communication, where nodes within a community communicate more frequently than nodes in different communities. Our analysis simplifies and generalizes prior work by forging a connection between asynchronous eigenvector computation and Oja's algorithm for streaming principal component analysis. We hope that our work serves as a starting point for building further connections between the analysis of stochastic iterative methods, like Oja's algorithm, and work on asynchronous and gossip-type algorithms for distributed computation.

Apr 24 2018

hep-th arXiv:1804.08358v1

A concept of measuring the quantum distance between two different quantum states which is called quantum information metric is presented. The holographic principle (AdS/CFT) suggests that the quantum information metric $G_{\lambda\lambda}$ between perturbed state and unperturbed state in field theory has a dual description in the classical gravity. In this work we calculate the quantum information metric of a theory which is dual to a conical defect geometry and we show that it is $n$ times the one of its covering space. We also give a holographic check for our result in the gravity side. Meanwhile, it was argued that $G_{\lambda\lambda}$ is dual to a codimension-one surface in spacetime and satisfies $G_{\lambda\lambda}=n_{d}\cdot\mbox{Vol}(\Sigma_{max})/L^{d}$. We show that the coefficient $n_d$ for conical defect should be rescaled by $n^2$ from the one for AdS. A limit case of conical defect --- the massless BTZ black hole--- is also considered. We show that the quantum information metric of the massless BTZ black hole disagrees with the one obtained by taking the vanishing temperature limit in BTZ black hole. This provides a new arena in differiating the different phases between BTZ spacetime and its massless cousin.

Apr 24 2018

cs.NI arXiv:1804.08403v1

The Least Loaded (LL) routing algorithm has been in recent decades the routing method of choice in circuit switched networks and therefore it provides a benchmark against which new methods can be compared. This paper improves the performance of the LL algorithm by additionally incorporating a machine learning approach, using a conceptually simple supervised naïve Bayes (NB) classifier. Based on a sequence of historical network snapshots, this predicts the potential future circuit blocking probability between each node pair. These snapshots are taken for each service request arriving to the network and record the number of busy capacity units on each link at that instant. The candidate route for serving a current service request is based on both the link loads and the potential future blocking probability of the entire network in case this route is indeed used. The performance of this proposed approach is studied via simulations and compared with both the conventional LL algorithm and the Shortest Path (SP) based approach. Results indicate that the proposed supervised naïve Bayes classifier-assisted LL routing algorithm significantly reduces blocking probability of service connection requests and outperforms both the conventional LL and SP routing algorithms. To enable the learning process based on a large number of network snapshots, we also develop a parallel computing framework to implement parallel learning and performance evaluation. Also, a network control system supporting naïve Bayes classifier-assisted LL routing algorithm is addressed.

Apr 24 2018

cs.SE arXiv:1804.07803v1

Most bug assignment approaches utilize text classification and information retrieval techniques. These approaches use the textual contents of bug reports to build recommendation models. The textual contents of bug reports are usually of high dimension and noisy source of information. These approaches suffer from low accuracy and high computational needs. In this paper, we investigate whether using categorical fields of bug reports, such as component to which the bug belongs, are appropriate to represent bug reports instead of textual description. We build a classification model by utilizing the categorical features, as a representation, for the bug report. The experimental evaluation is conducted using three projects namely NetBeans, Freedesktop, and Firefox. We compared this approach with two machine learning based bug assignment approaches. The evaluation shows that using the textual contents of bug reports is important. In addition, it shows that the categorical features can improve the classification accuracy.

Autonomous vehicles bring the promise of enhancing the consumer experience in terms of comfort and convenience and, in particular, the safety of the autonomous vehicle. Safety functions in autonomous vehicles such as Automatic Emergency Braking and Lane Centering Assist rely on computation, information sharing, and the timely actuation of the safety functions. One opportunity to achieve robust autonomous vehicle safety is by enhancing the robustness of in-vehicle networking architectures that support built-in resiliency mechanisms. Software Defined Networking (SDN) is an advanced networking paradigm that allows fine-grained manipulation of routing tables and routing engines and the implementation of complex features such as failover, which is a mechanism of protecting in-vehicle networks from failure, and in which a standby link automatically takes over once the main link fails. In this paper, we leverage SDN network programmability features to enable resiliency in the autonomous vehicle realm. We demonstrate that a Software Defined In-Vehicle Networking (SDIVN) does not add overhead compared to Legacy In-Vehicle Networks (LIVNs) under non-failure conditions and we highlight its superiority in the case of a link failure and its timely delivery of messages. We verify the proposed architectures benefits using a simulation environment that we have developed and we validate our design choices through testing and simulations

We present the second edition of a Best Practices Guide for academic departments and other institutions striving to create more inclusive environments for physicists and astronomers in the LGBT+ community. Our recommendations incorporate new research since the original, 2014 edition, and are designed for anyone who wishes to become aware of -- and help mitigate -- the extra burdens that face members of the LGBT+ community in the physical sciences.

Micro-sized cold atmospheric plasma (uCAP) has been developed to expand the applications of CAP in cancer therapy. In this paper, uCAP devices with different nozzle lengths were applied to investigate effects on both brain (glioblastoma U87) and breast (MDA-MB-231) cancer cells. Various diagnostic techniques were employed to evaluate the parameters of uCAP devices with different lengths such as potential distribution, electron density, and optical emission spectroscopy. The generation of short- and long-lived species (such as hydroxyl radical (.OH), superoxide (O2-), hydrogen peroxide (H2O2), nitrite (NO2-), et al) were studied. These data revealed that uCAP treatment with a 20 mm length tube has a stronger effect than that of the 60 mm tube due to the synergetic effects of reactive species and free radicals. Reactive species generated by uCAP enhanced tumor cell death in a dose-dependent fashion and was not specific with regards to tumor cell type.

Annotating temporal relations (TempRel) between events described in natural language is known to be labor intensive, partly because the total number of TempRels is quadratic in terms of the number of events. As a result, only a small number of documents are typically annotated, limiting the coverage of various lexical/semantic phenomena. One possibility is to make use of the readily available, partially annotated data (P) that cover more documents. However, missing annotations in P are known to hurt, rather than help, existing systems. This work is a case study in exploring various usages of P for TempRel extraction. Results show that despite missing annotations, P is still a useful supervision signal for this task.