The RIPr fit minimises \(KL(Q \| P)\) over mixtures P whose
components lie in the null. An oracle proposes the next component to
bring in; fw_step() and lb_step() differ only in how far ahead they look.
Details
Write \(P_i\) for the current mixture and \(G(\theta) = E_Q[P_\theta / P_i] = E_\theta[Q / P_i]\).
The Frank–Wolfe (Jaggi 2013)
linear oracle fw_step() asks
how fast KL falls as an infinitesimal amount of mass moves towards
\(P_\theta\):
$$\left.\frac{d}{d\epsilon} KL\!\left(Q \,\|\, (1-\epsilon) P_i + \epsilon P_\theta\right)\right|_{\epsilon=0} = 1 - G(\theta).$$
Equivalently, it finds where in the null the likelihood ratio
\(R_i=Q/P_i\) most fails to be an e-variable. The attained
\(\sup_{\theta \in \Theta_0} G(\theta) = 1 + \mathrm{gap}\)
bounds the KL suboptimality by Frank–Wolfe duality. Since the search is
non-convex, the reported gap is only a lower bound on the true gap. It is
the gap of the mixture the step started from, so it fills the previous
row's gap_after.
The Li–Barron (Li and Barron 1999)
greedy oracle lb_step()
does not linearise; it picks the atom minimising KL after choosing its
weight:
$$\theta^* = \arg\min_{\theta \in \Theta_0} KL\!\left(Q \,\|\, (1 - w(\theta)) P_i + w(\theta) P_\theta\right),$$
where \(w(\theta)\) comes from the weight update. Each
candidate may therefore cost a line search, or a full weight solve under
correction. It has no duality bound; record_gap = TRUE estimates the
Frank–Wolfe gap with an extra linear-oracle sweep, without adding its atom.
What a trace row records
Every verb writes one row per step to state@trace. A row spans a step, so
its columns split by which mixture they measure.
step,phaseThe row's index (
ripr_init()'s row is 0) and the verb that wrote it:"init", or the verb's name without_step, such as"fw"forfw_step(). Count steps of a kind with e.g.cumsum(trace$phase == "fw").oracle_value,oracle_thetaWhat the step's own search found at the mixture it stepped from. For
fw_step(),oracle_thetais the linear oracle's maximiser andoracle_valueisNA(its value is the previous row'sgap_after + 1); likewise forsfw_step(), whoseklis measured after the slide. Forlb_step()oracle_valueis the Li–Barron objective, not a gap; forweight_step()andct_step()it is the support gap before the step, plus one, with nooracle_theta. Whenpartis notNA, the atom went tooracle_theta.kl,gap_after,gap_after_theta,gap_after_partThe mixture the row produced, and the linear oracle's gap, maximiser and part for it. Filled by
record_gap = TRUEor the nextfw_step(); otherwiseNA.gap_after_elapsedSeconds the search that filled
gap_aftertook.part,step_size,direction,support_size,max_weightWhere an oracle step put its atom (
NAif none), the step length and direction, and the size and heaviest weight of the produced mixture.elapsedSeconds of the step rule's work, excluding diagnostics (
record_gap,snapshot,until). Anfw_step()row includes the linear-oracle search it consumed, even if cached. Per step; usecumsum(trace$elapsed)for the total.
Both theta columns are list columns holding the family's parameter, with
NA for rows that recorded none.
state@oracle caches the linear oracle's result for the current mixture
only: a step that changes the mixture clears it and record_gap = TRUE
sets it. fw_step() uses the cache when present, so an fw run pays one
search per step. The final row's gap_after stays NA unless
record_gap = TRUE or until stopped the run; ripr_finish(record_gap = TRUE) measures the mixture it returns.
Which to use
Prefer fw_step(): it is cheaper per iteration with similar guarantees
(none of which strictly hold, since the oracle is heuristic).
Expect the two to disagree sharply on the gap even if the KL is similar. Frank–Wolfe places its atom exactly at the worst-case \(\theta\), absorbing the point that defines the gap; Li–Barron places it wherever post-step KL is smallest, leaving that point untouched.