Let $\mathscr{F}_{n,d}$ be the class of all functions $f:\{-1,1\}^n\to[-1,1]$ on the $n$-dimensional discrete hypercube of degree at most $d$. In the first part of this paper, we prove that any (deterministic or randomized) algorithm which learns $\mathscr{F}_{n,d}$ with $L_2$-accuracy $\varepsilon$ requires at least $\Omega((1-\sqrt{\varepsilon})2^d\log n)$ queries for large enough $n$, thus establishing the sharpness as $n\to\infty$ of a recent upper bound of Eskenazis and Ivanisvili (2021). To do this, we show that the $L_2$-packing numbers $\mathsf{M}(\mathscr{F}_{n,d},\|\cdot\|_{L_2},\varepsilon)$ of the concept class $\mathscr{F}_{n,d}$ satisfy the two-sided estimate $$c(1-\varepsilon)2^d\log n \leq \log \mathsf{M}(\mathscr{F}_{n,d},\|\cdot\|_{L_2},\varepsilon) \leq \frac{2^{Cd}\log n}{\varepsilon^4}$$ for large enough $n$, where $c, C>0$ are universal constants. In the second part of the paper, we present a logarithmic upper bound for the randomized query complexity of classes of bounded approximate polynomials whose Fourier spectra are concentrated on few subsets. As an application, we prove new estimates for the number of random queries required to learn approximate juntas of a given degree, functions with rapidly decaying Fourier tails and constant depth circuits of given size. Finally, we obtain bounds for the number of queries required to learn the polynomial class $\mathscr{F}_{n,d}$ without error in the query and random example models.
相關內容
The most popular method for computing the matrix logarithm is a combination of the inverse scaling and squaring method in conjunction with a Pad\'e approximation, sometimes accompanied by the Schur decomposition. The main computational effort lies in matrix-matrix multiplications and left matrix division. In this work we illustrate that the number of such operations can be substantially reduced, by using a graph based representation of an efficient polynomial evaluation scheme. A technique to analyze the rounding error is proposed, and backward error analysis is adapted. We provide substantial simulations illustrating competitiveness both in terms of computation time and rounding errors.
We present a novel discontinuous Galerkin finite element method for numerical simulations of the rotating thermal shallow water equations in complex geometries using curvilinear meshes, with arbitrary accuracy. We derive an entropy functional which is convex, and which must be preserved in order to preserve model stability at the discrete level. The numerical method is provably entropy stable and conserves mass, buoyancy, vorticity, and energy. This is achieved by using novel entropy stable numerical fluxes, summation-by-parts principle, and splitting the pressure and convection operators so that we can circumvent the use of chain rule at the discrete level. Numerical simulations on a cubed sphere mesh are presented to verify the theoretical results. The numerical experiments demonstrate the robustness of the method for a regime of well developed turbulence, where it can be run stably without any dissipation. The entropy stable fluxes are sufficient to control the grid scale noise generated by geostrophic turbulence, eliminating the need for artificial stabilisation.
Given $n$ copies of an unknown quantum state $\rho\in\mathbb{C}^{d\times d}$, quantum state certification is the task of determining whether $\rho=\rho_0$ or $\|\rho-\rho_0\|_1>\varepsilon$, where $\rho_0$ is a known reference state. We study quantum state certification using unentangled quantum measurements, namely measurements which operate only on one copy of $\rho$ at a time. When there is a common source of shared randomness available and the unentangled measurements are chosen based on this randomness, prior work has shown that $\Theta(d^{3/2}/\varepsilon^2)$ copies are necessary and sufficient. This holds even when the measurements are allowed to be chosen adaptively. We consider deterministic measurement schemes (as opposed to randomized) and demonstrate that ${\Theta}(d^2/\varepsilon^2)$ copies are necessary and sufficient for state certification. This shows a separation between algorithms with and without shared randomness. We develop a unified lower bound framework for both fixed and randomized measurements, under the same theoretical framework that relates the hardness of testing to the well-established L\"uders rule. More precisely, we obtain lower bounds for randomized and fixed schemes as a function of the eigenvalues of the L\"uders channel which characterizes one possible post-measurement state transformation.
The structured $\varepsilon$-stability radius is introduced as a quantity to assess the robustness of transient bounds of solutions to linear differential equations under structured perturbations of the matrix. This applies to general linear structures such as complex or real matrices with a given sparsity pattern or with restricted range and corange, or special classes such as Toeplitz matrices. The notion conceptually combines unstructured and structured pseudospectra in a joint pseudospectrum, allowing for the use of resolvent bounds as with unstructured pseudospectra and for structured perturbations as with structured pseudospectra. We propose and study an algorithm for computing the structured $\varepsilon$-stability radius. This algorithm solves eigenvalue optimization problems via suitably discretized rank-1 matrix differential equations that originate from a gradient system. The proposed algorithm has essentially the same computational cost as the known rank-1 algorithms for computing unstructured and structured stability radii. Numerical experiments illustrate the behavior of the algorithm.
We introduce a strict saddle property for $\ell_p$ regularized functions, and propose an iterative reweighted $\ell_1$ algorithm to solve the $\ell_p$ regularized problems. The algorithm is guaranteed to converge only to local minimizers when randomly initialized. The strict saddle property is shown generic on these sparse optimization problems. Those analyses as well as the proposed algorithm can be easily extended to general nonconvex regularized problems.
We prove discrete versions of the first and second Weber inequalities on $\boldsymbol{H}(\mathbf{curl})\cap\boldsymbol{H}(\mathrm{div}_{\eta})$-like hybrid spaces spanned by polynomials attached to the faces and to the cells of a polyhedral mesh. The proven hybrid Weber inequalities are optimal in the sense that (i) they are formulated in terms of $\boldsymbol{H}(\mathbf{curl})$- and $\boldsymbol{H}(\mathrm{div}_{\eta})$-like hybrid semi-norms designed so as to embed optimally (polynomially) consistent face penalty terms, and (ii) they are valid for face polynomials in the smallest possible stability-compatible spaces. Our results are valid on domains with general, possibly non-trivial topology. In a second part we also prove, within a general topological setting, related discrete Maxwell compactness properties.
We show how to sample in parallel from a distribution $\pi$ over $\mathbb R^d$ that satisfies a log-Sobolev inequality and has a smooth log-density, by parallelizing the Langevin (resp. underdamped Langevin) algorithms. We show that our algorithm outputs samples from a distribution $\hat\pi$ that is close to $\pi$ in Kullback--Leibler (KL) divergence (resp. total variation (TV) distance), while using only $\log(d)^{O(1)}$ parallel rounds and $\widetilde{O}(d)$ (resp. $\widetilde O(\sqrt d)$) gradient evaluations in total. This constitutes the first parallel sampling algorithms with TV distance guarantees. For our main application, we show how to combine the TV distance guarantees of our algorithms with prior works and obtain RNC sampling-to-counting reductions for families of discrete distribution on the hypercube $\{\pm 1\}^n$ that are closed under exponential tilts and have bounded covariance. Consequently, we obtain an RNC sampler for directed Eulerian tours and asymmetric determinantal point processes, resolving open questions raised in prior works.
In this work, we study the Hermite interpolation on $n$-dimensional non-equally spaced, rectilinear grids over a field $\Bbbk $ of characteristic zero, given the values of the function at each point of the grid and the partial derivatives up to a maximum degree. First, we prove the uniqueness of the interpolating polynomial, and we further obtain a compact closed form that uses a single summation, irrespective of the dimensionality, which is algebraically simpler than the only alternative closed form for the $n$-dimensional classical Hermite interpolation [1]. We provide the remainder of the interpolation in integral form; we derive the ideal of the interpolation and express the interpolation remainder using only polynomial divisions, in the case of interpolating a polynomial function. Moreover, we prove the continuity of Hermite polynomials defined on adjacent $n$-dimensional grids, thus establishing spline behavior. Finally, we perform illustrative numerical examples to showcase the applicability and high accuracy of the proposed interpolant, in the simple case of few points, as well as hundreds of points on 3D-grids using a spline-like interpolation, which compares favorably to state-of-the-art spline interpolation methods.
Dirac delta distributionally sourced differential equations emerge in many dynamical physical systems from neuroscience to black hole perturbation theory. Most of these lack exact analytical solutions and are thus best tackled numerically. This work describes a generic numerical algorithm which constructs discontinuous spatial and temporal discretisations by operating on discontinuous Lagrange and Hermite interpolation formulae recovering higher order accuracy. It is shown by solving the distributionally sourced wave equation, which has analytical solutions, that numerical weak-form solutions can be recovered to high order accuracy by solving a first-order reduced system of ordinary differential equations. The method-of-lines framework is applied to the DiscoTEX algorithm i.e through discontinuous collocation with implicit-turned-explicit (IMTEX) integration methods which are symmetric and conserve symplectic structure. Furthermore, the main application of the algorithm is proved, for the first-time, by calculating the amplitude at any desired location within the numerical grid, including at the position (and at its right and left limit) where the wave- (or wave-like) equation is discontinuous via interpolation using DiscoTEX. This is shown, firstly by solving the wave- (or wave-like) equation and comparing the numerical weak-form solution to the exact solution. Finally, one shows how to reconstruct the scalar and gravitational metric perturbations from weak-form numerical solutions of a non-rotating black hole, which do not have known exact analytical solutions, and compare against state-of-the-art frequency domain results. One concludes by motivating how DiscoTEX, and related algorithms, open a promising new alternative Extreme-Mass-Ratio-Inspiral (EMRI)s waveform generation route via a self-consistent evolution for the gravitational self-force programme in the time-domain.
A set $S$ of vertices of a digraph $D$ is called an open neighbourhood locating-dominating set if every vertex in $D$ has an in-neighbour in $S$, and for every pair $u,v$ of vertices of $D$, there is a vertex in $S$ that is an in-neighbour of exactly one of $u$ and $v$. The smallest size of an open neighbourhood locating-dominating set of a digraph $D$ is denoted by $\gamma_{OL}(D)$. We study the class of digraphs $D$ whose only open neighbourhood locating-dominating set consists of the whole set of vertices, in other words, $\gamma_{OL}(D)$ is equal to the order of $D$. We call those digraphs extremal. By considering digraphs with loops allowed, our definition also applies to the related (and more widely studied) concept of identifying codes. We extend previous studies from the literature for both open neighbourhood locating-dominating sets and identifying codes of both undirected and directed graphs. These results all correspond to studying open neighbourhood locating-dominating sets on special classes of digraphs. To do so, we prove general structural properties of extremal digraphs, and we describe how they can all be constructed. We then use these properties to give new proofs of several known results from the literature. We also give a recursive and constructive characterization of the extremal di-trees (digraphs whose underlying undirected graph is a tree).
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191