It is often desirable to summarise a probability measure on a space $X$ in terms of a mode, or MAP estimator, i.e.\ a point of maximum probability. Such points can be rigorously defined using masses of metric balls in the small-radius limit. However, the theory is not entirely straightforward: the literature contains multiple notions of mode and various examples of pathological measures that have no mode in any sense. Since the masses of balls induce natural orderings on the points of $X$, this article aims to shed light on some of the problems in non-parametric MAP estimation by taking an order-theoretic perspective, which appears to be a new one in the inverse problems community. This point of view opens up attractive proof strategies based upon the Cantor and Kuratowski intersection theorems; it also reveals that many of the pathologies arise from the distinction between greatest and maximal elements of an order, and from the existence of incomparable elements of $X$, which we show can be dense in $X$, even for an absolutely continuous measure on $X = \mathbb{R}$.
相關內容
This article shows that a large class of posterior measures that are absolutely continuous with respect to a Gaussian prior have strong maximum a posteriori estimators in the sense of Dashti et al. (2013). This result holds in any separable Banach space and applies in particular to nonparametric Bayesian inverse problems with additive noise. When applied to Bayesian inverse problems, this significantly extends existing results on maximum a posteriori estimators by relaxing the conditions on the log-likelihood and on the space in which the inverse problem is set.
To mitigate the bias exhibited by machine learning models, fairness criteria can be integrated into the training process to ensure fair treatment across all demographics, but it often comes at the expense of model performance. Understanding such tradeoffs, therefore, underlies the design of fair algorithms. To this end, this paper provides a complete characterization of the inherent tradeoff of demographic parity on classification problems, under the most general multi-group, multi-class, and noisy setting. Specifically, we show that the minimum error rate achievable by randomized and attribute-aware fair classifiers is given by the optimal value of a Wasserstein-barycenter problem. On the practical side, our findings lead to a simple post-processing algorithm that derives fair classifiers from score functions, which yields the optimal fair classifier when the score is Bayes optimal. We provide suboptimality analysis and sample complexity for our algorithm, and demonstrate its effectiveness on benchmark datasets.
Leximin is a common approach to multi-objective optimization, frequently employed in fair division applications. In leximin optimization, one first aims to maximize the smallest objective value; subject to this, one maximizes the second-smallest objective; and so on. Often, even the single-objective problem of maximizing the smallest value cannot be solved accurately. What can we hope to accomplish for leximin optimization in this situation? Recently, Henzinger et al. (2022) defined a notion of \emph{approximate} leximin optimality. Their definition, however, considers only an additive approximation. In this work, we first define the notion of approximate leximin optimality, allowing both multiplicative and additive errors. We then show how to compute, in polynomial time, such an approximate leximin solution, using an oracle that finds an approximation to a single-objective problem. The approximation factors of the algorithms are closely related: an $(\alpha,\epsilon)$-approximation for the single-objective problem (where $\alpha \in (0,1]$ and $\epsilon \geq 0$ are the multiplicative and additive factors respectively) translates into an $\left(\frac{\alpha^2}{1-\alpha + \alpha^2}, \frac{\epsilon}{1-\alpha +\alpha^2}\right)$-approximation for the multi-objective leximin problem, regardless of the number of objectives. Finally, we apply our algorithm to obtain an approximate leximin solution for the problem of \emph{stochastic allocations of indivisible goods}. For this problem, assuming sub-modular objectives functions, the single-objective egalitarian welfare can be approximated, with only a multiplicative error, to an optimal $1-\frac{1}{e}\approx 0.632$ factor w.h.p. We show how to extend the approximation to leximin, over all the objective functions, to a multiplicative factor of $\frac{(e-1)^2}{e^2-e+1} \approx 0.52$ w.h.p or $\frac{1}{3}$ deterministically.
The Fisher information matrix is a quantity of fundamental importance for information geometry and asymptotic statistics. In practice, it is widely used to quickly estimate the expected information available in a data set and guide experimental design choices. In many modern applications, it is intractable to analytically compute the Fisher information and Monte Carlo methods are used instead. The standard Monte Carlo method produces estimates of the Fisher information that can be biased when the Monte-Carlo noise is non-negligible. Most problematic is noise in the derivatives as this leads to an overestimation of the available constraining power, given by the inverse Fisher information. In this work we find another simple estimate that is oppositely biased and produces an underestimate of the constraining power. This estimator can either be used to give approximate bounds on the parameter constraints or can be combined with the standard estimator to give improved, approximately unbiased estimates. Both the alternative and the combined estimators are asymptotically unbiased so can be also used as a convergence check of the standard approach. We discuss potential limitations of these estimators and provide methods to assess their reliability. These methods accelerate the convergence of Fisher forecasts, as unbiased estimates can be achieved with fewer Monte Carlo samples, and so can be used to reduce the simulated data set size by several orders of magnitude.
In this paper, we explore how to use topological tools to compare dimension reduction methods. We first make a brief overview of some of the methods often used dimension reduction such as Isometric Feature Mapping, Laplacian Eigenmaps, Fast Independent Component Analysis, Kernel Ridge Regression, t-distributed Stochastic Neighbor Embedding. We then give a brief overview of some topological notions used in topological data analysis, such as, barcodes, persistent homology, and Wasserstein distance. Theoretically, these methods applied on a data set can be interpreted differently. From EEG data embedded into a manifold of high dimension, we apply these methods and we compare them across persistent homologies of dimension 0, 1, and 2, that is, across connected components, tunnels and holes, shells around voids or cavities. We find that from three dimension clouds of points, it is not clear how distinct from each other the methods are, but Wasserstein and Bottleneck distances, topological tests of hypothesis, and various methods show that the methods qualitatively and significantly differ across homologies.
Wasserstein gradient flows of maximum mean discrepancy (MMD) functionals with non-smooth Riesz kernels show a rich structure as singular measures can become absolutely continuous ones and conversely. In this paper we contribute to the understanding of such flows. We propose to approximate the backward scheme of Jordan, Kinderlehrer and Otto for computing such Wasserstein gradient flows as well as a forward scheme for so-called Wasserstein steepest descent flows by neural networks (NNs). Since we cannot restrict ourselves to absolutely continuous measures, we have to deal with transport plans and velocity plans instead of usual transport maps and velocity fields. Indeed, we approximate the disintegration of both plans by generative NNs which are learned with respect to appropriate loss functions. In order to evaluate the quality of both neural schemes, we benchmark them on the interaction energy. Here we provide analytic formulas for Wasserstein schemes starting at a Dirac measure and show their convergence as the time step size tends to zero. Finally, we illustrate our neural MMD flows by numerical examples.
Continuous normalizing flows are widely used in generative tasks, where a flow network transports from a data distribution $P$ to a normal distribution. A flow model that transports from $P$ to an arbitrary $Q$, where both $P$ and $Q$ are accessible via finite samples, is of various application interests, particularly in the recently developed telescoping density ratio estimation (DRE) which calls for the construction of intermediate densities to bridge between the two densities. In this work, we propose such a flow by a neural-ODE model which is trained from empirical samples to transport invertibly from $P$ to $Q$ (and vice versa) and optimally by minimizing the transport cost. The trained flow model allows us to perform infinitesimal DRE along the time-parametrized $\log$-density by training an additional continuous-time network using classification loss, whose time integration provides a telescopic DRE. The effectiveness of the proposed model is empirically demonstrated on high-dimensional mutual information estimation and energy-based generative models of image data.
In this paper, we introduce the Maximum Matrix Contraction problem, where we aim to contract as much as possible a binary matrix in order to maximize its density. We study the complexity and the polynomial approximability of the problem. Especially, we prove this problem to be NP-Complete and that every algorithm solving this problem is at most a $2\sqrt{n}$-approximation algorithm where n is the number of ones in the matrix. We then focus on efficient algorithms to solve the problem: an integer linear program and three heuristics.
We initiate the study of the algorithmic problem of certifying lower bounds on the discrepancy of random matrices: given an input matrix $A \in \mathbb{R}^{m \times n}$, output a value that is a lower bound on $\mathsf{disc}(A) = \min_{x \in \{\pm 1\}^n} ||Ax||_\infty$ for every $A$, but is close to the typical value of $\mathsf{disc}(A)$ with high probability over the choice of a random $A$. This problem is important because of its connections to conjecturally-hard average-case problems such as negatively-spiked PCA, the number-balancing problem and refuting random constraint satisfaction problems. We give the first polynomial-time algorithms with non-trivial guarantees for two main settings. First, when the entries of $A$ are i.i.d. standard Gaussians, it is known that $\mathsf{disc} (A) = \Theta (\sqrt{n}2^{-n/m})$ with high probability. Our algorithm certifies that $\mathsf{disc}(A) \geq \exp(- O(n^2/m))$ with high probability. As an application, this formally refutes a conjecture of Bandeira, Kunisky, and Wein on the computational hardness of the detection problem in the negatively-spiked Wishart model. Second, we consider the integer partitioning problem: given $n$ uniformly random $b$-bit integers $a_1, \ldots, a_n$, certify the non-existence of a perfect partition, i.e. certify that $\mathsf{disc} (A) \geq 1$ for $A = (a_1, \ldots, a_n)$. Under the scaling $b = \alpha n$, it is known that the probability of the existence of a perfect partition undergoes a phase transition from 1 to 0 at $\alpha = 1$; our algorithm certifies the non-existence of perfect partitions for some $\alpha = O(n)$. We also give efficient non-deterministic algorithms with significantly improved guarantees. Our algorithms involve a reduction to the Shortest Vector Problem.
We present a new computation method for simulating reflection high-energy electron diffraction and the total-reflection high-energy positron diffraction experiments. The two experiments are used commonly for the structural analysis of material surface. The present paper improves the conventional numerical method, the multi-slice method, for faster computation, since the present method avoids the matrix-eigenvalue solver for the computation of matrix exponentials and can adopt higher-order ordinary differential equation solvers. Moreover, we propose a high-performance implementation based on multi-thread parallelization and cache-reusable subroutines. In our tests, this new method performs up to 2,000 times faster than the conventional method.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191