PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimized first-order methods for smooth convex minimization

Donghwan Kim, Jeffrey A. Fessler

arXiv:1406.5468v4math.OC

TL;DR

Existing optimized first-order coefficients for smooth unconstrained convex minimization are computationally expensive to obtain and use at large iteration counts. The paper derives optimized coefficients analytically, producing recursive methods with efficient implementations. OGM1 and OGM2 achieve a worst-case convergence bound twice as small as Nesterov’s methods, though optimality of the resulting bound remains open.

  • Problem

    Drori and Teboulle’s numerical coefficient optimization is expensive for large N, while the resulting general first-order algorithm requires impractical computation and memory for large-scale problems.

  • Method

    The paper analytically solves a relaxed coefficient-optimization problem and derives recursive optimized first-order algorithms resembling Nesterov’s fast gradient methods.

  • Results

    OGM1 and OGM2 achieve a worst-case convergence bound twice as small as Nesterov’s methods, with exact tightness established for their relaxed bound.

  • Takeaways & Limitations

    OGM1 and OGM2 provide efficient implementations and practical convergence acceleration for smooth unconstrained convex minimization.

  • Takeaways & Limitations

    The paper leaves open whether the smallest OGM1 and OGM2 upper bound is optimal for the original problem.

Abstract

from arXiv · show

We introduce new optimized first-order methods for smooth unconstrained convex minimization. Drori and Teboulle recently described a numerical method for computing the $N$-iteration optimal step coefficients in a class of first-order algorithms that includes gradient methods, heavy-ball methods, and Nesterov's fast gradient methods. However, Drori and Teboulle's numerical method is computationally expensive for large $N$, and the corresponding numerically optimized first-order algorithm requires impractical memory and computation for large-scale optimization problems. In this paper, we propose optimized first-order algorithms that achieve a convergence bound that is two times smaller than for Nesterov's fast gradient methods; our bound is found analytically and refines the numerical bound. Furthermore, the proposed optimized first-order methods have efficient recursive forms that are remarkably similar to Nesterov's fast gradient methods.

1 Introduction

The paper targets first-order methods for smooth convex minimization, where existing optimized coefficients are numerically expensive and can require impractical computation and memory. It proposes analytically derived optimized methods with efficient recursive implementations and a convergence bound twice as small as Nesterov’s.

  • First-order methods are widely used for large-scale optimization, including signal and image processing and machine learning.
  • Nesterov’s fast gradient methods provide fast convergence and efficient implementation for smooth unconstrained convex minimization.
  • Drori and Teboulle optimized first-order coefficients numerically, but their approach becomes expensive for large N and requires O(N^2d) operations and O(Nd) memory.
  • The proposed optimized first-order methods achieve a worst-case convergence bound twice as small as Nesterov’s methods.
  • The proposed methods retain efficient recursive forms requiring O(Nd) arithmetic operations and O(d) memory.

2 Problem and approach

The paper studies non-adaptive first-order methods for smooth convex minimization by optimizing predetermined gradient-combination coefficients against a worst-case performance bound. It replaces Drori and Teboulle’s computationally expensive numerical optimization with an analytical solution that yields a practical recursion.

  • 2.1 Smooth convex minimization problem: The problem assumes a convex, continuously differentiable function with L-Lipschitz continuous gradient and a nonempty optimal set.
  • 2.1 Smooth convex minimization problem: Performance is measured by the inaccuracy f(xN) − f(x∗) after N iterations.
  • 2.2 Optimizing the step coefficients h of first-order algorithms: Solving the exact coefficient-optimization problem would yield the best worst-case bound, but its relaxed SDP solution is expensive for large N and its algorithm stores gradient combinations impractically.
  • 2.2 Optimizing the step coefficients h of first-order algorithms: The paper analytically solves a relaxed problem and derives a convenient recursion resembling Nesterov’s efficient fast gradient methods.

3 Nesterov’s fast gradient methods

