Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimization

Zaid Harchaoui; Anatoli Juditsky; Arkadi Nemirovski

Source-linked AI summary

Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimization

Zaid Harchaoui, Anatoli Juditsky, Arkadi Nemirovski

arXiv:1302.2325v4Feb 10, 2013math.OCstat.COstat.ML

TL;DR

The paper addresses two norm-regularized convex problems when large dimension and difficult proximal subproblems limit standard first-order methods. It develops Conditional Gradient algorithms based on linear optimization oracles, reports applications and theoretical efficiency estimates, and finds strong TV-regularization gains in well-conditioned image-reconstruction experiments.

Problem
Large-scale norm-regularized problems can make proximal methods questionable when favorable geometry or computationally tractable subproblems are unavailable.
Method
The paper develops Conditional Gradient algorithms for norm minimization and composite optimization using linear-optimization oracles, including memory-based variants.
Results
TV regularization reduced combined relative recovery error by 80% in experiment C and 72% in experiment D, while giving about 25% improvement in experiments A and B.
Takeaways & Limitations
The framework applies to nuclear- and trace-norm matrix problems and Total Variation image reconstruction through comparatively simple linear optimization oracles.
Takeaways & Limitations
The setting assumes a closed convex cone, a norm, a smooth convex function with Lipschitz continuous gradient, and accessible linear-optimization oracles.

Abstract

from arXiv · show

Motivated by some applications in signal processing and machine learning, we consider two convex optimization problems where, given a cone $K$, a norm $\|\cdot\|$ and a smooth convex function $f$, we want either 1) to minimize the norm over the intersection of the cone and a level set of $f$, or 2) to minimize over the cone the sum of $f$ and a multiple of the norm. We focus on the case where (a) the dimension of the problem is too large to allow for interior point algorithms, (b) $\|\cdot\|$ is "too complicated" to allow for computationally cheap Bregman projections required in the first-order proximal gradient algorithms. On the other hand, we assume that {it is relatively easy to minimize linear forms over the intersection of $K$ and the unit $\|\cdot\|$-ball}. Motivating examples are given by the nuclear norm with $K$ being the entire space of matrices, or the positive semidefinite cone in the space of symmetric matrices, and the Total Variation norm on the space of 2D images. We discuss versions of the Conditional Gradient algorithm capable to handle our problems of interest, provide the related theoretical efficiency estimates and outline some applications.

1 Introduction

The paper studies norm-regularized convex problems in large-scale settings where proximal methods may be impractical because of unfavorable geometry or difficult subproblems. It develops Conditional Gradient alternatives relying on easier linear optimization over the cone–norm-ball domain.

The paper considers two norm-regularized convex optimization problems motivated by signal processing and machine learning.
Proximal-gradient methods require favorable domain geometry and repeated minimization involving a distance-generating function.
When these conditions fail, proximal algorithms can become questionable for norms such as ℓ∞ and matrix ℓ2,1.
Examples include nuclear-norm matrix completion, Total Variation image reconstruction, and multi-task learning with many tasks and features.
Conditional Gradient methods avoid these difficulties by minimizing a linear form over the problem domain at each iteration.

2 Problem statement

The paper formulates norm minimization and penalized norm minimization over a closed convex cone, using a smooth convex loss and an LO oracle for the cone intersected with the unit norm ball.

The common setting uses a closed convex cone K, a norm on E, and a convex function f with Lipschitz continuous gradient.
The two problem classes are norm minimization subject to a level-set constraint and penalized norm minimization over K.
Norm-minimization: The norm-minimization problem is approached through a parametric family and seeks an ϵ-solution with controlled norm and function-value feasibility.
Penalized norm minimization: Composite optimization is equivalently written over (x,r), with x ∈ K, ∥x∥≤r, and objective κr + f(x).
The LO oracle minimizes a linear form over {x ∈ K : ∥x∥≤1} and induces linear optimization over the lifted set K+[ρ].

3 Conditional Gradient algorithm

The proposed Conditional Gradient framework builds iterates using linear-optimization oracle calls, with standard and memory-based variants and online accuracy certificates. Memory can improve numerical efficiency but introduces storage and auxiliary-optimization costs.

