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:
- 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.
- 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