Linear Convergence of Proximal Gradient Algorithm with Extrapolation for a Class of Nonconvex Nonsmooth Minimization Problems

1. Introduction.

• FISTA uses Nesterov-style extrapolation with a coefficient recurrence and was shown to converge faster in objective values than proximal gradient.The method was proposed for convex f and continuous g; its analysis extends to proper closed convex g.Source: §1 · p. 2
• Adaptive restart resets extrapolation periodically and has global linear convergence of function values for strongly convex f when the restart interval is sufficiently large.The cited work also reports robustness to errors in estimating f’s strong-convexity modulus.Source: §1 · p. 2
• Other results include convergence for convex problems with βk bounded below 1, and local linear convergence for LASSO under uniqueness and additional assumptions.The LASSO results cited impose strict complementarity or other problem-specific conditions.Source: §1 · p. 2
• Prior linear-convergence results for extrapolated proximal gradient were limited to certain convex problems with unique optima and specific coefficient choices.The paper studies convergence under more general conditions, including possibly nonconvex cases.Source: §1 · p. 3
• Under the error bound condition, extrapolation coefficients below a threshold yield R-linear convergence of iterates to a stationary point and of objective values.For convex f, the threshold is 1, giving R-linear convergence of FISTA with fixed restart to an optimal solution.Source: §1 · p. 3
• The paper organizes its analysis around preliminaries, convergence results, FISTA with restart, and numerical experiments.The experiments illustrate the theoretical results.Source: §1 · p. 3

2. Notation and preliminaries.

• The paper uses R^n for Euclidean space, the standard inner product and Euclidean norm, and specified notation for ℓ1 and ℓ∞ norms and matrix eigenvalues.It also defines the all-ones vector and matrix transpose notation.Source: §2 · p. 3
• For proper closed convex functions, the section defines the subdifferential and proximal operator, and notes that the proximal operator is well defined.It also defines indicator functions, distance to a closed set, and projection onto a closed convex set.Source: §2 · pp. 3–4
• An optimal solution satisfies a first-order necessary condition, and any optimal solution is a stationary point under the paper’s definition.The set of stationary points is denoted by X.Source: §2 · p. 4
• The section distinguishes Q-linear from R-linear convergence and gives a lemma connecting them when one sequence is bounded above by a Q-linearly convergent sequence.Under those conditions, the bounded sequence is R-linearly convergent to zero.Source: §2 · p. 4

3. Convergence analysis of the proximal gradient algorithm with ex-

• The section presents a proximal-gradient algorithm with extrapolation and analyzes the convergence behavior of its generated sequence.Source: §3 · pp. 4–5

3.1. Auxiliary lemmas.

• With extrapolation coefficients below a threshold, the auxiliary sequence converges, steps are square-summable, accumulation points are stationary, and F is constant on the accumulation set.If F is level bounded, the generated iterates are bounded.Source: §3.1 · pp. 6–9

3.2. Linear convergence of {xk} and {F(xk)}.

• Under Assumption 3.1, the iterates converge R-linearly to a stationary point of F, and the objective values converge R-linearly.The analysis first establishes Q-linear convergence of the auxiliary sequence Hk,α.Source: §3.2 · pp. 9, 12
• The iterates converge R-linearly to a stationary point, and the objective-value sequence also converges R-linearly.The objective-value result follows from the Q-linear convergence of H_{k,α}.Source: §3.2 · p. 12

3.3. FISTA with restart: a special case of Algorithm 1.

• FISTA is a special case of Algorithm 1; the discussed restart schemes are fixed-interval resets and adaptive gradient-based resets.Fixed restart resets the parameters every K iterations; adaptive restart resets them when ⟨y_k − x_{k+1}, x_{k+1} − x_k⟩ > 0.Source: §3.3 · p. 13
• Under convexity and Assumption 3.1, FISTA with fixed restart, alone or with adaptive restart, converges R-linearly in iterates and objective values to global optima.The iterates converge to a globally optimal solution, and the objective values to the globally optimal value.Source: §3.3 · pp. 13–14
• For the LASSO, fixed restart or combined fixed and adaptive restart yields R-linear convergence of both iterates and objective values.Source: §3.3 · p. 14
• Unlike, the result covers convex f and both sequences, is local rather than global, and imposes no restriction on restart interval K.[12] guarantees global linear convergence of function values only for strongly convex f with g = 0, and requires K sufficiently large.Source: §3.3 · p. 14

4. Numerical experiments.

• The experiments cover three problem classes, comparing proximal gradient and extrapolation variants, with FISTA included as a heuristic for the possibly nonconvex case.The convex experiments include fixed and adaptive restart; the nonconvex experiments include βk ≡ 0 and βk ≡ 0.98/(L+l).Source: §4 · p. 14

4.1. ℓ1 regularized logistic regression.

• On ℓ1-regularized logistic regression, fixed- and adaptive-restart FISTA produce R-linearly convergent iterates and objective values and perform better than FISTA and proximal gradient.The comparisons use plots of iterate distance and objective-value gap against iteration count across three problem sizes.Source: §4.1 · p. 15, Figure 4.1 · p. 16, Figure 4.2 · p. 16

4.2. LASSO.

• On LASSO, fixed- and adaptive-restart FISTA produce R-linearly convergent iterates and objective values and outperform FISTA and proximal gradient.The plots compare iterate distance and objective-value gap across three problem sizes.Source: §4.2 · p. 17, Figure 4.4 · p. 18, Figure 4.5 · p. 18

4.3. Nonconvex quadratic programming with simplex constraints.

• For the nonconvex quadratic problem, Algorithm 1 with βk ≡ 0.98/(L+l) has R-linearly convergent iterates, but not all tested algorithms approach Fmin.The authors suggest that some iterates may have become stuck at local minimizers; Figure 4.7 plots iterate distance and objective-value gap against iterations.Source: §4.3 · p. 19, Figure 4.7 · p. 19
• On random nonconvex quadratic instances, PGe is always the fastest algorithm, although its termination function values can be slightly compromised for some instances.Table 4.1 reports iteration counts and termination function values averaged over 50 instances for each tested dimension.Source: §4.3 · p. 20, Table 4.1 · p. 20

• The iterates and objective values converge R-linearly under the error bound condition when extrapolation coefficients stay below a threshold.Source: §5 · p. 20
• The theory is applied to analyze FISTA with fixed restart for convex problems.Source: §5 · p. 20
• Numerical experiments illustrate the paper’s results.Source: §5 · p. 20