Generic Conditional Gradient algorithms operate on a closed bounded convex set supplied through a linear-optimization oracle.
The basic variants CndGa and CndGb use either a latest-oracle search point or minimization over the current segment.
Each run produces lower bounds on the optimum and an online accuracy certificate that can serve as a stopping criterion.
Memory extensions: CndG with memory reuses previous oracle points, while retaining the generic Conditional Gradient guarantees.
Implementation: Memory variants require solving a smooth auxiliary problem over a simplex, and bounded memory keeps this overhead manageable.

4 Conditional gradient algorithm for parametric optimization

The paper solves the parametric problem through a multi-stage conditional-gradient procedure that progressively improves lower bounds on the optimal parameter. Each stage applies conditional gradient over a norm-truncated cone, and the method terminates with theoretical complexity guarantees.

Multi-stage strategy: The algorithm uses a Newton-type multi-stage strategy to approximate the positive root ρ∗ of Opt(ρ) from below.Approximate solutions of inner problems provide first-order information and piecewise-linear lower bounds on Opt(ρ).
Initialization: The initialization handles trivial cases immediately and otherwise establishes the first lower bound ρ1 from f(0), the gradient at the origin, and the oracle direction.If f(0)≤ϵ or the oracle direction is zero, the origin provides the corresponding solution or optimum.
Inner optimization: At each stage, conditional gradient minimizes f over the truncated cone K[ρs] = {x ∈ K : ∥x∥≤ρs}.The linear-optimization oracle for K and the unit norm ball directly induces an oracle for K[ρs] by scaling its output.
Stage transitions: The method tracks the best current iterate together with a lower bound on Opt(ρs) and uses these quantities to decide whether to continue, terminate, or start a new stage.Stored affine lower bounds determine the next stage parameter through the smallest positive root.
Lower-bound construction: Convexity makes each affine model ℓk(ρ) a lower bound on Opt(ρ), allowing the algorithm to construct valid lower estimates from previous conditional-gradient iterates.The next parameter ρs+1 is selected from a root of the accumulated lower bound and remains below ρ∗.
Efficiency guarantees: Theorem 2 guarantees termination with an ϵ-solution, bounds the number of steps at every stage, and bounds the total number of stages before termination.The stage bound is expressed through a logarithmic quantity involving f(0) and the target tolerance.

5 Conditional Gradient algorithm for Composite Optimization

For composite optimization, the paper lifts the problem into an extended cone and applies conditional gradient using a linear-optimization oracle. The resulting algorithm is descent-preserving, has efficiency independent of the supplied upper bound, and admits memory and practical enhancements.

Problem formulation: COCndG solves composite optimization over K+ = {[x; r] : x ∈ K, ∥x∥≤r} using a first-order oracle for f and a linear-optimization oracle.The oracle assumption applies to the unit norm ball intersected with K.
Assumptions and guarantees: Under Assumption A, the algorithm uses a finite upper bound D+ while its efficiency estimate depends only on the data-induced quantity D∗.The estimate is independent of the a priori upper bound D+ supplied to the method.
Conditional-gradient step: Linear minimization over K+[ρ] is attained at a point in the segment-generated set Δ(z), enabling the conditional-gradient recurrence over Conv(Δ(zt) ∪ {zt}).The selected points include either a scaled oracle output or the origin.
Core result: Theorem 3 guarantees that generic COCndG iterates remain in K+ and that the objective is nonincreasing across iterations.Thus the method preserves feasibility while performing descent.
Memory variants: The memory variant retains the generic COCndG guarantees while selecting from current iterates and additional oracle-generated points.The basic method is recovered when the retained set contains only the current iterate and its associated oracle point.
Practical enhancements: For quadratic f, low-dimensional nearly quadratic subproblems can be solved accurately and can simultaneously produce feasible approximations for several penalty parameters.The solution for the specified penalty retains the theoretical estimates, while other penalty values yield additional feasible approximate solutions.
Practical enhancements: The memory strategy can control the cardinality of the retained set by removing older points and adding current and oracle-derived points.A fixed cardinality M preserves at least floor(M/3) recent gradients after sufficient iterations in the described construction.

6 Application examples

The paper applies conditional-gradient methods to large-scale nuclear/trace-norm and Total Variation problems, where linear-optimization oracles can be cheaper than proximal subproblems. These applications provide low-rank matrix iterates and flow-based TV oracles, with favorable implementation and complexity properties.

