Linear Convergence with Condition Number Independent Access of Full Gradients

Lijun Zhang, Mehrdad Mahdavi, Rong JinNeurIPS 2013 · OpenReview

TL;DR

This paper introduces Epoch Mixed Gradient Descent (EMGD), a hybrid optimization algorithm that achieves linear convergence for smooth, strongly convex problems. Its breakthrough contribution is making the number of expensive "full gradient" evaluations entirely independent of the condition number ($\kappa$), relying instead on cheap stochastic gradients to navigate ill-conditioned landscapes.

The Trade-off in Convex Optimization

In the world of convex optimization, researchers often face a strict trade-off between precision and computational speed per iteration:

  1. Full Gradient Descent (GD): Converges very quickly (linearly) but requires a pass over the entire dataset for every step. If the problem is "ill-conditioned" (meaning the optimization landscape is a narrow, steep valley), you need many of these expensive passes—specifically $O(\sqrt{\kappa} \log 1/\epsilon)$ passes.
  2. Stochastic Gradient Descent (SGD): Very cheap per iteration, but its convergence is sluggish ($O(1/\epsilon)$), making it hard to reach high-precision solutions.
Comparison of iteration complexities for standard Full and Stochastic Gradient methods.

The "gap" is the computational burden of ill-conditioned problems. When the condition number $\kappa$ (the ratio of smoothness to strong convexity) is large, standard accelerated methods still require too many full-data sweeps. The authors ask: Can we achieve fast linear convergence while keeping the number of full gradient evaluations independent of how "difficult" the landscape is?

Introducing Epoch Mixed Gradient Descent (EMGD)

To bridge this gap, the authors propose Epoch Mixed Gradient Descent (EMGD). The algorithm operates in a sequence of "epochs" and introduces a clever Mixed Gradient step to reduce variance.

  • The Epoch Structure: At the start of each epoch, the algorithm computes exactly one full gradient at the current best estimate.
  • The Mixed Gradient: During the epoch, instead of just using a raw, noisy stochastic gradient, EMGD uses a hybrid estimator: $$\tilde{g}_t = \nabla F(\text{start of epoch}) + \nabla f_t(\text{current point}) - \nabla f_t(\text{start of epoch})$$ This formula uses the "fresh" stochastic gradient to find the direction of change but anchors it to the "accurate" full gradient from the start of the epoch.

  • Variance Reduction: Because the objective is smooth, as the current point gets closer to the epoch's starting point, the noise in the stochastic components cancels out.

  • Domain Shrinking: In each epoch, the algorithm constrains its search to a progressively smaller ball (a "trust region"), which helps maintain stability despite stochastic noise.

Key Insights and Theoretical Advantages

  • Decoupling $\kappa$ from Full Gradients: The most significant theoretical breakthrough is that EMGD only needs $O(\log 1/\epsilon)$ full gradients to reach an $\epsilon$-optimal solution, regardless of the condition number. The "difficulty" of the problem ($\kappa$) is shifted entirely onto the number of cheap stochastic iterations.
  • Memory Efficiency: Unlike other fast stochastic methods like SAG or SDCA, which require storing a gradient for every single data point ($O(n)$ memory), EMGD only needs to store the current iterate and the anchor gradient ($O(d)$ memory, where $d$ is the dimension).
  • Constrained Optimization: Many fast stochastic algorithms only work for unconstrained problems. EMGD naturally handles constraints by performing the update over a convex domain.
  • High Probability Convergence: While many stochastic proofs only work "on average" (in expectation), the authors prove that EMGD converges with high probability, offering a much stronger theoretical guarantee.

Key Results and Complexity

The theoretical analysis shows that EMGD finds an $\epsilon$-optimal solution with:

  • Full Gradient Evaluations: $O(\log 1/\epsilon)$ — Note the total absence of $\kappa$!
  • Stochastic Gradient Evaluations: $O(\kappa^2 \log 1/\epsilon)$.
Comparison of total computational complexities across state-of-the-art algorithms.

For a dataset of size $n$, the total computational complexity is $O((n + \kappa^2) \log 1/\epsilon)$. This makes EMGD faster than Nesterov’s accelerated gradient descent whenever the condition number is relatively small compared to the dataset size (specifically $\kappa \le n^{2/3}$).

Limitations and Future Work

While theoretically sound, EMGD has a few practical limitations:

  • Knowledge of $\kappa$: EMGD requires knowing the condition number $\kappa$ (or the smoothness and strong convexity parameters) beforehand to set the epoch length and step size. In real-world problems, these are rarely known exactly.
  • The $\kappa^2$ Penalty: While the full gradients are independent of $\kappa$, the number of stochastic steps scales with $\kappa^2$. For extremely ill-conditioned problems, this quadratic dependence could become a bottleneck.

For future directions, the authors suggest developing methods to estimate $\kappa$ on the fly, perhaps by sampling the Hessian matrix to approximate the landscape's curvature dynamically.

Summary updated

Abstract

For smooth and strongly convex optimization, the optimal iteration complexity of the gradient-based algorithm is $O(\sqrt{\kappa}\log 1/\epsilon)$, where $\kappa$ is the conditional number. In the case that the optimization problem is ill-conditioned, we need to evaluate a larger number of full gradients, which could be computationally expensive. In this paper, we propose to reduce the number of full gradient required by allowing the algorithm to access the stochastic gradients of the objective function. To this end, we present a novel algorithm named Epoch Mixed Gradient Descent (EMGD) that is able to utilize two kinds of gradients. A distinctive step in EMGD is the mixed gradient descent, where we use an combination of the gradient and the stochastic gradient to update the intermediate solutions. By performing a fixed number of mixed gradient descents, we are able to improve the sub-optimality of the solution by a constant factor, and thus achieve a linear convergence rate. Theoretical analysis shows that EMGD is able to find an $\epsilon$-optimal solution by computing $O(\log 1/\epsilon)$ full gradients and $O(\kappa^2\log 1/\epsilon)$ stochastic gradients.
BibTeX
@inproceedings{zhang2013linear,
  author = {Lijun Zhang and Mehrdad Mahdavi and Rong Jin},
  title = {{Linear Convergence with Condition Number Independent Access of Full Gradients}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=rk4ArwZu-S},
}
Figure