Linear Convergence under Relaxed Strong Convexity

20 concepts14 papers1 proposal

In classical optimization, achieving a linear convergence rate—where the optimization error drops exponentially with each iteration—typically requires the objective function to be strongly convex. Geometrically, strong convexity means the function is globally bounded from below by a quadratic bowl. This sharp curvature guarantees that the gradient never becomes too small when far from the optimum, providing a steady, powerful "pull" toward a unique solution.

However, many modern machine learning and signal processing problems lack this ideal geometry. Matrix factorization, sparse recovery (such as LASSO), and distributed empirical risk minimization often feature flat valleys, multiple global minima, or even local non-convexity. Yet, in practice, standard optimization algorithms frequently maintain their rapid, linear convergence on these problems.

This gap between traditional theory and practice has driven a major research direction: proving that global strong convexity is a sufficient condition for linear convergence, but far from a necessary one. By identifying weaker, more localized geometric regularities, researchers have extended fast convergence guarantees to a much broader class of functions.

The Core Intuition: What Replaces the Quadratic Bowl?

To understand why an algorithm can converge linearly without global strong convexity, we must look at what strong convexity actually provides. It ensures that:

  1. The gradient magnitude is large enough relative to the suboptimality (ensuring significant progress per step).
  2. The distance to the optimal solution decreases predictably with every step.

If an objective function can guarantee these properties along specific search directions, locally within a neighborhood, or relative to a set of optimal solutions rather than a single unique point, linear convergence remains mathematically intact.

Strong Convexity              Weak Strong Convexity         Restricted Strong Convexity
   (Unique Bowl)                 (Flat Valley Floor)             (Curved in Sparse Directions)
       \   /                         |       |                         \   /
        \_/                          |_______|                          \_/
                                  (Optimal Set)                  (Flat in other directions)

Directional and Restricted Curvature

In high-dimensional problems like sparse recovery, a function might be entirely flat in many directions, but highly curved along the specific directions the algorithm actually explores. This is the core intuition behind Restricted Strong Convexity (RSC).

As shown by Nguyen et al., algorithms designed for sparse constraints (such as greedy pursuit methods) do not require global curvature; they only need the objective to behave like a strongly convex function over sparse subspaces.

This relaxation is remarkably versatile across different algorithmic architectures:

  • Incremental Methods: Sun et al. demonstrated that Proximal Incremental Aggregated Gradient (PIAG) methods maintain linear convergence under RSC. This geometric guarantee allows the algorithm to support significantly larger stepsizes than traditional theory would permit.
  • Momentum Methods: Sun et al. extended this intuition to momentum-based optimization, proving that the classic Heavy-Ball method converges linearly under RSC, even when the objective function is not strictly convex in all directions.

Curvature Relative to Solution Sets

When an optimization problem has multiple global minima, the function cannot be strongly convex because the minimum is not unique. However, it can still satisfy Weak Strong Convexity or a Quadratic Growth condition. Instead of curving upward from a single point, the function curves upward quadratically as you move orthogonally away from the entire set of optimal solutions.

Ma et al. leveraged this concept to unify randomized optimization frameworks. They proved that randomized coordinate descent methods converge linearly under weak strong convexity because every random step still pushes the iterate closer to the closest point in the optimal set.

Even in non-convex or weakly convex settings, Takahashi et al. showed that Frank–Wolfe algorithms with adaptive step-sizes achieve local linear convergence by exploiting a local quadratic growth condition around the solution set.

Sharpness as a Regularity Condition

For non-smooth and weakly convex functions, the concept of sharpness serves as a vital substitute for strong convexity. Sharpness implies that the function grows at least linearly with the distance to the optimal set, establishing a global error bound.

As analyzed by Davis et al., when a subgradient method is initialized within a specific neighborhood of the solution set, this sharpness property prevents the algorithm from stalling or wandering aimlessly. The sharp V-shaped landscape ensures that even without smooth curvature, the step sizes drive the algorithm at a linear rate toward the true solution set.


Algorithmic Manifestations Across Domains

By shifting the analytical focus from global function properties to these relaxed regularity conditions, researchers have unlocked linear convergence proofs across a wide array of specialized domains.

Distributed and Network Optimization

In distributed systems, data is scattered across multiple nodes, making global properties difficult or impossible to enforce. Relaxed strong convexity allows for fast distributed optimization without stringent global assumptions:

  • Approximate Multipliers: Wu et al. introduced an Approximate Method of Multipliers (AMM) framework that achieves linear convergence under local restricted strong convexity.
  • Decentralized Gradient Descent: Yun extended decentralized gradient methods to non-strongly convex problems, establishing convergence for general and quasi-strongly convex functions.
  • Saddle-Point Problems: For distributed minimax and saddle-point problems, Qureshi et al. demonstrated that gradient tracking can achieve linear convergence without requiring primal strong convexity.
  • Quantized Communication: Even under communication constraints, Chen et al. proved that quantized primal-dual network optimization algorithms can converge linearly for general convex objectives.

Structured Matrix and Linear Systems

The relaxation of strong convexity has also revolutionized structured matrix problems, where the underlying convex relaxations are inherently non-strongly convex:

  • Matrix Recovery: In rank-one matrix recovery, Garber bypassed the lack of strong convexity by designing a Frank–Wolfe variant that achieves linear convergence while avoiding computationally expensive singular value decompositions (SVDs).
  • Stochastic Linear Systems: Richtárik et al. showed that reformulating linear systems stochastically yields iterative methods with global linear convergence without relying on strong convexity assumptions.

Second-Order and Splitting Methods

Finally, large-scale empirical risk minimization (ERM) often relies on splitting or second-order methods to handle non-smooth regularizers:

  • Splitting Methods: Hong et al. developed a block successive upper-bound minimization method of multipliers (BSUM-M) for linearly constrained problems, proving linear convergence without strong convexity.
  • Quasi-Newton Methods: To reduce communication overhead in distributed ERM, Lee et al. proposed a distributed quasi-Newton algorithm that utilizes approximate Hessian information to guarantee global linear convergence for non-strongly convex objectives.

By moving away from the rigid requirement of a global quadratic bowl, this research direction bridges the gap between pessimistic classical theory and the highly efficient optimization performance observed in modern practice.

Key Foundational Work

Linear Convergence of Randomized Feasible Descent Methods Under the Weak Strong Convexity Assumption (2016) — contributed 2 concept elements to this direction.
Linear Convergence of Stochastic Iterative Greedy Algorithms With Sparse Constraints (2014) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_linear_convergence_without_strong_convex_c373101f,
  title = {linear convergence without strong convexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-convergence-without-strong-convexity/rdr_c373101f67c4460a8bb9e6ee58be252f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_linear_convergence_without_strong_convex_c373101f_v1,
  title = {linear convergence without strong convexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-convergence-without-strong-convexity/rdr_c373101f67c4460a8bb9e6ee58be252f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake