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!(active_set, 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.

ActiveSetQuadraticProductCaching{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. The objective function is assumed to be of the form f(x)=½⟨x,Ax⟩+⟨b,x⟩+c so that the gradient is simply ∇f(x)=Ax+b.

ActiveSetQuadraticLinearSolve{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. The objective function is assumed to be of the form f(x)=½⟨x,Ax⟩+⟨b,x⟩+c so that the gradient is ∇f(x)=Ax+b.

This active set stores an inner active_set that keeps track of the current set of vertices and convex decomposition. It therefore delegates all update, deletion, and addition operations to this inner active set. The weight, atoms, and x fields should only be accessed to read and are effectively the same objects as those in the inner active set. The flag wolfe_step determines whether to use a Wolfe step from the min-norm point algorithm or the normal direct solve. The Wolfe step solves the auxiliary subproblem over the affine hull of the current active set (instead of the convex hull).

The structure also contains a scheduler struct which is called with the should_solve_lp function. To define a new frequency at which the LP should be solved, one can define another scheduler struct and implement the corresponding method.

ActiveSetQuadraticLinearSolve(tuple_values::Vector{Tuple{R,AT}}, A, b, lp_optimizer)

Creates an ActiveSetQuadraticLinearSolve from the given Hessian A, linear term b and lp_optimizer by creating an inner ActiveSetQuadraticProductCaching active set.

ActiveSetQuadraticLinearSolve(tuple_values::Vector{Tuple{R,AT}}, grad!::Function, lp_optimizer)

Creates an ActiveSetQuadraticLinearSolve by computing the Hessian and linear term from grad!.

solve_quadratic_activeset_lp!(as::ActiveSetQuadraticLinearSolve{AT, R, IT, H}))

Solves the auxiliary LP over the current active set. The method is specialized by type H of the Hessian matrix A.

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.

SubspaceVector{HasMultiplicities, T}

Companion structure of SubspaceLMO containing three fields:

• data is the full structure to be deflated,
• vec is a vector in the reduced subspace in which computations are performed,
• mul is only used to compute scalar products when HasMultiplicities = true,

which should be avoided (when possible) for performance reasons.

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.

Given an array array, NegatingArray represents -1 * array lazily.

_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

Computes the linear minimizer in the direction on the precomputedset. Precomputedset stores the vertices computed as extreme points v in each iteration.

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.

The Lazy update order is discussed in "Flexible block-iterative analysis for the Frank-Wolfe algorithm," by Braun, Pokutta, & Woodstock (2024). 'lazyblock' is an index of a computationally expensive block to update; 'refreshrate' describes the frequency at which we perform a full activation; and 'blocksize' describes the number of "faster" blocks (i.e., those excluding 'lazyblock') activated (chosen uniformly at random) during each of the "faster" iterations; for more detail, see the article. If 'block_size' is unspecified, this defaults to

Note: This methodology is currently only proven to work with 'FrankWolfe.Shortstep' linesearches and a (not-yet implemented) adaptive method; see the article for details.

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, step_type):

• dual_gap is the updated FrankWolfe gap
• v is the used vertex
• d is the update direction
• gamma is the applied step-size
• step_type 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.

BlockVector{T, MT <: AbstractArray{T}, ST <: Tuple} <: AbstractVector{T}

Represents a vector consisting of blocks. T is the element type of the vector, MT is the type of the underlying data array, and ST is the type of the tuple representing the sizes of each block. Each block can be accessed with the blocks field, and the sizes of the blocks are stored in the block_sizes field.