A single potential governing convergence of conjugate gradient, accelerated gradient and geometric descent

1 First-order methods for strongly convex functions

• The three analyses use the Bubeck–Lee–Singh geometric lemma, relate the methods to an idealized algorithm, and track a shared potential.The potential is computable each iteration in O(n) operations when ℓ and L are known.Source: §1 · p. 3
• CG exactly implements the idealized algorithm on quadratic objectives, while GD and AG simulate it using partial information.The idealized algorithm itself is generally unimplementable because it requires prior knowledge of x*.Source: §1 · p. 3
• A computable scalar potential enables hybrid algorithms, including a proposed hybrid CG method tested computationally.The motivation is that CG can outperform its worst-case bound on particular instances, depending on A's eigenvalues.Source: §1 · p. 3

2 Notation

• The notation section defines closed balls, affine sets, and the tangent space of an affine set.For an affine set U = c + W, its tangent space is W.Source: §2 · p. 4

3 Preliminary lemmas

• If δ ≤ ∥x − y∥ and p lies in both B(x, ρ) and B(y, σ), the lemma bounds p within a ball centered at a weighted point z.The enclosing radius is given by (3), and its square-root argument is nonnegative when the two input balls intersect.Source: §3 · pp. 4–5
• The derivation verifies nonnegativity of the radius expression using the ball-intersection condition and the bound δ ≤ ∥x − y∥.The proof rewrites the radicand as a sum of nonnegative terms under the stated assumptions.Source: §3 · pp. 4–5
• Under ρ + σ ≥ δ and δ ≥ |ρ² − σ²|, expression (3) is minimized over λ ∈ [0, 1]; its right-hand side is a convex quadratic, minimized where its derivative is zero.Source: §3 · p. 5

4 Idealized algorithm

• At each iteration, the algorithm minimizes f over M_k, chooses y_k closest to x*, and expands the next affine space using y_k − x_k and the gradient.The initial space is generated by x_0 and ∇f(x_0).Source: §4 · p. 6
• The idealized algorithm is generally unimplementable because choosing y_k requires prior knowledge of x*.The paper uses it to describe different relationships with CG, accelerated gradient, and geometric descent.Source: §4 · p. 6
• The analysis uses a potential Ψ_k and a geometric-lemma point z*_k to compare the next iterate's distance to x* with the best available distance.Since y_{k+1} minimizes distance to x* in the next affine space, it is at least as close as z*_k.Source: §4 · pp. 6, 8

5 Analysis of the geometric descent algorithm

• GD's dogleg step combines a gradient step with movement toward y_k, and a line search selects x_k on the specified line.The line search requires an inner iteration; the analysis uses the resulting decrease and affine-space minimality properties.Source: §5 · p. 9
• GD maintains σ_k as an upper bound on ∥y_k − x*∥ and updates that bound inductively.Although γ_k alone requires x*, the difference γ_k − γ_{k−1} used by the algorithm does not.Source: §5 · pp. 9, 11
• Offsets γ_k increase the squared radii used by the geometric lemma, while adjusted quantities ρ̃_k and σ̃_k support their implementable updates.The offsets are adjusted at the start of each iteration.Source: §5 · pp. 9–10
• The section proves GD convergence through two theorems that are variants of results by Bubeck, Lee, and Singh [2].The algorithm is presented as an implementable method derived from properties used in the idealized algorithm's analysis.Source: §5 · pp. 9, 11

Relationship between GD and IA

• For x_k, GD uses ∇f(x_{k−1}), the search line, and the minimizer's location on that line; its choice is optimal over M_k given this information.IA instead chooses the optimal x_k for the true objective.Source: §6 · pp. 14–15
• For y_k, a separate construction establishes the analogous worst-case optimality over M_k, with y_k the midpoint attaining radius ξ*.The two constructed optimizers are 2ξ* apart.Source: §6 · pp. 16, 18
• The discussion treats the main case |ρ²−σ²| in GD's loop and omits the minor case.Condition (35) is used to establish (46) for the main case.Source: §6 · p. 18
• For condition (53), the band between the two bounds remains unresolved: F may be empty, or the proof's construction may fail.The bounds differ by a factor of 2.Source: §6 · p. 19
• GD's x_k and y_k choices solve minimization problems like IA's, but for worst-case objectives consistent with GD's partial information rather than the true objective.This frames the relationship between the two algorithms.Source: §6 · pp. 14, 19
• The examples suggest GD may be improved by using information it currently ignores, such as the third ball; [3] reports results in this direction.The section does not pursue this idea.Source: §6 · p. 19

7 Computability of the potential

• The GD potential is computable each iteration without knowing x*, although it requires prior knowledge of ℓ.The potential is computable in O(n) operations when ℓ and L are known.Source: §7 · p. 19
• A computable potential must be obtainable without prior knowledge of x* or f(x*), and should approach zero as the iterates approach x*.A fixed upper bound unrelated to the current iterate is computable but has no algorithmic use.Source: §7 · pp. 19–20
• Guaranteed potential decrease establishes linear convergence rates and could support a CG stagnation test, unlike the potentially oscillatory gradient norm.The authors note that a gradient-norm termination criterion is unsuitable for checking whether a single CG iteration succeeded.Source: §7 · p. 20
• The same slight variant of the GD potential also applies to CG and AG; the authors know of no other computable potential with these properties.The potential's run-time use as a measure of steady decrease is reported in later experiments.Source: §7 · p. 20

8 Analysis of linear conjugate gradient

