Efficient Regression in Metric Spaces via Approximate Lipschitz Extension

We present a framework for performing efficient regression in general metric spaces. Roughly speaking, our regressor predicts the value at a new point by computing an approximate Lipschitz extension— the smoothest function consistent with the observed data— after performing structural risk minimization to avoid overfitting. We obtain finite-sample risk bounds with minimal structural and noise assumptions, and a natural runtime-precision tradeoff. The offline (learning) and online (prediction) stages can be solved by convex programming, but this naive approach has runtime complexity $O(n^{3})$ , which is prohibitive for large data sets. We design instead a regression algorithm whose speed and generalization performance depend on the intrinsic dimension of the data, to which the algorithm adapts. While our main innovation is algorithmic, the statistical results may also be of independent interest.

• Publication year

  2011

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2011-11-18

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TIT.2017.2713820arXiv 1111.4470
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Foundations of Machine Learning

  2021influential reference
• A (1+ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs

  2015cited by this paper
• Algorithms for Lipschitz Learning on Graphs

  2015cited by this paper
• Maximum Margin Multiclass Nearest Neighbors

  2014cited by this paper
• Understanding Machine Learning - From Theory to Algorithms

  2014cited by this paper
• A Bayes consistent 1-NN classifier

  2014cited by this paper
• Empirical Entropy, Minimax Regret and Minimax Risk

  2013cited by this paper
• From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics

  2013cited by this paper
• Lx = b

  2013cited by this paper
• Adaptive metric dimensionality reduction

  2013influential reference
• Efficient Classification for Metric Data

  2013influential reference
• Concentration in unbounded metric spaces and algorithmic stability

  2013cited by this paper
• A tree-based regressor that adapts to intrinsic dimension

  2012cited by this paper
• Optimal euclidean spanners: really short, thin and lanky

  2012cited by this paper
• Proximity Algorithms for Nearly-Doubling Spaces

  2010influential reference
• Fast, smooth and adaptive regression in metric spaces

  2009cited by this paper
• Approximating Markov Processes by Averaging

  2009cited by this paper
• Rodeo: Sparse, greedy nonparametric regression

  2008cited by this paper
• An Optimal Dynamic Spanner for Doubling Metric Spaces

  2008influential reference
• Cover trees for nearest neighbor

  2006cited by this paper
• Sparse solutions for linear prediction problems

  2006cited by this paper
• Searching dynamic point sets in spaces with bounded doubling dimension

  2006cited by this paper
• All of Nonparametric Statistics (Springer Texts in Statistics)

  2006cited by this paper
• Theory of classification : a survey of some recent advances

  2005cited by this paper
• Nearest-Neighbor Searching and Metric Space Dimensions

  2005cited by this paper
• On hierarchical routing in doubling metrics

  2005cited by this paper
• Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations

  2005cited by this paper
• All of Nonparametric Statistics

  2005cited by this paper
• Navigating nets: simple algorithms for proximity search

  2004cited by this paper
• Triangulation and embedding using small sets of beacons

  2004cited by this paper
• Distance-Based Classification with Lipschitz Functions

  2004cited by this paper
• Fast construction of nets in low dimensional metrics, and their applications

  2004cited by this paper
• THEORY OF CLASSIFICATION: A SURVEY OF RECENT ADVANCES

  2004cited by this paper
• Bypassing the embedding: algorithms for low dimensional metrics

  2004cited by this paper
• Learning Over Compact Metric Spaces

  2004cited by this paper
• Generalization Error Bounds for Bayesian Mixture Algorithms

  2003cited by this paper
• Introduction à l'estimation non-paramétrique

  2003cited by this paper
• Rademacher and Gaussian Complexities: Risk Bounds and Structural Results

  2003cited by this paper
• Plongements lipschitziens dans Rn

  2003cited by this paper
• Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions

  2003cited by this paper
• Biased Skip Lists

  2002cited by this paper
• A Distribution-Free Theory of Nonparametric Regression

  2002cited by this paper
• A Distribution-Free Theory of Nonparametric Regression (Springer Series in Statistics)

  2002cited by this paper
• Empirical margin distributions and bounding the generalization error of combined classifiers

  2002cited by this paper
• Sequential and parallel algorithms for mixed packing and covering

  2001cited by this paper
• The Nature of Statistical Learning Theory

  2000cited by this paper
• Classification and Regression Trees

  2000cited by this paper
• Generalization Performance of Support Vector Machines and Other Pattern Classifiers

  1999cited by this paper
• Structural Risk Minimization Over Data-Dependent Hierarchies

  1998cited by this paper
• Nearest Neighbor Queries in Metric Spaces

  1997cited by this paper
• A Probabilistic Theory of Pattern Recognition

  1996cited by this paper
• The Nature of Statistical Learning

  1995cited by this paper
• Nonparametric estimation via empirical risk minimization

  1995cited by this paper
• On the Strong Universal Consistency of Nearest Neighbor Regression Function Estimates

  1994cited by this paper
• Applied Nonparametric Regression

  1994cited by this paper
• Scale-sensitive dimensions, uniform convergence, and learnability

  1993influential reference
• Nonparametric Estimation of Probability Densities and Regression Curves

  1988cited by this paper
• A course on empirical processes

  1984cited by this paper
• Nonparametric functional estimation

  1983cited by this paper
• Plongements lipschitziens dans ${\bbfR}\sp n$

  1983cited by this paper
• On Observing Nondeterminism and Concurrency

  1980cited by this paper
• ON CONVERGENCE OF STOCHASTIC PROCESSES

  1962cited by this paper
• Entropy and "-capacity of sets in func-tional spaces

  1961cited by this paper
• Analytic Extensions of Differentiable Functions Defined in Closed Sets

  1934cited by this paper
• Extension of range of functions

  1934cited by this paper
• Journal of Graph Algorithms and Applications Low-distortion Embeddings of Trees

  year unknowncited by this paper

• Light Spanners with Small Hop-Diameter

  2025cites this paper
• A Tight Lower Bound for Doubling Spanners

  2025cites this paper
• Information preservation with wasserstein autoencoders: generation consistency and adversarial robustness

  2025cites this paper
• The Complexity of Geodesic Spanners using Steiner Points

  2024cites this paper
• Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers

  2024cites this paper
• On Bits and Bandits: Quantifying the Regret-Information Trade-off

  2024cites this paper
• Consistency of Neural Causal Partial Identification

  2024cites this paper
• On the Expressivity and Sample Complexity of Node-Individualized Graph Neural Networks

  2024influential citation
• Generalization bounds for neural ordinary differential equations and deep residual networks

  2023cites this paper
• Efficient Agnostic Learning with Average Smoothness

  2023cites this paper
• S AMPLE C OMPLEXITY OF P ROBABILITY D IVERGENCES UNDER G ROUP S YMMETRY

  2023cites this paper
• Regret Bounds for Log-Loss via Bayesian Algorithms

  2023cites this paper
• Statistical Guarantees of Group-Invariant GANs

  2023cites this paper
• Extension of semi-Lipschitz maps on non-subadditive quasi-metric spaces: new tools for Artificial Intelligence

  2023cites this paper
• Near-optimal learning with average Hölder smoothness

  2023cites this paper
• Sample Complexity of Probability Divergences under Group Symmetry

  2023cites this paper
• Linear Mean-Field Games with Discounted Cost

  2023cites this paper
• Online Spanners in Metric Spaces

  2022cites this paper
• Instance-Dependent Generalization Bounds via Optimal Transport

  2022cites this paper
• Learning with metric losses

  2022cites this paper
• Low Treewidth Embeddings of Planar and Minor-Free Metrics

  2022cites this paper
• Euclidean Steiner Spanners: Light and Sparse

  2022cites this paper
• Supplementary Material for “Non-Asymptotic Error Bounds for Bidirectional GANs”

  2022influential citation
• Metric-valued regression

  2022cites this paper
• Greedy Spanners in Euclidean Spaces Admit Sublinear Separators

  2021cites this paper
• Clan embeddings into trees, and low treewidth graphs

  2021cites this paper
• 1 4 M ay 2 01 5 A light metric spanner

  2021cites this paper
• Two-Sided Kirszbraun Theorem

  2021cites this paper
• Hop-Constrained Metric Embeddings and their Applications

  2021cites this paper
• Online Euclidean Spanners

  2021cites this paper
• Reliable Estimation of KL Divergence using a Discriminator in Reproducing Kernel Hilbert Space

  2021cites this paper
• Non-Asymptotic Error Bounds for Bidirectional GANs

  2021influential citation
• Functions with average smoothness: structure, algorithms, and learning

  2020cites this paper
• Regret Bounds for Kernel-Based Reinforcement Learning

  2020influential citation
• Kernel-Based Reinforcement Learning: A Finite-Time Analysis

  2020cites this paper
• Light Euclidean Steiner Spanners in the Plane

  2020cites this paper
• Non-parametric Binary regression in metric spaces with KL loss

  2020cites this paper
• On Euclidean Steiner (1+ε)-Spanners

  2020cites this paper
• Active Local Learning

  2020cites this paper
• Regression via Kirszbraun Extension with Applications to Imitation Learning

  2019influential citation
• Truly Optimal Euclidean Spanners

  2019cites this paper
• Efficient Kirszbraun extension with applications to regression

  2019cites this paper
• Regression via Kirszbraun Extension

  2019influential citation
• Selecting Optimal Decisions via Distributionally Robust Nearest-Neighbor Regression

  2019influential citation
• Sample Compression for Real-Valued Learners

  2018cites this paper
• Structural Risk Minimization for C 1 , 1 p R d q Regression

  2018cites this paper
• Structural Risk Minimization for $C^{1,1}(\mathbb{R}^d)$ Regression

  2018cites this paper
• Large-width bounds for learning half-spaces on distance spaces

  2018cites this paper
• Time-Accuracy Tradeoffs in Kernel Prediction: Controlling Prediction Quality

  2017influential citation
• Intrinsic Metrics: Exact Equality between a Geodesic Metric and a Graph metric

  2017cites this paper
• Fast Classification with Binary Prototypes

  2017cites this paper
• Concentration inequalities for empirical processes of linear time series

  2017cites this paper
• Algorithms for Lipschitz Learning on Graphs

  2015cites this paper
• Optimal Euclidean Spanners

  2015cites this paper
• A Light Metric Spanner

  2015cites this paper
• Near-Optimal Sample Compression for Nearest Neighbors

  2014cites this paper