Meena Jagadeesan
2019-03-08
Feature hashing and more general projection schemes are commonly used in machine learning to reduce the dimensionality of feature vectors. The goal is to efficiently project a high-dimensional feature vector living in
into a lower-dimensional space , while approximately preserving Euclidean norm. These schemes can be constructed using sparse random projections, for example using a sparse Johnson-Lindenstrauss (JL) transform. In practice, feature vectors often have a low -to- norm ratio, and for this restricted set of vectors, many sparse JL-based schemes can achieve the norm-preserving objective with smaller dimension than is necessary for the scheme on the full space . A line of work introduced by Weinberger et. al (ICML '09) analyzes the sparse JL transform with one nonzero entry per column, which is a standard feature hashing scheme. Recently, Freksen, Kamma, and Larsen (NIPS '18) closed this line of work by proving an essentially tight tradeoff between -to- norm ratio, distortion, failure probability, and dimension for this feature hashing scheme. We study more general projection schemes that are constructed using sparse JL transforms permitted to have more than one (but still a small fraction of) nonzero entries per column. Our main result is an essentially tight tradeoff between -to- norm ratio, distortion, failure probability, and dimension for a general sparsity , that generalizes the result of Freksen et. al. We also connect our result to the sparse JL literature by showing that it implies lower bounds on dimension-sparsity tradeoffs that essentially match upper bounds by Cohen (SODA '16). Moreover, our proof introduces a new perspective on bounding moments of certain random variables, that could be useful in other settings in theoretical computer science.
Erik D. Demaine, John Iacono, Grigorios Koumoutsos, Stefan Langerman
2019-03-08
We revisit self-adjusting external memory tree data structures, which combine the optimal (and practical) worst-case I/O performances of B-trees, while adapting to the online distribution of queries. Our approach is analogous to undergoing efforts in the BST model, where Tango Trees (Demaine et al. 2007) were shown to be
-competitive with the runtime of the best offline binary search tree on every sequence of searches. Here we formalize the B-Tree model as a natural generalization of the BST model. We prove lower bounds for the B-Tree model, and introduce a B-Tree model data structure, the Belga B-tree, that executes any sequence of searches within a factor of the best offline B-tree model algorithm, provided . We also show how to transform any static BST into a static B-tree which is faster by a factor; the transformation is randomized and we show that randomization is necessary to obtain any significant speedup.
Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang
2019-03-08
We resolve the randomized one-way communication complexity of Dynamic Time Warping (DTW) distance. We show that there is an efficient one-way communication protocol using
bits for the problem of computing an -approximation for DTW between strings and of length , and we prove a lower bound of bits for the same problem. Our communication protocol works for strings over an arbitrary metric of polynomial size and aspect ratio, and we optimize the logarithmic factors depending on properties of the underlying metric, such as when the points are low-dimensional integer vectors equipped with various metrics or have bounded doubling dimension. We also consider linear sketches of DTW, showing that such sketches must have size .
André Rijo, Carla Ferreira, Nuno Preguiça
2019-03-08
Um CRDT 'e um tipo de dados que pode ser replicado e modificado concorrentemente sem coordena\c{c}~ao, garantindo-se a converg^encia das r'eplicas atrav'es da resolu\c{c}~ao autom'atica de conflitos. Cada CRDT implementa uma pol'itica espec'ifica para resolver conflitos. Por exemplo, um conjunto CRDT add-wins d'a prioridade ao "add" aquando da execu\c{c}~ao concorrente de um "add" e "rem" do mesmo elemento. Em algumas aplica\c{c}~oes pode ser necess'ario usar diferentes pol'iticas para diferentes execu\c{c}~oes de uma opera\c{c}~ao -- por exemplo, uma aplica\c{c}~ao que utilize um conjunto CRDT add-wins pode querer que alguns "removes" ganhem sobre "adds" concorrentes. Neste artigo 'e apresentado e avaliado o desenho dum conjunto CRDT que implementa as sem^anticas referidas. --- Conflict-Free Replicated Data Types (CRDTs) allow objects to be replicated and concurrently modified without coordination. CRDTs solve conflicts automatically and provide eventual consistency. Typically each CRDT uses a specific policy for solving conflicts. For example, in an add-wins set CRDT, when an element is concurrently add and removed in different replicas, priority is given to add, i.e., the element stays in the set. Unfortunately, this may be inadequate for some applications - it may be desired to overrule the default policy for some operation executions. For example, an application using an add-wins set may want some removes to win over concurrent adds. This paper present the design of a set CRDT that implements such semantics.
Dorian Gorgan, Ovidiu Vaduvescu, Teodor Stefanut, Victor Bacu, Adrian Sabou, Denisa Copandean Balazs, Constantin Nandra, Costin Boldea, Afrodita Boldea, Marian Predatu, Viktoria Pinter, Adrian Stanica
2019-03-08
The survey of the nearby space and continuous monitoring of the Near Earth Objects (NEOs) and especially Near Earth Asteroids (NEAs) are essential for the future of our planet and should represent a priority for our solar system research and nearby space exploration. More computing power and sophisticated digital tracking algorithms are needed to cope with the larger astronomy imaging cameras dedicated for survey telescopes. The paper presents the NEARBY platform that aims to experiment new algorithms for automatic image reduction, detection and validation of moving objects in astronomical surveys, specifically NEAs. The NEARBY platform has been developed and experimented through a collaborative research work between the Technical University of Cluj-Napoca (UTCN) and the University of Craiova, Romania, using observing infrastructure of the Instituto de Astrofisica de Canarias (IAC) and Isaac Newton Group (ING), La Palma, Spain. The NEARBY platform has been developed and deployed on the UTCN's cloud infrastructure and the acquired images are processed remotely by the astronomers who transfer it from ING through the web interface of the NEARBY platform. The paper analyzes and highlights the main aspects of the NEARBY platform development, and the results and conclusions on the EURONEAR surveys.
Zeke Wang, Kaan Kara, Hantian Zhang, Gustavo Alonso, Onur Mutlu, Ce Zhang
2019-03-08
Learning from the data stored in a database is an important function increasingly available in relational engines. Methods using lower precision input data are of special interest given their overall higher efficiency but, in databases, these methods have a hidden cost: the quantization of the real value into a smaller number is an expensive step. To address the issue, in this paper we present MLWeaving, a data structure and hardware acceleration technique intended to speed up learning of generalized linear models in databases. ML-Weaving provides a compact, in-memory representation enabling the retrieval of data at any level of precision. MLWeaving also takes advantage of the increasing availability of FPGA-based accelerators to provide a highly efficient implementation of stochastic gradient descent. The solution adopted in MLWeaving is more efficient than existing designs in terms of space (since it can process any resolution on the same design) and resources (via the use of bit-serial multipliers). MLWeaving also enables the runtime tuning of precision, instead of a fixed precision level during the training. We illustrate this using a simple, dynamic precision schedule. Experimental results show MLWeaving achieves up to16 performance improvement over low-precision CPU implementations of first-order methods.
Daniel Tenbrinck, Fjedor Gaede, Martin Burger
2019-03-07
In recent years new application areas have emerged in which one aims to capture the geometry of objects by means of three-dimensional point clouds. Often the obtained data consist of a dense sampling of the object's surface, containing many redundant 3D points. These unnecessary data samples lead to high computational effort in subsequent processing steps. Thus, point cloud sparsification or compression is often applied as a preprocessing step. The two standard methods to compress dense 3D point clouds are random subsampling and approximation schemes based on hierarchical tree structures, e.g., octree representations. However, both approaches give little flexibility for adjusting point cloud compression based on a-priori knowledge on the geometry of the scanned object. Furthermore, these methods lead to suboptimal approximations if the 3D point cloud data is prone to noise. In this paper we propose a variational method defined on finite weighted graphs, which allows to sparsify a given 3D point cloud while giving the flexibility to control the appearance of the resulting approximation based on the chosen regularization functional. The main contribution in this paper is a novel coarse-to-fine optimization scheme for point cloud sparsification, inspired by the efficiency of the recently proposed Cut Pursuit algorithm for total variation denoising. This strategy gives a substantial speed up in computing sparse point clouds compared to a direct application on all points as done in previous works and renders variational methods now applicable for this task. We compare different settings for our point cloud sparsification method both on unperturbed as well as noisy 3D point cloud data.
D. V. Gribanov, D. S. Malyshev, P. M. Pardalos, S. I. Veselov
2017-12-18
In this paper, we present FPT-algorithms for special cases of the shortest lattice vector, integer linear programming, and simplex width computation problems, when matrices included in the problems' formulations are near square. The parameter is the maximum absolute value of rank minors of the corresponding matrices. Additionally, we present FPT-algorithms with respect to the same parameter for the problems, when the matrices have no singular rank sub-matrices.
Holden Lee, Oren Mangoubi, Nisheeth K. Vishnoi
2019-02-21
Given a sequence of convex functions
, we study the problem of sampling from the Gibbs distribution for each epoch in an online manner. This problem occurs in applications to machine learning, Bayesian statistics, and optimization where one constantly acquires new data, and must continuously update the distribution. Our main result is an algorithm that generates independent samples from a distribution that is a fixed TV-distance from for every and, under mild assumptions on the functions, makes poly gradient evaluations per epoch. All previous results for this problem imply a bound on the number of gradient or function evaluations which is at least linear in . While we assume the functions have bounded second moment, we do not assume strong convexity. In particular, we show that our assumptions hold for online Bayesian logistic regression, when the data satisfy natural regularity properties. In simulations, our algorithm achieves accuracy comparable to that of a Markov chain specialized to logistic regression. Our main result also implies the first algorithm to sample from a -dimensional log-concave distribution where the 's are not assumed to be strongly convex and the total number of gradient evaluations is roughly as opposed to implied by prior works. Key to our algorithm is a novel stochastic gradient Langevin dynamics Markov chain that has a carefully designed variance reduction step built-in with fixed constant batch size. Technically, lack of strong convexity is a significant barrier to the analysis, and, here, our main contribution is a martingale exit time argument showing the chain is constrained to a ball of radius roughly poly for the duration of the algorithm.
Nikhil Bansal, Anupam Gupta
2017-12-13
This note discusses proofs for convergence of first-order methods based on simple potential-function arguments. We cover methods like gradient descent (for both smooth and non-smooth settings), mirror descent, and some accelerated variants.