This section reviews Nesterov’s fast gradient methods, relates their forms to the general first-order class, and establishes analytical convergence properties for their primary and secondary sequences. It motivates optimized methods by identifying a constant-factor gap despite Nesterov’s optimal rate.

  • FGM1’s mathematically equivalent class-FO representation is impractical at scale, whereas its recursive form is practically useful.
  • The primary sequence of FGM1 and FGM2 achieves the known analytical rate, while the secondary sequence’s matching rate was initially conjectured and later verified analytically.
  • FGM1 and FGM2 generate identical sequences for smooth unconstrained convex minimization.
  • Nesterov’s methods achieve the optimal rate O, while their bound leaves potential for improving first-order methods by a constant factor.
  • Drori and Teboulle’s relaxed PEP numerically found a bound twice smaller than the analytical bound, but numerical verification and SDP computation become difficult for large N.

4 DT’s convergence bound for first-order algorithms using PEP

DT’s PEP framework relaxes the worst-case smooth-convex optimization problem into tractable dual formulations that yield convergence bounds for first-order methods.

  • DT relax the infinite-dimensional functional constraint on f using properties of smooth convex functions.
  • The dual formulation represents function values and gradients through δ, G, and associated matrix constraints.
  • The dual problem can be solved numerically for fixed coefficients h and iteration count N, producing a valid bound independent of dimension d.
  • The resulting bound BD(h, N, L, R) is later optimized over the first-order coefficients h.
  • The PEP approach provides numerical convergence bounds, while analytical bounds were previously limited beyond constant-step gradient methods.

5 A new analytical bound for Nesterov’s fast gradient methods

This section derives an analytical upper bound for the secondary sequence in Nesterov’s fast gradient methods using feasible dual variables in the PEP framework.

  • An analytical bound is developed for the secondary sequence {xi} generated by FGM1 and FGM2.
  • The proposed dual variables form a feasible point of problem (D) for Nesterov’s FGM1 and FGM2 coefficients.
  • The feasibility proof verifies the positive semidefinite condition through the matrix S(h, λ, τ).
  • Because Nesterov’s coefficients are recursive and independent of a given N, the bound extends to all iterations n ≥ 1.
  • The feasible dual point yields a valid upper bound for the secondary sequence and verifies DT’s conjecture.

6 Towards optimized first-order algorithms

The paper analytically solves DT’s relaxed coefficient-optimization problem, derives optimized coefficients, and proves that they produce a convergence bound twice as small as Nesterov’s.

  • DT’s relaxed coefficient optimization is recast as a linear SDP whose numerical solution previously required expensive computation for large N.
  • The paper reformulates the SDP as an equivalent problem and constructs a feasible point satisfying its required conditions.
  • The constructed point is proved optimal for both reformulated SDP problems.
  • The analytically derived coefficients ˆh have a recursive form similar to Nesterov’s FGM2 coefficients.
  • The optimized coefficients are an optimal solution of the relaxed coefficient problem (HD).
  • The optimized Algorithm FO achieves a convergence bound twice as small as Nesterov’s fast gradient methods.
  • The theorem also characterizes the iteration requirement for reaching a target accuracy, with comparison to Nesterov’s method.

7 Efficient formulations of proposed optimized first-order algorithms

The optimized coefficients admit practical recursive implementations: OGM1 resembles FGM1, while OGM2 resembles FGM2 and retains the improved convergence bound.

  • 7 Efficient formulations of proposed optimized first-order algorithms: The optimized coefficient expression can be transformed into efficient recursive formulations analogous to Nesterov’s fast gradient methods.
  • 7 Efficient formulations of proposed optimized first-order algorithms: A recursive relationship for the optimized coefficients is established by an induction argument paralleling the equivalence proof for Nesterov’s formulations.
  • 7.1 Proposed optimized gradient method 1 (OGM1): OGM1 uses the alternative coefficient representation and is computationally similar to FGM1 while attaining the bound from Theorem 2.
  • 7.1 Proposed optimized gradient method 1 (OGM1): OGM1 accelerates FGM1 with one additional momentum term, and its intermediate coefficients do not depend on N.
  • 7.1 Proposed optimized gradient method 1 (OGM1): The OGM1 sequence is identical to the sequence generated by Algorithm FO with the corresponding optimized coefficients.
  • 7.2 Proposed optimized gradient method 2 (OGM2): OGM2 provides a formulation similar to FGM2 and achieves the fast convergence bound established in Theorem 2.
  • 7.2 Proposed optimized gradient method 2 (OGM2): OGM2 doubles the weight on previous gradients relative to FGM2 and requires comparable computation per iteration.
  • 7.2 Proposed optimized gradient method 2 (OGM2): The OGM2 sequence is identical to the sequence generated by Algorithm FO with the optimized coefficients, using a telescoping-sum equivalence.

