text: 34 LIOR BARY-SOROKER AND ARNO FEHM (cid:88) (cid:88) (cid:88) (cid:88) (cid:88) By (4.4) and (4.5), we conclude that r (σ) = r (xτ) = N r (τ) = 2n = n!2n = #H , n n τ n n ∈ ∈ ∈F ∈ ∈ (cid:104) (cid:105)σ Hn τ Sn x n2 τ Sn τ Sn (cid:3) and so r = 1. Hn Now we can compute the autocorrelation of r: ≥ ≥ − Theorem 4.4. Fix k 1, 1 (cid:15) > 0 and n > 2(cid:15) 1. Then for q an odd prime power, ∈ F ∈ F f [T ] monic of degree n and h , . . . , h [T ] of degree less than n and pairwise 0 q (cid:42) (cid:43) 1 k q distinct, (cid:89) k · (cid:104) (cid:105) − r (f + h ) = S r (f) k∈ + O (q 1/2) q i q,h q f Mn,q n,k | − | | | i=1 f f0 < f0 (cid:15) − = S + O (q 1/2) h n,k where the implied constant depends only on n and k, and S and S are deﬁned as in q,h h (1.13) and (1.14). · · · Proof. Apply Theorem 3.11 with ψ = = ψ = r. Note that Lemma 4.1 applies again, 1 k (cid:3) so the claim follow from Lemma 4.3. We now turn to cross-correlations of b and r with the prime indicator function 1P, which also have been studied by various authors: Starting from a conjecture of Hardy and Littlewood [HL24, Conjecture(cid:88)J] on the number of representations of an integer as the sum of two squares and a prime, [Hoo57, Theorem 2] proves an asymptotic formula for 1 (cid:104) − (cid:105) r(p + h) = r(n)1P(n h) ≤ x n x ≤ p x prime under the Extended Riemann Hypothesis, which [Bre62] then proves unconditionally. Mo- (cid:88) tohashi in [Mot70, Conjecture J*, Theorem 2] and [Mot71] gives a conjectural asymptotic formula for 1 − (cid:104) (cid:105) b(p 1) = b(n)1P(n + 1) ≤ − x n x 1 ≤ p x prime and proves upper and lower bounds. Iwaniec [Iwa72, p. 204] also proves lower and upper bounds and suggests a correction of Motohashi’s conjecture. We now give a function ﬁeld version of the Motohashi–Iwaniec conjecture (or rather a generalization of it from h = 1 to arbitrary h) and prove it in the large ﬁnite ﬁeld limit. ##LTLine## ##LTLine##

text: LIOR

text: BARY-SOROKER

text: AND

text: ARNO

text: FEHM

text: By

text: and

text: we

text: conclude

text: that

text: r

text: (σ)

text: r

text: (xτ)

text: N

text: r

text: (τ)

text: #H

text: n

text: n

text: τ

text: n

text: n

text: ∈F

text: Hn

text: τ

text: Sn

text: x

text: τ

text: Sn

text: τ

text: Sn

text: and

text: so

text: r

text: Hn

text: Now

text: we

text: can

text: compute

text: the

text: autocorrelation

text: of

text: r:

text: Theorem

text: Fix

text: k

text: and

text: n

text: Then

text: for

text: q

text: an

text: odd

text: prime

text: power,

text: F

text: F

text: f

