Frank Nielsen

ICML Conference 2024 Conference Paper

A Rate-Distortion View of Uncertainty Quantification

• Ifigeneia Apostolopoulou
• Benjamin Eysenbach
• Frank Nielsen
• Artur Dubrawski

In supervised learning, understanding an input’s proximity to the training data can help a model decide whether it has sufficient evidence for reaching a reliable prediction. While powerful probabilistic models such as Gaussian Processes naturally have this property, deep neural networks often lack it. In this paper, we introduce Distance Aware Bottleneck (DAB), i. e. , a new method for enriching deep neural networks with this property. Building on prior information bottleneck approaches, our method learns a codebook that stores a compressed representation of all inputs seen during training. The distance of a new example from this codebook can serve as an uncertainty estimate for the example. The resulting model is simple to train and provides deterministic uncertainty estimates by a single forward pass. Finally, our method achieves better out-of-distribution (OOD) detection and misclassification prediction than prior methods, including expensive ensemble methods, deep kernel Gaussian Processes, and approaches based on the standard information bottleneck.

NeurIPS Conference 2024 Conference Paper

Hyperbolic Embeddings of Supervised Models

• Richard Nock
• Ehsan Amid
• Frank Nielsen
• Alexander Soen
• Manfred K. Warmuth

Models of hyperbolic geometry have been successfully used in ML for two main tasks: embedding models in unsupervised learning ( e. g. hierarchies) and embedding data. To our knowledge, there are no approaches that provide embeddings for supervised models; even when hyperbolic geometry provides convenient properties for expressing popular hypothesis classes, such as decision trees (and ensembles). In this paper, we propose a full-fledged solution to the problem in three independent contributions. The first linking the theory of losses for class probability estimation to hyperbolic embeddings in Poincar\'e disk model. The second resolving an issue for a clean, unambiguous embedding of (ensembles of) decision trees in this model. The third showing how to smoothly tweak the Poincar\'e hyperbolic distance to improve its encoding and visualization properties near the border of the disk, a crucial region for our application, while keeping hyperbolicity. This last step has substantial independent interest as it is grounded in a generalization of Leibniz-Newton's fundamental Theorem of calculus.

AAAI Conference 2024 Conference Paper

Optimal Transport with Tempered Exponential Measures

• Ehsan Amid
• Frank Nielsen
• Richard Nock
• Manfred K. Warmuth

In the field of optimal transport, two prominent subfields face each other: (i) unregularized optimal transport, ``a-la-Kantorovich'', which leads to extremely sparse plans but with algorithms that scale poorly, and (ii) entropic-regularized optimal transport, ``a-la-Sinkhorn-Cuturi'', which gets near-linear approximation algorithms but leads to maximally un-sparse plans. In this paper, we show that an extension of the latter to tempered exponential measures, a generalization of exponential families with indirect measure normalization, gets to a very convenient middle ground, with both very fast approximation algorithms and sparsity, which is under control up to sparsity patterns. In addition, our formulation fits naturally in the unbalanced optimal transport problem setting.

ICML Conference 2023 Conference Paper

Simplifying Momentum-based Positive-definite Submanifold Optimization with Applications to Deep Learning

• Wu Lin
• Valentin Duruisseaux
• Melvin Leok
• Frank Nielsen
• Mohammad Emtiyaz Khan
• Mark Schmidt 0001

Riemannian submanifold optimization with momentum is computationally challenging because, to ensure that the iterates remain on the submanifold, we often need to solve difficult differential equations. Here, we simplify such difficulties for a class of structured symmetric positive-definite matrices with the affine-invariant metric. We do so by proposing a generalized version of the Riemannian normal coordinates that dynamically orthonormalizes the metric and locally converts the problem into an unconstrained problem in the Euclidean space. We use our approach to simplify existing approaches for structured covariances and develop matrix-inverse-free $2^\text{nd}$-order optimizers for deep learning in low precision settings.

UAI Conference 2021 Conference Paper

q-Paths: Generalizing the geometric annealing path using power means

• Vaden Masrani
• Rob Brekelmans
• Thang Bui
• Frank Nielsen
• Aram Galstyan
• Greg Ver Steeg
• Frank Wood

