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.

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.

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

_unsafe_equal(a, b)

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

active_set_add_weight!(active_set, lambda, i)

Adds lambda to the weight of the ith atom in active_set.

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_mul_weights!(active_set, lambda)

Multiplies all weights in active_set by lambda.

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_pairwise!(active_set, gamma, gamma_max, v_local_loc, a_loc, v_local, a, add_dropped_vertices, extra_vertex_storage)

Updates the active set for a pairwise step with step size gamma.

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.

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.

ActiveSetQuadraticPartialCaching{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.

In contrast to ActiveSetQuadraticProductCaching, this active set assumes that the Hessian matrix A is fixed up to a scaling factor λ and that the linear term b can change during the iterations. Therefore, we cache only the dot products ⟨A * x, a_i⟩ and ⟨A * a_i, a_j⟩. This active set might be used for experiments with Alternating Linear Minimization (ALM) or Split FW where we usually have chaning linear terms and Hessian matrices which only change in scale.

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.

AbstractStochasticObjective

Represents an objective function accessed through a zeroth and first-order oracle. It must implement the following functions:

• compute_value(f::AbstractStochasticObjective, θ; batch_size, rng)
• grad!(storage, θ, x)
• compute_gradient(f::AbstractStochasticObjective, θ; batch_size, rng)

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 finite sum function F(θ) = ∑_i f(θ, x_i) 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.

CallbackState

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

Fields

• t
• primal
• dual
• dual_gap
• time
• x
• v
• d
• gamma
• f
• grad!
• lmo
• gradient
• step_type

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.

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

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.

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

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 FrankWolfe.update_iterate.

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

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

The d passed as argument is used as a container to avoid allocating d inside the function

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.