Non-Asymptotic Convergence Analysis of Inexact Gradient Methods for Machine Learning Without Strong Convexity

Anthony Man-Cho So

TL;DR

This paper proves that Inexact Gradient Methods (IGMs)—which use approximate gradients to save computation—can achieve fast, linear convergence even for problems that aren't strongly convex, such as logistic regression. By developing a new "global error bound," the author provides the first non-asymptotic guarantees for a broad class of structured optimization problems common in machine learning.

What Problem Does This Paper Address?

In large-scale machine learning, calculating the exact gradient of a loss function over millions of samples is computationally prohibitive. Researchers often turn to Inexact Gradient Methods (IGMs), which use an approximation of the gradient (like a subset of the data) to update the model.

The "gold standard" for optimization speed is linear convergence (where the error drops exponentially). Historically, proving that an algorithm converges linearly required the objective function to be strongly convex. Unfortunately, many workhorse ML models—like Least Squares and Logistic Regression—are convex but not strongly convex when the data matrix isn't full rank.

Before this paper, theoretical guarantees for these models were either:

  1. Sublinear: Proving the algorithm works, but slowly.
  2. Asymptotic: Proving the algorithm eventually becomes fast, but only after an unknown, potentially infinite number of iterations.

The author seeks to bridge this gap by providing non-asymptotic (guaranteed from iteration one) linear convergence rates for these non-strongly convex problems.

Methods

The paper focuses on a specific problem structure: minimizing $f(x) = g(Ex)$, where $E$ is a linear operator (like a data matrix) and $g$ is a smooth, strictly convex function.

The core mathematical innovation is the development of a Global Error Bound.

  • Standard approach: Use strong convexity to relate the objective value to the distance to the optimal solution.
  • This paper's approach: The author proves a relationship between the distance to the set of optimal solutions and the norm of the gradient. Crucially, they show this relationship holds globally across the entire space, not just near the solution.

By combining this global error bound with a convergence framework originally proposed by Luo and Tseng, the author analyzes the IGM update: $$x^{k+1} = x^k - \alpha_k (\nabla f(x^k) + e^{k+1})$$ where $e^{k+1}$ represents the gradient approximation error.

Datasets

Not discussed in the paper. This is a purely theoretical work focused on mathematical proofs and convergence analysis. While it mentions applications to Least Squares and Logistic Regression, it does not perform empirical tests on specific datasets.

Key Insights and Ideas

  • Structure over Strong Convexity: The paper shows that you don't need the "bowl-like" curvature of strong convexity everywhere to get fast results. As long as the function is a composition of an affine mapping and a strictly convex function, the underlying structure is enough to support linear convergence.
  • Globalizing the Analysis: Most previous "error bound" theories only worked when the algorithm was already very close to the solution (local analysis). By making the error bound global, the author provides a guarantee that covers the entire trajectory of the algorithm.
  • Error Tolerance: The results quantify exactly how "inexact" your gradient can be. If your gradient errors decrease linearly to zero, your overall optimization will also converge linearly. This justifies the use of "growing sample size" strategies in incremental gradient methods.

Key Results

  • Linear Convergence Guarantee: If the squared error norms $\|e^k\|^2$ decrease linearly, the objective value $f(x^k) - f_{min}$ and the distance to the optimal set both converge linearly.
  • Sublinear Convergence Guarantee: If the errors decrease more slowly (sublinearly, at a rate of $O(1/k^{1+\rho})$), the algorithm still converges at that same sublinear rate.
  • Unified Framework: The paper successfully applies these results to both Least Squares (Scenario S1) and Logistic Regression (Scenario S2), providing the first non-asymptotic linear rates for IGMs on these specific problems without assuming strong convexity.

Limitations and Future Work

  • Error Sequence Assumptions: The analysis assumes that the error sequence $\{e^k\}$ is either deterministic and decreasing at a known rate, or that its expectation is bounded. In practice, controlling the exact decay of gradient error can be difficult.
  • Step Size Constraints: To simplify the proof, the author assumes a constant step size related to the Lipschitz constant. While they mention it can be extended to diminishing step sizes, the specific non-asymptotic bounds might change.
  • Future Directions: The author suggests that the "global error bound" technique could be applied to other first-order methods, such as accelerated gradient methods or proximal methods, to see if they also enjoy similar non-asymptotic benefits in non-strongly convex settings.

Summary updated

Abstract

Many recent applications in machine learning and data fitting call for the algorithmic solution of structured smooth convex optimization problems. Although the gradient descent method is a natural choice for this task, it requires exact gradient computations and hence can be inefficient when the problem size is large or the gradient is difficult to evaluate. Therefore, there has been much interest in inexact gradient methods (IGMs), in which an efficiently computable approximate gradient is used to perform the update in each iteration. Currently, non-asymptotic linear convergence results for IGMs are typically established under the assumption that the objective function is strongly convex, which is not satisfied in many applications of interest; while linear convergence results that do not require the strong convexity assumption are usually asymptotic in nature. In this paper, we combine the best of these two types of results and establish---under the standard assumption that the gradient approximation errors decrease linearly to zero---the non-asymptotic linear convergence of IGMs when applied to a class of structured convex optimization problems. Such a class covers settings where the objective function is not necessarily strongly convex and includes the least squares and logistic regression problems. We believe that our techniques will find further applications in the non-asymptotic convergence analysis of other first-order methods.
BibTeX
@inproceedings{so2013non,
  author = {Anthony Man-Cho So},
  title = {{Non-Asymptotic Convergence Analysis of Inexact Gradient Methods for Machine Learning Without Strong Convexity}},
  booktitle = {Optim. Methods Softw},
  year = {2013},
  doi = {10.1080/10556788.2017.1296439},
}
Figure