Sliding Frank–Wolfe step

One iteration of sliding Frank–Wolfe (Denoyelle et al. 2020) : a fully-corrective Frank–Wolfe step towards the linear oracle's atom (as fw_step(correct_weights = TRUE)), then a slide: a local descent of the KL over every weight and atom position jointly, each atom kept in its own part. Where fw_step() only adds atoms and em_step() moves them one at a time with the weights fixed, the slide moves them all together, so the support may settle in far fewer oracle calls.

Usage

sfw_step(state, times = 1L, record_gap = FALSE, until = NULL)

Arguments

state: A ripr_state.
times: Steps to take.
record_gap: Sweep the Frank–Wolfe oracle over the produced mixture after each step, filling gap_after. Earlier rows fill anyway from the next step's search, so TRUE buys the final row's gap for about one extra step.
until: Optional predicate function(state, candidate) tested before each step; see predicates.

Value

The updated ripr_state.

Details

The slide never increases KL. Atoms of the same part that slide onto the same point (to within merge_atol and merge_rtol from ripr_control()) are merged at their weight-averaged position, and atoms whose weight reaches zero are dropped. Since each step consumes one linear-oracle search, gap_below() works as until, as for fw_step(). The slide's tolerance and evaluation cap are slide_xtol and slide_max_eval in ripr_control().

A state that did not come from sfw_step() (fresh from ripr_init(), or last advanced by another verb) has its atoms slid once before the first insertion, and the oracle is searched again for the slid mixture. Without this the first Frank–Wolfe step can move all the mass onto the oracle's atom and leave a single atom whose oracle points barely lower the KL; with it, the incoming atoms are positioned before any is dropped.

References

Denoyelle Q, Duval V, Peyré G, Soubies E (2020). “The sliding Frank–Wolfe algorithm and its application to super-resolution microscopy.” Inverse Problems, 36(1), 014001.

Examples

set.seed(1)
fam <- multinomial_family(n_trials = 4L, k = 3L)
plurality <- null_model(
  fam,
  list(
    simplex_region(vertices = rbind(c(0.5, 0.5, 0), c(0, 1, 0), c(0, 0, 1))),
    simplex_region(vertices = rbind(c(0.5, 0, 0.5), c(0, 1, 0), c(0, 0, 1)))
  )
)
Q <- fam(c(0.4, 0.35, 0.25))
state <- ripr_init(Q, plurality) |>
  sfw_step(times = 10L, until = gap_below(1e-8))
state@trace[c("phase", "kl", "gap_after", "support_size")]
#>   phase          kl gap_after support_size
#> 1  init 0.024511510 0.2134123            2
#> 2   sfw 0.003144607 0.0000000            2