• Linear CG exactly implements IA on the same quadratic function and initial point, and therefore satisfies IA's convergence bound.The proof identifies the subspace used by IA with one CG constructs without computing IA's auxiliary iterate.Source: §8 · pp. 21–22
• For CG, x_k minimizes f over V_k and residual r_k equals −∇f(x_k); a less well-known property is that x_k + τ_k p_k minimizes ∥x − x*∥ over V_k.Source: §8 · p. 21
• The induction shows that CG identifies IA's subspace even though CG never computes IA's auxiliary y iterate.The line through the iterates agrees with the line generated by the CG search direction.Source: §8 · p. 22

9 A computable potential for linear conjugate gradient

• The GD potential gives CG a computable run-time potential, unlike the preceding IA-based potential, which requires knowing the optimizer.The authors say the earlier potential's decrease cannot be measured during the algorithm because it depends on the optimizer.Source: §9 · p. 22
• For CG, the authors define auxiliary y iterates using GD's formulas; these are not IA's true distance minimizers but shrink sufficiently fast for the potential decrease.They otherwise mimic GD's definitions and change xk to use CG.Source: §9 · pp. 22–23
• The same two theorems established for GD also hold for CG.The analysis notes orthogonality of the residual to CG's Krylov space and that each CG step improves the objective at least as much as taking no step.Source: §9 · p. 23

10 Accelerated gradient

• AG is presented as a looser approximation to IA than GD: its step lengths are fixed and it has no per-iteration optimization subproblem.The section introduces auxiliary sequences for the analysis.Source: §10 · p. 23, Accelerated Gradient · p. 24

Accelerated Gradient

• The analysis proves that ˜σk decreases at the appropriate rate and upper-bounds distance to the optimizer.The proof uses induction and the geometric lemma to establish the stated results.Source: Accelerated Gradient · pp. 24–26

11 Relationship between IA and AG

• AG only approximates IA: it uses fixed step sizes instead of optimization subproblems, and its coupled x_k and y_k computations complicate induction.The paper describes this relationship as weaker than IA’s relationship with GD or CG.Source: §11 · p. 26
• AG’s iterates are optimal up to a lower-order remainder given its partial information, whereas IA is separately optimal for both terms without a remainder.The comparison is for the specific function in the IA case.Source: §11 · p. 27
• When the gradient at w_{k−1} is unexpectedly small, AG may make suboptimal choices; an assumption like (82) is needed to establish its optimality.The stated concern is that strong convexity puts the true minimizer near w_{k−1} − g/ℓ, making the AG update to y_k suboptimal.Source: §11 · p. 29
• The orthogonality assumption (83) is a limitation of the quadratic construction, not necessarily a requirement for more general convex functions.The authors note that more general functions may have level curves whose elongation axes vary between levels.Source: §11 · p. 29

12 A hybrid nonlinear conjugate gradient

• The hybrid guarantees O(log(1/ε)√(L/ℓ)) convergence for smooth, strongly convex functions and reduces to optimal linear CG on quadratics.With exact line search, it produces the same sequence of iterates as linear conjugate gradient.Source: §12 · pp. 29, 32
• The hybrid targets nonlinear CG’s good behavior on nearly quadratic functions while retaining a guaranteed-complexity fallback.The authors expect nearly quadratic behavior close to typical practical objectives’ solutions.Source: §12 · pp. 29–30
• Its line search approximates the objective along the CG direction with a univariate quadratic, exact when the objective itself is quadratic.The quadratic coefficient is obtained using reverse-mode automatic differentiation.Source: §12 · p. 30
• The method accepts a nonlinear CG step when the objective and potential checks pass; otherwise, it takes a geometric descent step.The CG step is tested for objective decrease and sufficient potential decrease.Source: §12 · p. 30
• Approximate line search can trigger a safeguard that keeps y_k and σ_k unchanged; the implementation also addresses roundoff in its computations.The paper describes separate workarounds for roundoff in δ_{k−1} and in subtractions used to compute the potential.Source: §12 · p. 32

13 Computational Results

• The methods were tested on approximate BPDN and hinge-loss halfspace classification, using synthetic data and a gradient-norm stopping criterion.The reported tests used ∥∇f(x_k)∥ ≤ 10^-6 for the hinge-loss experiments and varied δ and problem size for approximate BPDN.Source: §13 · pp. 33–34
• HyNCG was superior in every test case, sometimes by a wide margin.Table 1 reports iteration counts for four algorithms on nine synthetic test cases.Source: Table 1 · p. 34, §13 · p. 34
• Table 1 reports inner line-search steps for NCG and GD, the sum of CG and inner line-search steps for HyNCG, and outer iterations for AG.DNC indicates that the algorithm achieved the requisite tolerance after 105 outer iterations.Source: §13 · p. 34
• For the HL problems, iteration counts were nearly invariant as λ varied, except AG’s running time grew as λ decreased.The authors state that they do not currently have an explanation for this pattern.Source: §13 · p. 34
• The potential-based hybrid outperformed the two alternative hybrids, often by a factor of 2 and sometimes by a large factor.The alternatives select steps by gradient-norm decrease or objective decrease, and require two evaluations per iteration; the potential can select a CG step without testing an alternative when it decreases sufficiently.Source: §13 · pp. 34–35, Table 2 · p. 35

• One computable potential bounds convergence of CG, AG, and GD, linking their analyses to an idealized algorithm and the Bubeck-Lee-Singh lemma.Source: §14 · p. 35
• The potential enables a hybrid that duplicates CG steps while retaining optimal complexity for general smooth, strongly convex problems.Source: §14 · p. 35
• The hybrid requires prior knowledge of ℓ and L, unlike linear CG, which does not require prior knowledge of its coefficient matrix.Source: §14 · p. 35
• A theoretical result establishing the hybrid's improved performance on nearly quadratic functions remains an open direction.Source: §14 · p. 35
• Unlike AG, the other algorithms have not been extended beyond unconstrained smooth, strongly convex optimization; extending CG ideas to constrained or composite minimization is proposed.Source: §14 · pp. 35–36