8 Discussion

The optimized methods’ relaxed bound is shown to be exact and tight through a worst-case convex function, while its dimension independence clarifies the result’s scope. The comparison with FGM bounds is qualified because those bounds are not tight, though they approach tightness asymptotically.

  • Tightness: OGM1 and OGM2 achieve the smallest upper bound in (6.17) exactly for the specified worst-case convex functions.The tightness result holds for all d ≥1.
  • Worst-case construction: The worst-case construction uses iterates that remain in an affine region of φ(x) with the same gradient value.The construction starts from x0 = Rν, where ν is a unit vector.
  • PEP interpretation: The exact PEP bound BP(ˆh, N, d, L, R) equals the relaxed bound BD(ˆh, N, L, R) and is independent of d.This establishes exactness of the relaxed bound for OGM1 and OGM2.
  • Comparison with FGM: The OGM bound (6.17) is tight, whereas the FGM bounds (3.5) and (5.5) are not tight.The FGM bounds become close to tight asymptotically as N increases, so the factor of 2 may have practical value for many iterations.

9 Conclusion

The paper concludes that OGM1 and OGM2 combine a worst-case bound twice as small as Nesterov’s with comparable implementation efficiency. It identifies unresolved analytical and extension questions, including intermediate-iteration bounds and nonsmooth composite minimization.

  • Conclusion: OGM1 and OGM2 achieve a worst-case convergence bound twice as small as Nesterov’s methods while remaining comparably efficient to implement.The paper reports practical convergence acceleration in large-scale imaging applications consistent with these bounds.
  • Open questions: The efficient formulations of OGM1 and OGM2 lack an analytical explanation of the fundamental causes of their acceleration.The paper proposes extending existing studies of Nesterov’s formulations to OGM methods.
  • Open questions: The new optimized methods lack analytical convergence bounds for intermediate iterations.Numerical bounds for intermediate iterations are studied in related work.
  • Extensions: Extending the proposed methods to general first-order algorithms and nonsmooth composite convex minimization remains future work.The paper presents these extensions as natural or important directions.
  • Open questions: The optimality of the smallest upper bound in (6.17) remains unproved for the exact PEP problem (HP).The paper leaves either proving optimality for (HP) or further optimizing the methods as future work.

10 Appendix

The appendix verifies feasibility of the analytically chosen parameters and derives their recursive structure. It then establishes coefficient properties used to characterize OGM1 and OGM2 iterates and their worst-case behavior.

  • Parameter feasibility: The choices (ˆr, ˆλ, ˆτ, γ) satisfy the feasible conditions (6.14) of (RD1).The derivation uses the specified relations among ˆλ, ˆτ, and ˆr.
  • Parameter recursion: Induction shows that the solution of recursion (10.1) is equivalent to the selected ˆλ in (6.10).The proof determines λ1 and then propagates the relation through the remaining indices.
  • Parameter feasibility: The feasibility proof concludes that the chosen parameters are feasible in both (RD) and (RD1).This completes the appendix’s verification of the analytical construction.
  • Coefficient properties: The appendix proves that the coefficients ˆh in (7.1) satisfy property (8.2), which determines useful sums and endpoint relations.The proof proceeds by induction and uses (3.2) and (6.15).
  • Coefficient properties: The resulting coefficient relations include separate formulas for interior indices, the final iterate, and boundary index pairs.These relations are used in the derivation of OGM1 and OGM2 behavior.
Loading 1406.5468v4…