Away-Step and Pairwise Frank-Wolfe Linear Convergence on Polytopes

Away-Step and Pairwise Frank-Wolfe Linear Convergence on Polytopes is a projection-free conditional gradient framework and affine-invariant geometric convergence theory introduced by Lacoste-Julien and Jaggi (2015) for minimizing a mu-strongly convex, L-smooth function f over a compact polytope M = conv(A) subseteq R^d. Whereas classical Frank-Wolfe (conditional gradient) zig-zags when the constrained optimum x^* lies on a boundary face of M (suffering an unavoidable Omega(1 / t^{1+epsilon}) sublinear rate), Away-Steps Frank-Wolfe (AFW, Algorithm 1) and Pairwise Frank-Wolfe (PFW, Algorithm 2) maintain an explicit active atom set S^{(t)} subseteq A with strict convex weights alpha_v^{(t)} > 0 for x^{(t)} = sum_{v in S^{(t)}} alpha_v^{(t)} v and query both the standard FW atom s_t = argmin_{v in A} <grad f(x^{(t)}), v> and the worst active away atom v_t = argmax_{v in S^{(t)}} <grad f(x^{(t)}), v>. AFW chooses the larger of the FW gap <grad f(x^{(t)}), x^{(t)} - s_t> and the away gap <grad f(x^{(t)}), v_t - x^{(t)}> (with maximum step gamma_max = alpha_{v_t}^{(t)} / (1 - alpha_{v_t}^{(t)})), while PFW moves weight directly along d_t^{PFW} = s_t - v_t (with gamma_max = alpha_{v_t}^{(t)}). By establishing the Geometric Strong Convexity bound h_t <= <grad f(x^{(t)}), v_t - s_t>^2 / (2 mu_f^G) in terms of the polytope's Pyramidal Width delta = PWidth(A) > 0 (Theorem 3, Lemma 4, and Theorem 6) and bounding the number of non-halving 'drop steps' (which remove an atom from S^{(t)}) by at most half the total steps, Theorem 1 and Theorem 8 prove that both AFW and PFW achieve global linear convergence h_t = f(x^{(t)}) - f(x^*) <= h_0 (1 - rho)^t regardless of whether x^* lies in the interior or on a low-dimensional boundary face of M.