Machine Learning seminars

There has been a surge of publications on using machine learning (ML) on experimental data from physical systems: social, biological, statistical, and quantum. However, can these methods discover fundamentally new physics? It can be that their biggest impact is in better data preprocessing, while inferring new physics is unrealistic without specifically adapting the learning machine to find what we are looking for — that is, without the “intuition” — and hence without having a good a priori guess about what we will find. Is machine learning a useful tool for physics discovery? Which minimal knowledge should we endow the machines with to make them useful in such tasks? How do we do this? Eight speakers below will anchor the workshop, exploring these questions in contexts of diverse systems (from quantum to biological), and from general theoretical advances to specific applications. Each speaker will deliver a 10 min talk with another 10 minutes set aside for moderated questions/discussion. We expect the talks to be broad, bold, and provocative, discussing where the field is heading, and what is needed to get us there.

Information is represented in the brain by the coordinated activity of populations of neurons. Recent large-scale neural recording methods in combination with machine learning algorithms are helping understand how sensory processing and cognition emerge from neural population activity. This talk will explore the most popular machine learning methods used to gather meaningful low-dimensional representations from higher-dimensional neural recordings. To illustrate the potential of these approaches, Pedro will present his research in which chemical information is decoded from the olfactory system of the mouse for technological applications. Pedro and co-researchers have successfully extracted odor identity and concentration from olfactory receptor neuron low-dimensional activity trajectories. They have further developed a novel method to identify a shared latent space that allowed decoding of odor information across animals.

Finding similar item pairs is a core task in recommendation systems. It can be expressed as finding large inner products in a collection of vectors, or large entries in a matrix product. This talk describes how randomized sampling ideas became a distributed algorithm used in Twitter’s production recommendation system. Existing approaches struggled with industrial-scale inputs containing hundreds of billions of nonzero entries. The algorithm combines low-dimensional projections, called hashes, with path-sampling techniques, called wedges. The presentation explains the mathematical ideas behind this combination and its application at production scale. Joint work with Aneesh Sharma of Twitter and Ashish Goel of Stanford.

Theory for high-dimensional nearest-neighbor search often assumes a known search radius, a specified approximation ratio, and a request for one nearby point. Practical applications instead ask for the exact k nearest points without knowing the relevant radius; an appropriate approximation parameter also depends on the data distribution. Existing reductions between these formulations introduce polylogarithmic time or space overhead that can make them unattractive in practice. This talk presents simple, more efficient reductions that solve k-nearest-neighbor search using locality-sensitive hashing and address this gap between theoretical guarantees and practical queries. Joint work with Tobias Christiani and Mikkel Thorup.

This talk establishes a general reduction from nonlinear spectral gaps of metric spaces to data-dependent space partitions in the form of locality-sensitive hashing. The reduction yields an approach to high-dimensional approximate near-neighbor search and a data structure for any d-dimensional norm whose query algorithm makes a sublinear number of probes. Its approximation factor is O(log d), improving on the square-root-of-d factor available from the generic approach based on John’s ellipsoid. The presentation connects spectral properties, geometric partitions, and efficient approximate search. Joint work with Assaf Naor, Aleksandar Nikolov, Ilya Razenshteyn, and Erik Waingarten.

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.