Nuclear and trace norm: Nuclear- and trace-norm applications target low-rank matrix recovery, including matrix completion and positive semidefinite covariance recovery.For symmetric matrices, the nuclear norm becomes the trace norm, and regularization similarly promotes low-rank recovery.
Nuclear and trace norm: Proximal methods may require complete singular-value or eigenvalue decompositions, whereas the conditional-gradient oracle requires only a leading singular vector or eigenvector.The leading-vector computation is usually cheaper for large matrices than a complete decomposition.
Nuclear and trace norm: Rank-1 oracle outputs imply that the t-th conditional-gradient iterate for composite minimization has rank at most t.The same property holds for parametric optimization when each stage starts from the zero matrix.
Total Variation: Total Variation regularization reconstructs noisy images, but proximal methods face difficult nonlinear optimization over the intersection of an ℓ1 ball and a large gradient-field subspace.The relevant subspace has both dimension and codimension of order n^2.
Total Variation: A Total Variation linear-optimization oracle reduces to a maximum-flow problem that can be solved reasonably fast even for images with n = 512 or n = 1024.The solver also returns dual information used to construct the oracle solution x[η] = −¯z/TV(¯z).
Total Variation: For a nonzero zero-mean image, the flow formulation has positive optimum and constructs x[η] as a maximizer of the linear form over the TV unit ball.The construction uses the centered dual vector ¯z and normalization by its Total Variation.

7 Numerical examples

The numerical examples evaluate memory-based Conditional Gradient variants on sparse matrix completion, nuclear-norm classification, and TV-regularized image reconstruction. Across these settings, memory often improves progress but introduces computational or storage trade-offs.

Sparse matrix completion: CndG with memory consistently outperforms memoryless CndG in the sparse matrix-completion experiments.Full memory uses the fewest iterations and produces the lowest-rank approximate solutions, while M = 5 balances numerical efficiency and memory demand.
Sparse matrix completion: Full-memory CndGM can become impractical for large matrices because of its memory requirements.The implementation could not complete the two largest matrix sizes, and the authors identify M = 5 as a reasonable compromise.
Multi-class classification: For multi-class classification, memory-based CndG routinely outperforms the memoryless version, but larger memory increases per-iteration computational load.The authors specifically note that solving the memory subproblem can become challenging for large M.
TV-regularized image reconstruction: In TV-regularized reconstruction, COCndGM has surprisingly low iteration counts despite O(1/t) convergence, with apparently tolerable running times.A single linear-optimization oracle call accounts for as much as 85% of an iteration, making larger memory and multiple penalty values comparatively inexpensive.
TV-regularized image reconstruction: Including gradient-derived points in the memory set substantially improves one TV experiment, reducing the objective ratio to 0.036 in 12 iterations.Without those points, the termination criterion was not met within 50 iterations.
TV-regularized image reconstruction: TV regularization improves recovery by about 25% for heavily ill-conditioned mappings, versus 80% and 72% for well-conditioned experiments.These comparisons use the combined relative recovery error against trivial recovery and correspond to different observation-noise levels.

8 Appendix

The appendix establishes convergence and complexity guarantees for the conditional-gradient methods, then develops the TV-specific constructions used in image reconstruction.

Convergence analysis: The algorithm output satisfies ρ̄ ≤ ρ* and f(x̄) ≤ ε whenever termination occurs, while the appendix verifies termination and stage-count bounds.The proof separately establishes the output guarantee, per-stage iteration control, and the bound on the number of stages.
Convergence analysis: The proof bounds stage curvature by L = 4ρ_s^2L_f and uses conditional-gradient decrease recurrences to control the number of iterations.The stage domain satisfies X − X ⊂ {x : ∥x∥ ≤ 2ρ_s}, yielding the stated smoothness bound.
Composite optimization: For composite optimization, the lifted variable z_t combines x_t with a scalar norm coordinate, and each step minimizes a linear form over K+[r*].The gradient of the lifted objective is [f′(x_t); κ], so the linear oracle operates over the cone-and-norm-bounded lifted set.
Composite optimization: The conditional-gradient recurrence yields an O(1/t) objective-gap bound under bounded iterates and smoothness assumptions.The recurrence is expressed through the diameter bound D* and the smoothness constant L_f.
Total variation construction: For TV regularization, periodic discrete derivatives, their l1 bounds, and a periodic Laplacian support the construction of unit-TV oracle solutions.The appendix relates the image gradient operator to a network-incidence representation and shows TV(z) = ∥Q*z∥1 for zero-mean images.