PaperlayerView exact revision on arXiv

Source-linked AI summary

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition

Hamed Karimi, Julie Nutini, Mark Schmidt

arXiv:1608.04636v4cs.LGmath.OCstat.COstat.ML

TL;DR

The paper addresses how to establish linear convergence without strong convexity for optimization problems arising in machine learning. It shows that the older Polyak-Łojasiewicz inequality is weaker than several alternatives, then extends the analysis across multiple first-order methods and to proximal-gradient optimization. The resulting framework supplies convergence analyses and simpler proofs for a broad range of machine-learning problems, including non-smooth and some non-convex cases.

  • Problem

    Strong convexity gives gradient descent a global linear rate, but important machine-learning objectives can be convex without being strongly convex, while alternatives have complicated proofs and unclear relationships.

  • Method

    The paper analyzes the Polyak-Łojasiewicz inequality and proposes a proximal generalization, applying them to gradient, coordinate, sign-based, stochastic, and proximal-gradient methods.

  • Results

    The PL inequality is weaker than several recent alternatives for global linear convergence and yields convergence results for numerous machine-learning models and algorithms, including some non-convex problems.

  • Takeaways & Limitations

    Many assumptions used to obtain linear convergence can be replaced by the PL inequality or its proximal generalization, often with simpler proofs and without strong convexity.

  • Takeaways & Limitations

    The work provides no experimental results because its main contributions are theoretical convergence analyses of existing algorithms.

Abstract

from arXiv · show

In 1963, Polyak proposed a simple condition that is sufficient to show a global linear convergence rate for gradient descent. This condition is a special case of the Łojasiewicz inequality proposed in the same year, and it does not require strong convexity (or even convexity). In this work, we show that this much-older Polyak-Łojasiewicz (PL) inequality is actually weaker than the main conditions that have been explored to show linear convergence rates without strong convexity over the last 25 years. We also use the PL inequality to give new analyses of randomized and greedy coordinate descent methods, sign-based gradient descent methods, and stochastic gradient methods in the classic setting (with decreasing or constant step-sizes) as well as the variance-reduced setting. We further propose a generalization that applies to proximal-gradient methods for non-smooth optimization, leading to simple proofs of linear convergence of these methods. Along the way, we give simple convergence results for a wide variety of problems in machine learning: least squares, logistic regression, boosting, resilient backpropagation, L1-regularization, support vector machines, stochastic dual coordinate ascent, and stochastic variance-reduced gradient methods.

1 Introduction

The paper argues that the older Polyak-Łojasiewicz (PL) inequality offers a weaker and simpler route to global linear convergence than several alternatives to strong convexity. It applies this perspective across gradient, stochastic, coordinate, sign-based, and proximal-gradient methods, including non-smooth problems.

  • Motivation: The paper situates PL among error bounds, essential strong convexity, weak strong convexity, restricted secant inequality, and quadratic growth conditions.It notes that the relationships among these conditions are rarely discussed and that their linear-convergence proofs are typically not straightforward.
  • Contribution: The PL inequality is weaker than recently studied alternatives to strong convexity for establishing global linear convergence to an optimal solution.The paper presents this relationship as a way to replace longer proofs under those conditions with simpler PL-based arguments.
  • Applications: PL yields linear convergence for least squares and logistic regression even when strong convexity is not guaranteed, and for some non-convex problems.These applications are presented as consequences of the paper’s PL analysis.
  • Extensions: The analysis extends to randomized and greedy coordinate descent, sign-based gradient methods, and stochastic gradient methods in classical and variance-reduced settings.The coordinate-descent results also imply a new convergence rate for certain boosting variants.
  • Proximal-gradient methods: A generalized PL condition for smooth-plus-simple-non-smooth objectives gives linear convergence of proximal-gradient methods without strong convexity.The generalization is equivalent to the Kurdyka-Łojasiewicz condition in this setting while yielding shorter proofs for problems such as support vector machines and ℓ1-regularized least squares.

2 Polyak- Lojasiewicz Inequality

