The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle

1 Introduction

• LCP methods solve large-scale convex programs by iteratively calling a linear optimization oracle, and a generic algorithm can form outputs as convex combinations of earlier iterates.The framework permits oracle input vectors based on gradients, approximations, random noise, or second-order information.Source: §1 · p. 1
• The paper establishes LO-oracle lower bounds for smooth, nonsmooth, and saddle-point problems, including bounds that apply to LCP methods using higher-order information.For smooth problems, the bounds make dependence on dimension and problem parameters explicit; the supplied passages do not provide the bound expressions.Source: §1 · p. 3
• Conditional gradient is optimal for smooth problems in sufficiently large dimensions and can attain optimal or nearly optimal complexity for several nonsmooth and saddle-point settings.For smooth problems, the stated sufficient condition is n ≥ LD_X^2/ε; variants use smoothing, including randomized smoothing for general nonsmooth problems.Source: §1 · p. 3
• PA-CndG and PDA-CndG replace projection subproblems in Nesterov’s accelerated methods with linear optimization subproblems.Their convergence rates depend on sums of distances among solutions; under specified conditions on the LO oracle they achieve O(1/√ε) iteration complexity for smooth problems. Preliminary experiments report that PDA-CndG can significantly outperform conditional gradient on some box-constrained problems.Source: §1 · pp. 3–4

1.1 Notation and terminology

• The notation section defines set diameters, conjugate norms, operator norms, and linear approximations used in the paper.It also notes that the smoothness constant L depends on the chosen norm.Source: §1.1 · p. 4

2.1 A generic LCP algorithm

• The generic LCP framework calls a linear optimization oracle each iteration and allows flexible search directions and convex-combination outputs.It includes the classic conditional gradient method and several new LCP methods as special cases.Source: §2.1 · pp. 4–5

2 Lower Complexity Bounds for CP under an LO oracle

• The section extends earlier LCP lower-bound work by making problem-dimension and parameter dependence explicit and treating nonsmooth and saddle-point problems as well as smooth optimization.The analysis assumes a resisting LO oracle that provides the least information needed by the algorithm in the worst case.Source: §2.2 · p. 5

2.2 Lower complexity bounds for smooth minimization

• For smooth problems, any LCP method faces a dimension-dependent lower complexity bound; assuming strong convexity does not improve it when n is sufficiently large.The smooth lower-bound analysis is developed for a class of convex problems with Lipschitz gradients.Source: §2.2 · pp. 5, 7

2.3 Lower complexity bounds for nonsmooth minimization

• For nonsmooth problems, the authors derive bounds for general convex minimization and bilinear saddle-point classes; the general bound applies even to LCP methods using higher-order information.The general nonsmooth bound is reported to be of the same order as the bound for general first-order methods.Source: §2.3 · pp. 7–8

3.1 Optimal CndG methods for smooth problems under an LO oracle

• With either standard stepsize policy, classic CndG achieves O(1/k) convergence and is an optimal LCP method for smooth problems when the dimension is sufficiently large.Its convergence analysis makes the rate depend explicitly on the distance between the previous iterate and the linear-oracle output; this distance need not vanish and can limit the bound.Source: §3.1 · pp. 9–11

3.2 Optimal CndG methods for saddle point problems under an LO oracle

• For saddle-point problems, a CndG variant using variable smoothing parameters achieves optimal complexity when the dimension is sufficiently large.The method need not know the target accuracy in advance, and inaccurate estimates of problem parameters affect its convergence rate only by a constant factor.Source: §3.2 · pp. 11–13

3.3 Nearly optimal CndG methods for general nonsmooth problems under an LO oracle

• For saddle-point problems, randomized CndG avoids the smoothing subproblems used by the method in Subsection 3.2 and can reduce them to linear optimization over Y when the stated term is zero.The authors describe this as the first proposal of this type of optimization algorithm in the literature.Source: §3.3 · pp. 15–16
• A randomized CndG method for general nonsmooth problems achieves a nearly optimal complexity bound relative to the lower bound.It uses convolution-based smoothing and sampled gradients; the analysis sets the sample count at iteration k to k, and generated samples can be reused in later iterations.Source: §3.3 · pp. 14–16
• The analysis gives relation (3.29) in expectation; an overwhelming-probability result via large-deviation analysis is possible but omitted for simplicity, with similar developments noted in [24].Source: §3.3 · p. 16

3.4 CndG methods for strongly convex problems under an enhanced LO oracle

• The shrinking CndG method uses an enhanced LO oracle and contracts the feasible region around the current iterate at each outer iteration.For a polytope, the passage suggests choosing the norm so the enhanced oracle’s local constrained problem is comparable in complexity to the original LO problem, though this may increase L/μ.Source: §3.4 · pp. 16–17
• The shrinking method performs 8L/μ inner iterations per outer round and at most ⌈max(log(μR0/ε), 1)⌉ outer rounds when finding an ε-solution.The theorem bounds the enhanced-oracle calls; the iteration counts follow from the proof and algorithm description.Source: §3.4 · p. 17

4 New variants of for LCP methods

• The new methods are obtained by replacing accelerated gradient methods' projection or prox-mapping subproblems with linear optimization; the algorithms can also be modified for saddle-point, nonsmooth, and strongly convex problems.Source: §4 · p. 17

4.1 Primal averaging CndG method

• PA-CndG averages the primal iterates before forming the gradient direction sent to the LO oracle, unlike classic CndG, which uses the previous iterate.The paper characterizes PA-CndG as an optimal LCP method for the stated smooth problem class when the dimension is sufficiently large.Source: §4.1 · pp. 18–19
• PA-CndG's convergence bound depends on the distance between consecutive LO-oracle outputs, and a faster O(1/k^2) rate follows under the stated Hölder continuity condition with ρ in (0.5,1].The paper notes that the continuity assumptions needed for this improvement are strong and difficult to satisfy globally.Source: §4.1 · p. 19

4.2 Primal-dual averaging CndG methods

• PDA-CndG uses a weighted average of past gradients as its LO-oracle direction and achieves the same stated optimal LCP status as PA-CndG for sufficiently large dimension.It also provides an online lower bound on the optimal value, enabling termination based on the gap between that bound and the current objective value.Source: §4.2 · pp. 20–21
• PDA-CndG's faster-rate connection to general optimal first-order methods is conditional: the LO oracle need not satisfy any positive-ρ Hölder condition.The paper says the oracle may satisfy only the ρ = 0 case with Q = D_X.Source: §4.2 · p. 22

4.3 Numerical Illustration

• On simplex/spectrahedron QPs, the three methods perform similarly, with CndG slightly ahead; PDA-CndG outperforms the others on hypercubes and by up to 2 orders of magnitude on hypercube–simplex intersections.For hypercube QPs, PDA-CndG's function values at 100 iterations are already comparable to those of CndG and PA-CndG at 1,000 iterations.Source: Table 3 · p. 23, Table 2 · p. 23, Table 4 · p. 24

• The paper establishes lower complexity bounds for LCP methods across different classes of convex programming problems.Source: §5 · p. 24
• The classic CndG method is optimal among LCP methods for solving smooth convex programming problems.Source: §5 · p. 24
• New CndG variants are optimal or nearly optimal for certain saddle-point and general nonsmooth problems under a linear optimization oracle.Source: §5 · p. 24
• PA-CndG and PDA-CndG, developed by modifying Nesterov’s accelerated gradient method, have optimal smooth-problem convergence rates under a linear optimization oracle.Source: §5 · p. 24
• Preliminary numerical experiments show that PDA-CndG can significantly outperform classic CndG on certain classes of large-scale problems.Source: §5 · p. 24