Modern large-scale ML applications require stochastic optimization algorithms to be implemented on distributed computational architectures. A key bottleneck is the communication overhead for exchanging information such as stochastic gradients among different workers. In this paper, to reduce the communication cost, we propose a convex optimization formulation to minimize the coding length of stochastic gradients.
The authors suggest a general oracle-based framework that captures different parallel stochastic optimization settings described by a dependency graph, and derive generic lower bounds in terms of this graph, as well as lower bounds for several specific parallel optimization settings. They highlight gaps between lower and upper bounds on the oracle complexity, and cases where the “natural” algorithms are not known to be optimal.
Sparse Principal Component Analysis (SPCA) and Sparse Linear Regression (SLR) have a wide range of applications and have attracted attention as canonical examples of statistical problems in high dimension. A variety of algorithms have been proposed for both SPCA and SLR, but an explicit connection between the two had not been made. This paper shows how to efficiently transform a black-box solver for SLR into an algorithm for SPCA.
The MiSoSouP algorithm provides a novel way to identify interesting subgroups in a dataset accurately and efficiently.
MiSoSouP is a suite of algorithms for extracting high-quality approximations of the most interesting subgroups, according to different interestingness measures, from a random sample of a transactional dataset.
In the machine learning research community, it is generally believed that there is a tension between memorization and generalization. This paper examines the extent to which this tension exists, by exploring whether it is possible to generalize by memorizing alone.
A senior Two Sigma researcher provides an overview of some of the most interesting Deep Learning research from ICML 2017.
A group of Two Sigma statisticians highlight a selection of interesting talks and presentations from the 2017 Joint Statistical Meeting.
Two Sigma Co-founder and Co-chairman David Siegel offers his views on these topics and more at Bloomberg’s Sooner Than You Think conference.
The authors present TRIÈST, a suite of one-pass streaming algorithms to compute unbiased, low-variance, high-quality approximations of the global and local number of triangles in a fully-dynamic graph represented as an adversarial stream of edge insertions and deletions.