Transcript Deterministic Random Walks - Max Planck Institute for Informatics

Component-by-Component Construction
of Low-Discrepancy Point Sets
Benjamin Doerr
Max-Planck-Institut für Informatik
Saarbrücken
joint work with Michael Gnewuch (Kiel), Peter Kritzer (Salzburg),
and Friedrich Pillichshammer (Linz)
Reminder: Star Discrepancy
 Definition:
– s ∈ N “dimension” (Austrian notation)
– P = {p0, p1, ..., pN-1} multi-set of N points in [0,1)s
– Discrepancy function: For x ∈ [0,1]s,
 Δ(x,P) := λ([0,x)) – #{i : pi ∈ [0,x)} / N
 “(how many points should be in [0,x) – how many actually
are there) normalized by N”
– Star discrepancy:
D*(P) := sup{ |Δ(x,P)| : x ∈ [0,1]s}
 Measure of how evenly P is distributed in [0,1)s
Benjamin Doerr
Reminder: Star Discrepancy
 Application: Numerical Integration
– Given f : [0,1]s → R
– Compute/estimate ∫[0,1]s f(x) dx !
 Hope: ∫[0,1]s f(x) dx ≈ (1/N) ∑i f(pi)
 Koksma-Hlawka inequality:
| ∫[0,1]s f(x) dx - (1/N) ∑i f(pi) | ≤ V(f) D*(P)
– V(f): Variation in the sense of Hardy and Krause
 Low star discrepancy = good integration 
Benjamin Doerr
Reminder: Star Discrepancy
 How good?
Benjamin Doerr
Reminder: Star Discrepancy
 Very good! There are N-point sets P with
D*(P) ≤ Cs (log N)s-1 / N
 “More points = drastically reduced integration error”
 Really?
Note: All constants ‘C’ may be different. They never depend
on N. If they depend on s, I call them ‘Cs’.
Benjamin Doerr
Reminder: Star Discrepancy
 Very good! – There are N-point sets P with
D*(P) ≤ Cs (log N)s-1 / N
 “More points = drastically reduced integration error”
 Really? No!
Benjamin Doerr
Problem: Only good for many points!
– Increasing for N ≤ e10 (more points = worse integration?)
– ≥ 1 (trivial bound), if N ≤ 1010
– ≥ D*(random point set), if N ≤ 102∙10
Need for “small” low-discrepancy point sets!
Benjamin Doerr
Motivation, Outline
 Previous slides:
– O((log N)s-1/N) bounds only good for many points
 many: at least exponential in dimension.
– Otherwise: Random points have better guarantees.
 Plan for this talk:
– Be inspired by random points
– ...and use this to construct better point sets 
 Note: Almost all ugly details omitted in this talk!
– For many technicalities, the sharpest bounds and more
results see the full paper (MCMAppl, to appear).
Benjamin Doerr
Previous Work (1)
 Heinrich, Novak, Wasilkowski, Woźniakowski (Acta
Arith., 2002):
– There are point sets with D*(P) ≤ C (s/N)1/2
 randomized construction
 Talagrand inequality
–  Good bounds for N polynomial in s
–  Existential result only, implicit constants not known
Benjamin Doerr
Previous Work (2)
 We build on previous results by D., Gnewuch,
Srivastav (JoC ‘05, MCQMC ’06):
– D*(P) ≤ C (s/N)1/2 (log N)1/2, C small
– via randomized rounding:
 discrepancy guarantee holds with high probability
– derandomization:
 deterministic construction of P in run-time (CN)s+2
 computes the exact star discrepancy on the way
– wait for Michael’s talk (next talk) to see how difficult
computing the star discrepancy can be...
Benjamin Doerr
Rounding Approach
 Task: Put N = 16 points in the unit cube nicely
Benjamin Doerr
Rounding Approach
 Task: Put N = 16 points in the unit cube nicely
 Partition the cube into small rectangles (“boxes”)
Benjamin Doerr
Rounding Approach
0.875
1.09375
1.96875
1.2656..
3.0625
1.96875
 Task: Put N = 16 points in the unit cube nicely
 Partition the cube into small rectangles (“boxes”)
 Compute the ‘fair’ number xB of points for each box B: xB = N vol(B)