Many common machine learning methods involve the geometric annealing path, a sequence of intermediate densities between two distributions of interest constructed using the geometric average. While alternatives such as the moment-averaging path have demonstrated performance gains in some settings, their practical applicability remains limited by exponential family endpoint assumptions and a lack of closed form energy function. In this work, we introduce $q$-paths, a family of paths which is derived from a generalized notion of the mean, includes the geometric and arithmetic mixtures as special cases, and admits a simple closed form involving the deformed logarithm function from nonextensive thermodynamics. Following previous analysis of the geometric path, we interpret our $q$-paths as corresponding to a $q$-exponential family of distributions, and provide a variational representation of intermediate densities as minimizing a mixture of $\alpha$-divergences to the endpoints. We show that small deviations away from the geometric path yield empirical gains for Bayesian inference using Sequential Monte Carlo and generative model evaluation using Annealed Importance Sampling.

ICML Conference 2021 Conference Paper

Tractable structured natural-gradient descent using local parameterizations

• Wu Lin
• Frank Nielsen
• Mohammad Emtiyaz Khan
• Mark Schmidt 0001

Natural-gradient descent (NGD) on structured parameter spaces (e. g. , low-rank covariances) is computationally challenging due to difficult Fisher-matrix computations. We address this issue by using \emph{local-parameter coordinates} to obtain a flexible and efficient NGD method that works well for a wide-variety of structured parameterizations. We show four applications where our method (1) generalizes the exponential natural evolutionary strategy, (2) recovers existing Newton-like algorithms, (3) yields new structured second-order algorithms, and (4) gives new algorithms to learn covariances of Gaussian and Wishart-based distributions. We show results on a range of problems from deep learning, variational inference, and evolution strategies. Our work opens a new direction for scalable structured geometric methods.

UAI Conference 2019 Conference Paper

Sinkhorn AutoEncoders

• Giorgio Patrini
• Rianne van den Berg
• Patrick Forré
• Marcello Carioni
• Samarth Bhargav 0001
• Max Welling
• Tim Genewein
• Frank Nielsen

Optimal transport offers an alternative to maximum likelihood for learning generative autoencoding models. We show that minimizing the $p$-Wasserstein distance between the generator and the true data distribution is equivalent to the unconstrained min-min optimization of the $p$-Wasserstein distance between the encoder aggregated posterior and the prior in latent space, plus a reconstruction error. We also identify the role of its trade-off hyperparameter as the capacity of the generator: its Lipschitz constant. Moreover, we prove that optimizing the encoder over any class of universal approximators, such as deterministic neural networks, is enough to come arbitrarily close to the optimum. We therefore advertise this framework, which holds for any metric space and prior, as a sweet-spot of current generative autoencoding objectives. We then introduce the Sinkhorn autoencoder (SAE), which approximates and minimizes the $p$-Wasserstein distance in latent space via backprogation through the Sinkhorn algorithm. SAE directly works on samples, i. e. it models the aggregated posterior as an implicit distribution, with no need for a reparameterization trick for gradients estimations. SAE is thus able to work with different metric spaces and priors with minimal adaptations. We demonstrate the flexibility of SAE on latent spaces with different geometries and priors and compare with other methods on benchmark data sets.

ICML Conference 2017 Conference Paper

DeepBach: a Steerable Model for Bach Chorales Generation

• Gaëtan Hadjeres
• François Pachet
• Frank Nielsen

This paper introduces DeepBach, a graphical model aimed at modeling polyphonic music and specifically hymn-like pieces. We claim that, after being trained on the chorale harmonizations by Johann Sebastian Bach, our model is capable of generating highly convincing chorales in the style of Bach. DeepBach’s strength comes from the use of pseudo-Gibbs sampling coupled with an adapted representation of musical data. This is in contrast with many automatic music composition approaches which tend to compose music sequentially. Our model is also steerable in the sense that a user can constrain the generation by imposing positional constraints such as notes, rhythms or cadences in the generated score. We also provide a plugin on top of the MuseScore music editor making the interaction with DeepBach easy to use.

ICML Conference 2017 Conference Paper

Relative Fisher Information and Natural Gradient for Learning Large Modular Models

• Ke Sun 0001
• Frank Nielsen

Fisher information and natural gradient provided deep insights and powerful tools to artificial neural networks. However related analysis becomes more and more difficult as the learner’s structure turns large and complex. This paper makes a preliminary step towards a new direction. We extract a local component from a large neural system, and define its relative Fisher information metric that describes accurately this small component, and is invariant to the other parts of the system. This concept is important because the geometry structure is much simplified and it can be easily applied to guide the learning of neural networks. We provide an analysis on a list of commonly used components, and demonstrate how to use this concept to further improve optimization.

AAAI Conference 2017 Conference Paper

Tsallis Regularized Optimal Transport and Ecological Inference

• Boris Muzellec
• Richard Nock
• Giorgio Patrini
• Frank Nielsen

