Utilities and data structures

AbstractActiveSet{AT, R, IT}

Abstract type for an active set of atoms of type AT with weights of type R and iterate of type IT. An active set is typically expected to have a field weights, a field atoms, and a field x. Otherwise, all active set methods from src/active_set.jl can be overwritten.

ActiveSet{AT, R, IT}

Represents an active set of extreme vertices collected in a FW algorithm, along with their coefficients (λ_i, a_i). R is the type of the λ_i, AT is the type of the atoms a_i. The iterate x = ∑λ_i a_i is stored in x with type IT.

Copies an active set, the weight and atom vectors and the iterate. Individual atoms are not copied.

active_set_argmin(active_set::AbstractActiveSet, direction)

Computes the linear minimizer in the direction on the active set. Returns (λ_i, a_i, i)

active_set_argminmax(active_set::AbstractActiveSet, direction)

Computes the linear minimizer in the direction on the active set. Returns (λ_min, a_min, i_min, val_min, λ_max, a_max, i_max, val_max, val_max-val_min ≥ Φ)

active_set_initialize!(as, v)

Resets the active set structure to a single vertex v with unit weight.

active_set_update!(active_set::AbstractActiveSet, lambda, atom)

Adds the atom to the active set with weight lambda or adds lambda to existing atom.

active_set_update_iterate_pairwise!(x, lambda, fw_atom, away_atom)

Operates x ← x + λ a_fw - λ a_aw.

active_set_update_scale!(x, lambda, atom)

Operates x ← (1-λ) x + λ a.

compute_active_set_iterate!(active_set::AbstractActiveSet) -> x

Recomputes from scratch the iterate x from the current weights and vertices of the active set. Returns the iterate x.

get_active_set_iterate(active_set)

Return the current iterate corresponding. Does not recompute it.

ObjectiveFunction

Represents an objective function optimized by algorithms. Subtypes of ObjectiveFunction must implement at least

• compute_value(::ObjectiveFunction, x) for primal value evaluation
• compute_gradient(::ObjectiveFunction, x) for gradient evaluation.

and optionally compute_value_gradient(::ObjectiveFunction, x) returning the (primal, gradient) pair. compute_gradient may always use the same storage and return a reference to it.

SimpleFunctionObjective{F,G,S}

An objective function built from separate primal objective f(x) and in-place gradient function grad!(storage, x). It keeps an internal storage of type s used to evaluate the gradient in-place.

StochasticObjective{F, G, XT, S}(f::F, grad!::G, xs::XT, storage::S)

Represents a composite function evaluated with stochastic gradient. f(θ, x) evaluates the loss for a single data point x and parameter θ. grad!(storage, θ, x) adds to storage the partial gradient with respect to data point x at parameter θ. xs must be an indexable iterable (Vector{Vector{Float64}} for instance). Functions using a StochasticObjective have optional keyword arguments rng, batch_size and full_evaluation controlling whether the function should be evaluated over all data points.

Note: grad! must not reset the storage to 0 before adding to it.

compute_gradient(f::ObjectiveFunction, x; [kwargs...])

Computes the gradient of f at x. May return a reference to an internal storage.

compute_value(f::ObjectiveFunction, x; [kwargs...])

Computes the objective f at x.

compute_value_gradient(f::ObjectiveFunction, x; [kwargs...])

Computes in one call the pair (value, gradient) evaluated at x. By default, calls compute_value and compute_gradient with keywords kwargs passed down to both.

Main structure created before and passed to the callback in first position.

ScaledHotVector{T}

Represents a vector of at most one value different from 0.

RankOneMatrix{T, UT, VT}

Represents a rank-one matrix R = u * vt'. Composes like a charm.

ConstantBatchIterator(batch_size)

Batch iterator always returning a constant batch size.

ConstantMomentumIterator{T}

Iterator for momentum with a fixed damping value, always return the value and a dummy state.

Vertex storage to store dropped vertices or find a suitable direction in lazy settings. The algorithm will look for at most return_kth suitable atoms before returning the best. See Extra-lazification with a vertex storage for usage.

A vertex storage can be any type that implements two operations:

1. Base.push!(storage, atom) to add an atom to the storage.

