The Bernstein-von Mises theorem (BvM) gives conditions under which the posterior distribution of a parameter $\theta\in\Theta\subseteq\mathbb R^d$ based on $n$ independent samples is asymptotically normal. In the high-dimensional regime, a key question is to determine the growth rate of $d$ with $n$ required for the BvM to hold. We show that up to a model-dependent coefficient, $n\gg d^2$ suffices for the BvM to hold in two settings: arbitrary generalized linear models, which include exponential families as a special case, and multinomial data, in which the parameter of interest is an unknown probability mass functions on $d+1$ states. Our results improve on the tightest previously known condition for posterior asymptotic normality, $n\gg d^3$. Our statements of the BvM are nonasymptotic, taking the form of explicit high-probability bounds. To prove the BvM, we derive a new simple and explicit bound on the total variation distance between a measure $\pi\propto e^{-nf}$ on $\Theta\subseteq\mathbb R^d$ and its Laplace approximation.
相關內容
We consider the problem of enumerating all minimal transversals (also called minimal hitting sets) of a hypergraph $\mathcal{H}$. An equivalent formulation of this problem known as the \emph{transversal hypergraph} problem (or \emph{hypergraph dualization} problem) is to decide, given two hypergraphs, whether one corresponds to the set of minimal transversals of the other. The existence of a polynomial time algorithm to solve this problem is a long standing open question. In \cite{fredman_complexity_1996}, the authors present the first sub-exponential algorithm to solve the transversal hypergraph problem which runs in quasi-polynomial time, making it unlikely that the problem is (co)NP-complete. In this paper, we show that when one of the two hypergraphs is of bounded VC-dimension, the transversal hypergraph problem can be solved in polynomial time, or equivalently that if $\mathcal{H}$ is a hypergraph of bounded VC-dimension, then there exists an incremental polynomial time algorithm to enumerate its minimal transversals. This result generalizes most of the previously known polynomial cases in the literature since they almost all consider classes of hypergraphs of bounded VC-dimension. As a consequence, the hypergraph transversal problem is solvable in polynomial time for any class of hypergraphs closed under partial subhypergraphs. We also show that the proposed algorithm runs in quasi-polynomial time in general hypergraphs and runs in polynomial time if the conformality of the hypergraph is bounded, which is one of the few known polynomial cases where the VC-dimension is unbounded.
In this paper, the stability of IMEX-BDF methods for delay differential equations (DDEs) is studied based on the test equation $y'(t)=-A y(t) + B y(t-\tau)$, where $\tau$ is a constant delay, $A$ is a positive definite matrix, but $B$ might be any matrix. First, it is analyzed the case where both matrices diagonalize simultaneously, but the paper focus in the case where the matrices $A$ and $B$ are not simultaneosly diagonalizable. The concept of field of values is used to prove a sufficient condition for unconditional stability of these methods and another condition which also guarantees their stability, but according to the step size. Several numerical examples in which the theory discussed here is applied to DDEs, but also parabolic problems given by partial delay differential equations with a diffusion term and a delayed term are presented.
We propose a new density estimation algorithm. Given $n$ i.i.d. observations from a distribution belonging to a class of densities on $\mathbb{R}^d$, our estimator outputs any density in the class whose ``perceptron discrepancy'' with the empirical distribution is at most $O(\sqrt{d/n})$. The perceptron discrepancy is defined as the largest difference in mass two distribution place on any halfspace. It is shown that this estimator achieves the expected total variation distance to the truth that is almost minimax optimal over the class of densities with bounded Sobolev norm and Gaussian mixtures. This suggests that the regularity of the prior distribution could be an explanation for the efficiency of the ubiquitous step in machine learning that replaces optimization over large function spaces with simpler parametric classes (such as discriminators of GANs). We also show that replacing the perceptron discrepancy with the generalized energy distance of Szekely and Rizzo (2013) further improves total variation loss. The generalized energy distance between empirical distributions is easily computable and differentiable, which makes it especially useful for fitting generative models. To the best of our knowledge, it is the first ``simple'' distance with such properties with minimax statistical guarantees.
A convergent numerical method for $\alpha$-dissipative solutions of the Hunter-Saxton equation is derived. The method is based on applying a tailor-made projection operator to the initial data, and then solving exactly using the generalized method of characteristics. The projection step is the only step that introduces any approximation error. It is therefore crucial that its design ensures not only a good approximation of the initial data, but also that errors due to the energy dissipation at later times remain small. Furthermore, it is shown that the main quantity of interest, the wave profile, converges in $L^{\infty}$ for all $t \geq 0$, while a subsequence of the energy density converges weakly for almost every time.
We consider an economic environment with one buyer and one seller. For a bundle $(t,q)\in [0,\infty[\times [0,1]=\mathbb{Z}$, $q$ refers to the winning probability of an object, and $t$ denotes the payment that the buyer makes. We consider continuous and monotone preferences on $\mathbb{Z}$ as the primitives of the buyer. These preferences can incorporate both quasilinear and non-quasilinear preferences, and multidimensional pay-off relevant parameters. We define rich single-crossing subsets of this class and characterize strategy-proof mechanisms by using monotonicity of the mechanisms and continuity of the indirect preference correspondences. We also provide a computationally tractable optimization program to compute the optimal mechanism for mechanisms with finite range. We do not use revenue equivalence and virtual valuations as tools in our proofs. Our proof techniques bring out the geometric interaction between the single-crossing property and the positions of bundles $(t,q)$s in the space $\mathbb{Z}$. We also provide an extension of our analysis to an $n-$buyer environment, and to the situation where $q$ is a qualitative variable.
Is there a fixed dimension $n$ such that translational tiling of $\mathbb{Z}^n$ with a monotile is undecidable? Several recent results support a positive answer to this question. Greenfeld and Tao disprove the periodic tiling conjecture by showing that an aperiodic monotile exists in sufficiently high dimension $n$ [Ann. Math. 200(2024), 301-363]. In another paper [to appear in J. Eur. Math. Soc.], they also show that if the dimension $n$ is part of the input, then the translational tiling for subsets of $\mathbb{Z}^n$ with one tile is undecidable. These two results are very strong pieces of evidence for the conjecture that translational tiling of $\mathbb{Z}^n$ with a monotile is undecidable, for some fixed $n$. This paper gives another supportive result for this conjecture by showing that translational tiling of the $4$-dimensional space with a set of three connected tiles is undecidable.
We propose and justify a matrix reduction method for calculating the optimal approximation of an observed matrix $A \in {\mathbb C}^{m \times n}$ by a sum $\sum_{i=1}^p \sum_{j=1}^q B_iX_{ij}C_j$ of matrix products where each $B_i \in {\mathbb C}^{m \times g_i}$ and $C_j \in {\mathbb C}^{h_j \times n}$ is known and where the unknown matrix kernels $X_{ij}$ are determined by minimizing the Frobenius norm of the error. The sum can be represented as a bounded linear mapping $BXC$ with unknown kernel $X$ from a prescribed subspace ${\mathcal T} \subseteq {\mathbb C}^n$ onto a prescribed subspace ${\mathcal S} \subseteq {\mathbb C}^m$ defined respectively by the collective domains and ranges of the given matrices $C_1,\ldots,C_q$ and $B_1,\ldots,B_p$. We show that the optimal kernel is $X = B^{\dag}AC^{\dag}$ and that the optimal approximation $BB^{\dag}AC^{\dag}C$ is the projection of the observed mapping $A$ onto a mapping from ${\mathcal T}$ to ${\mathcal S}$. If $A$ is large $B$ and $C$ may also be large and direct calculation of $B^{\dag}$ and $C^{\dag}$ becomes unwieldy and inefficient. { The proposed method avoids} this difficulty by reducing the solution process to finding the pseudo-inverses of a collection of much smaller matrices. This significantly reduces the computational burden.
We study the finite element approximation of problems involving the weighted $p$-Laplacian for $p \in (1,\infty)$ and weights belonging to the Muckenhoupt class $A_1$. In particular, we consider an equation and an obstacle problem for the weighted $p$-Laplacian and derive error estimates in both cases. The analysis is based on the language of weighted Orlicz and Orlicz--Sobolev spaces.
This work considers the problem of output-sensitive listing of occurrences of $2k$-cycles for fixed constant $k\geq 2$ in an undirected host graph with $m$ edges and $t$ $2k$-cycles. Recent work of Jin and Xu (and independently Abboud, Khoury, Leibowitz, and Safier) [STOC 2023] gives an $O(m^{4/3}+t)$ time algorithm for listing $4$-cycles, and recent work by Jin, Vassilevska Williams and Zhou [SOSA 2024] gives an $\widetilde{O}(n^2+t)$ time algorithm for listing $6$-cycles in $n$ node graphs. We focus on resolving the next natural question: obtaining listing algorithms for $6$-cycles in the sparse setting, i.e., in terms of $m$ rather than $n$. Previously, the best known result here is the better of Jin, Vassilevska Williams and Zhou's $\widetilde{O}(n^2+t)$ algorithm and Alon, Yuster and Zwick's $O(m^{5/3}+t)$ algorithm. We give an algorithm for listing $6$-cycles with running time $\widetilde{O}(m^{1.6}+t)$. Our algorithm is a natural extension of Dahlgaard, Knudsen and St\"ockel's [STOC 2017] algorithm for detecting a $2k$-cycle. Our main technical contribution is the analysis of the algorithm which involves a type of ``supersaturation'' lemma relating the number of $2k$-cycles in a bipartite graph to the sizes of the parts in the bipartition and the number of edges. We also give a simplified analysis of Dahlgaard, Knudsen and St\"ockel's $2k$-cycle detection algorithm (with a small polylogarithmic increase in the running time), which is helpful in analyzing our listing algorithm.
Density deconvolution deals with the estimation of the probability density function $f$ of a random signal from $n\geq1$ data observed with independent and known additive random noise. This is a classical problem in statistics, for which frequentist and Bayesian nonparametric approaches are available to estimate $f$ in static or batch domains. In this paper, we consider the problem of density deconvolution in a streaming or online domain, and develop a principled sequential approach to estimate $f$. By relying on a quasi-Bayesian sequential (learning) model for the data, often referred to as Newton's algorithm, we obtain a sequential deconvolution estimate $f_{n}$ of $f$ that is of easy evaluation, computationally efficient, and with constant computational cost as data increase, which is desirable for streaming data. In particular, local and uniform Gaussian central limit theorems for $f_{n}$ are established, leading to asymptotic credible intervals and bands for $f$, respectively. We provide the sequential deconvolution estimate $f_{n}$ with large sample asymptotic guarantees under the quasi-Bayesian sequential model for the data, proving a merging with respect to the direct density estimation problem, and also under a ``true" frequentist model for the data, proving consistency. An empirical validation of our methods is presented on synthetic and real data, also comparing with respect to a kernel approach and a Bayesian nonparametric approach with a Dirichlet process mixture prior.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191