We propose a new stochastic gradient method for optimizing the sum of a finite set of smooth functions, where the sum is strongly convex. While standard stochastic gradient methods converge at sublinear rates for this problem, the proposed method incorporates a memory of previous gradient values in order to achieve a linear convergence rate. In a machine learning context, numerical experiments indicate that the new algorithm can dramatically outperform standard algorithms, both in terms of optimizing the training error and reducing the test error quickly.

Non-linear dynamical systems (DS) have been used extensively for building generative models of human behavior. Its applications range from modeling brain dynamics to encoding motor commands. Many schemes have been proposed for encoding robot motions using dynamical systems with a single attractor placed at a predefined target in state space. Although these enable the robots to react against sudden perturbations without any re-planning, the motions are always directed towards a single target. In this work, we focus on combining several such DS with distinct attractors, resulting in a multi-stable DS.

The application of the maximum entropy principle to sequence modeling has been popularized by methods such as Conditional Random Fields (CRFs). However, these approaches are generally limited to modeling paths in discrete spaces of low dimensionality. We consider the problem of modeling distributions over paths in continuous spaces of high dimensionality---a problem for which inference is generally intractable. Our main contribution is to show that maximum entropy modeling of high-dimensional, continuous paths is tractable as long as the constrained features possess a certain kind of low dimensional structure. In this case, we show that the associated {\em partition function} is symmetric and that this symmetry can be exploited to compute the partition function efficiently in a compressed form. Empirical results are given showing an application of our method to maximum entropy modeling of high dimensional human motion capture data.

Stochastic gradient optimization is a class of widely used algorithms for training machine learning models. To optimize an objective, it uses the noisy gradient computed from the random data samples instead of the true gradient computed from the entire dataset. However, when the variance of the noisy gradient is large, the algorithm might spend much time bouncing around, leading to slower convergence and worse performance. In this paper, we develop a general approach of using control variate for variance reduction in stochastic gradient. Data statistics such as low-order moments (pre-computed or estimated online) is used to form the control variate.

We consider the problem of predictive monitoring (PM), i.e., predicting at runtime the satisfaction of a desired property from the current system's state. Due to its relevance for runtime safety assurance and online control, PM methods need to be efficient to enable timely interventions against predicted violations, while providing correctness guarantees. We introduce \textit{quantitative predictive monitoring (QPM)}, the first PM method to support stochastic processes and rich specifications given in Signal Temporal Logic (STL). Unlike most of the existing PM techniques that predict whether or not some property $\phi$ is satisfied, QPM provides a quantitative measure of satisfaction by predicting the quantitative (aka robust) STL semantics of $\phi$. QPM derives prediction intervals that are highly efficient to compute and with probabilistic guarantees, in that the intervals cover with arbitrary probability the STL robustness values relative to the stochastic evolution of the system. To do so, we take a machine-learning approach and leverage recent advances in conformal inference for quantile regression, thereby avoiding expensive Monte-Carlo simulations at runtime to estimate the intervals. We also show how our monitors can be combined in a compositional manner to handle composite formulas, without retraining the predictors nor sacrificing the guarantees. We demonstrate the effectiveness and scalability of QPM over a benchmark of four discrete-time stochastic processes with varying degrees of complexity.

We study a class of generalized linear programs (GLP) in a large-scale setting, which includes simple, possibly nonsmooth convex regularizer and simple convex set constraints. By reformulating (GLP) as an equivalent convex-concave min-max problem, we show that the linear structure in the problem can be used to design an efficient, scalable first-order algorithm, to which we give the name \emph{Coordinate Linear Variance Reduction} (\textsc{clvr}; pronounced "clever"). \textsc{clvr} yields improved complexity results for (GLP) that depend on the max row norm of the linear constraint matrix in (GLP) rather than the spectral norm. When the regularization terms and constraints are separable, \textsc{clvr} admits an efficient lazy update strategy that makes its complexity bounds scale with the number of nonzero elements of the linear constraint matrix in (GLP) rather than the matrix dimensions. On the other hand, for the special case of linear programs, by exploiting sharpness, we propose a restart scheme for \textsc{clvr} to obtain empirical linear convergence. Then we show that Distributionally Robust Optimization (DRO) problems with ambiguity sets based on both $f$-divergence and Wasserstein metrics can be reformulated as (GLPs) by introducing sparsely connected auxiliary variables. We complement our theoretical guarantees with numerical experiments that verify our algorithm's practical effectiveness, in terms of wall-clock time and number of data passes.

Spectral Toolkit of Algorithms for Graphs (STAG) is an open-source C++ and Python library of efficient spectral algorithms for graphs. Our objective is to implement advanced graph algorithms developed through algorithmic spectral graph theory, while making it practical to end users. This series of technical reports is to document our progress on STAG, including implementation details, engineering considerations, and the data sets against which our implementation is tested. The report is structured as follows: Section 2 describes the local clustering algorithm, which is the main update in this STAG release. The discussion is at a high level such that domain knowledge beyond basic algorithms is not needed. Section 3 provides a user guide to the essential features of STAG which allow a user to apply local clustering. Section 4 includes experiments and demonstrations of the functionality of STAG. Finally, Section 5 discusses several technical details; these include our choice of implemented algorithms, the default setup of parameters, and other technical choices. We leave these details to the final section, as it's not necessary for the reader to understand this when using STAG.

We introduce an information measure, termed clarity, motivated by information entropy, and show that it has intuitive properties relevant to dynamic coverage control and informative path planning. Clarity defines the quality of the information we have about a variable of interest in an environment on a scale of [0, 1], and has useful properties for control and planning such as: (I) clarity lower bounds the expected estimation error of any estimator, and (II) given noisy measurements, clarity monotonically approaches a level q_infty < 1. We establish a connection between coverage controllers and information theory via clarity, suggesting a coverage model that is physically consistent with how information is acquired. Next, we define the notion of perceivability of an environment under a given robotic (or more generally, sensing and control) system, i.e., whether the system has sufficient sensing and actuation capabilities to gather desired information. We show that perceivability relates to the reachability of an augmented system, and derive the corresponding Hamilton-Jacobi-Bellman equations to determine perceivability. In simulations, we demonstrate how clarity is a useful concept for planning trajectories, how perceivability can be determined using reachability analysis, and how a Control Barrier Function (CBF) based controller can dramatically reduce the computational burden.

In the context of large samples, a small number of individuals might spoil basic statistical indicators like the mean. It is difficult to detect automatically these atypical individuals, and an alternative strategy is using robust approaches. This paper focuses on estimating the geometric median of a random variable, which is a robust indicator of central tendency. In order to deal with large samples of data arriving sequentially, online stochastic Newton algorithms for estimating the geometric median are introduced and we give their rates of convergence. Since estimates of the median and those of the Hessian matrix can be recursively updated, we also determine confidences intervals of the median in any designated direction and perform online statistical tests.

Abstract: Taking the goodness of fit test (Chi test) as an example, this paper attempts to calculate the Bayesian factor BF10 of n-fold Bernoulli test by the Excel software (using JASP software as the evidence). The results showed that in the range of 0.15–0.55 Abstract: The sensitivity of gravitational wave searches is reduced by the presence of non-Gaussian noise in the detector data. These non-Gaussianities often match well with the template waveforms used in matched filter searches, and require signal-consistency tests to distinguish them from astrophysical signals. However, empirically tuning these tests for maximum efficacy is time consuming and limits the complexity of these tests. In this work we demonstrate a framework to use machine-learning techniques to automatically tune signal-consistency tests.