PaperlayerView exact revision on arXiv

Source-linked AI summary

Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functions

Amir Beck, Shimrit Shtern

arXiv:1504.05002v1math.OC

TL;DR

The paper extends earlier results and shows that the ASCG algorithm converges. The paper analyzes ASCG for problem (P) using duality arguments and error bounds, with a vertex-facet distance constant in place of pyramidal width. The paper establishes a linear convergence rate for ASCG on problem (P) using the vertex-facet distance of X, ΩX.

  • Problem

    The paper extends earlier results and shows that the ASCG algorithm converges.

    Source: §1 · p. 3

  • Method

    The paper analyzes ASCG for problem (P) using duality arguments and error bounds, with a vertex-facet distance constant in place of pyramidal width.

    Source: §1 · p. 3, §2.1 · p. 5, §3.3 · p. 18

  • Results

    The paper establishes a linear convergence rate for ASCG on problem (P) using the vertex-facet distance of X, ΩX.

    Source: §3.3 · p. 18

  • Takeaways & Limitations

    The analysis requires a vertex linear oracle on X rather than on the linear image EX.

    Source: §3.1 · p. 10

    Although g is strongly convex, f need not be strongly convex for a general matrix E.

    Source: §1 · p. 1

Abstract

from arXiv · show

We consider the problem of minimizing a function, which is the sum of a linear function and a composition of a strongly convex function with a linear transformation, over a compact polyhedral set. Jaggi and Lacoste-Julien [14] showed that the conditional gradient method with away steps employed on the aforementioned problem without the additional linear term has linear rate of convergence, depending on the so-called pyramidal width of the feasible set. We revisit this result and provide a variant of the algorithm and an analysis that is based on simple duality arguments, as well as corresponding error bounds. This new analysis (a) enables the incorporation of the additional linear term, (b) does not require a linear-oracle that outputs an extreme point of the linear mapping of the feasible set and (c) depends on a new constant, termed "the vertex-facet distance constant", which is explicitly expressed in terms of the problem's parameters and the geometry of the feasible set. This constant replaces the pyramidal width, which is difficult to evaluate.

1 Introduction

The paper extends away-step conditional gradient convergence analysis to the general problem with a linear term, using an analysis that replaces pyramidal width with a computable constant. It also avoids requiring a vertex linear oracle over the linearly mapped feasible set.

1 Introduction

  • Projection-based first-order methods generally have sublinear rates under convexity alone, while linear rates require additional conditions such as strong convexity.The cited feasible-descent analysis establishes error bounds for problem (P) under compactness and polyhedrality assumptions [17, 19].Source: §1 · p. 2
  • The analysis extends linear convergence of ASCG to problem (P) for any E and b, including an additional linear term absent from the result of Jaggi and Lacoste-Julien.The paper gives l1-regularized least squares over a compact polyhedral set as an example of the broader models enabled by the linear term.Source: §1 · p. 3
  • The analysis requires a vertex linear oracle on X, not on its linear image EX, where finding a suitable extreme-point oracle may be complex.For the away-step method, mapping an extreme point of X need not yield an extreme point of EX.Source: §1 · p. 3
  • The paper bases its convergence analysis on simple duality arguments rather than the geometric arguments used in.It presents corresponding error bounds and a new convergence constant.Source: §1 · p. 3
  • The new vertex-facet distance constant replaces pyramidal width and is explicitly expressed through problem parameters and feasible-set geometry.The paper notes that pyramidal width is defined through a complex optimization problem whose exact value is unknown even for simple polyhedral sets.Source: §1 · p. 4

2 Preliminaries

The preliminaries establish the assumptions and error-bound tools used in the analysis, then introduce linear oracles and the classical conditional gradient method.

2.1 Mathematical Preliminaries

  • The paper introduces the descent lemma for first-order convergence analysis and Hoffman’s lemma for error-bound analysis over polyhedral sets.Source: §2.1 · p. 5

2.2 Problem’s Properties

  • The analysis assumes a differentiable objective with Lipschitz gradient, a strongly convex function g, and a nonempty compact polyhedral feasible set X.Source: §2.2 · p. 5
  • The optimal set shares common values of Ex and ⟨b, x⟩ across all optimal solutions, and a compactness-based error bound avoids requiring strong convexity of f or the gradient mapping used in.Source: §2.2 · p. 6

