plot_sparsity (generic function with 1 method)Block-Coordinate Frank-Wolfe and Block-Vectors
In this example, we demonstrate the usage of the FrankWolfe.block_coordinate_frank_wolfe and FrankWolfe.BlockVector. We consider the problem of minimizing the squared Euclidean distance between two sets. We compare different update orders and different update steps.
Import and setup
We first import the necessary packages and include the code for plotting the results.
using FrankWolfe
using LinearAlgebra
include("plot_utils.jl")plot_sparsity (generic function with 1 method)Next, we define the objective function and its gradient. The iterates x are instances of the FrankWolfe.BlockVector type. The different blocks of the vector can be accessed via the blocks field.
f(x) = dot(x.blocks[1] - x.blocks[2], x.blocks[1] - x.blocks[2])
function grad!(storage, x)
@. storage.blocks = [x.blocks[1] - x.blocks[2], x.blocks[2] - x.blocks[1]]
endgrad! (generic function with 1 method)In our example we consider the probability simplex and an L-infinity norm ball as the feasible sets.
n = 100
lmo1 = FrankWolfe.ScaledBoundLInfNormBall(-ones(n), zeros(n))
lmo2 = FrankWolfe.ProbabilitySimplexOracle(1.0)
prod_lmo = FrankWolfe.ProductLMO((lmo1, lmo2))FrankWolfe.ProductLMO{2, Tuple{FrankWolfe.ScaledBoundLInfNormBall{Float64, 1, Vector{Float64}, Vector{Float64}}, FrankWolfe.ProbabilitySimplexOracle{Float64}}}((FrankWolfe.ScaledBoundLInfNormBall{Float64, 1, Vector{Float64}, Vector{Float64}}([-1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0 … -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0, -1.0], [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0 … 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]), FrankWolfe.ProbabilitySimplexOracle{Float64}(1.0)))We initialize the starting point x0 as a FrankWolfe.BlockVector with two blocks. The two other arguments are the block sizes and the overall number of entries.
x0 = FrankWolfe.BlockVector([-ones(n), [i == 1 ? 1 : 0 for i in 1:n]], [(n,), (n,)], 2 * n);Running block-coordinate Frank-Wolfe with different update-orders
In a first step, we compare different update orders. There are three different update orders implemented, FrankWolfe.FullUpdate, CyclicUpdate and Stochasticupdate. For creating a custome FrankWolfe.BlockCoordinateUpdateOrder, one needs to implement the function select_update_indices.
struct CustomOrder <: FrankWolfe.BlockCoordinateUpdateOrder end
function FrankWolfe.select_update_indices(::CustomOrder, state::FrankWolfe.CallbackState, dual_gaps)
return [rand() < 1 / n ? 1 : 2 for _ in 1:length(state.lmo.lmos)]
endWe run the block-coordinate Frank-Wolfe method with the different update orders and store the trajectories.
trajectories = []
for order in [
FrankWolfe.FullUpdate(),
FrankWolfe.CyclicUpdate(),
FrankWolfe.StochasticUpdate(),
CustomOrder(),
]
_, _, _, _, traj_data = FrankWolfe.block_coordinate_frank_wolfe(
f,
grad!,
prod_lmo,
x0;
verbose=true,
trajectory=true,
update_order=order,
)
push!(trajectories, traj_data)
end
Block coordinate Frank-Wolfe (BCFW).
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: DataType[FrankWolfe.Adaptive{Float64, Int64}, FrankWolfe.Adaptive{Float64, Int64}] EPSILON: 1.0e-7 MAXITERATION: 10000 TYPE: Float64
MOMENTUM: nothing GRADIENTTYPE: FrankWolfe.BlockVector{Float64, Vector{Float64}, Tuple{Int64}} UPDATE_ORDER: FrankWolfe.FullUpdate() UPDATE_STEP: DataType[FrankWolfe.FrankWolfeStep, FrankWolfe.FrankWolfeStep]
[ Info: In memory_mode memory iterates are written back into x0!
-------------------------------------------------------------------------------------------------
Type Iteration Primal Dual Dual Gap Time It/sec
-------------------------------------------------------------------------------------------------
I 1 5.732358e-01 -1.014268e+02 1.020000e+02 0.000000e+00 Inf
FW 1000 1.006522e-02 9.790473e-03 2.747434e-04 3.945157e-01 2.534753e+03
FW 2000 1.002905e-02 9.883695e-03 1.453591e-04 4.177063e-01 4.788054e+03
FW 3000 1.001690e-02 9.923899e-03 9.300514e-05 4.410217e-01 6.802386e+03
FW 4000 1.001088e-02 9.940501e-03 7.037823e-05 4.562200e-01 8.767700e+03
FW 5000 1.000730e-02 9.952154e-03 5.515099e-05 4.760016e-01 1.050417e+04
FW 6000 1.000507e-02 9.960902e-03 4.416633e-05 4.988345e-01 1.202804e+04
FW 7000 1.000360e-02 9.967424e-03 3.617261e-05 5.215289e-01 1.342207e+04
FW 8000 1.000260e-02 9.972504e-03 3.009367e-05 6.091148e-01 1.313381e+04
FW 9000 1.000190e-02 9.976620e-03 2.528359e-05 6.341737e-01 1.419170e+04
FW 10000 1.000141e-02 9.979993e-03 2.141696e-05 6.568415e-01 1.522437e+04
Last 10001 1.000141e-02 9.979981e-03 2.142870e-05 7.582650e-01 1.318932e+04
-------------------------------------------------------------------------------------------------
Block coordinate Frank-Wolfe (BCFW).
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: DataType[FrankWolfe.Adaptive{Float64, Int64}, FrankWolfe.Adaptive{Float64, Int64}] EPSILON: 1.0e-7 MAXITERATION: 10000 TYPE: Float64
MOMENTUM: nothing GRADIENTTYPE: FrankWolfe.BlockVector{Float64, Vector{Float64}, Tuple{Int64}} UPDATE_ORDER: FrankWolfe.CyclicUpdate(-1) UPDATE_STEP: DataType[FrankWolfe.FrankWolfeStep, FrankWolfe.FrankWolfeStep]
[ Info: In memory_mode memory iterates are written back into x0!
-------------------------------------------------------------------------------------------------
Type Iteration Primal Dual Dual Gap Time It/sec
-------------------------------------------------------------------------------------------------
I 1 5.732358e-01 -1.014268e+02 1.020000e+02 0.000000e+00 Inf
FW 1000 1.006522e-02 9.790473e-03 2.747434e-04 1.257483e-01 7.952392e+03
FW 2000 1.002905e-02 9.883695e-03 1.453591e-04 2.150809e-01 9.298827e+03
FW 3000 1.001690e-02 9.923899e-03 9.300514e-05 2.464568e-01 1.217252e+04
FW 4000 1.001088e-02 9.940501e-03 7.037823e-05 2.762288e-01 1.448075e+04
FW 5000 1.000730e-02 9.952154e-03 5.515099e-05 3.058596e-01 1.634737e+04
FW 6000 1.000507e-02 9.960902e-03 4.416633e-05 3.350088e-01 1.790997e+04
FW 7000 1.000360e-02 9.967424e-03 3.617261e-05 3.644264e-01 1.920827e+04
FW 8000 1.000260e-02 9.972504e-03 3.009367e-05 3.938649e-01 2.031153e+04
FW 9000 1.000190e-02 9.976620e-03 2.528359e-05 4.228602e-01 2.128363e+04
FW 10000 1.000141e-02 9.979993e-03 2.141696e-05 5.145945e-01 1.943278e+04
Last 10001 1.000141e-02 9.979981e-03 2.142870e-05 5.149724e-01 1.942046e+04
-------------------------------------------------------------------------------------------------
Block coordinate Frank-Wolfe (BCFW).
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: DataType[FrankWolfe.Adaptive{Float64, Int64}, FrankWolfe.Adaptive{Float64, Int64}] EPSILON: 1.0e-7 MAXITERATION: 10000 TYPE: Float64
MOMENTUM: nothing GRADIENTTYPE: FrankWolfe.BlockVector{Float64, Vector{Float64}, Tuple{Int64}} UPDATE_ORDER: FrankWolfe.StochasticUpdate(-1) UPDATE_STEP: DataType[FrankWolfe.FrankWolfeStep, FrankWolfe.FrankWolfeStep]
[ Info: In memory_mode memory iterates are written back into x0!
-------------------------------------------------------------------------------------------------
Type Iteration Primal Dual Dual Gap Time It/sec
-------------------------------------------------------------------------------------------------
I 1 5.732358e-01 -1.014268e+02 1.020000e+02 0.000000e+00 Inf
FW 1000 1.006649e-02 9.797679e-03 2.688115e-04 6.458421e-02 1.548366e+04
FW 2000 1.003282e-02 9.887544e-03 1.452767e-04 9.357221e-02 2.137387e+04
FW 3000 1.001920e-02 9.919860e-03 9.934003e-05 1.232392e-01 2.434291e+04
FW 4000 1.001224e-02 9.935454e-03 7.678946e-05 2.100172e-01 1.904606e+04
FW 5000 1.000812e-02 9.949492e-03 5.863302e-05 2.420344e-01 2.065822e+04
FW 6000 1.000561e-02 9.958403e-03 4.720724e-05 2.711276e-01 2.212980e+04
FW 7000 1.000400e-02 9.964922e-03 3.907771e-05 2.999578e-01 2.333662e+04
FW 8000 1.000288e-02 9.971244e-03 3.163293e-05 3.290759e-01 2.431050e+04
FW 9000 1.000209e-02 9.975610e-03 2.647559e-05 3.591794e-01 2.505712e+04
FW 10000 1.000153e-02 9.979405e-03 2.212997e-05 3.889933e-01 2.570739e+04
Last 10001 1.000153e-02 9.979008e-03 2.252590e-05 3.893947e-01 2.568345e+04
-------------------------------------------------------------------------------------------------
Block coordinate Frank-Wolfe (BCFW).
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: DataType[FrankWolfe.Adaptive{Float64, Int64}, FrankWolfe.Adaptive{Float64, Int64}] EPSILON: 1.0e-7 MAXITERATION: 10000 TYPE: Float64
MOMENTUM: nothing GRADIENTTYPE: FrankWolfe.BlockVector{Float64, Vector{Float64}, Tuple{Int64}} UPDATE_ORDER: Main.CustomOrder() UPDATE_STEP: DataType[FrankWolfe.FrankWolfeStep, FrankWolfe.FrankWolfeStep]
[ Info: In memory_mode memory iterates are written back into x0!
-------------------------------------------------------------------------------------------------
Type Iteration Primal Dual Dual Gap Time It/sec
-------------------------------------------------------------------------------------------------
I 1 1.024074e+02 -Inf Inf 0.000000e+00 Inf
FW 1000 1.003847e-02 9.875995e-03 1.624779e-04 7.549151e-02 1.324652e+04
FW 2000 1.001380e-02 9.931922e-03 8.188221e-05 1.158516e-01 1.726346e+04
FW 3000 1.000624e-02 9.955789e-03 5.044741e-05 1.559439e-01 1.923769e+04
FW 4000 1.000315e-02 9.969360e-03 3.378772e-05 1.956911e-01 2.044038e+04
FW 5000 1.000169e-02 9.978459e-03 2.323352e-05 2.956151e-01 1.691389e+04
FW 6000 1.000095e-02 9.983540e-03 1.740806e-05 3.351845e-01 1.790059e+04
FW 7000 1.000055e-02 9.987713e-03 1.283319e-05 3.744192e-01 1.869562e+04
FW 8000 1.000032e-02 9.990836e-03 9.486923e-06 4.140539e-01 1.932116e+04
FW 9000 1.000019e-02 9.992954e-03 7.238509e-06 4.542240e-01 1.981401e+04
FW 10000 1.000012e-02 9.994356e-03 5.760023e-06 5.574325e-01 1.793939e+04
Last 10001 1.000012e-02 9.994357e-03 5.759399e-06 5.578700e-01 1.792712e+04
-------------------------------------------------------------------------------------------------Plotting the results
labels = ["Full update", "Cyclic order", "Stochstic order", "Custom order"]
plot_trajectories(trajectories, labels, xscalelog=true)Running BCFW with different update methods
As a second step, we compare different update steps. We consider the FrankWolfe.BPCGStep and the FrankWolfe.FrankWolfeStep. One can either pass a tuple of FrankWolfe.UpdateStep to define for each block the update procedure or pass a single update step so that each block uses the same procedure.
trajectories = []
for us in [(FrankWolfe.BPCGStep(), FrankWolfe.FrankWolfeStep()), (FrankWolfe.FrankWolfeStep(), FrankWolfe.BPCGStep()), FrankWolfe.BPCGStep(), FrankWolfe.FrankWolfeStep()]
_, _, _, _, traj_data = FrankWolfe.block_coordinate_frank_wolfe(
f,
grad!,
prod_lmo,
x0;
verbose=true,
trajectory=true,
update_step=us,
)
push!(trajectories, traj_data)
end
Block coordinate Frank-Wolfe (BCFW).
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: DataType[FrankWolfe.Adaptive{Float64, Int64}, FrankWolfe.Adaptive{Float64, Int64}] EPSILON: 1.0e-7 MAXITERATION: 10000 TYPE: Float64
MOMENTUM: nothing GRADIENTTYPE: FrankWolfe.BlockVector{Float64, Vector{Float64}, Tuple{Int64}} UPDATE_ORDER: FrankWolfe.CyclicUpdate(-1) UPDATE_STEP: DataType[FrankWolfe.BPCGStep, FrankWolfe.FrankWolfeStep]
[ Info: In memory_mode memory iterates are written back into x0!
-------------------------------------------------------------------------------------------------
Type Iteration Primal Dual Dual Gap Time It/sec
-------------------------------------------------------------------------------------------------
I 1 5.732358e-01 -1.014268e+02 1.020000e+02 0.000000e+00 Inf
FW 1000 1.006522e-02 9.790473e-03 2.747434e-04 5.146518e-01 1.943061e+03
FW 2000 1.002905e-02 9.883695e-03 1.453591e-04 5.533604e-01 3.614281e+03
FW 3000 1.001690e-02 9.923899e-03 9.300514e-05 6.496491e-01 4.617878e+03
FW 4000 1.001088e-02 9.940501e-03 7.037823e-05 6.879497e-01 5.814379e+03
FW 5000 1.000730e-02 9.952154e-03 5.515099e-05 7.272088e-01 6.875605e+03
FW 6000 1.000507e-02 9.960902e-03 4.416633e-05 7.653944e-01 7.839096e+03
FW 7000 1.000360e-02 9.967424e-03 3.617261e-05 8.040460e-01 8.705970e+03
FW 8000 1.000260e-02 9.972504e-03 3.009367e-05 8.426696e-01 9.493638e+03
FW 9000 1.000190e-02 9.976620e-03 2.528359e-05 9.462730e-01 9.510997e+03
FW 10000 1.000141e-02 9.979993e-03 2.141696e-05 9.844744e-01 1.015770e+04
Last 10001 1.000141e-02 9.979981e-03 2.142870e-05 9.868643e-01 1.013412e+04
-------------------------------------------------------------------------------------------------
Block coordinate Frank-Wolfe (BCFW).
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: DataType[FrankWolfe.Adaptive{Float64, Int64}, FrankWolfe.Adaptive{Float64, Int64}] EPSILON: 1.0e-7 MAXITERATION: 10000 TYPE: Float64
MOMENTUM: nothing GRADIENTTYPE: FrankWolfe.BlockVector{Float64, Vector{Float64}, Tuple{Int64}} UPDATE_ORDER: FrankWolfe.CyclicUpdate(-1) UPDATE_STEP: DataType[FrankWolfe.FrankWolfeStep, FrankWolfe.BPCGStep]
[ Info: In memory_mode memory iterates are written back into x0!
-------------------------------------------------------------------------------------------------
Type Iteration Primal Dual Dual Gap Time It/sec
-------------------------------------------------------------------------------------------------
I 1 5.732358e-01 -1.014268e+02 1.020000e+02 0.000000e+00 Inf
Last 474 1.000000e-02 9.999910e-03 8.999181e-08 2.033088e-01 2.331429e+03
-------------------------------------------------------------------------------------------------
Block coordinate Frank-Wolfe (BCFW).
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: DataType[FrankWolfe.Adaptive{Float64, Int64}, FrankWolfe.Adaptive{Float64, Int64}] EPSILON: 1.0e-7 MAXITERATION: 10000 TYPE: Float64
MOMENTUM: nothing GRADIENTTYPE: FrankWolfe.BlockVector{Float64, Vector{Float64}, Tuple{Int64}} UPDATE_ORDER: FrankWolfe.CyclicUpdate(-1) UPDATE_STEP: DataType[FrankWolfe.BPCGStep, FrankWolfe.BPCGStep]
[ Info: In memory_mode memory iterates are written back into x0!
-------------------------------------------------------------------------------------------------
Type Iteration Primal Dual Dual Gap Time It/sec
-------------------------------------------------------------------------------------------------
I 1 5.732358e-01 -1.014268e+02 1.020000e+02 0.000000e+00 Inf
Last 474 1.000000e-02 9.999910e-03 8.999181e-08 8.511164e-02 5.569156e+03
-------------------------------------------------------------------------------------------------
Block coordinate Frank-Wolfe (BCFW).
MEMORY_MODE: FrankWolfe.InplaceEmphasis() STEPSIZE: DataType[FrankWolfe.Adaptive{Float64, Int64}, FrankWolfe.Adaptive{Float64, Int64}] EPSILON: 1.0e-7 MAXITERATION: 10000 TYPE: Float64
MOMENTUM: nothing GRADIENTTYPE: FrankWolfe.BlockVector{Float64, Vector{Float64}, Tuple{Int64}} UPDATE_ORDER: FrankWolfe.CyclicUpdate(-1) UPDATE_STEP: DataType[FrankWolfe.FrankWolfeStep, FrankWolfe.FrankWolfeStep]
[ Info: In memory_mode memory iterates are written back into x0!
-------------------------------------------------------------------------------------------------
Type Iteration Primal Dual Dual Gap Time It/sec
-------------------------------------------------------------------------------------------------
I 1 5.732358e-01 -1.014268e+02 1.020000e+02 0.000000e+00 Inf
FW 1000 1.006522e-02 9.790473e-03 2.747434e-04 3.071012e-02 3.256256e+04
FW 2000 1.002905e-02 9.883695e-03 1.453591e-04 5.962156e-02 3.354491e+04
FW 3000 1.001690e-02 9.923899e-03 9.300514e-05 8.864506e-02 3.384283e+04
FW 4000 1.001088e-02 9.940501e-03 7.037823e-05 1.180024e-01 3.389761e+04
FW 5000 1.000730e-02 9.952154e-03 5.515099e-05 1.475915e-01 3.387728e+04
FW 6000 1.000507e-02 9.960902e-03 4.416633e-05 1.769491e-01 3.390806e+04
FW 7000 1.000360e-02 9.967424e-03 3.617261e-05 2.061035e-01 3.396352e+04
FW 8000 1.000260e-02 9.972504e-03 3.009367e-05 2.987627e-01 2.677710e+04
FW 9000 1.000190e-02 9.976620e-03 2.528359e-05 3.303867e-01 2.724081e+04
FW 10000 1.000141e-02 9.979993e-03 2.141696e-05 3.594485e-01 2.782039e+04
Last 10001 1.000141e-02 9.979981e-03 2.142870e-05 3.597772e-01 2.779776e+04
-------------------------------------------------------------------------------------------------Plotting the results
labels = ["BPCG FW", "FW BPCG", "BPCG", "FW"]
plot_trajectories(trajectories, labels, xscalelog=true)This page was generated using Literate.jl.