Notes on the Frank-Wolfe Algorithm, Part I

Abstraction: Frank-Wolfe projection-free constrained optimization algorithm theory and convergence

Key points:

• Frank-Wolfe (conditional gradient) algorithm solves constrained optimization by replacing projections with a linear minimization oracle (LMO) over the feasible domain, enabling lower memory usage
• At each iteration: solve a linear subproblem over the domain to get vertex s_t, then step toward s_t with step size chosen by closed-form formula or line search
• Requires domain to be convex and compact; objective needs L-Lipschitz-continuous gradient (not necessarily convex)
• For non-convex objectives: O(1/sqrt(t)) convergence on the Frank-Wolfe gap; for convex objectives: O(1/t) convergence on function suboptimality (Theorems 1 and 2 with proofs)
• Lasso example: domain is ell_1 ball; LMO has closed-form solution (coordinate with maximum correlation with negative gradient); line search also has closed-form
• Iterates are always convex combinations of domain vertices — beneficial for sparse or infinite-dimensional settings (e.g., neural architecture search)

Connections: Fabian Pedregosa · Frank Wolfe Algorithm · Convex Optimization · Constrained Optimization

Source: http://fa.bianp.net/blog/2018/notes-on-the-frank-wolfe-algorithm-part-i/