Consider the problem of binary hypothesis testing. Given $Z$ coming from either $\mathbb P^{\otimes m}$ or $\mathbb Q^{\otimes m}$, to decide between the two with small probability of error it is sufficient and in most cases necessary to have $m \asymp 1/\epsilon^2$, where $\epsilon$ measures the separation between $\mathbb P$ and $\mathbb Q$ in total variation ($\mathsf{TV}$). Achieving this, however, requires complete knowledge of the distributions and can be done, for example, using the Neyman-Pearson test. In this paper we consider a variation of the problem, which we call likelihood-free (or simulation-based) hypothesis testing, where access to $\mathbb P$ and $\mathbb Q$ is given through $n$ iid observations from each. In the case when $\mathbb P,\mathbb Q$ are assumed to belong to a non-parametric family $\mathcal P$, we demonstrate the existence of a fundamental trade-off between $n$ and $m$ given by $nm \asymp n^2_\mathsf{GoF}(\epsilon,\cal P)$, where $n_\mathsf{GoF}$ is the minimax sample complexity of testing between the hypotheses $H_0: \mathbb P= \mathbb Q$ vs $H_1: \mathsf{TV}(\mathbb P,\mathbb Q) \ge \epsilon$. We show this for three families of distributions: $\beta$-smooth densities supported on $[0,1]^d$, the Gaussian sequence model over a Sobolev ellipsoid, and the collection of distributions on alphabet $[k]=\{1,2,\dots,k\}$ with pmfs bounded by $c/k$ for fixed $c$. For the larger family of all distributions on $[k]$ we obtain a more complicated trade-off that exhibits a phase-transition. The test that we propose, based on the $L^2$-distance statistic of Ingster, simultaneously achieves all points on the trade-off curve for the regular classes. This demonstrates the possibility of testing without fully estimating the distributions, provided $m\gg1/\epsilon^2$.
相關內容
Assuming the Exponential Time Hypothesis (ETH), a result of Marx (ToC'10) implies that there is no $f(k)\cdot n^{o(k/\log k)}$ time algorithm that can solve 2-CSPs with $k$ constraints (over a domain of arbitrary large size $n$) for any computable function $f$. This lower bound is widely used to show that certain parameterized problems cannot be solved in time $f(k)\cdot n^{o(k/\log k)}$ time (assuming the ETH). The purpose of this note is to give a streamlined proof of this result.
We propose a threshold-type algorithm to the $L^2$-gradient flow of the Canham-Helfrich functional generalized to $\mathbb{R}^N$. The algorithm to the Willmore flow is derived as a special case in $\mathbb{R}^2$ or $\mathbb{R}^3$. This algorithm is constructed based on an asymptotic expansion of the solution to the initial value problem for a fourth order linear parabolic partial differential equation whose initial data is the indicator function on the compact set $\Omega_0$. The crucial points are to prove that the boundary $\partial\Omega_1$ of the new set $\Omega_1$ generated by our algorithm is included in $O(t)$-neighborhood from $\partial\Omega_0$ for small time $t>0$ and to show that the derivative of the threshold function in the normal direction for $\partial\Omega_0$ is far from zero in the small time interval. Finally, numerical examples of planar curves governed by the Willmore flow are provided by using our threshold-type algorithm.
For the numerical solution of the cubic nonlinear Schr\"{o}dinger equation with periodic boundary conditions, a pseudospectral method in space combined with a filtered Lie splitting scheme in time is considered. This scheme is shown to converge even for initial data with very low regularity. In particular, for data in $H^s(\mathbb T^2)$, where $s>0$, convergence of order $\mathcal O(\tau^{s/2}+N^{-s})$ is proved in $L^2$. Here $\tau$ denotes the time step size and $N$ the number of Fourier modes considered. The proof of this result is carried out in an abstract framework of discrete Bourgain spaces, the final convergence result, however, is given in $L^2$. The stated convergence behavior is illustrated by several numerical examples.
Low-rank approximation of a matrix function, $f(A)$, is an important task in computational mathematics. Most methods require direct access to $f(A)$, which is often considerably more expensive than accessing $A$. Persson and Kressner (SIMAX 2023) avoid this issue for symmetric positive semidefinite matrices by proposing funNystr\"om, which first constructs a Nystr\"om approximation to $A$ using subspace iteration, and then uses the approximation to directly obtain a low-rank approximation for $f(A)$. They prove that the method yields a near-optimal approximation whenever $f$ is a continuous operator monotone function with $f(0) = 0$. We significantly generalize the results of Persson and Kressner beyond subspace iteration. We show that if $\widehat{A}$ is a near-optimal low-rank Nystr\"om approximation to $A$ then $f(\widehat{A})$ is a near-optimal low-rank approximation to $f(A)$, independently of how $\widehat{A}$ is computed. Further, we show sufficient conditions for a basis $Q$ to produce a near-optimal Nystr\"om approximation $\widehat{A} = AQ(Q^T AQ)^{\dagger} Q^T A$. We use these results to establish that many common low-rank approximation methods produce near-optimal Nystr\"om approximations to $A$ and therefore to $f(A)$.
We construct and analyze finite element approximations of the Einstein tensor in dimension $N \ge 3$. We focus on the setting where a smooth Riemannian metric tensor $g$ on a polyhedral domain $\Omega \subset \mathbb{R}^N$ has been approximated by a piecewise polynomial metric $g_h$ on a simplicial triangulation $\mathcal{T}$ of $\Omega$ having maximum element diameter $h$. We assume that $g_h$ possesses single-valued tangential-tangential components on every codimension-1 simplex in $\mathcal{T}$. Such a metric is not classically differentiable in general, but it turns out that one can still attribute meaning to its Einstein curvature in a distributional sense. We study the convergence of the distributional Einstein curvature of $g_h$ to the Einstein curvature of $g$ under refinement of the triangulation. We show that in the $H^{-2}(\Omega)$-norm, this convergence takes place at a rate of $O(h^{r+1})$ when $g_h$ is an optimal-order interpolant of $g$ that is piecewise polynomial of degree $r \ge 1$. We provide numerical evidence to support this claim.
We provide numerical bounds on the Crouzeix ratiofor KLS matrices $A$ which have a line segment on the boundary of the numerical range. The Crouzeix ratio is the supremum over all polynomials $p$ of the spectral norm of $p(A)$ dividedby the maximum absolute value of $p$ on the numerical range of $A$.Our bounds confirm the conjecture that this ratiois less than or equal to $2$. We also give a precise description of these numerical ranges.
We explore the maximum likelihood degree of a homogeneous polynomial $F$ on a projective variety $X$, $\mathrm{MLD}_F(X)$, which generalizes the concept of Gaussian maximum likelihood degree. We show that $\mathrm{MLD}_F(X)$ is equal to the count of critical points of a rational function on $X$, and give different geometric characterizations of it via topological Euler characteristic, dual varieties, and Chern classes.
Quasioptimal alternating projections and their use in low-rank approximation of matrices and tensors
We study the convergence of specific inexact alternating projections for two non-convex sets in a Euclidean space. The $\sigma$-quasioptimal metric projection ($\sigma \geq 1$) of a point $x$ onto a set $A$ consists of points in $A$ the distance to which is at most $\sigma$ times larger than the minimal distance $\mathrm{dist}(x,A)$. We prove that quasioptimal alternating projections, when one or both projections are quasioptimal, converge locally and linearly for super-regular sets with transversal intersection. The theory is motivated by the successful application of alternating projections to low-rank matrix and tensor approximation. We focus on two problems -- nonnegative low-rank approximation and low-rank approximation in the maximum norm -- and develop fast alternating-projection algorithms for matrices and tensor trains based on cross approximation and acceleration techniques. The numerical experiments confirm that the proposed methods are efficient and suggest that they can be used to regularise various low-rank computational routines.
We consider the task of estimating functions belonging to a specific class of nonsmooth functions, namely so-called tame functions. These functions appear in a wide range of applications: training deep learning, value functions of mixed-integer programs, or wave functions of small molecules. We show that tame functions are approximable by piecewise polynomials on any full-dimensional cube. We then present the first ever mixed-integer programming formulation of piecewise polynomial regression. Together, these can be used to estimate tame functions. We demonstrate promising computational results.
We build an asymptotically compatible energy of the variable-step L2-$1_{\sigma}$ scheme for the time-fractional Allen-Cahn model with the Caputo's fractional derivative of order $\alpha\in(0,1)$, under a weak step-ratio constraint $\tau_k/\tau_{k-1}\geq r_{\star}(\alpha)$ for $k\ge2$, where $\tau_k$ is the $k$-th time-step size and $r_{\star}(\alpha)\in(0.3865,0.4037)$ for $\alpha\in(0,1)$. It provides a positive answer to the open problem in [J. Comput. Phys., 414:109473], and, to the best of our knowledge, it is the first second-order nonuniform time-stepping scheme to preserve both the maximum bound principle and the energy dissipation law of time-fractional Allen-Cahn model. The compatible discrete energy is constructed via a novel discrete gradient structure of the second-order L2-$1_{\sigma}$ formula by a local-nonlocal splitting technique. It splits the discrete fractional derivative into two parts: one is a local term analogue to the trapezoid rule of the first derivative and the other is a nonlocal summation analogue to the L1 formula of Caputo derivative. Numerical examples with an adaptive time-stepping strategy are provided to show the effectiveness of our scheme and the asymptotic properties of the associated modified energy.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191