Metric Representations: Algorithms and Geometry
Talkat Algorithmic Advances for Statistical Inference with Combinatorial Structure · 2021-10-11..10-15·
summary
Shows that corrupted pairwise distances (e.g., 5% bad edges wrecking an Isomap embedding) are repairable by optimizing over the metric polytope; introduces project-and-forget — an iterative solver that uses Bregman projection plus a shortest-path separation oracle — and proves global convergence with asymptotic exponential decay under mild assumptions. Implements weighted correlation clustering and metric nearness at scale, outperforming prior solvers (handles ~11,000-node dense and up to 130,000 nodes sparse graphs versus ~4,000 previously) and produces a tree-based representation (TreeRep) for downstream hyperbolic embeddings.
AI-written summary · about
chapters (19)
- 0:00Intro
- 0:21Metric representations: Algorithms and Geometry
- 1:48Distorted geometry or broken metrics
- 2:42Metric failures
- 5:55Motivation
- 13:02Representative problems in metric learning
- 15:07Definitions
- 22:50Specific problem formulations, contd
- 24:30General problem formulation: metric constrained problems
- 26:06Optimization techniques: existing methods
- 28:38Project and Forget
- 32:38Metric violations: Separation oracle
- 33:43Metric violations: shortest path
- 34:39Bregman projection
- 34:55Theoretical results: Summary Theorem
- 35:41Experiments: Weighted correlation clustering (dense graphs)
- 42:03Experiments: Metric nearness
- 45:22New different directions: trees and hyperbolic embeddings
- 46:38Tree embedding workflow
related talks
11mGeometric Methods for Machine Learning and Optimization
43mOn Using Graph Distances to Estimate Euclidean and Related Distances
40mTopological Techniques for Unsupervised Learning
01h 11m(Hidden) Symmetries of Computational Problems (continued)
01h 03mMathematical connections of some local-to-global expressivity results over geometric graphs and...
15mGraphical Optimal Transport and Its Applications
39mLocalization and Nonmetric Multidimensional Scaling via Paired Comparisons
37mComputing Probabilistic Bisimilarity Distances via Policy Iteration