# Stochastic Constrained Decentralized Optimization for Machine Learning with Fewer Data Oracles: a Gradient Sliding Approach

arXiv: https://arxiv.org/abs/2404.02511 · HTML: https://mlsanity.com/paper/2404.02511/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 56 references that are in the map.
- First posted on arXiv 3 Apr 2024.

## Builds on (most cited first, 30 of 32)

- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication](https://mlsanity.com/paper/1902.00340/) (2019)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learning](https://mlsanity.com/paper/1805.09965/) (2018)
- [SGD and Hogwild! Convergence Without the Bounded Gradients Assumption](https://mlsanity.com/paper/1802.03801/) (2018)
- [On the Linear Convergence of the ADMM in Decentralized Consensus Optimization](https://mlsanity.com/paper/1307.5561/) (2013)
- [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014)
- [Communication-Efficient Algorithms for Decentralized and Stochastic Optimization](https://mlsanity.com/paper/1701.03961/) (2017)
- [Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2006.11773/) (2020)
- [Variance-Reduced and Projection-Free Stochastic Optimization](https://mlsanity.com/paper/1602.02101/) (2016)
- [On Lower Complexity Bounds for Large-Scale Smooth Convex Optimization](https://mlsanity.com/paper/1307.5001/) (2013)
- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [New Analysis and Results for the Frank-Wolfe Method](https://mlsanity.com/paper/1307.0873/) (2013)
- [On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error](https://mlsanity.com/paper/2202.03618/) (2022)
- [A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming](https://mlsanity.com/paper/1804.08544/) (2018)
- [Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimization](https://mlsanity.com/paper/1302.2325/) (2013)
- [Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization](https://mlsanity.com/paper/1512.08122/) (2015)
- [Non-convex Conditional Gradient Sliding](https://mlsanity.com/paper/1708.04783/) (2017)
- [On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers](https://mlsanity.com/paper/1307.8254/) (2013)
- [Decentralized Frank-Wolfe Algorithm for Convex and Non-convex Problems](https://mlsanity.com/paper/1612.01216/) (2016)
- [Convergence of First-Order Algorithms for Meta-Learning with Moreau Envelopes](https://mlsanity.com/paper/2301.06806/) (2023)
- [On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and Efficient Gradient Methods](https://mlsanity.com/paper/2312.13970/) (2023)
- [Projection-Free Adaptive Gradients for Large-Scale Optimization](https://mlsanity.com/paper/2009.14114/) (2020)
- [Graph topology invariant gradient and sampling complexity for decentralized and stochastic optimization](https://mlsanity.com/paper/2101.00143/) (2021)
- [A Decentralized Second-Order Method with Exact Linear Convergence Rate for Consensus Optimization](https://mlsanity.com/paper/1602.00596/) (2016)
- [A low-rank augmented Lagrangian method for large-scale semidefinite programming based on a hybrid convex-nonconvex approach](https://mlsanity.com/paper/2401.12490/) (2024)
- [On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems](https://mlsanity.com/paper/1503.06833/) (2015)
- [Second-order Conditional Gradient Sliding](https://mlsanity.com/paper/2002.08907/) (2020)
- [DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers](https://mlsanity.com/paper/1508.02073/) (2015)
- [Scalable Electric Vehicle Charging Protocols](https://mlsanity.com/paper/1510.00403/) (2015)

## Built on by (most cited first, 2 of 2)

- [Sparse Partial Optimal Transport via Quadratic Regularization](https://mlsanity.com/paper/2508.08476/) (2025)
- [Accelerated Algorithm for Sparse Regularized Partial Optimal Transport](https://mlsanity.com/paper/2609.40075/) (2026)

## Abstract (arXiv)

In modern decentralized applications, ensuring communication efficiency and privacy for the users are the key challenges. In order to train machine-learning models, the algorithm has to communicate to the data center and sample data for its gradient computation, thus exposing the data and increasing the communication cost. This gives rise to the need for a decentralized optimization algorithm that is communication-efficient and minimizes the number of gradient computations. To this end, we propose the primal-dual sliding with conditional gradient sliding framework, which is communication-efficient and achieves an varepsilon-approximate solution with the optimal gradient complexity of O(1/√varepsilon+σ2/varepsilon2) and O(log(1/varepsilon)+σ2/varepsilon) for the convex and strongly convex setting respectively and an LO (Linear Optimization) complexity of O(1/varepsilon2) for both settings given a stochastic gradient oracle with variance σ2. Compared with the prior work citewai-fw-2017, our framework relaxes the assumption of the optimal solution being a strict interior point of the feasible set and enjoys wider applicability for large-scale training using a stochastic gradient oracle. We also demonstrate the efficiency of our algorithms with various numerical experiments.