Decentralized Optimization with Distributed Features and Non-Smooth Objective Functions

Cristiano Gratton, Naveen K. D. Venkategowda, Reza Arablouei, Stefan WernerarXiv 2022 · DOI · arXiv

TL;DR

This paper introduces a fully decentralized algorithm for machine learning problems where data features are split across different agents (vertical partitioning). By cleverly navigating the "dual domain" of the optimization problem, the authors eliminate the need to calculate complex conjugate functions, making it possible to solve non-smooth problems like Elastic-Net regression across a network without a central coordinator.

What Problem Does This Paper Address?

In traditional distributed learning, we usually assume horizontal partitioning: every agent has a few complete data samples. However, many modern scenarios involve feature partitioning (or vertical partitioning), where different agents hold different attributes of the same data samples. For example, in a healthcare study, a hospital might have clinical records while a lab has genetic data for the same set of patients.

The mathematical challenge here is that the objective function is "non-separable." You cannot simply sum up local costs because the features are coupled. Existing solutions for this often require computing "conjugate functions"—a mathematical transformation that is often difficult or impossible to derive for non-smooth functions (like the $L_1$ penalty used in Lasso). Furthermore, many current methods rely on a central hub, creating a single point of failure and increasing privacy risks.

Methods

The authors propose a consensus-based distributed algorithm that tackles these hurdles through a two-layered optimization strategy:

  1. Dual Problem Reformulation: They first transform the original (primal) non-separable problem into a dual form. In this dual space, the problem becomes separable, making it a perfect candidate for the Alternating Direction Method of Multipliers (ADMM).
  2. The "Dual-of-the-Dual" Trick: Standard ADMM update steps usually require the conjugate of the objective function. To avoid this, the authors treat the ADMM update itself as a new optimization problem. They solve its dual using Block Coordinate Descent (BCD).
  3. Fully Distributed Architecture: The resulting algorithm (Algorithm 1) allows agents to reach a global consensus by only communicating with their immediate neighbors. No central server is required.

Datasets

The researchers evaluated their algorithm using synthetic datasets designed to mimic various regression challenges:

  • Data Generation: Features and noise were drawn from multivariate normal distributions.
  • Problem Types: They tested the algorithm on Elastic-Net (which is non-smooth and lacks a simple conjugate function), Ridge, and Lasso regression.
  • Network Topologies: To ensure robustness, they tested various graph structures, including random, line, ring, star, and fully-connected networks.

Key Insights and Ideas

  • Bypassing the Conjugate: The most significant "aha moment" is the realization that one can solve the ADMM primal update in its own dual domain. This effectively "undoes" the need for an explicit conjugate function, allowing the algorithm to handle almost any convex, non-smooth objective.
  • Separability via Duality: While the original problem is a tangled mess of features across agents, the dual variables act as a bridge, allowing agents to optimize their local models while slowly aligning with the rest of the network.
  • Network Influence: The simulations reveal that the algorithm converges faster when the network is more "connected" (e.g., a fully-connected network vs. a line) and when individual agents hold fewer features.

Key Results

  • Theoretical Optimality: The authors provide a formal proof (Theorem 2) that their decentralized algorithm converges to the same optimal solution as a centralized "all-knowing" processor.
  • Elastic-Net Success: The algorithm successfully solved Elastic-Net problems where many competing algorithms fail because they cannot handle the specific non-smooth math involved.
  • Competitive Performance: In Ridge and Lasso benchmarks, the proposed method performed on par with or better than state-of-the-art methods like DC-ADMM, while maintaining the advantage of being more general-purpose.
  • Scalability: Accuracy improved as the number of data samples ($M$) increased, confirming the algorithm's utility for "big data" applications.

Limitations and Future Work

  • Convexity Constraint: The current framework relies on the objective functions being convex. Extending this to non-convex problems (like deep neural networks) remains a significant challenge.
  • Communication Efficiency: While the algorithm only requires single-hop communication, ADMM-based methods can sometimes require many iterations to reach high precision. Future work could explore "event-triggered" communication to save bandwidth.
  • Synchronicity: The paper assumes agents update in a somewhat synchronized fashion. Exploring how the algorithm handles "stragglers" (slow agents) or asynchronous updates would be a valuable next step for real-world IoT deployments.

Summary updated

Abstract

We develop a new consensus-based distributed algorithm for solving learning problems with feature partitioning and non-smooth convex objective functions. Such learning problems are not separable, i.e., the associated objective functions cannot be directly written as a summation of agent-specific objective functions. To overcome this challenge, we redefine the underlying optimization problem as a dual convex problem whose structure is suitable for distributed optimization using the alternating direction method of multipliers (ADMM). Next, we propose a new method to solve the minimization problem associated with the ADMM update step that does not rely on any conjugate function. Calculating the relevant conjugate functions may be hard or even unfeasible, especially when the objective function is non-smooth. To obviate computing any conjugate function, we solve the optimization problem associated with each ADMM iteration in the dual domain utilizing the block coordinate descent algorithm. Unlike the existing related algorithms, the proposed algorithm is fully distributed and does away with the conjugate of the objective function. We prove theoretically that the proposed algorithm attains the optimal centralized solution. We also confirm its network-wide convergence via simulations.
BibTeX
@misc{gratton2022decentralized,
  author = {Cristiano Gratton and Naveen K. D. Venkategowda and Reza Arablouei and Stefan Werner},
  title = {{Decentralized Optimization with Distributed Features and Non-Smooth Objective Functions}},
  year = {2022},
  eprint = {2208.11224},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2208.11224},
}
Figure