The PL inequality guarantees global linear convergence for gradient descent under smoothness without requiring convexity, and is weaker than several commonly studied alternatives. It also covers non-convex and machine-learning objectives, including strongly convex functions composed with linear maps.

  • Gradient descent under PL: The PL inequality, together with an L-Lipschitz gradient and a non-empty solution set, gives gradient descent with step-size 1/L a global linear convergence rate.The proof applies the smoothness inequality and then the PL inequality recursively.
  • Gradient descent under PL: The proof of linear convergence under PL is simpler than typical proofs under strong convexity or other conditions and does not assume convexity.This makes PL one of the few stated general conditions for global linear convergence on non-convex problems.
  • Relationships between conditions: Among the considered alternatives, PL and the equivalent error-bound condition are the most general conditions guaranteeing linear convergence to a global minimizer; quadratic growth is weaker but permits non-global local minima.For convex functions, quadratic growth, error bounds, PL, and the restricted secant condition become equivalent in the stated relationships.
  • Invex and non-convex functions: PL implies invexity because every stationary point is a global minimizer, while the example f(x) = x2 + 3 sin2(x) is invex, non-convex, and satisfies PL with µ = 1/32.Therefore, gradient descent has a global linear convergence rate on this example.
  • Invex and non-convex functions: The PL-based local convergence phase can be larger than the locally strongly-convex phase, although many complicated models have non-optimal stationary points and are not invex.For f(x) = x2 + 3 sin2(x), the locally PL region is all of IR, whereas the locally strongly-convex interval cited is [−1, 1].
  • Relevant problems: Functions that are strongly convex after composition with a linear map satisfy PL; this includes least squares and all convex quadratic functions.Logistic regression can also satisfy PL over compact sets when its strictly convex component is not strongly convex, provided the iterates remain bounded.

3 Convergence of Huge-Scale Methods

The PL inequality extends simple linear-convergence analyses to randomized coordinate descent and stochastic gradient methods beyond strong-convex settings. The section also gives explicit greedy-coordinate results and classical stochastic-gradient rates under decreasing or constant step sizes.

  • Section contribution: The analyses aim to cover more general function classes than previous coordinate-descent and stochastic-gradient convergence results while retaining simple proofs.The section positions PL as the common condition used for these large-scale methods.
  • Randomized coordinate descent: Randomized coordinate descent achieves an expected linear convergence rate when the objective has coordinate-wise Lipschitz gradients, a non-empty solution set, and satisfies PL.The method uses step-size 1/L and selects the updated coordinate uniformly at random.
  • Greedy coordinate descent: Greedy Gauss–Southwell coordinate descent satisfies the randomized rate, while an infinity-norm PL formulation yields a faster rate than random selection.The faster-rate comparison follows from norm equivalence, with µ/d ≤ µ1.
  • Greedy coordinate descent: The PL-based coordinate-descent result provides the first explicit convergence rate for the analyzed boosting variants viewed as Gauss–Southwell coordinate descent.Earlier error-bound analyses established linear convergence but not an explicit rate.
  • Stochastic gradient methods: Stochastic gradient methods are analyzed under PL with unbiased sampled gradients and bounded expected component-gradient norms, using both decreasing and constant step sizes.The section considers finite-sum objectives, where each component typically corresponds to one training example.
  • Stochastic gradient methods: A decreasing step size gives an O(1/k) rate matching stochastic-gradient convergence under strong convexity, while a constant step size gives linear convergence up to a solution level proportional to α.The O(1/k) result is also stated for least squares, though with worse constants than a stochastic Newton method.

4 Proximal-Gradient Generalization

