For Lagrange polynomial interpolation on open arcs $X=\gamma$ in $\CC$, it is well-known that the Lebesgue constant for the family of Chebyshev points ${\bf{x}}_n:=\{x_{n,j}\}^{n}_{j=0}$ on $[-1,1]\subset \RR$ has growth order of $O(log(n))$. The same growth order was shown in \cite{ZZ} for the Lebesgue constant of the family ${\bf {z^{**}_n}}:=\{z_{n,j}^{**}\}^{n}_{j=0}$ of some properly adjusted Fej\'er points on a rectifiable smooth open arc $\gamma\subset \CC$. On the other hand, in our recent work \cite{CZ2021}, it was observed that if the smooth open arc $\gamma$ is replaced by an $L$-shape arc $\gamma_0 \subset \CC$ consisting of two line segments, numerical experiments suggest that the Marcinkiewicz-Zygmund inequalities are no longer valid for the family of Fej\'er points ${\bf z}_n^{*}:=\{z_{n,j}^{*}\}^{n}_{j=0}$ on $\gamma$, and that the rate of growth for the corresponding Lebesgue constant $L_{{\bf {z}}^{*}_n}$ is as fast as $c\,log^2(n)$ for some constant $c>0$. The main objective of the present paper is 3-fold: firstly, it will be shown that for the special case of the $L$-shape arc $\gamma_0$ consisting of two line segments of the same length that meet at the angle of $\pi/2$, the growth rate of the Lebesgue constant $L_{{\bf {z}}_n^{*}}$ is at least as fast as $O(Log^2(n))$, with $\lim\sup \frac{L_{{\bf {z}}_n^{*}}}{log^2(n)} = \infty$; secondly, the corresponding (modified) Marcinkiewicz-Zygmund inequalities fail to hold; and thirdly, a proper adjustment ${\bf z}_n^{**}:=\{z_{n,j}^{**}\}^{n}_{j=0}$ of the Fej\'er points on $\gamma$ will be described to assure the growth rate of $L_{{\bf z}_n^{**}}$ to be exactly $O(Log^2(n))$.
相關內容
We consider the problem of simultaneous learning in stochastic games with many players in the finite-horizon setting. While the typical target solution for a stochastic game is a Nash equilibrium, this is intractable with many players. We instead focus on variants of {\it correlated equilibria}, such as those studied for extensive-form games. We begin with a hardness result for the adversarial MDP problem: even for a horizon of 3, obtaining sublinear regret against the best non-stationary policy is \textsf{NP}-hard when both rewards and transitions are adversarial. This implies that convergence to even the weakest natural solution concept -- normal-form coarse correlated equilbrium -- is not possible via black-box reduction to a no-regret algorithm even in stochastic games with constant horizon (unless $\textsf{NP}\subseteq\textsf{BPP}$). Instead, we turn to a different target: algorithms which {\it generate} an equilibrium when they are used by all players. Our main result is algorithm which generates an {\it extensive-form} correlated equilibrium, whose runtime is exponential in the horizon but polynomial in all other parameters. We give a similar algorithm which is polynomial in all parameters for "fast-mixing" stochastic games. We also show a method for efficiently reaching normal-form coarse correlated equilibria in "single-controller" stochastic games which follows the traditional no-regret approach. When shared randomness is available, the two generative algorithms can be extended to give simultaneous regret bounds and converge in the traditional sense.
An $r$-quasiplanar graph is a graph drawn in the plane with no $r$ pairwise crossing edges. Let $s \geq 3$ be an integer and $r=2^s$. We prove that there is a constant $C$ such that every $r$-quasiplanar graph with $n \geq r$ vertices has at most $n\left(Cs^{-1}\log n\right)^{2s-4}$ edges. A graph whose vertices are continuous curves in the plane, two being connected by an edge if and only if they intersect, is called a string graph. We show that for every $\epsilon>0$, there exists $\delta>0$ such that every string graph with $n$ vertices, whose chromatic number is at least $n^{\epsilon}$ contains a clique of size at least $n^{\delta}$. A clique of this size or a coloring using fewer than $n^{\epsilon}$ colors can be found by a polynomial time algorithm in terms of the size of the geometric representation of the set of strings. In the process, we use, generalize, and strengthen previous results of Lee, Tomon, and others. All of our theorems are related to geometric variants of the following classical graph-theoretic problem of Erdos, Gallai, and Rogers. Given a $K_r$-free graph on $n$ vertices and an integer $s<r$, at least how many vertices can we find such that the subgraph induced by them is $K_s$-free?
We develop a hybrid spatial discretization for the wave equation in second order form, based on high-order accurate finite difference methods and discontinuous Galerkin methods. The hybridization combines computational efficiency of finite difference methods on Cartesian grids and geometrical flexibility of discontinuous Galerkin methods on unstructured meshes. The two spatial discretizations are coupled by a penalty technique at the interface such that the overall semidiscretization satisfies a discrete energy estimate to ensure stability. In addition, optimal convergence is obtained in the sense that when combining a fourth order finite difference method with a discontinuous Galerkin method using third order local polynomials, the overall convergence rate is fourth order. Furthermore, we use a novel approach to derive an error estimate for the semidiscretization by combining the energy method and the normal mode analysis for a corresponding one dimensional model problem. The stability and accuracy analysis are verified in numerical experiments.
The local discontinuous Galerkin (LDG) method is studied for a third-order singularly perturbed problem of the convection-diffusion type. Based on a regularity assumption for the exact solution, we prove almost $O(N^{-(k+1/2)})$ (up to a logarithmic factor) energy-norm convergence uniformly in the perturbation parameter. Here, $k\geq 0$ is the maximum degree of piecewise polynomials used in discrete space, and $N$ is the number of mesh elements. The results are valid for the three types of layer-adapted meshes: Shishkin-type, Bakhvalov-Shishkin type, and Bakhvalov-type. Numerical experiments are conducted to test the theoretical results.
We study the problem of covering and learning sums $X = X_1 + \cdots + X_n$ of independent integer-valued random variables $X_i$ (SIIRVs) with unbounded, or even infinite, support. De et al. at FOCS 2018, showed that the maximum value of the collective support of $X_i$'s necessarily appears in the sample complexity of learning $X$. In this work, we address two questions: (i) Are there general families of SIIRVs with unbounded support that can be learned with sample complexity independent of both $n$ and the maximal element of the support? (ii) Are there general families of SIIRVs with unbounded support that admit proper sparse covers in total variation distance? As for question (i), we provide a set of simple conditions that allow the unbounded SIIRV to be learned with complexity $\text{poly}(1/\epsilon)$ bypassing the aforementioned lower bound. We further address question (ii) in the general setting where each variable $X_i$ has unimodal probability mass function and is a different member of some, possibly multi-parameter, exponential family $\mathcal{E}$ that satisfies some structural properties. These properties allow $\mathcal{E}$ to contain heavy tailed and non log-concave distributions. Moreover, we show that for every $\epsilon > 0$, and every $k$-parameter family $\mathcal{E}$ that satisfies some structural assumptions, there exists an algorithm with $\tilde{O}(k) \cdot \text{poly}(1/\epsilon)$ samples that learns a sum of $n$ arbitrary members of $\mathcal{E}$ within $\epsilon$ in TV distance. The output of the learning algorithm is also a sum of random variables whose distribution lies in the family $\mathcal{E}$. En route, we prove that any discrete unimodal exponential family with bounded constant-degree central moments can be approximated by the family corresponding to a bounded subset of the initial (unbounded) parameter space.
Imposition methods of interface conditions for the second-order wave equation with non-conforming grids is considered. The spatial discretization is based on high order finite differences with summation-by-parts properties. Previously presented solution methods for this problem, based on the simultaneous approximation term (SAT) method, have shown to introduce significant stiffness. This can lead to highly inefficient schemes. Here, two new methods of imposing the interface conditions to avoid the stiffness problems are presented: 1) a projection method and 2) a hybrid between the projection method and the SAT method. Numerical experiments are performed using traditional and order-preserving interpolation operators. Both of the novel methods retain the accuracy and convergence behavior of the previously developed SAT method but are significantly less stiff.
This work is concerned with approximating a trivariate function defined on a tensor-product domain via function evaluations. Combining tensorized Chebyshev interpolation with a Tucker decomposition of low multilinear rank yields function approximations that can be computed and stored very efficiently. The existing Chebfun3 algorithm [Hashemi and Trefethen, SIAM J. Sci. Comput., 39 (2017)]uses a similar format but the construction of the approximation proceeds indirectly, via a so called slice-Tucker decomposition. As a consequence, Chebfun3 sometimes uses unnecessarily many function evaluations and does not fully benefit from the potential of the Tucker decomposition to reduce, sometimes dramatically, the computational cost. We propose a novel algorithm Chebfun3F that utilizes univariate fibers instead of bivariate slices to construct the Tucker decomposition. Chebfun3F reduces the cost for the approximation in terms of the number of function evaluations for nearly all functions considered, typically by 75%, and sometimes by over 98%.
We study a variant of classical clustering formulations in the context of algorithmic fairness, known as diversity-aware clustering. In this variant we are given a collection of facility subsets, and a solution must contain at least a specified number of facilities from each subset while simultaneously minimizing the clustering objective ($k$-median or $k$-means). We investigate the fixed-parameter tractability of these problems and show several negative hardness and inapproximability results, even when we afford exponential running time with respect to some parameters. Motivated by these results we identify natural parameters of the problem, and present fixed-parameter approximation algorithms with approximation ratios $\big(1 + \frac{2}{e} +\epsilon \big)$ and $\big(1 + \frac{8}{e}+ \epsilon \big)$ for diversity-aware $k$-median and diversity-aware $k$-means respectively, and argue that these ratios are essentially tight assuming the gap-exponential time hypothesis. We also present a simple and more practical bicriteria approximation algorithm with better running time bounds. We finally propose efficient and practical heuristics. We evaluate the scalability and effectiveness of our methods in a wide variety of rigorously conducted experiments, on both real and synthetic data.
A burgeoning line of research has developed deep neural networks capable of approximating the solutions to high dimensional PDEs, opening related lines of theoretical inquiry focused on explaining how it is that these models appear to evade the curse of dimensionality. However, most theoretical analyses thus far have been limited to linear PDEs. In this work, we take a step towards studying the representational power of neural networks for approximating solutions to nonlinear PDEs. We focus on a class of PDEs known as \emph{nonlinear elliptic variational PDEs}, whose solutions minimize an \emph{Euler-Lagrange} energy functional $\mathcal{E}(u) = \int_\Omega L(\nabla u) dx$. We show that if composing a function with Barron norm $b$ with $L$ produces a function of Barron norm at most $B_L b^p$, the solution to the PDE can be $\epsilon$-approximated in the $L^2$ sense by a function with Barron norm $O\left(\left(dB_L\right)^{p^{\log(1/\epsilon)}}\right)$. By a classical result due to Barron [1993], this correspondingly bounds the size of a 2-layer neural network needed to approximate the solution. Treating $p, \epsilon, B_L$ as constants, this quantity is polynomial in dimension, thus showing neural networks can evade the curse of dimensionality. Our proof technique involves neurally simulating (preconditioned) gradient in an appropriate Hilbert space, which converges exponentially fast to the solution of the PDE, and such that we can bound the increase of the Barron norm at each iterate. Our results subsume and substantially generalize analogous prior results for linear elliptic PDEs.
Motivated by a recently established result saying that within the class of bivariate Archimedean copulas standard pointwise convergence implies weak convergence of almost all conditional distributions this contribution studies the class $\mathcal{C}_{ar}^d$ of all $d$-dimensional Archimedean copulas with $d \geq 3$ and proves the afore-mentioned implication with respect to conditioning on the first $d-1$ coordinates. Several proper\-ties equivalent to pointwise convergence in $\mathcal{C}_{ar}^d$ are established and - as by-product of working with conditional distributions (Markov kernels) - alternative simple proofs for the well-known formulas for the level set masses $\mu_C(L_t)$ and the Kendall distribution function $F_K^d$ as well as a novel geometrical interpretation of the latter are provided. Viewing normalized generators $\psi$ of $d$-dimensional Archimedean copulas from the perspective of their so-called Williamson measures $\gamma$ on $(0,\infty)$ is then shown to allow not only to derive surprisingly simple expressions for $\mu_C(L_t)$ and $F_K^d$ in terms of $\gamma$ and to characterize pointwise convergence in $\mathcal{C}_{ar}^d$ by weak convergence of the Williamson measures but also to prove that regularity/singularity properties of $\gamma$ directly carry over to the corresponding copula $C_\gamma \in \mathcal{C}_{ar}^d$. These results are finally used to prove the fact that the family of all absolutely continuous and the family of all singular $d$-dimensional copulas is dense in $\mathcal{C}_{ar}^d$ and to underline that despite of their simple algebraic structure Archimedean copulas may exhibit surprisingly singular behavior in the sense of irregularity of their conditional distribution functions.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191