Consider a stream of$d$-dimensional rows (points in$\mathbb {R}^{d}$) arriving sequentially. An$\epsilon$-coreset is a positively weighted subset that approximates their sum of squared distances to any linear subspace of$\mathbb {R}^{d}$, up to a$1 \pm \epsilon$factor. Unlike other data summarizations, such a coreset: (1) can be used to minimize faster any optimization function that uses this sum, such as regularized or constrained regression, (2) preserves input sparsity; (3) easily interpretable; (4) avoids numerical errors; (5) applies to problems with constraints on the input, such as subspaces that are spanned by few input points. Our main result is the first algorithm that returns such an$\epsilon$-coreset using finite and constant memory during the streaming, i.e., independent of$n$, the number of rows seen so far. The coreset consists of$O(d \log ^{2}\;d / \epsilon ^{2})$weighted rows, which is nearly optimal according to existing lower bounds of$\Omega (d / \epsilon ^{2})$. We support our findings with experiments on the Wikipedia dataset benchmarked against state-of-the-art algorithms.

A coreset for a set of points is a small subset of weighted points that approximately preserves important properties of the original set. Specifically, if $P$ is a set of points, $Q$ is a set of queries, and $f:P\times Q\to\mathbb{R}$ is a cost function, then a set $S\subseteq P$ with weights $w:P\to[0,\infty)$ is an $\epsilon$-coreset for some parameter $\epsilon>0$ if $\sum_{s\in S}w(s)f(s,q)$ is a $(1+\epsilon)$ multiplicative approximation to $\sum_{p\in P}f(p,q)$ for all $q\in Q$. Coresets are used to solve fundamental problems in machine learning under various big data models of computation. Many of the suggested coresets in the recent decade used, or could have used a general framework for constructing coresets whose size depends quadratically on the total sensitivity $t$. In this paper we improve this bound from $O(t^2)$ to $O(t\log t)$. Thus our results imply more space efficient solutions to a number of problems, including projective clustering, $k$-line clustering, and subspace approximation. The main technical result is a generic reduction to the sample complexity of learning a class of functions with bounded VC dimension. We show that obtaining an $(\nu,\alpha)$-sample for this class of functions with appropriate parameters $\nu$ and $\alpha$ suffices to achieve space efficient $\epsilon$-coresets. Our result implies more efficient coreset constructions for a number of interesting problems in machine learning; we show applications to $k$-median/$k$-means, $k$-line clustering, $j$-subspace approximation, and the integer $(j,k)$-projective clustering problem.

An ε-coreset to the dimensionality reduction problem for a (possibly very large) matrix A ∈ Rn x d is a small scaled subset of its n rows that approximates their sum of squared distances to every affine k-dimensional subspace of Rd, up to a factor of 1±ε. Such a coreset is useful for boosting the running time of computing a low-rank approximation (k-SVD/k-PCA) while using small memory. Coresets are also useful for handling streaming, dynamic and distributed data in parallel. With high probability, non-uniform sampling based on the so called leverage score or sensitivity of each row in A yields a coreset. The size of the (sampled) coreset is then near-linear in the total sum of these sensitivity bounds. We provide algorithms that compute provably tight bounds for the sensitivity of each input row. It is based on two ingredients: (i) iterative algorithm that computes the exact sensitivity of each row up to arbitrary small precision for (non-affine) k-subspaces, and (ii) a general reduction for computing a coreset for affine subspaces, given a coreset for (non-affine) subspaces in Rd. Experimental results on real-world datasets, including the English Wikipedia documents-term matrix, show that our bounds provide significantly smaller and data-dependent coresets also in practice. Full open source code is also provided.

Long-term, repeated measurements of individual synaptic properties have revealed that synapses can undergo significant directed and spontaneous changes over time scales of minutes to weeks. These changes are presumably driven by a large number of activity-dependent and independent molecular processes, yet how these processes integrate to determine the totality of synaptic size remains unknown. Here we propose, as an alternative to detailed, mechanistic descriptions, a statistical approach to synaptic size dynamics. The basic premise of this approach is that the integrated outcome of the myriad of processes that drive synaptic size dynamics are effectively described as a combination of multiplicative and additive processes, both of which are stochastic and taken from distributions parametrically affected by physiological signals. We show that this seemingly simple model, known in probability theory as the Kesten process, can generate rich dynamics which are qualitatively similar to the dynamics of individual glutamatergic synapses recorded in long-term time-lapse experiments in ex-vivo cortical networks. Moreover, we show that this stochastic model, which is insensitive to many of its underlying details, quantitatively captures the distributions of synaptic sizes measured in these experiments, the long-term stability of such distributions and their scaling in response to pharmacological manipulations. Finally, we show that the average kinetics of new postsynaptic density formation measured in such experiments is also faithfully captured by the same model. The model thus provides a useful framework for characterizing synapse size dynamics at steady state, during initial formation of such steady states, and during their convergence to new steady states following perturbations. These findings show the strength of a simple low dimensional statistical model to quantitatively describe synapse size dynamics as the integrated result of many underlying complex processes.