Computer Science seminars

Fast computation often trades statistical accuracy for speed. In nearest-neighbor prediction, achieving optimal accuracy generally requires the number of neighbors to grow as a root of the sample size, creating a corresponding computational burden even with fast search. This talk shows how bias or variance corrections after data quantization or subsampling, together with black-box fast-search techniques, can retain accuracy while reducing prediction-time computation to O(log n). The analysis explains how much quantization or subsampling is compatible with optimal accuracy. Extensive experiments on large datasets from several domains test these theoretical insights. The talk draws on work with N. Verma and L. Xue.

Locality-sensitive hashing is widely used for high-dimensional nearest-neighbor search. This talk develops another view of hashing as a biased sampling method for density-estimation queries. Given a point set and a query, one may estimate kernel density by summing distance-dependent influence functions, or count points within a chosen radius. A linear scan is costly for large datasets and many queries. The presentation surveys recent methods that preprocess the data and use locality-sensitive hashing to construct unbiased estimators for these problems and their extensions. It covers joint work with Arturs Backurs, Piotr Indyk, Vishnu Natchu, Paris Syminelakis, and Xian (Carrie) Wu.

At extreme scale, even conventional sampling and projection methods can become too expensive. This talk treats locality-sensitive hashing as an amortized constant-time adaptive sampler, connecting probabilistic hash tables with efficient unbiased statistical estimators. A few hash lookups can support adaptive estimation at a cost close to uniform sampling. Applications include partition-function estimation for large natural-language models such as word2vec, adaptive gradient estimation for stochastic gradient descent, and sublinear deep learning with very large parameter spaces. The talk also considers memory reduction through a hashing method related to count-min sketches. An example trains a classifier with 100,000 classes and 400,000 features on a single Titan X while using at most five percent of the memory needed to store all weights; a conventional logistic-regression model for that dataset requires 320 GB.

This talk examines randomized sampling methods for approximating positive semidefinite matrices. Fast leverage-score approximation combined with the Nystrom method yields provably accurate, linear-time algorithms for kernel ridge regression and kernel principal-component analysis, avoiding the usual quadratic-time cost. Related sampling techniques give relative-error low-rank approximations of positive semidefinite matrices in sublinear time without assumptions about incoherence or condition number. The results illustrate how randomized algorithms can exploit positive semidefinite structure beyond the capabilities of traditional methods. The talk concludes with open questions, particularly about oblivious sketches of kernel matrices.

This two-part tutorial considers the problem of indexing points in a metric space so that a query can efficiently retrieve an approximately closest stored point. It surveys established and newer data structures for high-dimensional nearest-neighbor search. The first part examines search under the l1 and Euclidean l2 distances, including locality-sensitive hashing and data-dependent hashing. The second part turns to non-Euclidean geometries and recent approaches such as spectral partitioning for metric spaces.

Building on the preceding linear-algebra tutorials, this lecture presents two further approaches to matrix sketching: leverage-score sampling and the Subsampled Randomized Hadamard Transform. It examines how these methods produce effective compressed matrix representations for a variety of applications.

This tutorial surveys nearly optimal algorithms for regression, low-rank approximation and related numerical problems. The central approach is sketch and solve: compress a large problem into a smaller representation, then apply an algorithm to that reduced problem. These techniques provide fast methods for fundamental machine-learning and numerical-linear-algebra tasks, with running times proportional to the number of nonzero entries in the input.

Worst-case bounds described as optimal can remain loose for the data encountered in practice. This talk develops distribution-specific analyses for local, nonparametric methods, focusing on nearest neighbors. The statistical results give closely matching upper and lower bounds for classification convergence for each data distribution, characterize metric measure spaces supporting universal consistency, and motivate a smoothness concept adapted to nearest-neighbor methods. The algorithmic results characterize the performance of tree-based nearest-neighbor search through the configuration of the data, with specializations to common forms of structure. The talk concludes with open statistical and algorithmic questions.

This talk develops optimal hashing methods for approximate nearest-neighbor search by reducing worst-case high-dimensional point sets to random instances. The approach connects the structure of arbitrary datasets with hashing constructions designed for random data. The work is joint with Ilya Razenshteyn.

Maximum inner-product search ranks candidate vectors by their unnormalized dot product with a query. This similarity creates difficulties for conventional locality-sensitive hashing. The talk introduces an asymmetric hashing framework in which queries and stored vectors undergo different transformations, turning approximate MIPS into a standard approximate nearest-neighbor problem. An explicit construction provides provably sublinear search and a simple implementation. Experiments on recommendation tasks using Netflix and MovieLens data compare the method with sign random projection and p-stable hashing for Euclidean distance, demonstrating substantial computational savings.

Spectral methods for high-dimensional nearest-neighbor search can perform well in practice even when random projections appear preferable under worst-case theory. This talk studies that difference in a semi-random model: points lie in an unknown low-dimensional subspace and are then perturbed by Gaussian noise in the full ambient space. The algorithms repeatedly compute a leading principal component or subspace and achieve query times polynomial in the ambient dimension and logarithm of the number of points over substantial parameter ranges. They can remain effective when noise is much larger than the distances among the original points. The work is joint with Amirali Abdullah, Ravi Kannan and Robi Krauthgamer.

The success of deep neural networks raises questions about the scalability of kernel methods and the roles of large datasets, depth and training algorithms. This talk examines techniques that make kernel learning practical for large datasets in both scalar and multivariate prediction. The methods combine randomized data embeddings, Quasi-Monte Carlo acceleration, distributed convex optimization and input-output kernel learning. Experiments on speech-recognition and computer-vision datasets compare randomized kernel methods with deep neural networks and report essentially matching performance. The talk explores how randomized kernel constructions can resemble neural-network architectures, and how invariant kernel learning and matrix-valued kernels might support deeper architectures. It discusses research results and connections between these approaches.

Aram Harrow connects the Unique Games conjecture, especially small-set expansion, with the quantum separability problem. The Lasserre hierarchy used for Unique Games and the k-extendible relaxation of quantum separability turn out to be closely equivalent algorithmic approaches. The talk examines how quantum-information conjectures could yield quasipolynomial algorithms or hardness results for Unique Games, and discusses promising research directions. It introduces the necessary quantum mechanics, Unique Games, and hierarchy background rather than presupposing it. The presentation draws partly on the papers arXiv:1205.4484 and arXiv:1210.6367.

Randomization offers an alternative approach to large matrix computations arising in scientific data analysis. This talk explains how randomized algorithms approximate matrix multiplication and singular-value decomposition, solve least-squares problems and linear systems, and support data-analysis applications. The accompanying presentation develops matrix sketches through row and column sampling, compares length-squared sampling with leverage-score sampling, and describes their use in low-rank approximation and matrix factorizations. It also explains how leverage scores can be approximated efficiently and how sampling guarantees support least-squares and feature-selection procedures.