Skip to contents

Frank–Wolfe step

Source: R/fit.R
fw_step.Rd

Maximises \(G(\theta)\) over the null, then moves the iterate towards the maximiser; see oracles. The search is skipped if state@oracle already holds it (e.g. after record_gap = TRUE), so each step costs one search.

Usage

fw_step(
  state,
  times = 1L,
  variant = c("standard", "away-step", "pairwise"),
  size = c("line-search", "fixed"),
  correct_weights = FALSE,
  insert = c("single", "multi"),
  record_gap = FALSE,
  until = NULL
)

Arguments

state

A ripr_state.

times

Steps to take.

variant

Which Frank–Wolfe algorithm to run. "standard" moves only towards the oracle's atom. "away-step" may instead move away from the worst current atom, whichever maximises \(\langle -\nabla f, d\rangle\). "pairwise" moves mass from that worst atom directly to the new one.

size

"line-search", or "fixed" for the open-loop schedule.

correct_weights

Re-solve the weights with atoms fixed after each step, by the weight_solver set in ripr_control() (as weight_step() does). The solve replaces the step variant and size would choose, so setting either alongside it is an error.

insert

"single" adds the oracle's atom. "multi" also adds every other distinct local maximiser of \(G\) with \(G > 1\) that the oracle's multi-start found. This is the multi-point insertion of PDAP (Pieper and Walter 2021) . Needs correct_weights = TRUE, since only the weight solve can give the extra atoms mass.

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

correct_weights = TRUE gives fully-corrective Frank–Wolfe: after each step every weight is re-solved to optimality over the current atoms.

References

Pieper K, Walter D (2021). “Linear convergence of accelerated conditional gradient algorithms in spaces of measures.” ESAIM: Control, Optimisation and Calculus of Variations, 27, 38.

See also

oracles, predicates

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) |> fw_step(times = 10L)
state@trace$kl
#>  [1] 0.024511510 0.016814201 0.016233235 0.014378214 0.014067308 0.010669095
#>  [7] 0.009956367 0.009264086 0.006123735 0.006009159 0.005895949

# Where each step put its atom.
do.call(rbind, state@trace$oracle_theta[state@trace$phase == "fw"])
#>            [,1]       [,2]      [,3]
#>  [1,] 0.5000000 0.50000000 0.0000000
#>  [2,] 0.5000000 0.00000000 0.5000000
#>  [3,] 0.4364247 0.43642469 0.1271506
#>  [4,] 0.4813254 0.03734924 0.4813254
#>  [5,] 0.3934494 0.39344935 0.2131013
#>  [6,] 0.5000000 0.00000000 0.5000000
#>  [7,] 0.4128027 0.17439464 0.4128027
#>  [8,] 0.3713623 0.37136235 0.2572753
#>  [9,] 0.4808577 0.03828451 0.4808577
#> [10,] 0.4382642 0.43826423 0.1234715