Optimal transport is a powerful framework for computing distances between probability distributions. We unify the two main approaches to optimal transport, namely Monge- Kantorovitch and Sinkhorn-Cuturi, into what we define as Tsallis regularized optimal transport (TROT). TROT interpolates a rich family of distortions from Wasserstein to Kullback-Leibler, encompassing as well Pearson, Neyman and Hellinger divergences, to name a few. We show that metric properties known for Sinkhorn-Cuturi generalize to TROT, and provide efficient algorithms for finding the optimal transportation plan with formal convergence proofs. We also present the first application of optimal transport to the problem of ecological inference, that is, the reconstruction of joint distributions from their marginals, a problem of large interest in the social sciences. TROT provides a convenient framework for ecological inference by allowing to compute the joint distribution — that is, the optimal transportation plan itself — when side information is available, which is e. g. typically what census represents in political science. Experiments on data from the 2012 US presidential elections display the potential of TROT in delivering a faithful reconstruction of the joint distribution of ethnic groups and voter preferences.

IJCAI Conference 2016 Conference Paper

Clustering Financial Time Series: How Long Is Enough?

• Gautier Marti
• S
• eacute; bastien Andler
• Frank Nielsen
• Philippe Donnat

Researchers have used from 30 days to several years of daily returns as source data for clustering financial time series based on their correlations. This paper sets up a statistical framework to study the validity of such practices. We first show that clustering correlated random variables from their observed values is statistically consistent. Then, we also give a first empirical answer to the much debated question: How long should the time series be? If too short, the clusters found can be spurious; if too long, dynamics can be smoothed out.

ICML Conference 2016 Conference Paper

k-variates++: more pluses in the k-means++

• Richard Nock
• Raphaël Canyasse
• Roksana Boreli
• Frank Nielsen

k-means++ seeding has become a de facto standard for hard clustering algorithms. In this paper, our first contribution is a two-way generalisation of this seeding, k-variates++, that includes the sampling of general densities rather than just a discrete set of Dirac densities anchored at the point locations, *and* a generalisation of the well known Arthur-Vassilvitskii (AV) approximation guarantee, in the form of a *bias+variance* approximation bound of the *global* optimum. This approximation exhibits a reduced dependency on the "noise" component with respect to the optimal potential — actually approaching the statistical lower bound. We show that k-variates++ *reduces* to efficient (biased seeding) clustering algorithms tailored to specific frameworks; these include distributed, streaming and on-line clustering, with *direct* approximation results for these algorithms. Finally, we present a novel application of k-variates++ to differential privacy. For either the specific frameworks considered here, or for the differential privacy setting, there is little to no prior results on the direct application of k-means++ and its approximation bounds — state of the art contenders appear to be significantly more complex and / or display less favorable (approximation) properties. We stress that our algorithms can still be run in cases where there is *no* closed form solution for the population minimizer. We demonstrate the applicability of our analysis via experimental evaluation on several domains and settings, displaying competitive performances vs state of the art.

ICML Conference 2016 Conference Paper

Loss factorization, weakly supervised learning and label noise robustness

• Giorgio Patrini
• Frank Nielsen
• Richard Nock
• Marcello Carioni

We prove that the empirical risk of most well-known loss functions factors into a linear term aggregating all labels with a term that is label free, and can further be expressed by sums of the same loss. This holds true even for non-smooth, non-convex losses and in any RKHS. The first term is a (kernel) mean operator — the focal quantity of this work — which we characterize as the sufficient statistic for the labels. The result tightens known generalization bounds and sheds new light on their interpretation. Factorization has a direct application on weakly supervised learning. In particular, we demonstrate that algorithms like SGD and proximal methods can be adapted with minimal effort to handle weak supervision, once the mean operator has been estimated. We apply this idea to learning with asymmetric noisy labels, connecting and extending prior work. Furthermore, we show that most losses enjoy a data-dependent (by the mean operator) form of noise robustness, in contrast with known negative results.

ICML Conference 2011 Conference Paper

On tracking portfolios with certainty equivalents on a generalization of Markowitz model: the Fool, the Wise and the Adaptive

• Richard Nock
• Brice Magdalou
• Eric Briys
• Frank Nielsen

NeurIPS Conference 2008 Conference Paper

On the Efficient Minimization of Classification Calibrated Surrogates

• Richard Nock
• Frank Nielsen