text: [T

text: monic

text: of

text: degree

text: n

text: and

text: h

text: h

text: [T

text: of

text: degree

text: less

text: than

text: n

text: and

text: pairwise

text: q

text: k

text: q

text: distinct,

text: k

text: r

text: (f

text: h

text: S

text: r

text: (f)

text: k∈

text: O

text: (q

text: q

text: i

text: q,h

text: q

text: f

text: Mn,q

text: n,k

text: f

text: S

text: O

text: (q

text: h

text: n,k

text: where

text: the

text: implied

text: constant

text: depends

text: only

text: on

text: n

text: and

text: k,

text: and

text: S

text: and

text: S

text: are

text: deﬁned

text: as

text: in

text: q,h

text: h

text: and

text: Proof.

text: Apply

text: Theorem

text: with

text: ψ

text: ψ

text: r.

text: Note

text: that

text: Lemma

text: applies

text: again,

text: k

text: so

text: the

text: claim

text: follow

text: from

text: Lemma

text: We

text: now

text: turn

text: to

text: cross-correlations

text: of

text: b

text: and

text: r

text: with

text: the

text: prime

text: indicator

text: function

text: which

text: also

text: have

text: been

text: studied

text: by

text: various

text: authors:

text: Starting

text: from

text: a

text: conjecture

text: of

text: Hardy

text: and

text: Littlewood

text: on

text: the

text: number

text: of

text: representations

text: of

text: an

text: integer

text: as

text: the

text: sum

text: of

text: two

text: squares

text: and

text: a

text: prime,

text: Theorem

text: proves

text: an

text: asymptotic

text: formula

text: for

text: r(p

text: h)

text: h)

text: x

text: n

text: x

text: p

text: x

text: prime

text: under

text: the

text: Extended

text: Riemann

text: Hypothesis,

text: which

text: then

text: proves

text: unconditionally.

text: Mo-

text: tohashi

text: in

text: Conjecture

text: J*,

text: Theorem

text: and

text: gives

text: a

text: conjectural

text: asymptotic

text: formula

text: for

text: b(p

text: x

text: n

text: x

text: p

text: x

text: prime

text: and

text: proves

text: upper

text: and

text: lower

text: bounds.

text: Iwaniec

text: p.

text: also

text: proves

text: lower

text: and

text: upper

text: bounds

text: and

text: suggests

text: a

text: correction

text: of

text: Motohashi’s

text: conjecture.

text: We

text: now

text: give

text: a

text: function

text: ﬁeld

text: version

text: of

text: the

text: Motohashi–Iwaniec

text: conjecture

text: (or

text: rather

text: a

text: generalization

text: of

text: it

text: from

text: h

text: to

text: arbitrary

text: h)

text: and

text: prove

text: it

text: in

text: the

text: large

text: ﬁnite

text: ﬁeld

text: limit.

text: ##LTLine##

text: ##LTLine##


text: 38 LIOR BARY-SOROK(cid:18)ER AND ARN(cid:19)O FEHM − (cid:104) (cid:105) n + r 1 d = − . r Hn r 1 → (cid:18) (cid:19) Proof. Since dr,n factors through(cid:88)π : Hn Sn, we(cid:80)have (cid:88) − (cid:104) (cid:105) 1 1 + r 1 d,s λσ(d,1,s) 1 d = − = rω(τ) r Hn 2nn! ∈ r 1 n! ∈ σ Hn τ Sn where ω(τ) is the number of cycles of τ. Viewing rω(τ) as the number of partitions of { } 1, . . . , n into r sets that are unions of orbits of τ and changing order of summation we get that (cid:88) (cid:88) (cid:89) r (cid:96) rω(τ) = #A ! i ∈ { } τ Sn 1,...,n = ri=1 Ai i=1 Splitting the sum according to the cardinality of A and applying induction on r we 1 (cid:18) (cid:19) conclude (cid:88) (cid:89) (cid:88) (cid:16) (cid:17) − − (cid:96) r n n − n a + r 2 #A ! = (cid:18) a!(n a)(cid:19)! (cid:18)− (cid:19) i (cid:88) a r 2 { } 1,...,n = ri=1 Ai i=1 a=0 − − n a + r 2 n + r 1 = n! − = n! − . r 2 r 1 a=0 (cid:3) ∈ ∗ − (cid:104) (cid:105) Lemma 4.10. Let ψ Λ with ψ(d, 1, 1) = ψ(d, 1, 1) for all d. Then ψχ = 0. Hn (cid:88) (cid:88) (cid:88) (cid:88) (cid:88) ◦ → ˜ Proof. Write ψ = ψ π with π : H S the quotient map. Then n n n n ˜ ψ (σ)χ (σ) = ψ (σ)χ (σ) = ψ (τ) χ (σ) = 0, n n n n n n ∈ ∈ ∈ − ∈ ∈ − σ Hn τ Sn σ π 1(τ) τ Sn σ π 1(τ) − − since χ (σ) = 1 for half of the 2n many σ in each π 1(τ), and χ (σ) = 1 for the other n n (cid:3) half. ##LTLine## ##LTLine##

label: paragraph

text: LIOR

label: equation

text: AND

text: FEHM

text: n

text: r

text: d

text: r

text: Hn

text: r

text: Proof.

text: Since

text: dr,n

text: factors

text: Hn

text: Sn,

text: r

text: d,s

text: d

text: rω(τ)

text: r

text: Hn

text: r

text: n!

text: σ

text: Hn

text: τ

text: Sn

text: where

text: ω(τ)

text: is

text: the

text: number

text: of

text: cycles

text: of

text: τ.

text: Viewing

text: rω(τ)

text: as

text: the

text: number

text: of

text: partitions

text: of

text: n

text: into

text: r

text: sets

text: that

text: are

text: unions

text: of

text: orbits

text: of

text: τ

text: and

text: changing

text: order

text: of

text: summation

text: we

text: get

text: that

text: r

text: rω(τ)

text: #A

text: i

text: τ

text: Sn

text: Ai

text: Splitting

text: the

text: sum

text: according

text: to

text: the

text: cardinality

text: of

text: A

text: and

text: applying

text: induction

text: on

text: r

text: we

text: conclude

text: r

text: n

text: n

text: n

text: a

text: r

text: #A

text: a!(n

text: i

text: a

text: r

text: Ai

text: n

text: a

text: r

text: n

text: r

text: n!

text: n!

text: r

text: r

text: Lemma

text: Let

text: ψ

text: Λ

text: with

text: ψ(d,

text: ψ(d,

text: for

text: all

text: d.

text: Then

text: ψχ

text: Hn

text: Proof.

text: Write

text: ψ

text: ψ

text: π

text: with

text: π

text: H

text: S

text: the

text: quotient

text: map.

text: Then

text: n

text: n

text: n

text: n

text: ψ

text: (σ)χ

text: (σ)

text: ψ

text: (σ)χ

text: (σ)

text: ψ

text: (τ)

text: χ

text: (σ)

text: n

text: n

text: n

text: n

text: n

text: n

text: σ

text: Hn

text: τ

text: Sn

text: σ

text: π

text: τ

text: Sn

text: σ

text: π

text: since

text: χ

text: (σ)

text: for

text: half

text: of

text: the

text: many

text: σ

text: in

text: each

text: π

text: and

text: χ

text: (σ)

text: for

text: the

text: other

text: n

text: n

text: half.

text: ##LTLine##

text: ##LTLine##


text: CORRELATIONS IN FUNCTION FIELDS 41 [Bre62] B. M. Bredihin. Binary additive problems with prime numbers. Dokl. Akad. Nauk SSSR 142:766– 768, 1962. (document) [Car15] D. Carmon. The autocorrelation of the M¨obius function and Chowla’s conjecture for the rational function ﬁeld in characteristic 2. Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, Theo Murphy meeting issue ‘Number ﬁelds and function ﬁelds: coalescences, contrasts and emerging applications’ compiled and edited by J. P. Keating, Z. Rudnick and T. D. Wooley, 373(2040), 2015. (document) [CR14] D. Carmon and Z. Rudnick. The autocorrelation of the M¨obius function and Chowla’s conjecture for the rational function ﬁeld. Q. J. Math. 65(1):53–61, 2014. (document), 4 [CD87] T. Cochrane and R. E. Dressler. Consecutive triples of sums of two squares. Archiv Math. 49:301– 304, 1987. (document) [CK97] R. D. Connors and J. P. Keating. Two-point spectral correlations for the square billiard J. Phys. A: Math. Gen. 30:1817–1830, 1997. (document) [CG01] J. B. Conrey and S. M. Gonek. High moments of the Riemann zeta-function. Duke Math. J. 107(3):577–604, 2001. (document) [CK16] B. Conrey and J. P. Keating. Moments of zeta and correlations of divisor-sums: IV. Res. Number Theory 2, 2016. (document) [Est32] T. Estermann. An asymptotic formula in the theory of numbers. Proc. London Math. Soc. 34:280– 292, 1932. (document) [FJ08] M. D. Fried and M. Jarden. Field Arithmetic. Third Edition. Springer, 2008. (document) [FKR17] T. Freiberg, P. Kurlberg and L. Rosenzweig. Poisson distribution for gaps between sums of two squares and level spacings for toral point scatterers. arXiv:1701.01157 [math-ph], 2017. (document) [Gor16] O. Gorodetsky. A Polynomial Analogue of Landau’s Theorem and Related Problems. arXiv:1603.02890 [math.NT], 2016. (document) [Hal06] C. Hall. L-functions of twisted Legendre curves. J. Number Theory 119(1):128–147, 2006. 1 [HL24] G. H. Hardy and J. E. Littlewood. Some Problems of ’Partitio Numerorum’(V): A Further Contribution to the Study of Goldbach’s Problem. Proc. London Math. Soc. S2-22 no. 1, 46–56, 1924. (document) [Hoo57] C. Hooley. On the representation of a number as the sum of two squares and a prime. Acta Math. 97:189–210, 1957. (document) [Hoo71] C. Hooley. On the intervals between numbers that are sums of two squares. Acta Math. 127(1):279–297, 1971. (document) [Hoo73] C. Hooley. On the intervals between numbers that are sums of two squares. II. J. Number Theory 5:215–217, 1973. (document) [Hoo74] C. Hooley. On the intervals between numbers that are sums of two squares. III. J. Reine Angew. Math. 267(1):207–218, 1974. (document) [Hoo94] C. Hooley. On the intervals between numbers that are sums of two squares. IV. J. Reine Angew. Math. 452:79–109, 1994. (document) [IS72] K.-H. Indlekofer and W. Schwarz. U¨ber B-Zwillinge. Archiv Math. 23:251–256, 1972 (document) [Ind74] K.-H. Indlekofer. Scharfe untere Absch¨atzung fu¨r die Anzahlfunktion der B-Zwillinge. Acta Arith- metica 26:207–212, 1974. (document) [Ivi97] A. Ivic. The general additive divisor problem and moments of the zeta-function. New trends in probability and statistics 4:69–89, 1997. (document) [Iwa72] H. Iwaniec. Primes of the type ϕ(x, y)+A where ϕ is a quadratic form. Acta Arithmetica 21:203– 234, 1972. (document) [Iwa76] H. Iwaniec. The half dimensional sieve. Acta Arithmetica 29:69–95, 1976. (document) [KGH07] J. P. Keating, S. M. Gonek, and C. P. Hughes. A hybrid Euler-Hadamard product for the Riemann zeta function. Duke Math. J 136:507–549, 2007. (document)

text: CORRELATIONS

text: IN

text: FUNCTION

text: FIELDS

label: reference

text: B.

text: M.

text: Bredihin.

text: Binary

text: additive

text: problems

text: with

text: prime

text: numbers.

text: Dokl.

text: Akad.

text: Nauk

text: SSSR

text: (document)

text: D.

text: Carmon.

text: The

text: autocorrelation

text: of

text: the

text: M¨obius

text: function

text: and

text: Chowla’s

text: conjecture

text: for

text: the

text: rational

text: function

text: ﬁeld

text: in

text: characteristic

text: Philosophical

text: Transactions

text: of

text: the

text: Royal

text: Society

text: of

text: London

text: A:

text: Mathematical,

text: Physical

text: and

text: Engineering

text: Sciences,

text: Theo

text: Murphy

text: meeting

text: issue

text: ‘Number

text: ﬁelds

text: and

text: function

text: ﬁelds:

text: coalescences,

text: contrasts

text: and

text: emerging

text: applications’

text: compiled

text: and

text: edited

text: by

text: J.

text: P.

text: Keating,

text: Z.

text: Rudnick

text: and

text: T.

text: D.

text: Wooley,

text: (document)

text: D.

text: Carmon

text: and

text: Z.

text: Rudnick.

text: The

text: autocorrelation

text: of

text: the

text: M¨obius

text: function

text: and

text: Chowla’s

text: conjecture

text: for

text: the

text: rational

text: function

text: ﬁeld.

text: Q.

text: J.

text: Math.

text: (document),

text: T.

text: Cochrane

text: and

text: R.

text: E.

text: Dressler.

text: Consecutive

text: triples

text: of

text: sums

text: of

text: two

text: squares.

text: Archiv

text: Math.

text: (document)

text: R.

text: D.

text: Connors

text: and

text: J.

text: P.

text: Keating.

text: Two-point

text: spectral

text: correlations

text: for

text: the

text: square

text: billiard

text: J.

text: Phys.

text: A:

text: Math.

text: Gen.

text: (document)

text: J.

text: B.

text: Conrey

text: and

text: S.

text: M.

text: Gonek.

text: High

text: moments

text: of

text: the

text: Riemann

text: zeta-function.

text: Duke

text: Math.

text: J.

text: (document)

text: B.

text: Conrey

text: and

text: J.

text: P.

text: Keating.

text: Moments

text: of

text: zeta

text: and

text: correlations

text: of

text: divisor-sums:

text: IV.

text: Res.

text: Number

text: Theory

text: (document)

text: T.

text: Estermann.

text: An

text: asymptotic

text: formula

text: in

text: the

text: theory

text: of

text: numbers.

text: Proc.

text: London

text: Math.

text: Soc.

text: (document)

text: M.

text: D.

text: Fried

text: and

text: M.

text: Jarden.

text: Field

text: Arithmetic.

text: Third

text: Edition.

text: Springer,

text: (document)

text: T.

text: Freiberg,

text: P.

text: Kurlberg

text: and

text: L.

text: Rosenzweig.

text: Poisson

text: distribution

text: for

text: gaps

text: between

text: sums

text: of

text: two

text: squares

text: and

text: level

text: spacings

text: for

text: toral

text: point

text: scatterers.

text: [math-ph],

text: (document)

text: O.

text: Gorodetsky.

text: A

text: Polynomial

text: Analogue

text: of

text: Landau’s

text: Theorem

text: and

text: Related

text: Problems.

text: [math.NT],

text: (document)

text: C.

text: Hall.

text: L-functions

text: of

text: twisted

text: Legendre

text: curves.

text: J.

text: Number

text: Theory

text: G.

text: H.

text: Hardy

text: and

text: J.

text: E.

text: Littlewood.

text: Some

text: Problems

text: of

text: ’Partitio

text: Numerorum’(V):

text: A

text: Further

text: Contribution

text: to

text: the

text: Study

text: of

text: Goldbach’s

text: Problem.

text: Proc.

text: London

text: Math.

text: Soc.

text: no.

text: (document)

text: C.

text: Hooley.

text: On

text: the

text: representation

text: of

text: a

text: number

text: as

text: the

text: sum

text: of

text: two

text: squares

text: and

text: a

text: prime.

text: Acta

text: Math.

text: (document)

text: C.

text: Hooley.

text: On

text: the

text: intervals

text: between

text: numbers

text: that

text: are

text: sums

text: of

text: two

text: squares.

text: Acta

text: Math.

text: (document)

text: C.

text: Hooley.

text: On

text: the

text: intervals

text: between

text: numbers

text: that

text: are

text: sums

text: of

text: two

text: squares.

text: II.

text: J.

text: Number

text: Theory

text: (document)

text: C.

text: Hooley.

text: On

text: the

text: intervals

text: between

text: numbers

text: that

text: are

text: sums

text: of

text: two

text: squares.

text: III.

text: J.

text: Reine

text: Angew.

text: Math.

text: (document)

text: C.

text: Hooley.

text: On

text: the

text: intervals

text: between

text: numbers

text: that

text: are

text: sums

text: of

text: two

text: squares.

text: IV.

text: J.

text: Reine

text: Angew.

text: Math.

text: (document)

text: K.-H.

text: Indlekofer

text: and

text: W.

text: Schwarz.

text: U¨ber

text: B-Zwillinge.

text: Archiv

text: Math.

text: (document)

text: K.-H.

text: Indlekofer.

text: Scharfe

text: untere

text: Absch¨atzung

text: fu¨r

text: die

text: Anzahlfunktion

text: der

text: B-Zwillinge.

text: Acta

text: Arith-

text: metica

text: (document)

text: A.

text: Ivic.

text: The

text: general

text: additive

text: divisor

text: problem

text: and

text: moments

text: of

text: the

text: zeta-function.

text: New

text: trends

text: in

text: probability

text: and

text: statistics

text: (document)

text: H.

text: Iwaniec.

text: Primes

text: of

text: the

text: type

text: ϕ(x,

text: y)+A

text: where

text: ϕ

text: is

text: a

text: quadratic

text: form.

text: Acta

text: Arithmetica

text: (document)

text: H.

text: Iwaniec.

text: The

text: half

text: dimensional

text: sieve.

text: Acta

text: Arithmetica

text: (document)

text: J.

text: P.

text: Keating,

text: S.

text: M.

text: Gonek,

text: and

text: C.

text: P.

text: Hughes.

text: A

text: hybrid

text: Euler-Hadamard

text: product

text: for

text: the

text: Riemann

text: zeta

text: function.

text: Duke

text: Math.

text: J

text: (document)


text: 8 LIOR BARY-SOROKER AND ARNO FEHM ∈ F Moreover, for h = (h , . . . , h ) [T ]k we let 1 k q A { ∈ F ∈ A } (P ν) = f [T ]/(P ν) : f + h , . . . , f + h (P ν) . q,h q 1 k q ∈ A ∈ A ≤ Note that if f (P ν) then trivially f (P ξ) for all ξ ν, hence the sequence | |− A q,h q,h P ν# (P ν) is monotone decreasing and therefore the limit q,h | |− A δ (P ) = lim P ν# (P ν) q,h →∞ q,h ν A exists. We will also show below (Corollary 2.14) that δ (P ) = 0 if and only if (P ν) = ∅ q,h q,h for some ν > 0 in which case we say that there exists local obstruction at P . Our heuristic assumption is that the b (f + h ), i = 1, . . . , k, behave like i.i.d. random q i | − | | | variables as f is randomly picked from a short interval f f < f (cid:15), up to a correction (cid:81) 0 0 factor coming from the fact that they are not independent modulo polynomials g. By the Chinese Remainder Theorem, one may reduce to g = P ν a prime power, for which the actual mean of b (f + h ) is given by δ (P ) while the random model would predict a i q i q,h mean of δ (P )k. This leads to 0 ≥ ≥ ≥ ≥ Conjecture 2.2. For every k 1, d 1 and 1 (cid:15) > 0 there exists N 1 such that for ∈ F ≥ ∈ F q an odd prime power, f [T ] monic of degree n N and h , . . . , h [T ] of degree (cid:42) 0 q (cid:43) 1 k q less than d and pair(cid:89)wise distinct, k ∼ · (cid:104) (cid:105) (2.2) b (f + h ) S b (f) k∈(cid:18) (cid:19) q i q,h q f Mn,q | − | | | i=1 f f0 < f0 (cid:15) ∼ · · 1 2n k (2.3) S Kk q,h q 4nk n → ∞ uniformly as qn , where S and K are deﬁned as in (1.13) resp. (1.12). q,h q We note that if there exists a local obstruction, then clearly both sides in (2.2) equal 0, so in this case the conjecture is uninteresting and correct. We now show that the δ (P ) can be computed in theory and give estimates in general q,h and concrete formulas in certain special cases. In particular, we show that the inﬁnite product in (1.13) that deﬁnes S indeed converges. q,h ∈ F ∈ F (cid:54)≡ Lemma 2.3. Let P [T ] be monic irreducible and f [T ]. Assume that f 0 ≡ q ≤ q ∈ F mod P ν and write f P αg mod P ν with maximal 0 α < ν and any suitable g [T ]. q ##LTLine##

text: LIOR

text: BARY-SOROKER

text: AND

text: ARNO

text: FEHM

text: F

text: Moreover,

text: for

text: h

text: (h

text: h

text: [T

text: ]k

text: we

text: let

text: k

text: q

text: A

text: F

text: A

text: (P

text: ν)

text: f

text: [T

text: ]/(P

text: ν)

text: f

text: h

text: f

text: h

text: (P

text: ν)

text: q,h

text: q

text: k

text: q

text: A

text: A

text: Note

text: that

text: if

text: f

text: (P

text: ν)

text: then

text: trivially

text: f

text: (P

text: ξ)

text: for

text: all

text: ξ

text: ν,

text: hence

text: the

text: sequence

text: A

text: q,h

text: q,h

text: P

text: ν#

text: (P

text: ν)

text: is

text: monotone

text: decreasing

text: and

text: therefore

text: the

text: limit

text: q,h

text: A

text: δ

text: (P

text: lim

text: P

text: ν#

text: (P

text: ν)

text: q,h

text: q,h

text: ν

text: A

text: exists.

text: We

text: will

text: also

text: show

text: below

text: (Corollary

text: that

text: δ

text: (P

text: if

text: and

text: only

text: if

text: (P

text: ν)

text: q,h

text: q,h

text: for

text: some

text: ν

text: in

text: which

text: case

text: we

text: say

text: that

text: there

text: exists

text: local

text: obstruction

text: at

text: P

text: Our

text: heuristic

text: assumption

text: is

text: that

text: the

text: b

text: (f

text: h

text: i

text: k,

text: behave

text: like

text: i.i.d.

text: random

text: q

text: i

text: variables

text: as

text: f

text: is

text: randomly

text: picked

text: from

text: a

text: short

text: interval

text: f

text: f

text: f

text: up

text: to

text: a

text: correction

text: factor

text: coming

text: from

text: the

text: fact

text: that

text: they

text: are

text: not

text: independent

text: modulo

text: polynomials

text: g.

text: By

text: the

text: Chinese

text: Remainder

text: Theorem,

text: one

text: may

text: reduce

text: to

text: g

text: P

text: ν

text: a

text: prime

text: power,

text: for

text: which

text: the

text: actual

text: mean

text: of

text: b

text: (f

text: h

text: is

text: given

text: by

text: δ

text: (P

text: while

text: the

text: random

text: model

text: would

text: predict

text: a

text: i

text: q

text: i

text: q,h

text: mean

text: of

text: δ

text: (P

text: )k.

text: This

text: leads

text: to

text: Conjecture

text: For

text: every

text: k

text: d

text: and

text: there

text: exists

text: N

text: such

text: that

text: for

text: F

text: F

text: q

text: an

text: odd

text: prime

text: power,

text: f

text: [T

text: monic

text: of

text: degree

text: n

text: N

text: and

text: h

text: h

text: [T

text: of

text: degree

text: q

text: k

text: q

text: less

text: than

text: d

text: and

text: distinct,

text: k

text: b

text: (f

text: h

text: S

text: b

text: (f)

text: q

text: i

text: q,h

text: q

text: f

text: Mn,q

text: f

text: k

text: S

text: Kk

text: q,h

text: q

text: n

text: uniformly

text: as

text: qn

text: where

text: S

text: and

text: K

text: are

text: deﬁned

text: as

text: in

text: resp.

text: q,h

text: q

text: We

text: note

text: that

text: if

text: there

text: exists

text: a

text: local

text: obstruction,

text: then

text: clearly

text: both

text: sides

text: in

text: equal

text: so

text: in

text: this

text: case

text: the

text: conjecture

text: is

text: uninteresting

text: and

text: correct.

text: We

text: now

text: show

text: that

text: the

text: δ

text: (P

text: can

text: be

text: computed

text: in

text: theory

text: and

text: give

text: estimates

text: in

text: general

text: q,h

text: and

text: concrete

text: formulas

text: in

text: certain

text: special

text: cases.

text: In

text: particular,

text: we

text: show

text: that

text: the

text: inﬁnite

text: product

text: in

text: that

text: deﬁnes

text: S

text: indeed

text: converges.

text: q,h

text: F

text: F

text: Lemma

text: Let

text: P

text: [T

text: be

text: monic

text: irreducible

text: and

text: f

text: [T

text: Assume

text: that

text: f

text: q

text: q

text: F

text: mod

text: P

text: ν

text: and

text: write

text: f

text: P

text: αg

text: mod

text: P

text: ν

text: with

text: maximal

text: α

text: ν

text: and

text: any

text: suitable

text: g

text: [T

text: q

text: ##LTLine##


text: We use a variant of progressive validation, similar to [20], data and unobserved cross-features: LR is unable to predict for our experiments. The day following the training period the value associated with a cross-feature that is not part serves as a validation set. As shown on Figure 1 below, of the training data; on the other hand, FFMs are able to the process is repeated N times, shifting the learning period better generalize through their latent representation (see de- (indicated by ”tr”) by 1 day at each step. The ﬁnal results tailed explanation and example in [14, Section 2]). For large are the average metrics over all the test sets (indicated by advertisers LR has enough data to learn a good model, but ”te”). for small advertisers FFMs handle this data sparsity issue better than LR. tr #1 te #1 During the tuning of the hyper-parameters, we observed very similar results as in [14] in terms of performance w.r.t tr #2 te #2 each hyper-parameter. The most important parameter is . .. the number of epochs and we use early-stopping to auto- matically tune it. Figure 1: Progressive validation We also investigated the prediction time of FFM com- pared to the baseline model, which is expected to increase Parameter tuning is done on a separate temporal slice despite the fact that we constrained our FFM models to be of data from the data of 1 used for the ﬁnal experiments. of the same size of the baseline. This is because the number Following [14] the following parameters are tuned: the reg- of operations to compute the prediction (1) is O(F2k) while ularization parameter, the learning rate, and the number of LR with all cross-features requires only O(F2) operations. latent factors. We use early-stopping to avoid over-ﬁtting. We observed that the slowdown of FFM is indeed propor- Below and in the rest of the paper, we use conﬁdence tional to the number of latent factors k. It turns out that intervals computed using bootstraps [10] at the 90% level. k = 2 is a good trade-oﬀ: it hardly degrades the accuracy Finally the learning of FFMs is multi-threaded as in [14] to results compared to the results above which were obtained reduce the learning time. with 4 latent factors (0.1% in NLL) and a 2x in prediction time in our system is acceptable since prediction is is not Latency & memory consumption. the most time-consuming part of processing a request (com- pared to extracting raw features, pre-processing them, etc.). One potential drawback of using FFM in a production system is that they require more CPU time for inference [14]. 2.3 Online comparison This may lead to increased latency online when responding to bid requests and therefore come more timeouts. FFM also As the oﬄine results were quite promising, we decided to require more memory for storing the model as the number run an A/B test using FFM for both CTR and CR pre- of latent factors and/or the number of ﬁelds increase, which dictions models. Although FFM require more time for the may lead to a much larger memory consumption than LR. inference (see above), we did not observe any signiﬁcant im- To solve the memory issue, we propose to reduce the size of pact on our timeouts while serving live traﬃc. So, we were the hashing space of FFM models (compared to our baseline) able to A/B test FFM on a large portion of our live traﬃc. ∼ ∼ so that FFM models have the same size as the LR models This A/B test served 5B displays ( 2.5B for each popula- (the exact value depends on the number of ﬁelds and on the tion). number of latent factors). Note that if we had not reduced During the A/B test, we ensured that both the baseline the size of the hashing space, but kept it constant, the size model and FFM were refreshed online synchronously since of FFM models would be more than a 100 times larger than diﬀerent refresh rates might bias the results. Even with our baseline, which would make it impractical. Therefore, multi-threading, the learning time of FFM is indeed much in the results below, FFM and LR models have the same higher than for our distributed optimization baseline. In number of parameters (unlike in [14]). Section and , we will see how to reduce this learning time, To solve the latency issue, we propose to reduce the num- but now we focus only on the performance improvements we ber of latent factors as much as possible without signiﬁcantly can get online with FFM. The results we obtained are the degrading the performance of FFM. Using these two solu- following. tions, FFM and LR consume the same amount of memory Results are shown in Table 3. We observed an increase in and we can limit the impact on latency to handle the re- the number of displays (+4.59%), while the overall display quirement of our production system, as we will see below. cost stayed almost constant. We observed less clicks, but more conversions leading to more advertiser value for the Ofﬂine results. same cost. Our change therefore resulted in a signiﬁcant We compare LR and FFM on our CTR and CR predic- positive impact: +0.97% of Return On Investment (ROI), tion tasks in terms of NLL (Table 1) and Utility (Table 2). that is of advertiser value over cost, which is substantial. FFM achieves signiﬁcantly better results with a large eﬀect We also observed that the improvements were even larger compared to LR, both in terms of NLL and of Utility for on small advertisers (deﬁned as the ones with less than 30 our CTR model, thus conﬁrming the results from [14] on sales per day), which represent a signiﬁcant portion of our our data. We also observe large gains on our CR model, traﬃc. On small advertisers, we observed an increase in the thus extending the results from [14] to CR models on all our number of displays (+4.85%), while the overall display cost oﬄine metrics. stayed almost constant too. We also observed less clicks, but We also observe that the improvements are even larger even more conversions leading to even more advertiser value on small advertisers, which represent a signiﬁcant portion of for the same cost and to +2.61% of Return On Investment our traﬃc, for both our CTR and CR models on all metrics. (ROI), which is remarkable. Our hypothesis to explain these results has to do with sparse This conﬁrms our oﬄine results and shows that one of

text: We

text: use

text: a

text: variant

text: of

text: progressive

text: validation,

text: similar

text: to

text: data

text: and

text: unobserved

text: cross-features:

text: LR

text: is

text: unable

text: to

text: predict

text: for

text: our

text: experiments.

text: The

text: day

text: following

text: the

text: training

text: period

text: the

text: value

text: associated

text: with

text: a

text: cross-feature

text: that

text: is

text: not

text: part

text: serves

text: as

text: a

text: validation

text: set.

text: As

text: shown

text: on

text: Figure

text: below,

text: of

text: the

text: training

text: data;

text: on

text: the

text: other

text: hand,

text: FFMs

text: are

text: able

text: to

text: the

text: process

text: is

text: repeated

text: N

text: times,

text: shifting

text: the

text: learning

text: period

text: better

text: generalize

text: through

text: their

text: latent

text: representation

text: (see

text: de-

text: (indicated

text: by

text: ”tr”)

text: by

text: day

text: at

text: each

text: step.

text: The

text: ﬁnal

text: results

text: tailed

text: explanation

text: and

text: example

text: in

text: Section

text: For

text: large

text: are

text: the

text: average

text: metrics

text: over

text: all

text: the

text: test

text: sets

text: (indicated

text: by

text: advertisers

text: LR

text: has

text: enough

text: data

text: to

text: learn

text: a

text: good

text: model,

text: but

text: ”te”).

text: for

text: small

text: advertisers

text: FFMs

text: handle

text: this

text: data

text: sparsity

text: issue

text: better

text: than

text: LR.

text: tr

text: te

text: During

text: the

text: tuning

text: of

text: the

text: hyper-parameters,

text: we

text: observed

text: very

text: similar

text: results

text: as

text: in

text: in

text: terms

text: of

text: performance

text: w.r.t

text: tr

text: te

text: each

text: hyper-parameter.

text: The

text: most

text: important

text: parameter

text: is

text: the

text: number

text: of

text: epochs

text: and

text: we

text: use

text: early-stopping

text: to

text: auto-

text: matically

text: tune

text: it.

text: Figure

text: Progressive

text: validation

text: We

text: also

text: investigated

text: the

text: prediction

text: time

text: of

text: FFM

text: com-

text: pared

text: to

text: the

text: baseline

text: model,

text: which

text: is

text: expected

text: to

text: increase

text: Parameter

text: tuning

text: is

text: done

text: on

text: a

text: separate

text: temporal

text: slice

text: despite

text: the

text: fact

text: that

text: we

text: constrained

text: our

text: FFM

text: models

text: to

text: be

text: of

text: data

text: from

text: the

text: data

text: of

text: used

text: for

text: the

text: ﬁnal

text: experiments.

text: of

text: the

text: same

text: size

text: of

text: the

text: baseline.

text: This

text: is

text: because

text: the

text: number

text: Following

text: the

text: following

text: parameters

text: are

text: tuned:

text: the

text: reg-

text: of

text: operations

text: to

text: compute

text: the

text: prediction

text: is

text: while

text: ularization

text: parameter,

text: the

text: learning

text: rate,

text: and

text: the

text: number

text: of

text: LR

text: with

text: all

text: cross-features

text: requires

text: only

text: operations.

text: latent

text: factors.

text: We

text: use

text: early-stopping

text: to

text: avoid

text: over-ﬁtting.

text: We

text: observed

text: that

text: the

text: slowdown

text: of

text: FFM

text: is

text: indeed

text: propor-

text: Below

text: and

text: in

text: the

text: rest

text: of

text: the

text: paper,

text: we

text: use

text: conﬁdence

text: tional

text: to

text: the

text: number

text: of

text: latent

text: factors

text: k.

text: It

text: turns

text: out

text: that

text: intervals

text: computed

text: using

text: bootstraps

text: at

text: the

text: level.

text: k

text: is

text: a

text: good

text: trade-oﬀ:

text: it

text: hardly

text: degrades

text: the

text: accuracy

text: Finally

text: the

text: learning

text: of

text: FFMs

text: is

text: multi-threaded

text: as

text: in

text: to

text: results

text: compared

text: to

text: the

text: results

text: above

text: which

text: were

text: obtained

text: reduce

text: the

text: learning

text: time.

text: with

text: latent

text: factors

text: in

text: NLL)

text: and

text: a

text: in

text: prediction

text: time

text: in

text: our

text: system

text: is

text: acceptable

text: since

text: prediction

text: is

text: is

text: not

text: Latency

text: memory

text: consumption.

text: the

text: most

text: time-consuming

text: part

text: of

text: processing

text: a

text: request

text: (com-

text: pared

text: to

text: extracting

text: raw

text: features,

text: pre-processing

text: them,

text: etc.).

text: One

text: potential

text: drawback

text: of

text: using

text: FFM

text: in

text: a

text: production

text: system

text: is

text: that

text: they

text: require

text: more

text: CPU

text: time

text: for

text: inference

text: Online

text: comparison

text: This

text: may

text: lead

text: to

text: increased

text: latency

text: online

text: when

text: responding

text: to

text: bid

text: requests

text: and

text: therefore

text: come

text: more

text: timeouts.

text: FFM

text: also

text: As

text: the

text: oﬄine

text: results

text: were

text: quite

text: promising,

text: we

text: decided

text: to

text: require

text: more

text: memory

text: for

text: storing

text: the

text: model

text: as

text: the

text: number

text: run

text: an

text: A/B

text: test

text: using

text: FFM

text: for

text: both

text: CTR

text: and

text: CR

text: pre-

text: of

text: latent

text: factors

text: and/or

text: the

text: number

text: of

text: ﬁelds

text: increase,

text: which

text: dictions

text: models.

text: Although

text: FFM

text: require

text: more

text: time

text: for

text: the

text: may

text: lead

text: to

text: a

text: much

text: larger

text: memory

text: consumption

text: than

text: LR.

text: inference

text: (see

text: above),

text: we

text: did

text: not

text: observe

text: any

text: signiﬁcant

text: im-

text: To

text: solve

text: the

text: memory

text: issue,

text: we

text: propose

text: to

text: reduce

text: the

text: size

text: of

text: pact

text: on

text: our

text: timeouts

text: while

text: serving

text: live

text: traﬃc.

text: So,

text: we

text: were

text: the

text: hashing

text: space

text: of

text: FFM

text: models

text: (compared

text: to

text: our

text: baseline)

text: able

text: to

text: A/B

text: test

text: FFM

text: on

text: a

text: large

text: portion

text: of

text: our

text: live

text: traﬃc.

text: so

text: that

text: FFM

text: models

text: have

text: the

text: same

text: size

text: as

text: the

text: LR

text: models

text: This

text: A/B

text: test

text: served

text: displays

text: for

text: each

text: popula-

text: (the

text: exact

text: value

text: depends

text: on

text: the

text: number

text: of

text: ﬁelds

text: and

text: on

text: the

text: tion).

text: number

text: of

text: latent

text: factors).

text: Note

text: that

text: if

text: we

text: had

text: not

text: reduced

text: During

text: the

text: A/B

text: test,

text: we

text: ensured

text: that

text: both

text: the

text: baseline

text: the

text: size

text: of

text: the

text: hashing

text: space,

text: but

text: kept

text: it

text: constant,

text: the

text: size

text: model

text: and

text: FFM

text: were

text: refreshed

text: online

text: synchronously

text: since

text: of

text: FFM

text: models

text: would

text: be

text: more

text: than

text: a

text: times

text: larger

text: than

text: diﬀerent

text: refresh

text: rates

text: might

text: bias

text: the

text: results.

text: Even

text: with

text: our

text: baseline,

text: which

text: would

text: make

text: it

text: impractical.

text: Therefore,

text: multi-threading,

text: the

text: learning

text: time

text: of

text: FFM

text: is

text: indeed

text: much

text: in

text: the

text: results

text: below,

text: FFM

text: and

text: LR

text: models

text: have

text: the

text: same

text: higher

text: than

text: for

text: our

text: distributed

text: optimization

text: baseline.

text: In

text: number

text: of

text: parameters

text: (unlike

text: in

text: Section

text: and

text: we

text: will

text: see

text: how

text: to

text: reduce

text: this

text: learning

text: time,

text: To

text: solve

text: the

text: latency

text: issue,

text: we

text: propose

text: to

text: reduce

text: the

text: num-

text: but

text: now

text: we

text: focus

text: only

text: on

text: the

text: performance

text: improvements

text: we

text: ber

text: of

text: latent

text: factors

text: as

text: much

text: as

text: possible

text: without

text: signiﬁcantly

text: can

text: get

text: online

text: with

text: FFM.

text: The

text: results

text: we

text: obtained

text: are

text: the

text: degrading

text: the

text: performance

text: of

text: FFM.

text: Using

text: these

text: two

text: solu-

text: following.

text: tions,

text: FFM

text: and

text: LR

text: consume

text: the

text: same

text: amount

text: of

text: memory

text: Results

text: are

text: shown

text: in

text: Table

text: We

text: observed

text: an

text: increase

text: in

text: and

text: we

text: can

text: limit

text: the

text: impact

text: on

text: latency

text: to

text: handle

text: the

text: re-

text: the

text: number

text: of

text: displays

text: while

text: the

text: overall

text: display

text: quirement

text: of

text: our

text: production

text: system,

text: as

text: we

text: will

text: see

text: below.

text: cost

text: stayed

text: almost

text: constant.

text: We

text: observed

text: less

text: clicks,

text: but

text: more

text: conversions

text: leading

text: to

text: more

text: advertiser

text: value

text: for

text: the

text: Ofﬂine

text: results.

text: same

text: cost.

text: Our

text: change

text: therefore

text: resulted

text: in

text: a

text: signiﬁcant

text: We

text: compare

text: LR

text: and

text: FFM

text: on

text: our

text: CTR

text: and

text: CR

text: predic-

text: positive

text: impact:

text: of

text: Return

text: On

text: Investment

text: (ROI),

text: tion

text: tasks

text: in

text: terms

text: of

text: NLL

text: (Table

text: and

text: Utility

text: (Table

text: that

text: is

text: of

text: advertiser

text: value

text: over

text: cost,

text: which

text: is

text: substantial.

text: FFM

text: achieves

text: signiﬁcantly

text: better

text: results

text: with

text: a

text: large

text: eﬀect

text: We

text: also

text: observed

text: that

text: the

text: improvements

text: were

text: even

text: larger

text: compared

text: to

text: LR,

text: both

text: in

text: terms

text: of

text: NLL

text: and

text: of

text: Utility

text: for

text: on

text: small

text: advertisers

text: (deﬁned

text: as

text: the

text: ones

text: with

text: less

text: than

text: our

text: CTR

text: model,

text: thus

text: conﬁrming

text: the

text: results

text: from

text: on

text: sales

text: per

text: day),

text: which

text: represent

text: a

text: signiﬁcant

text: portion

text: of

text: our

text: our

text: data.

text: We

text: also

text: observe

text: large

text: gains

text: on

text: our

text: CR

text: model,

text: traﬃc.

text: On

text: small

text: advertisers,

text: we

text: observed

text: an

text: increase

text: in

text: the

text: thus

text: extending

text: the

text: results

text: from

text: to

text: CR

text: models

text: on

text: all

text: our

text: number

text: of

text: displays

text: while

text: the

text: overall

text: display

text: cost

text: oﬄine

text: metrics.

text: stayed

text: almost

text: constant

text: too.

text: We

text: also

text: observed

text: less

text: clicks,

text: but

text: We

text: also

text: observe

text: that

text: the

text: improvements

text: are

text: even

text: larger

text: even

text: more

text: conversions

text: leading

text: to

text: even

text: more

text: advertiser

text: value

text: on

text: small

text: advertisers,

text: which

text: represent

text: a

text: signiﬁcant

text: portion

text: of

text: for

text: the

text: same

text: cost

text: and

text: to

text: of

text: Return

text: On

text: Investment

text: our

text: traﬃc,

text: for

text: both

text: our

text: CTR

text: and

text: CR

text: models

text: on

text: all

text: metrics.

text: (ROI),

text: which

text: is

text: remarkable.

text: Our

text: hypothesis

text: to

text: explain

text: these

text: results

text: has

text: to

text: do

text: with

text: sparse

text: This

text: conﬁrms

text: our

text: oﬄine

text: results

text: and

text: shows

text: that

text: one

text: of


text: Table 1: Oﬄine relative comparison between Logistic Regression (baseline) and FFM on our CTR and CR prediction tasks in terms of the NLL metric (3). We present results on all advertisers and on small advertisers – deﬁned as advertisers with less than 30 sales per day on average. NLL of the CTR (resp. CR) model is the NLL of the probability of a click (resp. sale) (cid:78) given a display. Statistical signiﬁcance is indicated by . NLL NLL Prediction model with FFM on all advertisers on small advertisers (cid:78) (cid:78) CTR +3.71% +5.9% (cid:78) (cid:78) CTR + CR +1.21% +6.2% Table 2: Oﬄine relative comparison between Logistic Regression (baseline) and FFM on our CTR and CR prediction tasks in terms of Utility metrics (4). We report the Utility of our model for the expected number of sales given display, which uses (cid:78) our CTR and CR models as sub-models. Statistical signiﬁcance is indicated by . Utility Utility Utility Utility Prediction model with FFM β=10 β=10 β=1000 β=1000 on all advertisers on small advertisers on all advertisers on small advertisers (cid:78) (cid:78) (cid:78) (cid:78) CTR +6.29% +9.70% +2.22% +4.39% (cid:78) (cid:78) (cid:78) (cid:78) CTR + CR +11.42% +38.44% +5.43% +18.34% the strengths of FFM is indeed their ability to generalize time w.r.t to the hyper-parameters (no need for constant better than logistic regression through their use of a latent re-tuning). representation. As we have not been able to ﬁnd a satisfying regularizer for FFM, we use early-stopping to avoid over-ﬁtting [14]— the only solution we have. So, some monitoring should also 2.4 Discussion be added to ensure that we are not under-ﬁtting or over- ﬁtting despite using early stopping (e.g., if the small amount Our positive online results motivate us to use FFM in of data used for testing and deciding when to stop is not production instead of LR. To do so, the code change is rather representative). small if SGD is already available. However, there are a few Note ﬁnally that for eﬃcient regression testing [16], we challenges to keep in mind when using FFM instead of LR need to ﬁx the seed used for randomizing the initial weights in a production system. [14]. The main concern with rolling out FFM is the learning time, which is much higher than the baseline as discussed 3. A SIMPLE DISTRIBUTED SETTING before. This means that our models would be refreshed less often with FFM, at the cost of reducing the performance In the previous section, we discussed that the training of the system. All our oﬄine experiments to improve our time of FFM is too slow to meet our production requirement, models would also take much longer. This is not acceptable even after applying the parallelization approach mentioned and we will discuss in the next two sections how to tackle this in [14] on a multi-core machine. problem to handle the scale of a large production system, in To get more speed-up, a natural option is to train FFM particular by distributing the learning on multiple machines. on a distributed system. Generally speaking, for sequential There are also other challenges. Above, we discussed the algorithms such as SGD or dual coordinate descent, the con- memory consumption and prediction latency issues and we vergence of their parallelization depends on how often each showed how to manage them. Another potential problem is worker can access the model. In shared-memory systems, the non-convexity of the objective function of FFM, which because each thread can access the model in real-time, it is may lead to some instability in the performance of FFM due possible that the convergence remains the same, as shown in to local minimums. To investigate this, we learned multiple [14]. However, in distributed systems, where we need to use FFMs on the same dataset initialized with random weights the network for communication, we can no longer share the as in [14]. We observed that all the models have similar per- model among machines in real-time (due to network over- ± formance ( 0.05% of NLL) despite the diﬀerent initializa- head). There are two main ways of distributing a stochastic tions. The local minimum issue is thus not a major concern. gradient algorithm, synchronously and asynchronously. In We also saw above that the number of hyper-parameters both cases, each machine has a subset of the data and its in FFM is larger than for LR with the addition of the learn- own local model and it updates the global model after a ing rate (as we use L-BFGS for training our LR models) and batch of data points has been processed. The asynchronous of the number of latent factors, while we only had the regu- training is often referred to as the parameter server approach larization parameter to tune for LR. This means that tuning [17, 18, 7]: some machines are dedicated to storing the global takes more time when improving our models. However, and model and the workers are continuously reading and updat- as discussed in [14], this is not a major problem for multiple ing that model with their local model. The synchronous reasons. First, the performance is not very sensitive to the training on the other hand is referred to as iterative param- number of latent factors and to the regularization parame- eter mixing (IPM) [19, 29, 1]: all the models are averaged ter, while a good value for the learning rate is easy to ﬁnd. after a certain amount of data has been processed (e.g. ev- We also found the performance of FFM to be stable over ery epoch). From an engineering point of view, simplicity is ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Table

text: Oﬄine

label: caption

text: relative

text: comparison

text: between

text: Logistic

text: Regression

text: (baseline)

text: and

text: FFM

text: on

text: our

text: CTR

text: and

text: CR

text: prediction

text: tasks

text: in

text: terms

text: of

text: the

text: NLL

text: metric

text: We

text: present

text: results

text: on

text: all

text: advertisers

text: and

text: on

text: small

text: advertisers

text: deﬁned

text: as

text: advertisers

text: with

text: less

text: than

text: sales

text: per

text: day

text: on

text: average.

text: NLL

text: of

text: the

text: CTR

text: (resp.

text: CR)

text: model

text: is

text: the

text: NLL

text: of

text: the

text: probability

text: of

text: a

text: click

text: (resp.

text: sale)

text: given

text: a

text: display.

text: Statistical

text: signiﬁcance

text: is

text: indicated

text: by

text: NLL

label: table

text: NLL

text: Prediction

text: model

text: with

text: FFM

text: on

text: all

text: advertisers

text: on

text: small

text: advertisers

text: CTR

text: CTR

text: CR

text: Table

text: Oﬄine

text: relative

text: comparison

text: between

text: Logistic

text: Regression

text: (baseline)

text: and

text: FFM

text: on

text: our

text: CTR

text: and

text: CR

text: prediction

text: tasks

text: in

text: terms

text: of

text: Utility

text: metrics

text: We

text: report

text: the

text: Utility

text: of

text: our

text: model

text: for

text: the

text: expected

text: number

text: of

text: sales

text: given

text: display,

text: which

text: uses

text: our

text: CTR

text: and

text: CR

text: models

text: as

text: sub-models.

text: Statistical

text: signiﬁcance

text: is

text: indicated

text: by

text: Utility

text: Utility

text: Utility

text: Utility

text: Prediction

text: model

text: with

text: FFM

text: on

text: all

text: advertisers

text: on

text: small

text: advertisers

text: on

text: all

text: advertisers

text: on

text: small

text: advertisers

text: CTR

text: CTR

text: CR

text: the

text: strengths

text: of

text: FFM

text: is

text: indeed

text: their

text: ability

text: to

text: generalize

text: time

text: w.r.t

text: to

text: the

text: hyper-parameters

text: (no

text: need

text: for

text: constant

text: better

text: than

text: logistic

text: regression

text: through

text: their

text: use

text: of

text: a

text: latent

text: re-tuning).

text: representation.

text: As

text: we

text: have

text: not

text: been

text: able

text: to

text: ﬁnd

text: a

text: satisfying

text: regularizer

text: for

text: FFM,

text: we

text: use

text: early-stopping

text: to

text: avoid

text: over-ﬁtting

text: the

text: only

text: solution

text: we

text: have.

text: So,

text: some

text: monitoring

text: should

text: also

text: Discussion

text: be

text: added

text: to

text: ensure

text: that

text: we

text: are

text: not

text: under-ﬁtting

text: or

text: over-

text: ﬁtting

text: despite

text: using

text: early

text: stopping

text: (e.g.,

text: if

text: the

text: small

text: amount

text: Our

text: positive

text: online

text: results

text: motivate

text: us

text: to

text: use

text: FFM

text: in

text: of

text: data

text: used

text: for

text: testing

text: and

text: deciding

text: when

text: to

text: stop

text: is

text: not

text: production

text: instead

text: of

text: LR.

text: To

text: do

text: so,

text: the

text: code

text: change

text: is

text: rather

text: representative).

text: small

text: if

text: SGD

text: is

text: already

text: available.

text: However,

text: there

text: are

text: a

text: few

text: Note

text: ﬁnally

text: that

text: for

text: eﬃcient

text: regression

text: testing

text: we

text: challenges

text: to

text: keep

text: in

text: mind

text: when

text: using

text: FFM

text: instead

text: of

text: LR

text: need

text: to

text: ﬁx

text: the

text: seed

text: used

text: for

text: randomizing

text: the

text: initial

text: weights

text: in

text: a

text: production

text: system.

text: The

text: main

text: concern

text: with

text: rolling

text: out

text: FFM

text: is

text: the

text: learning

text: time,

text: which

text: is

text: much

text: higher

text: than

text: the

text: baseline

text: as

text: discussed

text: A

text: SIMPLE

text: DISTRIBUTED

text: SETTING

text: before.

text: This

text: means

text: that

text: our

text: models

text: would

text: be

text: refreshed

text: less

text: often

text: with

text: FFM,

text: at

text: the

text: cost

text: of

text: reducing

text: the

text: performance

text: In

text: the

text: previous

text: section,

text: we

text: discussed

text: that

text: the

text: training

text: of

text: the

text: system.

text: All

text: our

text: oﬄine

text: experiments

text: to

text: improve

text: our

text: time

text: of

text: FFM

text: is

text: too

text: slow

text: to

text: meet

text: our

text: production

text: requirement,

text: models

text: would

text: also

text: take

text: much

text: longer.

text: This

text: is

text: not

text: acceptable

text: even

text: after

text: applying

text: the

text: parallelization

text: approach

text: mentioned

text: and

text: we

text: will

text: discuss

text: in

text: the

text: next

text: two

text: sections

text: how

text: to

text: tackle

text: this

text: in

text: on

text: a

text: multi-core

text: machine.

text: problem

text: to

text: handle

text: the

text: scale

text: of

text: a

text: large

text: production

text: system,

text: in

text: To

text: get

text: more

text: speed-up,

text: a

text: natural

text: option

text: is

text: to

text: train

text: FFM

text: particular

text: by

text: distributing

text: the

text: learning

text: on

text: multiple

text: machines.

text: on

text: a

text: distributed

text: system.

text: Generally

text: speaking,

text: for

text: sequential

text: There

text: are

text: also

text: other

text: challenges.

text: Above,

text: we

text: discussed

text: the

text: algorithms

text: such

text: as

text: SGD

text: or

text: dual

text: coordinate

text: descent,

text: the

text: con-

text: memory

text: consumption

text: and

text: prediction

text: latency

text: issues

text: and

text: we

text: vergence

text: of

text: their

text: parallelization

text: depends

text: on

text: how

text: often

text: each

text: showed

text: how

text: to

text: manage

text: them.

text: Another

text: potential

text: problem

text: is

text: worker

text: can

text: access

text: the

text: model.

text: In

text: shared-memory

text: systems,

text: the

text: non-convexity

text: of

text: the

text: objective

text: function

text: of

text: FFM,

text: which

text: because

text: each

text: thread

text: can

text: access

text: the

text: model

text: in

text: real-time,

text: it

text: is

text: may

text: lead

text: to

text: some

text: instability

text: in

text: the

text: performance

text: of

text: FFM

text: due

text: possible

text: that

text: the

text: convergence

text: remains

text: the

text: same,

text: as

text: shown

text: in

text: to

text: local

text: minimums.

text: To

text: investigate

text: this,

text: we

text: learned

text: multiple

text: However,

text: in

text: distributed

text: systems,

text: where

text: we

text: need

text: to

text: use

text: FFMs

text: on

text: the

text: same

text: dataset

text: initialized

text: with

text: random

text: weights

text: the

text: network

text: for

text: communication,

text: we

text: can

text: no

text: longer

text: share

text: the

text: as

text: in

text: We

text: observed

text: that

text: all

text: the

text: models

text: have

text: similar

text: per-

text: model

text: among

text: machines

text: in

text: real-time

text: (due

text: to

text: network

text: over-

text: formance

text: of

text: NLL)

text: despite

text: the

text: diﬀerent

text: initializa-

text: head).

text: There

text: are

text: two

text: main

text: ways

text: of

text: distributing

text: a

text: stochastic

text: tions.

text: The

text: local

text: minimum

text: issue

text: is

text: thus

text: not

text: a

text: major

text: concern.

text: gradient

text: algorithm,

text: synchronously

text: and

text: asynchronously.

text: In

text: We

text: also

text: saw

text: above

text: that

text: the

text: number

text: of

text: hyper-parameters

text: both

text: cases,

text: each

text: machine

text: has

text: a

text: subset

text: of

text: the

text: data

text: and

text: its

text: in

text: FFM

text: is

text: larger

text: than

text: for

text: LR

text: with

text: the

text: addition

text: of

text: the

text: learn-

text: own

text: local

text: model

text: and

text: it

text: updates

text: the

text: global

text: model

text: after

text: a

text: ing

text: rate

text: (as

text: we

text: use

text: L-BFGS

text: for

text: training

text: our

text: LR

text: models)

text: and

text: batch

text: of

text: data

text: points

text: has

text: been

text: processed.

text: The

text: asynchronous

text: of

text: the

text: number

text: of

text: latent

text: factors,

text: while

text: we

text: only

text: had

text: the

text: regu-

text: training

text: is

text: often

text: referred

text: to

text: as

text: the

text: parameter

text: server

text: approach

text: larization

text: parameter

text: to

text: tune

text: for

text: LR.

text: This

text: means

text: that

text: tuning

text: some

text: machines

text: are

text: dedicated

text: to

text: storing

text: the

text: global

text: takes

text: more

text: time

text: when

text: improving

text: our

text: models.

text: However,

text: and

text: model

text: and

text: the

text: workers

text: are

text: continuously

text: reading

text: and

text: updat-

text: as

text: discussed

text: in

text: this

text: is

text: not

text: a

text: major

text: problem

text: for

text: multiple

text: ing

text: that

text: model

text: with

text: their

text: local

text: model.

text: The

text: synchronous

text: reasons.

text: First,

text: the

text: performance

text: is

text: not

text: very

text: sensitive

text: to

text: the

text: training

text: on

text: the

text: other

text: hand

text: is

text: referred

text: to

text: as

text: iterative

text: param-

text: number

text: of

text: latent

text: factors

text: and

text: to

text: the

text: regularization

text: parame-

text: eter

text: mixing

text: (IPM)

text: all

text: the

text: models

text: are

text: averaged

text: ter,

text: while

text: a

text: good

text: value

text: for

text: the

text: learning

text: rate

text: is

text: easy

text: to

text: ﬁnd.

text: after

text: a

text: certain

text: amount

text: of

text: data

text: has

text: been

text: processed

text: (e.g.

text: ev-

text: We

text: also

text: found

text: the

text: performance

text: of

text: FFM

text: to

text: be

text: stable

text: over

text: ery

text: epoch).

text: From

text: an

text: engineering

text: point

text: of

text: view,

text: simplicity

text: is

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (a) (b) (c) Fig. 4: Left: Top-down and Right: side view of our environment map Fig. 3: Input to our algorithm consists of (a) 3D geometry, (b) surface discretization. The light depicted here consists of 21 rings and 522 total albedos, and (c) one or more masked reference images with corresponding discrete directions. camera intrinsics and 6-DOF pose. at point p. The BRDF deﬁnes how much of the incident then account for the camera’s vignetting using [11]. While radiance arriving at p along ω is reﬂected in direction ω . multiple reference images can be used in our optimization i o Finally, θ is the angle between ω and the surface normal we ﬁnd a single well-placed image is often sufﬁcient to i i found at p. Figure 5 illustrates these relationships. Using accurately estimate the lighting conditions. Monte Carlo integration we can rewrite Eq. (1) as the ﬁnite D. Environment Light sum: (cid:88) In this work we model light using an environment map [9, 13, 19]. Instead of sampling points in 3D space, en- | | N vironment map lighting admits directional sampling. This L (p, ω ) = 1 f(p, ωo, ωi)Li(p, ωi) cos θi (2) representation works best when approximating lights located o o N p(ω ) i i=1 further from the observed scene. While many works have considered in-scene lighting examples [12, 14], we instead where N is the number of directions ω sampled from the dis- i focus on out-of-scene sources [2, 8, 21, 24]. To compute tribution described by the probability density function (PDF) the direct incident radiance from our environment map Ld p. The incident radiance Li represents both the radiance arriving at a point p we trace a ray with origin p in some coming directly from our light source, which we denote direction ω. If the ray is unobstructed by the scene geometry, by L , and the radiance reﬂected off surrounding surfaces, d point p will receive the full radiance traveling along ω as which we denote by L . Given the recursive nature of path- r determined by the environment map. tracing, we can effectively rewrite the incident radiance L r To compute the radiance emitted by the environment map as exitant radiance L : o along a given direction, we ﬁrst discretize a unit sphere into a ﬁnite number of uniformly spaced points, with each point (cid:48) L (p, ω) = L (p , ω) (3) representing a direction that can be sampled. We perform r o a similar discretization as described in [9] over an entire sphere. The resolution of this discretization is indicated by where p(cid:48) is the point where a ray leaving from p in direction the number of desired rings. The spacing of points around ω ﬁrst intersects the scene. As we recursively bounce rays each ring is computed to be as close to the inter-ring around our scene the BRDF, PDF and cos θ terms of the spacing as possible, as seen in Figure 4. When tracing a ray LTE are compounded. We refer to this product as throughput. along a given direction we determine the nearest-neighbor Formally, the throughput T of the ith point p in our current i direction from the discretized environment map and return path is deﬁned as: (cid:89) its associated RGB value λ as the emitted radiance. IV. LIGHT TRANSPORT EQUATION i f(p , ω − , ω )| cos θ | T(p ) = j j 1 j j (4) In this section we provide a brief overview of the light i p(ω ) j transport equation (LTE), so that the reader may better j=1 understand how we perform our light source estimation. With this deﬁnition of throughput, we can now deﬁne L as: Intuitively, the LTE describes how radiance emitted from a d light source is distributed throughout a scene. Formally, we compute the exitant radiance L leaving a point p in direction Ld(p, ωi) = V (p, ωi)T(p)λi (5) o ω as: (cid:90) o where λ is the estimated radiance for the direction in our i L (p, ω ) = f(p, ω , ω )L (p, ω )| cos θ |dω (1) environment map that is closest to ωi. The visibility function o o H o i i i i i V evaluates to 1 if a ray leaving from point p in direction 2 ω is not obstructed by the scene geometry, and 0 otherwise. i This integral evaluates the amount of incident radiance L To compute the ﬁnal pixel intensity I, we integrate the H i arriving at p over the unit hemisphere 2 oriented with intensities of all rays M arriving at the corresponding point the surface normal found at p. The function f denotes the on our synthetic sensor (of the form of Eq. (2)). Using Monte bidirectional reﬂectance distribution function (BRDF) found Carlo integration we can evaluate this with the ﬁnite sum: ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: (a)

text: (b)

text: (c)

text: Fig.

text: Left:

text: Top-down

text: and

text: Right:

text: side

text: view

text: of

text: our

text: environment

text: map

text: Fig.

text: Input

text: to

text: our

text: algorithm

text: consists

text: of

text: (a)

text: geometry,

text: (b)

text: surface

text: discretization.

text: The

text: light

text: depicted

text: here

text: consists

text: of

text: rings

text: and

text: total

text: albedos,

text: and

text: (c)

text: one

text: or

text: more

text: masked

text: reference

text: images

text: with

text: corresponding

text: discrete

text: directions.

text: camera

text: intrinsics

text: and

text: pose.

text: at

text: point

text: p.

text: The

text: BRDF

text: deﬁnes

text: how

text: much

text: of

text: the

text: incident

text: then

text: account

text: for

text: the

text: camera’s

text: vignetting

text: using

text: While

text: radiance

text: arriving

text: at

text: p

text: along

text: ω

text: is

text: reﬂected

text: in

text: direction

text: ω

text: multiple

text: reference

text: images

text: can

text: be

text: used

text: in

text: our

text: optimization

text: i

text: o

text: Finally,

text: θ

text: is

text: the

text: angle

text: between

text: ω

text: and

text: the

text: surface

text: normal

text: we

text: ﬁnd

text: a

text: single

text: well-placed

text: image

text: is

text: often

text: sufﬁcient

text: to

text: i

text: i

text: found

text: at

text: p.

text: Figure

text: illustrates

text: these

text: relationships.

text: Using

text: accurately

text: estimate

text: the

text: lighting

text: conditions.

text: Monte

text: Carlo

text: integration

text: we

text: can

text: rewrite

text: Eq.

text: as

text: the

text: ﬁnite

text: D.

text: Environment

text: Light

text: sum:

text: In

text: this

text: work

text: we

text: model

text: light

text: using

text: an

text: environment

text: map

text: Instead

text: of

text: sampling

text: points

text: in

text: space,

text: en-

text: N

text: vironment

text: map

text: lighting

text: admits

text: directional

text: sampling.

text: This

text: L

text: (p,

text: ω

text: f(p,

text: ωo,

text: ωi)Li(p,

text: ωi)

text: cos

text: θi

text: representation

text: works

text: best

text: when

text: approximating

text: lights

text: located

text: o

text: o

text: N

text: p(ω

text: i

text: further

text: from

text: the

text: observed

text: scene.

text: While

text: many

text: works

text: have

text: considered

text: in-scene

text: lighting

text: examples

text: we

text: instead

text: where

text: N

text: is

text: the

text: number

text: of

text: directions

text: ω

text: sampled

text: from

text: the

text: dis-

text: i

text: focus

text: on

text: out-of-scene

text: sources

text: To

text: compute

text: tribution

text: described

text: by

text: the

text: probability

text: density

text: function

text: (PDF)

text: the

text: direct

text: incident

text: radiance

text: from

text: our

text: environment

text: map

text: Ld

text: p.

text: The

text: incident

text: radiance

text: Li

text: represents

text: both

text: the

text: radiance

text: arriving

text: at

text: a

text: point

text: p

text: we

text: trace

text: a

text: ray

text: with

text: origin

text: p

text: in

text: some

text: coming

text: directly

text: from

text: our

text: light

text: source,

text: which

text: we

text: denote

text: direction

text: ω.

text: If

text: the

text: ray

text: is

text: unobstructed

text: by

text: the

text: scene

text: geometry,

text: by

text: L

text: and

text: the

text: radiance

text: reﬂected

text: off

text: surrounding

text: surfaces,

text: d

text: point

text: p

text: will

text: receive

text: the

text: full

text: radiance

text: traveling

text: along

text: ω

text: as

text: which

text: we

text: denote

text: by

text: L

text: Given

text: the

text: recursive

text: nature

text: of

text: path-

text: r

text: determined

text: by

text: the

text: environment

text: map.

text: tracing,

text: we

text: can

text: effectively

text: rewrite

text: the

text: incident

text: radiance

text: L

text: r

text: To

text: compute

text: the

text: radiance

text: emitted

text: by

text: the

text: environment

text: map

text: as

text: exitant

text: radiance

text: L

text: o

text: along

text: a

text: given

text: direction,

text: we

text: ﬁrst

text: discretize

text: a

text: unit

text: sphere

text: into

text: a

text: ﬁnite

text: number

text: of

text: uniformly

text: spaced

text: points,

text: with

text: each

text: point

text: L

text: (p,

text: ω)

text: L

text: (p

text: ω)

text: representing

text: a

text: direction

text: that

text: can

text: be

text: sampled.

text: We

text: perform

text: r

text: o

text: a

text: similar

text: discretization

text: as

text: described

text: in

text: over

text: an

text: entire

text: sphere.

text: The

text: resolution

text: of

text: this

text: discretization

text: is

text: indicated

text: by

text: where

text: is

text: the

text: point

text: where

text: a

text: ray

text: leaving

text: from

text: p

text: in

text: direction

text: the

text: number

text: of

text: desired

text: rings.

text: The

text: spacing

text: of

text: points

text: around

text: ω

text: ﬁrst

text: intersects

text: the

text: scene.

text: As

text: we

text: recursively

text: bounce

text: rays

text: each

text: ring

text: is

text: computed

text: to

text: be

text: as

text: close

text: to

text: the

text: inter-ring

text: around

text: our

text: scene

text: the

text: BRDF,

text: PDF

text: and

text: cos

text: θ

text: terms

text: of

text: the

text: spacing

text: as

text: possible,

text: as

text: seen

text: in

text: Figure

text: When

text: tracing

text: a

text: ray

text: LTE

text: are

text: compounded.

text: We

text: refer

text: to

text: this

text: product

text: as

text: throughput.

text: along

text: a

text: given

text: direction

text: we

text: determine

text: the

text: nearest-neighbor

text: Formally,

text: the

text: throughput

text: T

text: of

text: the

text: ith

text: point

text: p

text: in

text: our

text: current

text: i

text: direction

text: from

text: the

text: discretized

text: environment

text: map

text: and

text: return

text: path

text: is

text: deﬁned

text: as:

text: its

text: associated

text: RGB

text: value

text: λ

text: as

text: the

text: emitted

text: radiance.

text: IV.

text: LIGHT

text: TRANSPORT

text: EQUATION

text: i

text: f(p

text: ω

text: ω

text: cos

text: θ

text: T(p

text: j

text: j

text: j

text: j

text: In

text: this

text: section

text: we

text: provide

text: a

text: brief

text: overview

text: of

text: the

text: light

text: i

text: p(ω

text: j

text: transport

text: equation

text: (LTE),

text: so

text: that

text: the

text: reader

text: may

text: better

text: understand

text: how

text: we

text: perform

text: our

text: light

text: source

text: estimation.

text: With

text: this

text: deﬁnition

text: of

text: throughput,

text: we

text: can

text: now

text: deﬁne

text: L

text: as:

text: Intuitively,

text: the

text: LTE

text: describes

text: how

text: radiance

text: emitted

text: from

text: a

text: d

text: light

text: source

text: is

text: distributed

text: throughout

text: a

text: scene.

text: Formally,

text: we

text: compute

text: the

text: exitant

text: radiance

text: L

text: leaving

text: a

text: point

text: p

text: in

text: direction

text: Ld(p,

text: ωi)

text: V

text: (p,

text: ωi)T(p)λi

text: o

text: ω

text: as:

text: o

text: where

text: λ

text: is

text: the

text: estimated

text: radiance

text: for

text: the

text: direction

text: in

text: our

text: i

text: L

text: (p,

text: ω

text: f(p,

text: ω

text: ω

text: )L

text: (p,

text: ω

text: cos

text: θ

text: |dω

text: environment

text: map

text: that

text: is

text: closest

text: to

text: ωi.

text: The

text: visibility

text: function

text: o

text: o

text: H

text: o

text: i

text: i

text: i

text: i

text: i

text: V

text: evaluates

text: to

text: if

text: a

text: ray

text: leaving

text: from

text: point

text: p

text: in

text: direction

text: ω

text: is

text: not

text: obstructed

text: by

text: the

text: scene

text: geometry,

text: and

text: otherwise.

text: i

text: This

text: integral

text: evaluates

text: the

text: amount

text: of

text: incident

text: radiance

text: L

text: To

text: compute

text: the

text: ﬁnal

text: pixel

text: intensity

text: I,

text: we

text: integrate

text: the

text: H

text: i

text: arriving

text: at

text: p

text: over

text: the

text: unit

text: hemisphere

text: oriented

text: with

text: intensities

text: of

text: all

text: rays

text: M

text: arriving

text: at

text: the

text: corresponding

text: point

text: the

text: surface

text: normal

text: found

text: at

text: p.

text: The

text: function

text: f

text: denotes

text: the

text: on

text: our

text: synthetic

text: sensor

text: (of

text: the

text: form

text: of

text: Eq.

text: Using

text: Monte

text: bidirectional

text: reﬂectance

text: distribution

text: function

text: (BRDF)

text: found

text: Carlo

text: integration

text: we

text: can

text: evaluate

text: this

text: with

text: the

text: ﬁnite

text: sum:

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: n the collective probability of sampling unreachable lights is high enough, it could have a negative impact on the ω ω variance of our path-traces. This concept is explained further o i θ in the follow sections. With this additional term our ﬁnal i objectivation function E becomes: p E = E + Φ (9) p Fig. 5: Components of a single ray bounce in the LTE. p is the point of intersection, ωo is the direction of exitant radiance Lo, ωi is the direction B. Light Transport Derivatives of incident radiance Li, n is the surface normal found at p, and θi is the angle between n and ωi. In order to perform our light optimization we ﬁrst need to compute the Jacobian of partial derivatives of pixel values (cid:88) with respect to the lighting parameters. We initialize the Jacobian with all values set to zero. We then populate the M 1 L (p , ω ) values of the Jacobian by tracing the given scene with our I = o i i (6) M p(ω ) custom path-tracer. For each pixel sample we construct the i i=1 path a ray of light takes as it bounces around the scene, where p refers to the point where a ray originating from our while computing the throughput of the path as described in i sensor and traveling along ω ﬁrst intersects with the scene. Section . When a ray eventually samples the light source, we i For more information on path-tracing and the LTE see [18]. add the ray’s ﬁnal throughput to the corresponding value in V. LIGHT SOURCE ESTIMATION the Jacobian. Following Eq. (5), we can formally deﬁne the In this section we present our algorithm for light source partial derivative of the pixel Ii with respect to the sampled estimation. We construct the optimization problem by ﬁrst light λj for each color cha(cid:88)nnel c as the ﬁnite sum: initializing all lighting parameters to be near zero, resulting K in a completely dark scene. As light parameters are uniformly ∂Ii,c = 1 V (pk, ωj)Tc(pk) (10) initialized, each light starts with the same probability of ∂λ MN p(ω ) j,c i k=1 being sampled. A. Objective where K is the number of samples for pixel I that sample i light source λ , p is the ﬁnal point on in path k before Our objective function minimizes the photometric error j k { } sampling the light source, and T is the throughput value for between the set of original reference image I and a set c { } o color channel c. of corresponding reconstructed images I , which depict r In additional to the partial derivatives corresponding to our current lighting estimation. So the photometric error E (cid:88) (cid:88) p the images formation, we also need to compute the partial can be deﬁned as: derivatives for our activation cost. Following Eq. (8) we − compute the partial derivative of the activation cost Φ with E = (I (p) I (p))2 (7) i p ∈ o,i r,i respect to the light λi for each c(cid:80)olor channel c as: i p Pi ∂Φ αβ Given the prevalence of large discrepancies caused by i = (11) ∂λ 1 + β( n λ ) an imperfect scene reconstruction or under-sampling, we i,c j=1 i,j employ the Cauchy robust norm on the raw photometric error C. Gradient Descent values. Due to the potential over-parameterization of lighting, Having estimated our Jacobian, we can now perform the an activation penalty function is used as an additional cost. light location and intensity optimization. As our Jacobian Each light direction λ has an associated activation penalty i Φ deﬁned as: (cid:88) will typically be extremely large, dense, and exhibit no i anticipated structure we can leverage, we employ gradient n descent with backtracking as inverting or decomposing the Φi = α log(1 + β λi,c) (8) Jacobian would be computationally prohibitive. To account c=1 for the inherent constraint that light parameters cannot be where α and β are constant weights and n is the number negative we apply gradient projection after each update of channels in our images. This logarithmic cost penalizes [20]. We continue this process until the optimization has the initial activation of a light direction but then plateaus as converged, as indicated by the Wolfe conditions on gradient the intensity of light increases. Increasing the weight of α magnitude [17]. D. Sequential Monte Carlo and β favor solutions with fewer activated lights. The use of an activation cost has the additional beneﬁt of completely As described in Section , we leverage importance sampling disabling lights that can never be sampled due to the scene when tracing the scene, so that our estimated derivatives geometry and viewing angle of the reference images. While will exhibit a lower amount of variance while using a all lighting parameters are initialized to be near zero, if smaller number of samples. However, when we ﬁrst construct ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: n

text: the

text: collective

text: probability

text: of

text: sampling

text: unreachable

text: lights

text: is

text: high

text: enough,

text: it

text: could

text: have

text: a

text: negative

text: impact

text: on

text: the

text: ω

text: ω

text: variance

text: of

text: our

text: path-traces.

text: This

text: concept

text: is

text: explained

text: further

text: o

text: i

text: θ

text: in

text: the

text: follow

text: sections.

text: With

text: this

text: additional

text: term

text: our

text: ﬁnal

text: i

text: objectivation

text: function

text: E

text: becomes:

text: p

text: E

text: E

text: Φ

text: p

text: Fig.

text: Components

text: of

text: a

text: single

text: ray

text: bounce

text: in

text: the

text: LTE.

text: p

text: is

text: the

text: point

text: of

text: intersection,

text: ωo

text: is

text: the

text: direction

text: of

text: exitant

text: radiance

text: Lo,

text: ωi

text: is

text: the

text: direction

text: B.

label: section

text: Light

text: Transport

text: Derivatives

text: of

text: incident

text: radiance

text: Li,

text: n

text: is

text: the

text: surface

text: normal

text: found

text: at

text: p,

text: and

text: θi

text: is

text: the

text: angle

text: between

text: n

text: and

text: ωi.

text: In

text: order

text: to

text: perform

text: our

text: light

text: optimization

text: we

text: ﬁrst

text: need

text: to

text: compute

text: the

text: Jacobian

text: of

text: partial

text: derivatives

text: of

text: pixel

text: values

text: with

text: respect

text: to

text: the

text: lighting

text: parameters.

text: We

text: initialize

text: the

text: Jacobian

text: with

text: all

text: values

text: set

text: to

text: zero.

text: We

text: then

text: populate

text: the

text: M

text: L

text: (p

text: ω

text: values

text: of

text: the

text: Jacobian

text: by

text: tracing

text: the

text: given

text: scene

text: with

text: our

text: I

text: o

text: i

text: i

text: M

text: p(ω

text: custom

text: path-tracer.

text: For

text: each

text: pixel

text: sample

text: we

text: construct

text: the

text: i

text: path

text: a

text: ray

text: of

text: light

text: takes

text: as

text: it

text: bounces

text: around

text: the

text: scene,

text: where

text: p

text: refers

text: to

text: the

text: point

text: where

text: a

text: ray

text: originating

text: from

text: our

text: while

text: computing

text: the

text: throughput

text: of

text: the

text: path

text: as

text: described

text: in

text: i

text: sensor

text: and

text: traveling

text: along

text: ω

text: ﬁrst

text: intersects

text: with

text: the

text: scene.

text: Section

text: When

text: a

text: ray

text: eventually

text: samples

text: the

text: light

text: source,

text: we

text: i

text: For

text: more

text: information

text: on

text: path-tracing

text: and

text: the

text: LTE

text: see

text: add

text: the

text: ray’s

text: ﬁnal

text: throughput

text: to

text: the

text: corresponding

text: value

text: in

text: V.

text: LIGHT

text: SOURCE

text: ESTIMATION

text: the

text: Jacobian.

text: Following

text: Eq.

text: we

text: can

text: formally

text: deﬁne

text: the

text: In

text: this

text: section

text: we

text: present

text: our

text: algorithm

text: for

text: light

text: source

text: partial

text: derivative

text: of

text: the

text: pixel

text: Ii

text: with

text: respect

text: to

text: the

text: sampled

text: estimation.

text: We

text: construct

text: the

text: optimization

text: problem

text: by

text: ﬁrst

text: light

text: λj

text: for

text: each

text: color

text: c

text: as

text: the

text: ﬁnite

text: sum:

text: initializing

text: all

text: lighting

text: parameters

text: to

text: be

text: near

text: zero,

text: resulting

text: K

text: in

text: a

text: completely

text: dark

text: scene.

text: As

text: light

text: parameters

text: are

text: uniformly

text: ∂Ii,c

text: V

text: (pk,

text: ωj)Tc(pk)

text: initialized,

text: each

text: light

text: starts

text: with

text: the

text: same

text: probability

text: of

text: ∂λ

text: MN

text: p(ω

text: j,c

text: i

text: being

text: sampled.

text: A.

text: Objective

text: where

text: K

text: is

text: the

text: number

text: of

text: samples

text: for

text: pixel

text: I

text: that

text: sample

text: i

text: light

text: source

text: λ

text: p

text: is

text: the

text: ﬁnal

text: point

text: on

text: in

text: path

text: k

text: before

text: Our

text: objective

text: function

text: minimizes

text: the

text: photometric

text: error

text: j

text: k

text: sampling

text: the

text: light

text: source,

text: and

text: T

text: is

text: the

text: throughput

text: value

text: for

text: between

text: the

text: set

text: of

text: original

text: reference

text: image

text: I

text: and

text: a

text: set

text: c

text: o

text: color

text: channel

text: c.

text: of

text: corresponding

text: reconstructed

text: images

text: I

text: which

text: depict

text: r

text: In

text: additional

text: to

text: the

text: partial

text: derivatives

text: corresponding

text: to

text: our

text: current

text: lighting

text: estimation.

text: So

text: the

text: photometric

text: error

text: E

text: p

text: the

text: images

text: formation,

text: we

text: also

text: need

text: to

text: compute

text: the

text: partial

text: can

text: be

text: deﬁned

text: as:

text: derivatives

text: for

text: our

text: activation

text: cost.

text: Following

text: Eq.

text: we

text: compute

text: the

text: partial

text: derivative

text: of

text: the

text: activation

text: cost

text: Φ

text: with

text: E

text: (I

text: (p)

text: I

text: i

text: p

text: o,i

text: r,i

text: respect

text: to

text: the

text: light

text: λi

text: for

text: each

text: channel

text: c

text: as:

text: i

text: p

text: Pi

text: ∂Φ

text: αβ

text: Given

text: the

text: prevalence

text: of

text: large

text: discrepancies

text: caused

text: by

text: i

text: ∂λ

text: β(

text: n

text: λ

text: an

text: imperfect

text: scene

text: reconstruction

text: or

text: under-sampling,

text: we

text: i,c

text: i,j

text: employ

text: the

text: Cauchy

text: robust

text: norm

text: on

text: the

text: raw

text: photometric

text: error

text: C.

text: Gradient

text: Descent

text: values.

text: Due

text: to

text: the

text: potential

text: over-parameterization

text: of

text: lighting,

text: Having

text: estimated

text: our

text: Jacobian,

text: we

text: can

text: now

text: perform

text: the

text: an

text: activation

text: penalty

text: function

text: is

text: used

text: as

text: an

text: additional

text: cost.

text: light

text: location

text: and

text: intensity

text: optimization.

text: As

text: our

text: Jacobian

text: Each

text: light

text: direction

text: λ

text: has

text: an

text: associated

text: activation

text: penalty

text: i

text: Φ

text: deﬁned

text: as:

text: will

text: typically

text: be

text: extremely

text: large,

text: dense,

text: and

text: exhibit

text: no

text: i

text: anticipated

text: structure

text: we

text: can

text: leverage,

text: we

text: employ

text: gradient

text: n

text: descent

text: with

text: backtracking

text: as

text: inverting

text: or

text: decomposing

text: the

text: Φi

text: α

text: β

text: λi,c)

text: Jacobian

text: would

text: be

text: computationally

text: prohibitive.

text: To

text: account

text: for

text: the

text: inherent

text: constraint

text: that

text: light

text: parameters

text: cannot

text: be

text: where

text: α

text: and

text: β

text: are

text: constant

text: weights

text: and

text: n

text: is

text: the

text: number

text: negative

text: we

text: apply

text: gradient

text: projection

text: after

text: each

text: update

text: of

text: channels

text: in

text: our

text: images.

text: This

text: logarithmic

text: cost

text: penalizes

text: We

text: continue

text: this

text: process

text: until

text: the

text: optimization

text: has

text: the

text: initial

text: activation

text: of

text: a

text: light

text: direction

text: but

text: then

text: plateaus

text: as

text: converged,

text: as

text: indicated

text: by

text: the

text: Wolfe

text: conditions

text: on

text: gradient

text: the

text: intensity

text: of

text: light

text: increases.

text: Increasing

text: the

text: weight

text: of

text: α

text: magnitude

text: D.

text: Sequential

text: Monte

text: Carlo

text: and

text: β

text: favor

text: solutions

text: with

text: fewer

text: activated

text: lights.

text: The

text: use

text: of

text: an

text: activation

text: cost

text: has

text: the

text: additional

text: beneﬁt

text: of

text: completely

text: As

text: described

text: in

text: Section

text: we

text: leverage

text: importance

text: sampling

text: disabling

text: lights

text: that

text: can

text: never

text: be

text: sampled

text: due

text: to

text: the

text: scene

text: when

text: tracing

text: the

text: scene,

text: so

text: that

text: our

text: estimated

text: derivatives

text: geometry

text: and

text: viewing

text: angle

text: of

text: the

text: reference

text: images.

text: While

text: will

text: exhibit

text: a

text: lower

text: amount

text: of

text: variance

text: while

text: using

text: a

text: all

text: lighting

text: parameters

text: are

text: initialized

text: to

text: be

text: near

text: zero,

text: if

text: smaller

text: number

text: of

text: samples.

text: However,

text: when

text: we

text: ﬁrst

text: construct

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Speciﬁcally, given a sa(cid:104)mple {ξ (cid:88)}N(cid:48) ,(cid:88)the g(cid:2)ap observations(cid:3)are then calcu(cid:105)lated as j j=1 Gap = c(cid:62)(cid:104)xˆ + (cid:88) (cid:88)E Φ(cid:2) (ξt)h (ξt)(cid:62) βˆ(cid:3) + F (βˆ, ξ ) (cid:105) j 1 1 tk t tk j ∈ ∈ t [T] k [Kt] − (cid:62) E (cid:62) d γˆ + Φ (ξt)b (ξt) αˆ + G(αˆ, ξ ) , 1 1 tk t tk j ∈ ∈ t [T] k [Kt] ∈ (cid:48) for j [N ]. These values can then be used to construct a conﬁdence interval on the gap. 4 Illustrative example: capacity expansion In this section, we present results from a capacity expansion problem which illustrate that two-stage LDR has the potential to yield better bounds and policies for MSLP than static LDR. 4.1 Problem description We consider a variant of the stochastic capacity expansion problem given in [14]. We wish to determine an investment schedule over T stages for the installation of new capacities of I diﬀerent power generation technologies, together with some operational decisions to meet demand for power over time. The demand is modeled by a load duration curve, which is approximated by partitioning each stage into J segments (of possibly diﬀerent length). ∈ ∈ The demand corresponding to segment j [J] in t [T ] is denoted by d . The amount tj ∈ ∈ of new capacity of technology i [I] added in stage t [T ] is represented by u+, and is ti assumed to be available for use immediately, i.e., at the beginning of stage t. The unit cost of u+ is denoted by cu+. The state variable s represents the current installed capacity of ti ∈ ti ti ∈ technology i [I] in the beginning of stage t [T ], which incurs holding cost of cs per ∈ ti unit. We assume that it is possible to discard (i.e., remove) some capacity of i [I] in ∈ − − ∈ t [T ], denoted by u , at a (possibly zero) unit cost of cu . The operating level of i [I] ∈ ti ∈ ti at t [T ] for meeting the demand in segment j [J] is represented by the decision variable x , while the amount of unsatisﬁed demand is represented as z , whose unit costs are cx tij tj tij and cz , respectively. Then, the stochastic capacity expansion problem is formulated as an tj 19

text: Speciﬁcally,

text: given

text: a

text: {ξ

text: then

text: as

text: j

text: Gap

text: (ξt)h

text: F

text: (βˆ,

text: ξ

text: j

text: tk

text: t

text: tk

text: j

text: t

text: [T]

text: k

text: [Kt]

text: E

text: d

text: γˆ

text: Φ

text: (ξt)b

text: (ξt)

text: αˆ

text: G(αˆ,

text: ξ

text: tk

text: t

text: tk

text: j

text: t

text: [T]

text: k

text: [Kt]

text: for

text: j

text: [N

text: These

text: values

text: can

text: then

text: be

text: used

text: to

text: construct

text: a

text: conﬁdence

text: interval

text: on

text: the

text: gap.

text: Illustrative

text: example:

text: capacity

text: expansion

text: In

text: this

text: section,

text: we

text: present

text: results

text: from

text: a

text: capacity

text: expansion

text: problem

text: which

text: illustrate

text: that

text: two-stage

text: LDR

text: has

text: the

text: potential

text: to

text: yield

text: better

text: bounds

text: and

text: policies

text: for

text: MSLP

text: than

text: static

text: LDR.

text: Problem

text: description

text: We

text: consider

text: a

text: variant

text: of

text: the

text: stochastic

text: capacity

text: expansion

text: problem

text: given

text: in

text: We

text: wish

text: to

text: determine

text: an

text: investment

text: schedule

text: over

text: T

text: stages

text: for

text: the

text: installation

text: of

text: new

text: capacities

text: of

text: I

text: diﬀerent

text: power

text: generation

text: technologies,

text: together

text: with

text: some

text: operational

text: decisions

text: to

text: meet

text: demand

text: for

text: power

text: over

text: time.

text: The

text: demand

text: is

text: modeled

text: by

text: a

text: load

text: duration

text: curve,

text: which

text: is

text: approximated

text: by

text: partitioning

text: each

text: stage

text: into

text: J

text: segments

text: (of

text: possibly

text: diﬀerent

text: length).

text: The

text: demand

text: corresponding

text: to

text: segment

text: j

text: [J]

text: in

text: t

text: [T

text: is

text: denoted

text: by

text: d

text: The

text: amount

text: tj

text: of

text: new

text: capacity

text: of

text: technology

text: i

text: [I]

text: added

text: in

text: stage

text: t

text: [T

text: is

text: represented

text: by

text: u+,

text: and

text: is

text: ti

text: assumed

text: to

text: be

text: available

text: for

text: use

text: immediately,

text: i.e.,

text: at

text: the

text: beginning

text: of

text: stage

text: t.

text: The

text: unit

text: cost

text: of

text: u+

text: is

text: denoted

text: by

text: cu+.

text: The

text: state

text: variable

text: s

text: represents

text: the

text: current

text: installed

text: capacity

text: of

text: ti

text: ti

text: ti

text: technology

text: i

text: [I]

text: in

text: the

text: beginning

text: of

text: stage

text: t

text: [T

text: which

text: incurs

text: holding

text: cost

text: of

text: cs

text: per

text: ti

text: unit.

text: We

text: assume

text: that

text: it

text: is

text: possible

text: to

text: discard

text: (i.e.,

text: remove)

text: some

text: capacity

text: of

text: i

text: [I]

text: in

text: t

text: [T

text: denoted

text: by

text: u

text: at

text: a

text: (possibly

text: zero)

text: unit

text: cost

text: of

text: cu

text: The

text: operating

text: level

text: of

text: i

text: [I]

text: ti

text: ti

text: at

text: t

text: [T

text: for

text: meeting

text: the

text: demand

text: in

text: segment

text: j

text: [J]

text: is

text: represented

text: by

text: the

text: decision

text: variable

text: x

text: while

text: the

text: amount

text: of

text: unsatisﬁed

text: demand

text: is

text: represented

text: as

text: z

text: whose

text: unit

text: costs

text: are

text: cx

text: tij

text: tj

text: tij

text: and

text: cz

text: respectively.

text: Then,

text: the

text: stochastic

text: capacity

text: expansion

text: problem

text: is

text: formulated

text: as

text: an

text: tj