The paper generalizes PL to proximal-gradient optimization, proving global linear convergence under proximal-PL and applying the result to regularized, constrained, coordinate-wise, and dual optimization problems.

  • Proximal-PL condition: The proximal-PL inequality extends PL to minimizing F(x)=f(x)+g(x), where f has an L-Lipschitz gradient and g is simple, convex, and potentially non-smooth.The paper defines proximal-PL for this composite setting and notes that it reduces to standard PL when g is constant or linear.
  • Proximal-gradient convergence: With step-size 1/L, proximal-gradient converges linearly to the optimal value when F has a non-empty solution set and satisfies proximal-PL.The resulting proof is presented as simpler than analyses based on several alternative conditions.
  • Function classes: The proximal-PL framework covers standard classes including PL functions with constant g, strongly convex f, and strongly convex functions composed with linear maps.The paper also relates proximal-PL to other regularized problem classes through its equivalence with KL.
  • Least squares with ℓ1-regularization: For ℓ1-regularized least squares, proximal-PL yields global linear convergence without additional assumptions or algorithmic modifications.Earlier results required conditions such as restricted isometry or modified restricted convexity and smoothness, whereas the cited KL and EB results imply proximal-PL here.
  • Coordinate-wise proximal-gradient: Coordinate-wise proximal-gradient requires separable g and achieves a convergence rate under uniformly random coordinate selection.The paper presents this as an extension of its coordinate-descent and proximal-gradient analyses.
  • Applications: The framework also gives linear-rate results for SVM dual coordinate optimization and for many ℓ2-regularized linear prediction problems, including cases with non-smooth primal objectives.For SVMs, the dual QG property supports the result, and dual accuracy transfers to primal accuracy through the cited relationship.

5 Discussion

The paper presents PL and proximal-PL as a unifying way to simplify linear-convergence analyses across machine-learning optimization problems. It emphasizes theoretical convergence implications rather than experimental evaluation.

  • Unifying perspective: PL and its proximal generalization replace many assumptions previously used to establish linear convergence rates across optimization methods and machine-learning models.The paper frames this replacement as a unifying and simplifying view of convergence-rate analysis.
  • Scope of evidence: The paper provides no experimental results because its contributions concern proving that existing algorithms converge faster on standard problems than previously recognized.The authors distinguish these theoretical contributions from empirical evaluation.

Appendix A Relationships Between Conditions

The appendix organizes relationships among strong convexity, alternative regularity conditions, PL, and quadratic growth. It establishes implication chains showing that PL is weaker than several commonly used conditions and implies QG and EB.

  • Definitions: The appendix defines SC, ESC, WSC, RSI, EB, PL, and QG using constants μ>0 and projections onto the solution set.Convex QG is additionally identified with optimal strong convexity or related terminology.
  • Implication chain: The established implication chain includes SC→ESC→WSC→RSI→EB→PL.The appendix derives these implications using projection choices, rearrangement, Cauchy–Schwarz, and Lipschitz continuity.
  • PL and QG: PL implies QG with the same constant, and convex QG implies RSI, further positioning PL within the network of convergence conditions.The PL-to-QG proof uses a gradient-flow argument reaching the optimal set in finite time and bounds the orbit length by projection distance.
  • PL and QG: The appendix concludes the PL-to-QG derivation by obtaining the QG bound from the finite-time gradient-flow construction.The argument uses the endpoint in the optimal set and the path-length comparison with the projection distance.

Appendix B Relevant Problems

The appendix verifies PL-based convergence for strongly convex objectives and for strongly convex functions composed with linear maps. These examples recover known rates while extending beyond unique-solution settings.

  • Strongly convex functions: Strong convexity implies PL with the same constant, so gradient descent with step-size 1/L recovers the known linear rate for μ-strongly convex functions.The appendix obtains PL by minimizing the strong-convexity inequality over y.
  • Strongly convex compositions: For f(x)=g(Ax) with strongly convex g, the appendix derives PL using the smallest non-zero singular value of A.The resulting PL constant is μ=σθ(A), where σ is the strong-convexity parameter of g.

Appendix C Sign-Based Gradient Methods

The appendix analyzes sign-based gradient descent with coordinate-specific step sizes under Lipschitz-gradient assumptions. The chosen step sizes yield linear convergence when the PL inequality holds.

  • Sign-Based Gradient Methods: RPROP updates coordinates using individual step sizes through coordinate-wise multiplication.The method is presented as a long-used machine-learning heuristic, with a convergence analysis developed here.
  • Assumptions: Constants L_i define a norm in which the gradient is Lipschitz continuous.Such constants exist whenever the gradient is Lipschitz continuous, so this choice does not add assumptions on f.
  • Method: The analyzed step sizes are chosen coordinate-wise using the constants L_i.The resulting coordinate-wise iteration is substituted into the smoothness bound and combined with the PL inequality.
  • Result: The resulting method achieves a linear convergence rate for problems satisfying the PL inequality.

Appendix D Linear Convergence Rate of SVRG Method