Bartlett et al (2006) recently proved that a ground condition for convex surrogates, classification calibration, ties up the minimization of the surrogates and classification risks, and left as an important problem the algorithmic questions about the minimization of these surrogates. In this paper, we propose an algorithm which provably minimizes any classification calibrated surrogate strictly convex and differentiable --- a set whose losses span the exponential, logistic and squared losses ---, with boosting-type guaranteed convergence rates under a weak learning assumption. A particular subclass of these surrogates, that we call balanced convex surrogates, has a key rationale that ties it to maximum likelihood estimation, zero-sum games and the set of losses that satisfy some of the most common requirements for losses in supervised learning. We report experiments on more than 50 readily available domains of 11 flavors of the algorithm, that shed light on new surrogates, and the potential of data dependent strategies to tune surrogates.

IJCAI Conference 2007 Conference Paper

• Claudia Henry
• Richard Nock
• Frank Nielsen

In the past ten years, boosting has become a major field of machine learning and classification. This paper brings contributions to its theory and algorithms. We first unify a well-known top-down decision tree induction algorithm due to Kearns and Mansour, and discrete AdaBoost, as two versions of a same higher-level boosting algorithm. It may be used as the basic building block to devise simple provable boosting algorithms for complex classifiers. We provide one example: the first boosting algorithm for Oblique Decision Trees, an algorithm which turns out to be simpler, faster and significantly more accurate than previous approaches.

AIJ Journal 2007 Journal Article

A R eal generalization of discrete AdaBoost

• Richard Nock
• Frank Nielsen

Scaling discrete AdaBoost to handle real-valued weak hypotheses has often been done under the auspices of convex optimization, but little is generally known from the original boosting model standpoint. We introduce a novel generalization of discrete AdaBoost which departs from this mainstream of algorithms. From the theoretical standpoint, it formally displays the original boosting property, as it brings fast improvements of the accuracy of a weak learner up to arbitrary high levels; furthermore, it brings interesting computational and numerical improvements that make it significantly easier to handle “as is”. Conceptually speaking, it provides a new and appealing scaling to R of some well known facts about discrete (ada)boosting. Perhaps the most popular is an iterative weight modification mechanism, according to which examples have their weights decreased iff they receive the right class by the current discrete weak hypothesis. In our generalization, this property does not hold anymore, as examples that receive the right class can still be reweighted higher with real-valued weak hypotheses. From the experimental standpoint, our generalization displays the ability to produce low error formulas with particular cumulative margin distribution graphs, and it provides a nice handling of those noisy domains that represent Achilles' heel for common Adaptive Boosting algorithms.

SODA Conference 2007 Conference Paper

On Bregman Voronoi diagrams

• Frank Nielsen
• Jean-Daniel Boissonnat
• Richard Nock

TCS Journal 2007 Journal Article

Self-improved gaps almost everywhere for the agnostic approximation of monomials

• Richard Nock
• Frank Nielsen

Given a learning sample, we focus on the hardness of finding monomials having low error, inside the interval bounded below by the smallest error achieved by a monomial (the best rule), and bounded above by the error of the default class (the poorest rule). It is well-known that when its lower bound is zero, it is an easy task to find, in linear time, a monomial with zero error. What we prove is that when this bound is not zero, regardless of the location of the default class in ( 0, 1 / 2 ), it becomes a huge complexity burden to beat significantly the default class. In fact, under some complexity-theoretical assumptions, it may already be hard to beat the trivial approximation ratios, even when relaxing the time complexity constraint to be quasi-polynomial or sub-exponential. Our results also hold with uniform weights over the examples.

ECAI Conference 2006 Conference Paper

A Real Generalization of Discrete AdaBoost

• Richard Nock
• Frank Nielsen

Scaling discrete AdaBoost to handle real-valued weak hypotheses has often been done under the auspices of convex optimization, but little is generally known from the original boosting model standpoint. We introduce a novel generalization of discrete AdaBoost which departs from this mainstream of algorithms. From the theoretical standpoint, it formally displays the original boosting property; furthermore, it brings interesting computational and numerical improvements that make it significantly easier to handle “as is”. Conceptually speaking, it provides a new and appealing scaling to R of some well known facts about discrete (ada)boosting. Perhaps the most popular is an iterative weight modification mechanism, according to which examples have their weights decreased iff they receive the right class by the current discrete weak hypothesis. Our generalization to real values makes that decreasing weights affect only the examples on which the hypothesis' margin exceeds its average margin. Thus, while both properties coincide on the discrete case, examples that receive the right class can still be reweighted higher with real-valued weak hypotheses. From the experimental standpoint, our generalization displays the ability to produce low error formulas with particular cumulative margin distributions, and it provides a nice handling of those noisy domains that represent Achilles' heel for common Adaptive Boosting algorithms.

ECAI Conference 2006 Conference Paper

Soft Uncoupling of Markov Chains for Permeable Language Distinction: A New Algorithm

