Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization

By Blake E. Woodworth, Jialei Wang, H. Brendan McMahan, Nati Srebro. 2018

128 citations recorded by the source corpus.

We suggest a general oracle-based framework that captures parallel stochastic optimization in different parallelization settings described by a dependency graph, and derive generic lower bounds in terms of this graph. We then use the framework and derive lower bounds to study several specific parallel optimization settings, including delayed updates and parallel processing with intermittent communication. We highlight gaps between lower and upper bounds on the oracle complexity, and cases where the ``natural'' algorithms are not known to be optimal.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Vision and Pattern Recognition, Statistical Learning Theory, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Vision and Pattern Recognition

In Statistical Learning Theory

In Algorithms & Complexity

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “[411] highlights several gaps between upper and lower bounds for optimization relevant to the federated learning setting, particularly for “intermittent communication graphs”, which captures local SGD approaches, but convergence rates for such approaches are not known to match the corresponding lowe”
Federated Optimization in Heterogeneous Networks (2018, background): “For instance, parallel SGD and related variants (Zhang et al., 2015; Shamir et al., 2014; Reddi et al., 2016; Zhou & Cong, 2018; Stich, 2019; Wang & Joshi, 2018; Woodworth et al., 2018; Lin et al., 2020), which make local updates similar to FedAvg, have been studied in the IID setting.”
Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization (2020, background): “[31] Blake E Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, and Nati Srebro.”
Is Local SGD Better than Minibatch SGD? (2020, methodology): “If this were possible, it would match the lower bound of Woodworth et al. (2018) and therefore be optimal with respect to this communication structure.”
SCAFFOLD: Stochastic Controlled Averaging for On-Device Federated Learning (2019, background): “…et al., 2018; Karimireddy et al., 2019; Basu et al., 2019), the study of lower bounds for parallel stochastic optimization with a dependency graph (Woodworth et al., 2018b), devising eﬃcient distributed optimization methods beneﬁting from diﬀerential privacy guarantees (Agarwal et al., 2018),…”
On the Convergence of FedAvg on Non-IID Data (2019, background): “The prior work [35, 41, 28, 30, 33] assumes the data are iid generated by or partitioned among the N devices, that is, D k = D for all k ∈ [ N ] .”
Fair Resource Allocation in Federated Learning (2019, background): “, compared to traditional distributed (stochastic) gradient descent, which would simply calculate a subset of the gradients (Stich, 2019; Wang & Joshi, 2018; Woodworth et al., 2018; Yu et al., 2019).”
Semi-Cyclic Stochastic Gradient Descent (2019, methodology): “The main observation is that each vector v2k+i is only revealed after w includes a component in direction v2k+i–1 (more formally: it is not revealed if w ∈ span{v1, . . . , v2k+i–2}), and only when f (w, i) is queried (Woodworth et al., 2018, Lemma 9).”
Agnostic Federated Learning (2019, methodology): “…2017), devising efﬁcient distributed optimization methods beneﬁting from differential privacy guarantees (Agarwal, Suresh, Yu, Kumar, and McMahan, 2018), as well as recent guarantees for parallel stochastic optimization with a dependency graph (Woodworth, Wang, Smith, McMahan, and Srebro, 2018).”
Local SGD Converges Fast and Communicates Little (2018, background): “[41] provided a lower bound for parallel stochastic optimization (in the convex setting, and not for strongly convex functions as considered here).”
Federated Learning: Challenges, Methods, and Future Directions (2019, neutral): “setting [68, 93, 104, 108, 120, 121, 122, 125, 136, 140].”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, background): “In fact, currently the best known lower bound for the oracle complexity of local SGD is Ω̃ ( σ2 µǫ + K √ L µ ) by (Woodworth et al., 2018).”
Lower Bounds and Optimal Algorithms for Personalized Federated Learning (2020, background): “1 can be omitted by choosing the worst-case objective adversarially based on the algorithm decisions [36, 51, 52].”
SCAFFOLD: Stochastic Controlled Averaging for Federated Learning (2019, background): “…efﬁcient communication strategies (Koneˇcn`y et al., 2016b;a; Suresh et al., 2017; Stich et al., 2018; Karimireddy et al., 2019; Basu et al., 2019), the study of lower bounds (Woodworth et al., 2018), differential privacy guarantees (Agarwal et al., 2018), security (Bonawitz et al., 2017), etc.”
Think Locally, Act Globally: Federated Learning with Local and Global Representations (2020, background): “Differential privacy has also been integrated with deep learning [1], distributed learning [2, 79, 7, 18, 35], and federated learning [29, 73, 28].”