Distance-Based Classification with Lipschitz Functions

By Ulrike von Luxburg, Olivier Bousquet. 2004

249 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Media Technology

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Media Technology

Citations in the corpus

On the empirical estimation of integral probability metrics (2012, methodology): “We then show that the empirical estimators of the Kantorovichmetric, Dudley metric and kernel distance are related to themargins of the Lipschitz classifier [51], bounded Lipschitz classifier, and support vector machine, respectively.”
Exploring Generalization in Deep Learning (2017, background): “Luxburg and Bousquet [13] studied the capacity of functions with bounded Lipschitz constant on metric space ( X , M ) with a ﬁnite diameter diam M ( X ) = sup x,y ∈ X M ( x, y ) and showed that the capacity is proportional to C M γ margin n diam M ( X ) .”
On integral probability metrics, φ-divergences and binary classification (2009, positive): “Theorem 1 ( γ F ⋆ is a φ -divergence): Let F ⋆ be the set of all real-valued measurable functions on M and let Then Proof: (8) simply follows by using F ⋆ and φ ⋆ in γ F and D φ or by using φ ∗ ⋆ ( u ) = u in (4).”
Implicit Regularization in Deep Learning (2017, background): “Unlike existing generalization bounds [28, 58, 29, 30, 31], our sharpness based bound does not suffer from exponential dependence on depth.”
Learning in Hilbert vs. Banach Spaces: A Measure Embedding Viewpoint (2011, methodology): “To sample the literature, classification in Banach spaces, more generally in metric spaces were studied in [3, 24, 12, 6].”
A Closer Look at Accuracy vs. Robustness (2020, background): “For linear classifiers, it is known that imposing Lipschitzness reduces to bounding the norm of the classifier, which in turn implies large margin [31, 61].”
Sharp convergence rates for empirical optimal transport with smooth costs (2021, background): “…) is the logarithm of the ǫ -covering number N ( ǫ, A, η ) of ( A, η ) , deﬁned by (cid:8) (cid:9) The following version of Dudley’s bound will be sufﬁcient for our purposes, and can be deduced for instance from Lemma 16 of von Luxburg and Bousquet (2004) (see also Lemma 3.2 of van de Geer (2000)).”
Asymptotic learning curves of kernel methods: empirical data v.s. Teacher-Student paradigm (2019, background): “For regression, if the target function being learned is simply assumed to be Lipschitz, then the best guarantee is β = 1/d (Luxburg and Bousquet, 2004; Bach, 2017) where d is the data dimension.”
Locality defeats the curse of dimensionality in convolutional teacher–student scenarios (2021, background): “(222) 1(1)4012 Locality defeats the curse of dimensionality in convolutional teacher–student scenarios supervised learning model suffers in principle from the curse of dimensionality: under minimal assumptions on the function to be learnt, achieving a fixed target generalisation error requires a num”
Fast and robust Earth Mover's Distances (2009, background): “Practical considerations include speed of computation and the metric property that enables fast algorithms for nearest neighbor searches [41, 7], fast clustering [10] and large margin classifiers [15, 36].”
Learning Adversary Behavior in Security Games: A PAC Model Perspective (2015, methodology): “For the NPL case we use results from [32] along with our technique of bounding the mixed strategy space of the defender; these results [32] have also been used in the study of Lipschitz classifiers [21] but we differ as our hypothesis functions are real vector-valued.”
Lipschitz Continuity Guided Knowledge Distillation (2021, background): “By Definition 1, ∥f∥Lip has an excellent property of upper bounding the relationship between input perturbation and output variation for a given distance (generally L2 norm), thus it is considered as a metric to evaluate the robustness of neural networks to small perturbations [27, 40, 1].”
Reproducing kernel Banach spaces for machine learning (2009, background): “A function K : X x X -----+ ce is called a positive definite kernel if for all finite subsets x :== {Xj : j E Nn } ~ X the matrix 978-1-4244-3553-1/09/$25.00 ©2009 IEEE 3520 by certain data structures with asymmetric similarity.”
Geometric compression of invariant manifolds in neural nets (2020, background): “If mild assumptions are made on the task (for example regressing a Lipschitz continuous function), then (p) cannot be guaranteed to decay faster than ∝ p−β with an exponent β = O (1/d) [1]: learning is essentially impossible.”
Parallelized Stochastic Gradient Descent (2010, unknown): “Lipschitz seminorm: [10] introduce a seminorm.”
Linear-Time Computation of Similarity Measures for Sequential Data (2008, background): “Numerous applications exist for which relationships are defined as metric or non-metric distances (e.g., Anderberg , 1973; Jacobs et al., 2000; von Luxburg and Bousquet, 2004), similarity or dissimilarity measures (e.g., Graepel et al., 1999; Roth et al., 2003; Laub and Müller, 2004; Laub et al.,…”
Lipschitz regularity of deep neural networks: analysis and efficient estimation (2018, background): “learning theory, novel generalization bounds critically rely on the Lipschitz constant of the neural network [16, 17, 18].”