Applied Mathematics seminars

Complex systems can be modeled at various levels of granularity, e.g., we can model a person at the cognitive level, on the neuronal level, or down to the biochemical level. When multiple models represent the same system at different scales, we would like to be able to reason about the causal effects of interventions on each level in such a way that the models remain consistent across levels. In the first part of this talk, I consider which conditions must be fulfilled for two structural equation models (SEMs) to stand in such a causally consistent relation. In the second part of the talk, I present recent work on learning causally consistent SEMs across multiple levels, distinguishing between bottom-up (micro- to macro-level) and top-down (macro- to micro-level) approaches.

Ideas about optimization are at the core of how we approach biological complexity. Quantitative predictions about biological systems have been successfully derived from first principles in the context of efficient coding, metabolic and transport networks, evolution, reinforcement learning, and decision making, by postulating that a system has evolved to optimize some utility function under biophysical constraints. Yet as normative theories become increasingly high-dimensional and optimal solutions stop being unique, it gets progressively hard to judge whether theoretical predictions are consistent with, or "close to", data. I will illustrate these issues using efficient coding applied to simple neuronal models as well as to a complex and realistic biochemical reaction network. As a solution, we developed a statistical framework which smoothly interpolates between ab initio optimality predictions and Bayesian parameter inference from data, while also permitting statistically rigorous tests of optimality hypotheses.

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.

Nassim Nicholas Taleb examines distributions whose behaviour is dominated by extremes and tail events. He classifies these distributions and identifies circumstances in which familiar statistical tools become unreliable, including slow or problematic convergence of sample averages under the law of large numbers. The lecture questions the robustness of commonly used statistical procedures in fat-tailed settings, the reliability of frequency-based forecasting, and the use of past averages as guides to future outcomes. Taleb then develops implications for decision-making and the changes in method needed when extreme observations have disproportionate influence.

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.

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.

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.