Non-asymptotic convergence analysis of inexact gradient methods for machine learning without strong convexity

Anthony Man-Cho So, Zirui Zhou

Abstract

In modern machine learning, optimization problems often lack global strong convexity, yet they exhibit structured properties that allow for fast convergence. This paper provides a non-asymptotic analysis of Inexact Gradient Methods (IGMs) for a broad class of structured convex problems, including logistic regression and least squares. By establishing a new global error bound, the author proves that linear convergence is achievable even without strong convexity, provided the gradient approximation error decreases at an appropriate rate. This work bridges the gap between theoretical optimization and the practical use of approximate gradients in large-scale machine learning.

Introduction

Empirical risk minimization (ERM) is the cornerstone of supervised machine learning. To find the optimal parameters for a model, practitioners typically employ gradient-based optimization. However, as datasets grow to include millions or billions of samples, calculating the exact gradient of the loss function becomes computationally prohibitive.

To address this, Inexact Gradient Methods (IGMs) are used. These methods update model parameters using an approximation of the gradient:

$$x^{k+1} = x^k - \alpha_k (\nabla f(x^k) + e^{k+1})$$

where $e^{k+1}$ represents the error or noise in the gradient estimate. While the convergence of IGMs is well-understood for "strongly convex" functions—those with a sharp, bowl-like curvature—many essential machine learning models, such as logistic regression, do not satisfy this condition globally. Previous theoretical frameworks for these non-strongly convex problems were often limited to asymptotic results (describing behavior as iterations approach infinity) or predicted slow, sublinear convergence rates. This paper provides the first non-asymptotic, finite-time analysis showing that fast linear convergence is indeed possible for these structured problems.

Methodology: The Global Error Bound

The primary challenge in analyzing non-strongly convex functions is that the distance to the optimal solution set cannot be easily bounded by the gradient norm. The author overcomes this by focusing on a specific, widely applicable structure: functions that are a composition of a strictly convex function $g$ and a linear operator $E$, expressed as $f(x) = g(Ex)$.

This structure is significant because it allows the matrix $E$ to be rank-deficient—the primary reason strong convexity fails in models like least squares or logistic regression when the number of features is large. The author develops a Global Error Bound that holds across the entire optimization trajectory, rather than just in a local neighborhood of the optimum. This bound ensures that the gradient remains "informative" enough to drive progress toward the solution set at every step.

Convergence Analysis and Key Results

The paper establishes explicit, non-asymptotic rates of convergence for both the objective function value $f(x^k) - f_{min}$ and the distance to the optimal set $dist(x^k, \mathcal{X})$.

Linear Convergence

The analysis proves that if the gradient approximation error $e^k$ decreases at a linear rate, the algorithm itself will converge linearly. Specifically, for the class of structured convex problems defined, the algorithm achieves a rate of $O(c^k)$ for some $c \in (0, 1)$. This confirms that IGMs can be nearly as efficient on logistic regression as they are on strongly convex quadratic problems, provided the error is controlled.

Sublinear Convergence

In scenarios where the gradient error decreases more slowly (e.g., at a polynomial rate $1/k^{1+\rho}$), the paper provides corresponding sublinear convergence rates. This allows practitioners to predict performance even when high-precision gradients are too expensive to compute.

Practical Implications

These theoretical findings provide a rigorous foundation for several common practices in large-scale optimization:

  1. Growing Sample Sizes: The results justify strategies where the algorithm starts with a small subset of data (high error, low cost) and gradually increases the batch size (low error, high cost) as it nears the optimum. This maintains a balance between computational effort and progress.
  2. Broad Model Support: Unlike previous theories that were restricted to quadratic objectives, this analysis applies to any $g$ that is strictly convex on compact sets. This directly encompasses the log-loss used in logistic regression, making the theory highly relevant to modern classification tasks.

Limitations and Future Work

While the paper significantly advances our understanding of IGMs, it assumes that the gradient error $e^k$ can be explicitly controlled or decreased over time. This analysis does not directly apply to standard Stochastic Gradient Descent (SGD) with a fixed batch size, where the error variance remains constant. Future research may explore applying these global error bound techniques to accelerated methods, such as Nesterov’s acceleration, or proximal gradient methods to determine if they share similar non-asymptotic advantages in the absence of strong convexity.

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 and Zirui Zhou},
  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