Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Sharp Discrepancy Bound for Jittered Sampling
95
0
0.0
(
0
)
Added by
Benjamin Doerr
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Benjamin Doerr
Ask ChatGPT about the research
No Arabic abstract
For $m, d in {mathbb N}$, a jittered sampling point set $P$ having $N = m^d$ points in $[0,1)^d$ is constructed by partitioning the unit cube $[0,1)^d$ into $m^d$ axis-aligned cubes of equal size and then placing one point independently and uniformly at random in each cube. We show that there are constants $c ge 0$ and $C$ such that for all $d$ and all $m ge d$ the expected non-normalized star discrepancy of a jittered sampling point set satisfies [c ,dm^{frac{d-1}{2}} sqrt{1 + log(tfrac md)} le {mathbb E} D^*(P) le C, dm^{frac{d-1}{2}} sqrt{1 + log(tfrac md)}.] This discrepancy is thus smaller by a factor of $Thetabig(sqrt{frac{1+log(m/d)}{m/d}},big)$ than the one of a uniformly distributed random point set of $m^d$ points. This result improves both the upper and the lower bound for the discrepancy of jittered sampling given by Pausinger and Steinerberger (Journal of Complexity (2016)). It also removes the asymptotic requirement that $m$ is sufficiently large compared to $d$.
rate research
Read More
In the stochastic online vector balancing problem, vectors $v_1,v_2,ldots,v_T$ chosen independently from an arbitrary distribution in $mathbb{R}^n$ arrive one-by-one and must be immediately given a $pm$ sign. The goal is to keep the norm of the discrepancy vector, i.e., the signed prefix-sum, as small as possible for a given target norm. We consider some of the most well-known problems in discrepancy theory in the above online stochastic setting, and give algorithms that match the known offline bounds up to $mathsf{polylog}(nT)$ factors. This substantially generalizes and improves upon the previous results of Bansal, Jiang, Singla, and Sinha (STOC 20). In particular, for the Koml{o}s problem where $|v_t|_2leq 1$ for each $t$, our algorithm achieves $tilde{O}(1)$ discrepancy with high probability, improving upon the previous $tilde{O}(n^{3/2})$ bound. For Tusn{a}dys problem of minimizing the discrepancy of axis-aligned boxes, we obtain an $O(log^{d+4} T)$ bound for arbitrary distribution over points. Previous techniques only worked for product distributions and gave a weaker $O(log^{2d+1} T)$ bound. We also consider the Banaszczyk setting, where given a symmetric convex body $K$ with Gaussian measure at least $1/2$, our algorithm achieves $tilde{O}(1)$ discrepancy with respect to the norm given by $K$ for input distributions with sub-exponential tails. Our key idea is to introduce a potential that also enforces constraints on how the discrepancy vector evolves, allowing us to maintain certain anti-concentration properties. For the Banaszczyk setting, we further enhance this potential by combining it with ideas from generic chaining. Finally, we also extend these results to the setting of online multi-color discrepancy.
Consider a unit interval $[0,1]$ in which $n$ points arrive one-by-one independently and uniformly at random. On arrival of a point, the problem is to immediately and irrevocably color it in ${+1,-1}$ while ensuring that every interval $[a,b] subseteq [0,1]$ is nearly-balanced. We define emph{discrepancy} as the largest imbalance of any interval during the entire process. If all the arriving points were known upfront then we can color them alternately to achieve a discrepancy of $1$. What is the minimum possible expected discrepancy when we color the points online? We show that the discrepancy of the above problem is sub-polynomial in $n$ and that no algorithm can achieve a constant discrepancy. This is a substantial improvement over the trivial random coloring that only gets an $widetilde{O}(sqrt n)$ discrepancy. We then obtain similar results for a natural generalization of this problem to $2$-dimensions where the points arrive uniformly at random in a unit square. This generalization allows us to improve recent results of Benade et al.cite{BenadeKPP-EC18} for the online envy minimization problem when the arrivals are stochastic.
For the $h$-finite-element method ($h$-FEM) applied to the Helmholtz equation, the question of how quickly the meshwidth $h$ must decrease with the frequency $k$ to maintain accuracy as $k$ increases has been studied since the mid 80s. Nevertheless, there still do not exist in the literature any $k$-explicit bounds on the relative error of the FEM solution (the measure of the FEM error most often used in practical applications), apart from in one dimension. The main result of this paper is the sharp result that, for the lowest fixed-order conforming FEM (with polynomial degree, $p$, equal one), the condition $h^2 k^3$ sufficiently small is sufficient for the relative error of the FEM solution in 2 or 3 dimensions to be controllably small (independent of $k$) for scattering of a plane wave by a nontrapping obstacle and/or a nontrapping inhomogeneous medium. We also prove relative-error bounds on the FEM solution for arbitrary fixed-order methods applied to scattering by a nontrapping obstacle, but these bounds are not sharp for $pgeq 2$. A key ingredient in our proofs is a result describing the oscillatory behaviour of the solution of the plane-wave scattering problem, which we prove using semiclassical defect measures.
Let $mathcal{H}$ be a $t$-regular hypergraph on $n$ vertices and $m$ edges. Let $M$ be the $m times n$ incidence matrix of $mathcal{H}$ and let us denote $lambda =max_{v perp overline{1},|v| = 1}|Mv|$. We show that the discrepancy of $mathcal{H}$ is $O(sqrt{t} + lambda)$. As a corollary, this gives us that for every $t$, the discrepancy of a random $t$-regular hypergraph with $n$ vertices and $m geq n$ edges is almost surely $O(sqrt{t})$ as $n$ grows. The proof also gives a polynomial time algorithm that takes a hypergraph as input and outputs a coloring with the above guarantee.
Let Pd denote the space of all real polynomials of degree at most d. It is an old result of Stein and Wainger that for every polynomial P in Pd: |p.v.int_R {e^{iP(t)} dt/t} | < C(d) for some constant C(d) depending only on d. On the other hand, Carbery, Wainger and Wright claim that the true order of magnitude of the above principal value integral is log d. We prove this conjecture.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
