General Proximal Incremental Aggregated Gradient Algorithms: Better and Novel Results under General Scheme

Tao Sun, Yuejiao Sun, Dongsheng Li, Qing Liao

Executive Summary

This paper introduces a unifying framework for Proximal Incremental Aggregated Gradient (PIAG) algorithms, demonstrating that they operate effectively under much broader conditions than previously established. The authors prove that these algorithms can achieve linear convergence without requiring strict strong convexity and can handle nonconvex objectives. Furthermore, the framework supports significantly larger stepsizes and introduces a new, highly efficient line search strategy.

Introduction: The Challenge of Large-Scale Optimization

In large-scale machine learning and network optimization, researchers frequently need to minimize a composite objective function of the form $F(x) = \sum f_i(x) + g(x)$, where $f_i$ represents smooth, data-dependent loss terms and $g$ acts as a regularizer. When the number of components $m$ is massive, computing the full gradient at every step becomes computationally prohibitive.

Incremental Aggregated Gradient (IAG) methods address this bottleneck by utilizing "stale" gradients from previous iterations stored in memory, updating only one (or a small batch) of component gradients at a time. However, traditional theoretical guarantees for these methods have been quite restrictive. They typically required the objective function to be strongly convex, forced the use of very small stepsizes (which inherently slows down training), and lacked robust analysis for nonconvex problems or noisy environments.

A Unified Methodological Framework

To overcome these limitations, the authors propose a General PIAG framework that unifies several state-of-the-art algorithms—such as SAGA, SVRG, and decentralized SGD—into a single, cohesive mathematical scheme.

Key technical innovations of this framework include:

  • Lyapunov Function Analysis: Moving away from standard convergence proofs, the authors employ a custom Lyapunov function—a mathematical "energy" function guaranteed to decrease over time. This technique allows them to rigorously track the algorithm's progress even when gradients are delayed or noisy.
  • General Scheme for Real-World Conditions: The framework explicitly accounts for gradient delays ($\tau$), noise ($e^k$), and proximal operators, making it highly applicable to a wide variety of real-world distributed computing scenarios.
  • Adaptive Line Search Strategy: The authors introduce a deterministic line search version of PIAG. This allows the algorithm to adaptively choose the stepsize in each iteration, rather than relying on a fixed, often overly conservative, theoretical constant.

Key Insights and Theoretical Guarantees

Summary of the paper's novel algorithmic and theoretical results.

The theoretical analysis yields several breakthroughs that significantly advance the understanding of PIAG methods:

  • Breaking the Strong Convexity Barrier: A major insight is the proof that PIAG can achieve linear convergence under a "restricted" strong convexity condition, which is a much weaker and more realistic assumption than standard strong convexity. Under this condition, the algorithm achieves a linear rate of $O(\omega^k)$, where the stepsize no longer depends on a potentially tiny strong convexity constant.
  • Sublinear Convergence for General Convexity: For general convex functions, the authors successfully prove a non-ergodic convergence rate of $O(1/k)$. This marks the first time such a rate has been established for PIAG.
  • Validating Larger Stepsizes: Previous literature suggested that stepsizes had to be tiny to guarantee convergence in delayed settings. This paper proves that for cyclic updates, the stepsize can be up to half the size of what is used in standard gradient descent, regardless of the strong convexity constant.
  • Embracing Nonconvexity: The paper provides some of the first rigorous convergence results for PIAG applied to nonconvex functions. By leveraging the "semi-algebraic" property (Kurdyka-Łojasiewicz inequality), the authors prove that the sequence of iterates reliably converges to a critical point.
  • Noise Tolerance: The framework demonstrates that as long as the noise in the gradient is "square-summable" (meaning it decreases sufficiently over time), the algorithm remains stable and convergent.

Experimental Validation

The authors evaluated their generalized algorithms and the new line search strategy on two standard machine learning benchmarks: MNIST (handwritten digit recognition) and ijcnn1 (binary classification).

They tested both convex (logistic regression) and nonconvex (squared logistic loss with MCP regularization) loss functions to validate their theoretical claims. The numerical experiments confirmed that the version of PIAG utilizing the line search converged significantly faster—often by an order of magnitude in terms of CPU time—compared to versions relying on fixed theoretical stepsizes.

Limitations and Future Work

While the paper provides a substantial leap in theoretical understanding, a few areas remain open for future exploration:

  • Boundedness Assumptions: Some results for the sublinear rate require the proximal map to be bounded. The authors work around this by modifying the problem (e.g., adding box constraints), but a more direct proof for unbounded cases would be ideal.
  • Stochastic Delay: The current analysis assumes a maximum, bounded delay $\tau$. In extremely volatile distributed systems, delays might be stochastic or unbounded, a scenario not fully covered by the current framework.
  • Communication Costs: While the line search dramatically speeds up convergence in terms of iterations, it requires additional function evaluations. In specific distributed architectures, this could increase communication overhead, presenting a trade-off that warrants further study.

Summary updated

Abstract

The incremental aggregated gradient algorithm is popular in network optimization and machine learning research. However, the current convergence results require the objective function to be strongly convex. And the existing convergence rates are also limited to linear convergence. Due to the mathematical techniques, the stepsize in the algorithm is restricted by the strongly convex constant, which may make the stepsize be very small (the strongly convex constant may be small). In this paper, we propose a general proximal incremental aggregated gradient algorithm, which contains various existing algorithms including the basic incremental aggregated gradient method. Better and new convergence results are proved even with the general scheme. The novel results presented in this paper, which have not appeared in previous literature, include: a general scheme, nonconvex analysis, the sublinear convergence rates of the function values, much larger stepsizes that guarantee the convergence, the convergence when noise exists, the line search strategy of the proximal incremental aggregated gradient algorithm and its convergence.
BibTeX
@inproceedings{sun2019general,
  author = {Tao Sun and Yuejiao Sun and Dongsheng Li and Qing Liao},
  title = {{General Proximal Incremental Aggregated Gradient Algorithms: Better and Novel Results under General Scheme}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=sP6KFJ9ky1l},
}
Figure