• Richard Nock
• Pascal Vaillant
• Frank Nielsen
• Claudia Henry

Without prior knowledge, distinguishing different languages may be a hard task, especially when their borders are permeable. We develop an extension of spectral clustering — a powerful unsupervised classification toolbox — that is shown to resolve accurately the task of soft language distinction. At the heart of our approach, we replace the usual hard membership assignment of spectral clustering by a soft, probabilistic assignment, which also presents the advantage to bypass a well-known complexity bottleneck of the method. Experiments with a readily available system display the potential of the method, which brings a visually appealing soft distinction of languages that may define altogether a whole corpus.

TCS Journal 2004 Journal Article

On domain-partitioning induction criteria: worst-case bounds for the worst-case based

• Richard Nock
• Frank Nielsen

One of the most popular induction scheme for supervised learning is also one of the oldest. It builds a classifier in a top-down fashion, following the minimization of a so-called index criterion. While numerous papers have reported experiments on this scheme, little has been known on its theoretical aspect until recent works on decision trees and branching programs using a powerful classification tool: boosting. In this paper, we look at this problem from a worst-case computational (rather than informational) standpoint. Our conclusions for the ranking of these indexes’ minimization follow almost exactly that of boosting (with matching upper and lowerbounds), and provide extensions to more classes of Boolean formulas such as decision lists, multilinear polynomials and symmetric functions. Our results also exhibit a strong worst-case for the induction scheme, as we build particularly hard samples for which the replacement of most index criteria, or the class of concept representation, even when producing the same ranking as boosting does for the indexes, makes no difference at all for the concept induced. This is clearly not a limit of previous analyses, but a consequence of the induction scheme.

TCS Journal 2001 Journal Article

Combinatorial optimization algorithms for radio network planning

• Patrice Calégari
• Frédéric Guidec
• Pierre Kuonen
• Frank Nielsen

This paper uses a realistic problem taken from the telecommunication world as the basis for comparing different combinatorial optimization algorithms. The problem recalls the minimum hitting set problem, and is solved with greedy-like, Darwinism and genetic algorithms. These three paradigms are described and analyzed with emphasis on the Darwinism approach, which is based on the computation of ε-nets.

TCS Journal 2001 Journal Article

On point covers of c-oriented polygons

• Frank Nielsen

Let S be any family of n c-oriented polygons of the two-dimensional Euclidean plane E 2, i. e. , bounded intersection of halfplanes whose normal directions of edges belong to a fixed collection of c distinct directions. Let φ(S) denote the packing number of S, that is the maximum number of pairwise disjoint objects of S. Let τ(S) be the transversal number of S, that is the minimum number of points required so that each object contains at least one of those points. We prove that τ(S)⩽G(2, c)φ(S) log 2 c−1(φ(S)+1), where G(2, c) is the Gallai number of pairwise intersecting c-oriented polygons. Our bound collapses to τ(S)=O(G(2, c)φ(S)) if objects are more or less of the same size. We describe a t(n, c)+O(nc log φ(S))-time algorithm with linear storage that computes such a 0-transversal, where t(n, c) is the time required to pierce pairwise intersecting c-oriented polygons. We provide linear-time algorithms t(n, c)=Θ(nc) for α-fat c-oriented polytopes, translates or homothets of E d proving that G(2, c)=O(α)d, G(2, c)⩽dd and G(2, c)⩽(3d3/2)d respectively.

TCS Journal 2000 Journal Article

Fast stabbing of boxes in high dimensions

• Frank Nielsen

We present in this paper a simple yet efficient algorithm for stabbing a set S of n axis-parallel boxes in d-dimensional space with c(S) points in output-sensitive time O(dn log c(S)) and linear space. Let c∗(S) and b∗(S) be, respectively, the minimum number of points required to stab S and the maximum number of pairwise disjoint boxes of S. We prove that b∗(S)⩽c∗(S)⩽c(S)⩽b∗(S)(1+log 2 b∗(S))d−1. Since finding a minimal set of c∗(S) points is NP-complete as soon as d>1, we obtain a fast precision-sensitive heuristic for stabbing S whose quality does not depend on the input size. In the case of congruent or constrained isothetic boxes, our algorithm reports, respectively, c(S)⩽2d−1b∗(S) and c(S)=Od(b∗(S)) stabbing points. Moreover, we show that the bounds we get on c(S) are asymptotically tight and corroborate our results with some experiments. We also describe an optimal output-sensitive algorithm for finding a minimal-size optimal stabbing point-set of intervals. Finally, we conclude with insights for further research.