An Incremental Gradient Method for Large-scale Distributed Nonlinearly\n Constrained Optimization

Harshal D. Kaushik, Farzad Yousefian

TL;DR

This paper introduces a new algorithm, aIR-IG, for optimizing large-scale problems with many component functions and complex, hard-to-project constraints. Unlike existing methods that get bogged down by these projections, aIR-IG uses an iterative regularization technique to avoid them entirely, achieving competitive convergence rates and outperforming standard methods in numerical experiments.

What Problem Does This Paper Address?

Many real-world problems in machine learning and sensor networks involve minimizing a sum of many individual (and often non-differentiable) convex functions. Each function might be owned by a different "agent" or correspond to a subset of data. A common challenge is that these problems often come with constraints – conditions that the solution must satisfy. These constraints can be linear or nonlinear.

Existing popular methods for these "finite sum" problems, like incremental gradient (IG) methods, work by processing one component function at a time. However, when constraints are present, these methods typically require a "projection" step at each iteration. This means finding the closest point within the feasible set (the set of all valid solutions). This projection step can become computationally very expensive, especially when the constraints are nonlinear or there are a huge number of linear constraints. This bottleneck limits the scalability of these methods. This paper aims to overcome this limitation by developing an IG method that doesn't require these costly projections, even for problems with complex constraints.

Methods

The core innovation is the averaged iteratively regularized incremental gradient (aIR-IG) algorithm. Instead of directly projecting onto the hard-to-project feasible set, aIR-IG introduces a novel regularization-based relaxation technique. At each step, agents update their local estimates using a subgradient of a regularized error metric. This metric cleverly combines the objective function's components with a measure of constraint violation, penalized by a regularization parameter.

Key aspects of the method include:

  • Iterative Regularization: A regularization parameter ($\eta_k$) is introduced and updated at each iteration. This parameter helps to "smooth out" the effect of the hard constraints, making the problem easier to handle without explicit projection.
  • Averaging: The algorithm maintains a weighted average of iterates, which is crucial for achieving convergence guarantees.
  • Local Information: Each agent only needs its local function ($f_i, h_i$), constraint matrix ($A_i$), and vector ($b_i$). Communication between agents is assumed to happen in a cyclic manner.
  • No Hard Projections: The algorithm's update rule avoids any explicit projection onto the potentially complex feasible set. Instead, it relies on the projection onto an "easy-to-project" convex set $X$ (which could be the entire space $\mathbb{R}^n$ if there are no simple bounds).

The authors provide theoretical convergence analysis, deriving non-asymptotic rates for both suboptimality (how close the objective value is to the optimum) and infeasibility (how much the constraints are violated).

Datasets

Not discussed in the paper. The paper focuses on a general problem formulation and uses a simulated distributed soft-margin Support Vector Machine (SVM) problem for numerical evaluation.

Key Insights and Ideas

  • Regularization as a Projection Alternative: The most significant insight is that iterative regularization can serve as a powerful alternative to costly projections for handling complex constraints in distributed optimization. By carefully tuning the regularization parameter, the algorithm can effectively navigate the feasible region without explicit geometric projections.
  • Bridging the Gap for Hard Constraints: Existing incremental gradient methods struggle with nonlinear or numerous linear constraints due to projection costs. aIR-IG directly addresses this gap, making these powerful optimization techniques applicable to a wider range of real-world problems.
  • Theoretical Guarantees for a Novel Approach: The paper not only proposes a novel algorithm but also provides rigorous theoretical backing, establishing convergence rates for both the objective function and constraint satisfaction. This is crucial for building confidence in the method's effectiveness.

Key Results

  • Convergence Rates: The paper derives non-asymptotic convergence rates for suboptimality and infeasibility. Under specific stepsize and regularization parameter update rules, these rates are shown to be polynomial in the number of iterations ($N$), specifically $O(N^{-0.5+\delta})$ for some $\delta > 0$.
  • Numerical Performance: In numerical experiments on distributed soft-margin SVM problems, aIR-IG consistently outperformed standard projected IG methods. This advantage became more pronounced as the problem size (number of samples and dimension) increased, highlighting the scalability benefits of avoiding expensive projections. For instance, the paper notes that projection evaluations take longer and degrade performance, especially for larger problem instances.

Limitations and Future Work

  • Assumptions: The convergence analysis relies on certain assumptions, such as the convexity of component functions and the existence of a non-empty feasible set. The paper also assumes an "easy-to-project" convex set $X$.
  • Averaging vs. Individual Iterates: The theoretical analysis primarily focuses on the convergence of the averaged iterate. While the paper suggests that similar rates might hold for other agents' iterates, this is left as a future direction.
  • Stronger Assumptions for Faster Rates: The authors mention that convergence rates can be improved under stronger assumptions, such as the smoothness and strong convexity of the objective functions. This is identified as a promising avenue for future research.
  • Distributed ADMM and Other Methods: While aIR-IG is compared to IG-based methods, its performance relative to other distributed optimization techniques like ADMM for similar problem structures could be an area for further exploration.

Summary updated

Abstract

Motivated by applications arising from sensor networks and machine learning,\nwe consider the problem of minimizing a finite sum of nondifferentiable convex\nfunctions where each component function is associated with an agent and a\nhard-to-project constraint set. Among well-known avenues to address finite sum\nproblems is the class of incremental gradient (IG) methods where a single\ncomponent function is selected at each iteration in a cyclic or randomized\nmanner. When the problem is constrained, the existing IG schemes (including\nprojected IG, proximal IAG, and SAGA) require a projection step onto the\nfeasible set at each iteration. Consequently, the performance of these schemes\nis afflicted with costly projections when the problem includes: (1) nonlinear\nconstraints, or (2) a large number of linear constraints. Our focus in this\npaper lies in addressing both of these challenges. We develop an algorithm\ncalled averaged iteratively regularized incremental gradient (aIR-IG) that does\nnot involve any hard-to-project computation. Under mild assumptions, we derive\nnon-asymptotic rates of convergence for both suboptimality and infeasibility\nmetrics. Numerically, we show that the proposed scheme outperforms the standard\nprojected IG methods on distributed soft-margin support vector machine\nproblems.\n
BibTeX
@misc{kaushik2020incremental,
  author = {Harshal D. Kaushik and Farzad Yousefian},
  title = {{An Incremental Gradient Method for Large-scale Distributed Nonlinearly\textbackslash\{\}n Constrained Optimization}},
  year = {2020},
  eprint = {2006.07956},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.07956},
}
Figure