2.3 Conditional Gradient and Linear Oracles

  • A linear oracle returns a feasible minimizer of a queried linear function, and for some feasible sets it has a closed form or efficient implementation.Source: §2.3 · p. 8
  • The classical conditional gradient method uses a linear oracle to minimize a convex function over a compact polyhedral set.Source: §2.3 · p. 8
  • O(1/k) convergence is guaranteed for several classical conditional-gradient step-size rules, and the upper bound is tight.Source: §2.3 · p. 9

3 Away Steps Conditional Gradient

The section develops a duality-based convergence analysis of away-step conditional gradient for the general problem (P), using a vertex linear oracle on X and the vertex-facet distance constant ΩX. It establishes a linear-rate theorem, bounds the occurrence of drop steps, and outlines computing ΩX for the unit simplex, ℓ1 ball, and ℓ∞ ball.

3.1 Vertex Linear Oracles

  • The analysis uses a vertex linear oracle on X, making per-iteration oracle cost independent of E and dependent only on X’s geometry.Constructing a vertex linear oracle for EX can add computational cost, since mapping an optimal vertex of X may not yield a vertex of EX.Source: §3.1 · pp. 10, 12

3.2 The ASCG Method

  • ASCG maintains a convex-combination representation of each iterate, using forward steps to add vertices and away steps to reduce or remove their coefficients.The method supports representation reduction, and its function values are nonincreasing under the stated stepsize strategies.Source: §3.2 · pp. 12–14

3.3 Rate of Convergence Analysis

  • The duality-based analysis replaces the pyramidal width with ΩX, a computable constant defined as a normalized minimal distance between facet hyperplanes and vertices outside them.The paper states that ΩX can be computed for many choices of X.Source: §3.3 · pp. 15, 17
  • Theorem 3.1 establishes a linear convergence rate for ASCG on problem (P), extending Jaggi and Lacoste-Julien [14] using an error bound and ΩX.The theorem allows a representation-reduction procedure with constant N.Source: §3.3 · p. 18
  • Drop steps occur at most ⌊(k−1)/2⌋ times by iteration k, because removals cannot exceed additions and each iteration adds, removes, or neither.A drop step removes one vertex from the representation before representation reduction.Source: §3.3 · p. 20
  • The convergence proof concludes by applying Lemma 2.4 at the initial iterate to obtain f(x1) − f* ≤ C and the desired result (3.20).Source: §3.3 · p. 21

3.4 Examples of Computing the Vertex-Facet Distance ΩX

  • The vertex-facet distance constant ΩX is computed from its definition after expressing each set as X = {x : Ax ≤ a}, using A, a, and the vertex set V.The examples considered are the unit simplex, ℓ1 ball, and ℓ∞ ball.Source: §3.4 · p. 21
  • For the simplex, its n extreme points are affinely independent, so Carathéodory-based rank reduction does not change the representation; for the ℓ∞ ball, representation reduction is crucial at scale.The ℓ∞ ball has 2n extreme points according to the passage.Source: §3.4 · p. 22

Appendix A Incremental Representation Reduction using the Carath´eodory Theorem

The Incremental Representation Reduction scheme updates a point’s vertex representation alongside matrices that preserve an affine-independence structure. It can keep the representation to at most n+1 vertices at O(n^2) operations per iteration, though the reduction procedure is optional.

Appendix A Incremental Representation Reduction using the Carathéodory Theorem

  • The representation reduction can be omitted, in which case the upper bound on its vertex count is the number of extreme points of X.The authors describe the incremental procedure as optional and identify the unchanged representation as the alternative.Source: Appendix A · p. 24
  • At most n+1 vertices and O(n^2) operations per iteration are sufficient for the described representation maintenance.The scheme incrementally implements a constructive Carathéodory reduction; the authors also allow a trivial procedure that leaves the representation unchanged.Source: Appendix A · p. 24
  • Matrices T_k and W_k are updated so W_k = T_kV_k remains in row echelon form, without storing V_k.V_k contains differences from the reference vertex; only T_k and W_k are updated at each iteration.Source: Appendix A · p. 25
  • IRR can reduce the representation only after a forward step, but it is applied every iteration to maintain W_k and T_k.After other steps, the vertices in the representation are affinely independent.Source: Appendix A · p. 26
  • The O(n^2) cost relies on only a small number of vertices changing and assumes |I| = O(1) during forward-step reduction.The authors describe larger |I| as numerically unlikely; the reduction updates the representation and associated matrices incrementally.Source: Appendix A · p. 27

Related papers

Loading 1504.05002v1…