Benjamin Doerr
Rounding Approach
0.875




0.5625 0.31..
1
0
1
0
1.09375
0.7031..
1
1
0
1
1.96875
1.2656..
2
1
1
0
3.0625
1.96875
3
2
1
1
Task: Put N = 16 points in the unit cube nicely
Partition the cube into small rectangles (“boxes”)
Compute the ‘fair’ number xB of points for each box B: xB = N vol(B)
Round these numbers to integers yB ...
Benjamin Doerr
Rounding Approach
0.875
0.5625 0.31..
1
0
1
0
1.09375
0.7031..
1
1
0
1
1.96875
1.2656..
2
1
1
0
3.0625
1.96875
3
2
1
1
xC=12.25




yC=12
Task: Put N = 16 points in the unit cube nicely
Partition the cube into small rectangles (“boxes”)
Compute the ‘fair’ number xB of points for each box B: xB = N vol(B)
Round these numbers to integers yB such that for all aligned corners C,
yC := ∑B⊆CyB is close to xC := ∑B⊆CxB.
Benjamin Doerr
Rounding Approach
0.875




0.5625 0.31..
1
0
1
0
1.09375
0.7031..
1
1
0
1
1.96875
1.2656..
2
1
1
0
3.0625
1.96875
3
2
1
1
Task: Put N = 16 points in the unit cube nicely
Partition the cube into small rectangles (“boxes”)
Compute the ‘fair’ number xB of points for each box B: xB = N vol(B)
Round these numbers to integers yB such that for all aligned corners C,
yC := ∑B⊆CyB is close to xC := ∑B⊆CxB. Then put yB points in B arbitrarily.
Benjamin Doerr
Classical Rounding Theory
 Let x1, ..., xn be numbers, N:=||x||1 and I1, ..., Im ⊆ {1, ...,n}.
 Randomized Rounding:
– If xi is an integer, yi := xi
– If not, then yi := ⌈xi⌉ with probability equal to the fractional part of xi
and yi := ⌊xi⌋ otherwise
 Theorem: With probability 1-ε, we have for all 1 ≤ k ≤ m
(*)
| ∑i ∈ I
k
yi - ∑i ∈ I xi | ≤ (0.5 N log(2m/ε))1/2
k
 Derandomization: A rounding (yi) satisfying (*) with ε=1 can
be computed deterministically in time O(mn).
 Experiment: Derandomization yields smaller rounding errors.
Benjamin Doerr
Rounding Approach (continued)
0.875




0.5625 0.31..
1
0
1
0
1.09375
0.7031..
1
1
0
1
1.96875
1.2656..
2
1
1
0
3.0625
1.96875
3
2
1
1
Task: Put N = 16 points in the unit cube nicely
Partition the cube into small rectangles (“boxes”)
Compute the ‘fair’ number xB of points for each box B: xB = N vol(B)
Round these numbers to integers yB such that for all aligned corners C,
| ∑B⊆CyB - ∑B⊆CxB | ≤ (0.5 N log(2 #boxes))1/2 ...
Benjamin Doerr
New Result:
 The same can be done in a component-by-component way:
– Compoment-by-compoment: Given an (s-1)-dimensional lowdiscrepancy point set, add an sth component to each point.
– Adjust the randomized-rounding approach accordingly.
 Advantage:
– Fewer variables to be rounded in each iteration.
– Total run-time (over all s iterations) roughly N(s+3)/2 instead of Ns+2.
 Surprise: Discrepancy increases only by a factor of s.
– Roughly C s3/2 N-1/2 log(N)1/2 instead of C s1/2 N-1/2 log(N)1/2
 That’s OK, because we can now compute N2 points in
roughly the same time as needed for N points before.
Benjamin Doerr
Summary and Conclusion
 Result: Component-by-Component derandomized
construction is much faster and yields only slightly higher
discrepancies compared to “all at once”.
 Outlook: Could also be useful if components are of different
importance. E.g., do the expensive derandomization only
for few components.
 Open problem: Come up with something really efficient....
(instead of NCs).
Merci/Thanks!
Benjamin Doerr