Reading Group
Home
Topics
Previous
Schedule
Summer 2017
Fall 2016
Summer 2016

Algorithms, Geometry and Learning

Older Topics, Stanford University

  • A list of topics that were proposed during previous quarters.

Approximation Algorithms using Tree Embeddings

Many optimization problems can be solved efficiently on trees. A central algorithmic paradigm in approximation algorithms is to map the problem on a tree, solve it, and then quantify the loss that the tree approximation induces. Two general such problems are the 0-extension problem and its generalization, Metric Labeling problem.

Probabilistic Tree Decompositions

Starting with the seminal work of Bartal STOC ’98, it is now known that any finite metric space can be approximated by a distribution on trees such that all distances are preserved . Here we will review the technique and some recent improvements. This technique is a basic building block in metric embedings.

Exponential Clocks Techniques

Metric Embeddings and Negative Type Metrics

We will review a set of techniques that are important in obtaining metric embeddings of general metric spaces into Euclidean space: the Single Scale embedding and the (inter-scale) Gluing lemma. We then are going to consider a special class of metric spaces those of negative type, i.e. metrics (X, d) suchs that (X,sqrt{d}) is an Euclidean metric. These spaces arise in the context of approximation algorithms through SDP relaxations, the prime example of which is Sparsest Cut problem. We present a structural theorem for these spaces (Core Theorem) first discovered by Arora, Rao, Vazirani (ARV). The presentation will be based on Distance Scales, Embeddings, and Metrics of Negative Type, by James R. Lee, 2006.

Generalized Sparsest Cut and Negative Type Metrics

The previous approach of embedding negative type spaces was based on three ingredients, the Single Scale Embedding, the (inter-scale) Gluing Lemma and the ARV Core theorem. Only the last of which used the special properties of negative type spaces. Arora, Lee and Naor devised an additional technique (intra-scale) Gluing Lemma that allowed them to improve on the previous results and provide the best known approximation ration for Generalized Sparsest cut.

epsilon-nets for finite metric spaces with applications.

In many applications, due to computational considerations we would like to have a concise representation of a metric space, such that all distances are approximately preserved. Such representations are typically called epsilon-nets. Here, we review algorithms that take a finite metric space and construct such nets. We will focus on general metric spaces of bounded doubling dimension and on doubling metrics induced by graphs. We also will discuss applications of such constructions in algorithm design.

Lipschitz Extensions, Classification and SVM's.

Classification in Metric Spaces

Average Distortion Embeddings and Quantitative Trade-offs

Typically, in metric embeddings we concern ourselves with bounding the maximum distortion that we incure when we embed a metric space in L_{p} (usually for p=2). In this paper, a number of novel techniques are introduced: (hierarchically) uniformly padded partitions, partial and scaling embeddings, that allow one not only to get a bound on the maximum distortion but also to achieve constant average distortion. Applications in approximations algorithms and network embeddings (distance labeling schemes) are given.

Random Feature Maps

Different characterizations (Bochners, Schoenbecks) for family of (Shift Invariant, Dot Product kernels) are used to define embeddings (random feature maps) of the Hilbert space such that dot products are preserved.

Sketching (Polynomial) Kernels

MinWise Hashing and Min-max Kernel

Local Embeddings

In modern data analysis often practicioners care about the local structure of the metric space (e.g. k-nearest neighbors, manifolds) and implicitly assume that the euclidean space information about long distances is inaccurate. Here we review two works that get improved dimension/distortion bounds if we only care about preserving the local distances.

Ordinal Embeddings

Locality Sensitive Filtering and Asymmetric LSH

Ultrametrics and Majorizing Measures

We have already seen how trees can be used to approximate metric spaces. In fact a more general statement is true, every compact metric space contains a large ultrametric skeleton. The flagship application of this theorem is that one can easily derive a deep theorem due to Talagrand and Fernique, Majorizing Measure Theorem.

Chaining Arguments and their Applications.

Spanners and their Applications

PAC Learning

Learning Halfspaces

Theory for Neural Networks

Nearest-Neighbors Estimators

Tree Based Estimators

Sample Compression Schemes

Local Dimensionality Reduction

Dimensionality Reduction for Classification

Lipschitz Extensions