Note that it is the storage type responsibility to ensure uniqueness of the atoms present.

1. storage_find_argmin_vertex(storage, direction, lazy_threshold) -> (found, vertex)

returning whether a vertex with sufficient progress was found and the vertex. It is up to the storage to remove vertices (or not) when they have been picked up.

ExpMomentumIterator{T}

Iterator for the momentum used in the variant of Stochastic Frank-Wolfe. Momentum coefficients are the values of the iterator: ρ_t = 1 - num / (offset + t)^exp

The state corresponds to the iteration count.

Source: Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization Aryan Mokhtari, Hamed Hassani, Amin Karbasi, JMLR 2020.

IncrementBatchIterator(starting_batch_size, max_batch_size, [increment = 1])

Batch size starting at startingbatchsize and incrementing by increment at every iteration.

_unsafe_equal(a, b)

Like isequal on arrays but without the checks. Assumes a and b have the same axes.

batchsize_iterate(iter::BatchSizeIterator) -> b

Method to implement for a batch size iterator of type BatchSizeIterator. Calling batchsize_iterate returns the next batch size and typically update the internal state of iter.

momentum_iterate(iter::MomentumIterator) -> ρ

Method to implement for a type MomentumIterator. Returns the next momentum value ρ and updates the iterator internal state.

muladd_memory_mode(memory_mode::MemoryEmphasis, d, x, v)

Performs d = x - v in-place or not depending on MemoryEmphasis

(memory_mode::MemoryEmphasis, storage, x, gamma::Real, d)

Performs storage = x - gamma * d in-place or not depending on MemoryEmphasis

(memory_mode::MemoryEmphasis, x, gamma::Real, d)

Performs x = x - gamma * d in-place or not depending on MemoryEmphasis

Give the vertex v in the storage that minimizes s = direction ⋅ v and whether s achieves s ≤ lazy_threshold.

trajectory_callback(storage)

Callback pushing the state at each iteration to the passed storage. The state data is only the 5 first fields, usually: (t,primal,dual,dual_gap,time)

A function acting like the normal objective f but tracking the number of calls.

A function acting like the normal grad! but tracking the number of calls.

TrackingLMO{LMO}(lmo)

An LMO wrapping another one and tracking the number of calls.

Update order for a block-coordinate method. A BlockCoordinateUpdateOrder must implement

select_update_indices(::BlockCoordinateUpdateOrder, s::CallbackState, dual_gaps)

select_update_indices(::BlockCoordinateUpdateOrder, s::CallbackState, dual_gaps)

Returns a list of lists of the block indices. Each sublist represents one round of updates in an iteration. The indices in a list show which blocks should be updated parallely in one round. For example, a full update is given by [1:l] and a blockwise update by [[i] for i=1:l], where l is the number of blocks.

The full update initiates a parallel update of all blocks in one single round.

The cyclic update initiates a sequence of update rounds. In each round only one block is updated. The order of the blocks is determined by the given order of the LMOs.

The stochastic update initiates a sequence of update rounds. In each round only one block is updated. The order of the blocks is a random.

Update step for block-coordinate Frank-Wolfe. These are implementations of different FW-algorithms to be used in a blockwise manner. Each update step must implement

update_iterate(
    step::UpdateStep,
    x,
    lmo,
    f,
    gradient,
    grad!,
    dual_gap,
    t,
    line_search,
    linesearch_workspace,
    memory_mode,
    epsilon,
)

update_iterate(
    step::UpdateStep,
    x,
    lmo,
    f,
    gradient,
    grad!,
    dual_gap,
    t,
    line_search,
    linesearch_workspace,
    memory_mode,
    epsilon,
)

Executes one iteration of the defined FrankWolfe.UpdateStep and updates the iterate x implicitly. The function returns a tuple (dual_gap, v, d, gamma, tt):

• dual_gap is the updated FrankWolfe gap
• v is the used vertex
• d is the update direction
• gamma is the applied step-size
• tt is the applied step-type

Implementation of the vanilla Frank-Wolfe algorithm as an update step for block-coordinate Frank-Wolfe.

Implementation of the blended pairwise conditional gradient (BPCG) method as an update step for block-coordinate Frank-Wolfe.