This appendix establishes linear convergence of SVRG when component functions are convex and smooth while their finite-sum objective satisfies the PL inequality. The proof uses a projection onto the solution set and the equivalence of PL and quadratic growth in the convex setting.

  • SVRG Setup: SVRG is analyzed for a finite-sum optimization problem using sampled component gradients and periodic snapshot updates.The algorithm selects component indices uniformly and refreshes the snapshot and full gradient after every m steps.
  • Assumptions: The component functions are convex with Lipschitz-continuous gradients, and the aggregate objective satisfies the PL inequality.The step size is assumed to satisfy α < 2/L.
  • Proof Strategy: The convergence proof analyzes the outer SVRG iterates and selects the projection of the previous iterate onto the solution set.Quadratic growth, equivalent to PL for this convex setting, is then applied to obtain the rate.
  • Result: For sufficiently large m and sufficiently small α, SVRG has a linear convergence rate.
  • Auxiliary Result: The appendix also establishes that D_g(x, λ) is nondecreasing in λ for convex g when λ increases.This follows from the stated lemma and its corollary.

Appendix F Relevant Problems

The appendix verifies proximal-PL for several composite optimization classes and notes that it reduces to ordinary PL when the nonsmooth term is constant. It also connects proximal-PL to standard structural conditions.

  • Relevant Problems: Functions satisfying the KL inequality or proximal-EB condition are identified as an additional class linked to proximal-PL.
  • Relevant Problems: Proximal-PL is shown for objectives where f satisfies PL and g is constant.In this case, the proximal-PL inequality simplifies directly to the PL inequality.
  • Relevant Problems: The condition is established when f is strongly convex in F(x) = f(x) + g(x).The proof uses strong convexity and minimizes the resulting inequality over y.
  • Relevant Problems: Proximal-PL also covers f(Ax) + g(x) with strongly convex f, linear A, and polyhedral-set indicator g.The argument uses a projection onto the optimal solution set and Hoffman's bound.
  • Relevant Problems: Convex f combined with a quadratic-growth objective F is another class satisfying proximal-PL.The proof applies convexity of f and the QG condition.

Appendix G Equivalence of Proximal-PL with KL and EB

This appendix relates proximal-PL to the KL and proximal-EB conditions for composite objectives with differentiable smooth terms and convex nonsmooth terms. It proves implications among these conditions using subgradient and proximal constructions.

  • Equivalence Proof: The proof establishes proximal-EB implies proximal-PL by bounding the forward-backward envelope and using Lipschitz continuity of ∇f.
  • Definitions: The appendix defines proximal-PL, proximal-EB, and the KL condition with exponent 1 for F(x) = f(x) + g(x).For differentiable f and convex g, the Frechet subdifferential combines the gradient of f with subgradients of g.
  • Definitions: The KL condition generalizes PL by using the minimum-norm subgradient as the descent-direction measure.This provides the nonsmooth analogue of the gradient quantity used in the smooth setting.
  • Equivalence Proof: Proximal-PL implies KL by comparing the proximal residual with the minimum-norm subgradient of F.The argument uses the subgradient definition and minimizes the resulting bound over y.
  • Equivalence Proof: KL implies proximal-EB through semiconvexity, subgradient curves, and bounds on the curve-length residual.The proof shows the residual converges to zero and derives a bound with a constant C.
  • Equivalence Proof: The proximal construction defines a point using the proximal operator and then derives the proximal-EB condition from subgradient and Lipschitz bounds.

Appendix H Proximal Coordinate Descent

The appendix establishes linear convergence for randomized proximal coordinate descent under a proximal PL condition, coordinate-wise Lipschitz continuity, and separable convex regularization. The proof bounds coordinate improvements, relates their expectation to Dg, and applies the proximal-PL inequality.

  • Linear convergence holds for randomized coordinate descent when F satisfies the proximal PL inequality, ∇f is coordinate-wise Lipschitz continuous, and g is separable convex.
  • Coordinate-wise Lipschitz continuity and separability provide an upper bound on the improvement in F for each coordinate step.
  • Each coordinate descent update chooses its coordinate value to minimize the upper bound on the improvement in F.
  • Random coordinate selection connects expected improvement to Dg, after which subtracting F* and applying proximal PL yields the linear convergence rate.
Loading 1608.04636v4…