{'fraction_non_alphanumeric': 0.052763873074526825, 'fraction_numerical': 0.012997615313554043, 'mean_word_length': 3.913754882297055, 'pattern_counts': {'":': 0, '<': 44, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 50, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization

We suggest a general oracle-based framework that captures different parallel stochastic optimization 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 for 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.


Introduction
Recently, there has been great interest in stochastic optimization and learning algorithms that leverage parallelism, including e.g. delayed updates arising from pipelining and asynchronous concurrent processing; synchronous singleinstruction-multiple-data parallelism; and parallelism across distant devices. With the abundance of parallelization settings and associated algorithms, it is important to precisely formulate the problem, which allows us to ask questions such as "is there a better method for this problem than what we have?" and "what is the best we could possibly expect?" Oracle models have long been a useful framework for formalizing stochastic optimization and learning problems. In an oracle model, we place limits on the algorithm's access to the optimization objective, but not what it may do with the information it receives. This allows us to obtain sharp lower bounds, which can be used to argue that an algorithm is optimal and to identify gaps between current algorithms and what might be possible. Finding such gaps can be very useful-for example, the gap between the first order optimization lower bound of Nemirovski et al. [20] and the best known algorithms at the time inspired Nesterov's accelerated gradient descent algorithm [21].
We propose an oracle framework for formalizing different parallel optimization problems. We specify the structure of parallel computation using a dependency graph which indicates how an algorithm accesses the oracle. Each node in the graph corresponds to a single stochastic oracle query, and that query (e.g. the point at which a gradient is calculated) must be computed using only oracle accesses in ancestors of the node. We generally think of each stochastic oracle access as being based on a single data sample, thus involving one or maybe a small number of vector operations.
In Section 3 we devise generic lower bounds for parallel optimization problems in terms of simple properties of the associated dependency graph, namely the length of the longest dependency chain and the total number of nodes. In Section 4 we study specific parallel optimization settings in which many algorithms have been proposed, formulate them as graph-based oracle parallel optimization problems, instantiate our lower bounds, and compare them with the performance guarantees of specific algorithms. We highlight gaps between the lower bound and the best known upper bound and also situations where we can devise an optimal algorithm that matches the lower bound, but where this is not the "natural" and typical algorithm used in this settings. The latter indicates either a gap in our understanding of the "natural" algorithm or a need to depart from it.
Previously suggested models Previous work studied communication lower bounds for parallel convex optimization where there are M machines each containing a local function (e.g. a collection of samples from a distribution). Each machine can perform computation on its own function, and then periodically every machine is allowed to transmit information to the others. In order to prove meaningful lower bounds based on the number of rounds of communication, it is necessary to prevent the machines from simply transmitting their local function to a central machine, or else any objective could be optimized in one round. There are two established ways of doing this. First, one can allow arbitrary computation on the local machines, but restrict the number of bits that can be transmitted in each round. There is work focusing on specific statistical estimation problems that establishes communication lower bounds via information-theoretic arguments [8,12,28]. Alternatively, one can allow the machines to communicate real-valued vectors, but restrict the types of computation they are allowed to perform. For instance, Arjevani and Shamir [3] present communication complexity lower bounds for algorithms which can only compute vectors that lie in a certain subspace, which includes e.g. linear combinations of gradients of their local function. Lee et al.
[15] assume a similar restriction, but allow the data defining the local functions to be allocated to the different machines in a strategic manner. Our framework applies to general stochastic optimization problems and does not impose any restrictions on what computation the algorithm may perform, and is thus a more direct generalization of the oracle model of optimization.

The graph-based oracle model
We consider the following stochastic optimization problem (1) The problem (1) captures many important tasks, such as supervised learning, in which case f (x; z) is the loss of a model parametrized by x on data instance z and the goal is to minimize the population risk E [f (x; z)]. We assume that f (·; z) is convex, L-Lipschitz, and H-smooth for all z. We also allow f to be non-smooth, which corresponds to H = ∞. A function g is L-Lipschitz when g(x) − g(y) ≤ L x − y for all x, y, and it is H-smooth when it is differentiable and its gradient is H-Lipschitz. We consider optimization algorithms that use either a stochastic gradient or stochastic prox oracle (O grad and O prox respectively): O grad (x, z) = (f (x; z), ∇f (x; z)) (2) where prox f (·;z) (x, β) = arg min The prox oracle is quite powerful and provides global rather than local information about f . In particular, querying the prox oracle with β = 0 fully optimizes f (·; z).
As stated, z is an argument to the oracle, however there are two distinct cases. In the standard stochastic oracle setting, the algorithm receives an oracle answer corresponding to a random and unknown z ∼ P. We also consider a setting in which the algorithm is allowed to "actively query" the oracle. In this case, the algorithm may either sample z ∼ P or choose a desired z and receive an oracle answer for that z. Our lower bounds hold for either type of oracle. Most optimization algorithms only use the fully stochastic oracle, but some require more powerful active queries.
We capture the structure of a parallel optimization algorithm with a directed, acyclic dependency graph G. Its depth, D, is the length of the longest directed path, and the size, N , is the number of nodes. Each node in the graph represents a single stochastic oracle access, and the edges in the graph indicate where the results of that oracle access may be used: only the oracle accesses from ancestors of each node are available when issuing a new query. These limitations might arise e.g. due to parallel computation delays or the expense of communicating between disparate machines.
Let Q be the set of possible oracle queries, with the exact form of queries (e.g., q = x vs. q = (x, β, z)) implied by the setting. Formally, a randomized optimization algorithm that accesses the stochastic oracle O as prescribed by the graph G is specified by associating with each node v t a query rule R t : (Q, O(Q)) * × Ξ → Q, plus a single output ruleX : (Q, O(Q)) * × Ξ → X . We grant all of the nodes access to a source of shared randomness ξ ∈ Ξ (e.g. an infinite stream of random bits). The mapping R t selects a query q t to make at node v t using the set of queries and oracle responses in ancestors of v t , namely Similarly, the output ruleX maps from all of the queries and oracle responses to the algorithm's output asx = The essential question is: for a class of optimization problems (G, O, F) specified by a dependency graph G, a stochastic oracle O, and a function class F, what is the best possible guarantee on the expected suboptimality of an algorithm's output, i.e.
In this paper, we consider optimization problems (G, O, F L,H,B ) where F L,H,B is the class of convex, L-Lipschitz, and H-smooth functions on the domain {x ∈ R m : x ≤ B} and parametrized by z, and O is either a stochastic gradient oracle O grad (2) or a stochastic prox oracle O prox (3). We consider this function class to contain Lipschitz but non-smooth functions too, which corresponds to H = ∞. Our function class does not bound the dimension m of the problem, as we seek to understand the best possible guarantees in terms of Lipschitz and smoothness constants that hold in any dimension. Indeed, there are (typically impractical) algorithms such as center-of-mass methods [7], which might use the dimension in order to significantly reduce the oracle complexity, but at a potentially huge computational cost. Nemirovski [19] studied non-smooth optimization in the case that the dimension is bounded, proving lower bounds in this setting that scale with the 1/3-power of the dimension but have only logarithmic dependence on the suboptimality. We do not analyze strongly convex functions, but the situation is similar and lower bounds can be established via reduction [27].

Lower bounds
These are the tightest possible lower bounds in terms of D and N in the sense that for all D, N there are graphs G and associated algorithms which match the lower bound. Of course, for specific, mostly degenerate graphs they might not be tight. For instance, our lower bound for the graph consisting of a short sequential chain plus a very large number of disconnected nodes might be quite loose due to the artificial inflation of N . Nevertheless, for many interesting graphs they are tight, as we shall see in Section 4.
Each lower bound has two components: an "optimization" term and a "statistical" term. The statistical term Ω(LB/ √ N ) is well known, although we include a proof of this portion of the bound in Appendix D for completeness. The optimization term depends on the depth D, and indicates, intuitively, the best suboptimality guarantee that can be achieved by an algorithm using unlimited parallelism but only D rounds of communication. Arjevani and Shamir [3] also obtain lower bounds in terms of rounds of communication, which are similar to how our lower bounds depend on depth. However they restricted the type of computations that are allowed to the algorithm to a specific class of operations, while we only limit the number of oracle queries and the dependency structure between them, but allow forming the queries in any arbitrary way.
Similar to Arjevani and Shamir [3], to establish the optimization term in the lower bounds, we construct functions that require multiple rounds of sequential oracle accesses to optimize. In the gradient case, we use a single, deterministic function which resembles a standard construction for first order optimization lower bounds. For the prox case, we construct two functions inspired by previous lower bounds for round-based and finite sum optimization [3,27]. In order to account for randomized algorithms that might leave the span of gradients or proxs returned by the oracle, we use a technique that was proposed by Woodworth and Srebro [26,27] and refined by Carmon et al. [9]; this portion of the analysis is detailed in Appendix A.
Our lower bounds also have a novel technical element, which is that they apply when both the Lipschitz constant and smoothness are bounded concurrently. Consequently, "non-smooth" in the subsequent discussion can be read as simply identifying the case where the L term achieves the minimum as opposed to the H term (even if H < ∞). This is particularly important in for studying stochastic parallel optimization, since obtaining non-trivial guarantees in a purely stochastic setting requires some sort of control on the magnitude of the gradients (smoothness by itself is not sufficient), while obtaining parallelization speedups often requires smoothness, and so we would like to ask what is the best that can be done when both Lipschitz and smoothness are controlled. Interestingly, the dependence on both L and H in our bounds is tight, even when the other is constrained, which shows that the optimization term cannot be substantially reduced by using both conditions together.
In order to be handle Lipschitz and smoothness concurrently, we use only a single construction to handle both smooth and non-smooth objectives. In contrast, previous lower bounds typically treat Lipschitz functions and smooth functions separately, constructing Lipschitz functions that are not at all smooth and vice versa. Our unified construction is thus also simpler in a way (one construction instead of two), and might be of independent interest more broadly.
In the case of the gradient oracle, we "smooth out" a standard non-smooth lower bound construction-this is similar to the approach taken by Agarwal and Hazan [2] when studying higher order oracle complexities. For ≤ L and η ≤ H, and orthonormal v 1 , . . . , v D+1 drawn uniformly at random, we define the -Lipschitz but non-smooth functionf , and its -Lipschitz, η-smooth "η-Moreau envelope" [5]: This defines a distribution over f 's based on the randomness in the draw of v 1 , . . . , v D+1 , and we apply Yao's minimax principle. In Appendix B, we prove Theorem 1 using this construction.
In the case of the prox oracle, we "straighten out" the smooth construction of Woodworth and Srebro [27]. For, fixed constants c, γ, we define the following Lipschitz and smooth scalar function φ c :

Graph example
With gradient oracle With gradient and prox oracle path(T ) (Section 4.1) For P = Uniform {1, 2} and orthonormal v 1 , . . . , v 2D drawn uniformly at random, we define Again, this defines a distribution over f 's based on the randomness in the draw of v 1 , . . . , v 2D and we apply Yao's minimax principle. In Appendix C, we prove Theorem 2 using this construction.

Specific dependency graphs
We now use our framework to study four specific parallelization structures. The main results (tight complexities and gaps between lower and upper bounds) are summarized in Table 1. For simplicity and without loss of generality, we set B = 1, i.e. we normalize the optimization domain to be {x ∈ R m : x ≤ 1}. All stated upper and lower bounds are for the expected suboptimality E[F (x)] − F (x * ) of the algorithm's output.

Sequential computation: the path graph
We begin with the simplest model, that of sequential computation captured by the path graph of length T depicted above. The ancestors of each vertex v i , i = 1 . . . T are all the preceding vertices (v 1 , . . . , v i−1 ). The sequential model is of course well studied and understood. To see how it fits into our framework: A path graph of length T has a depth of D = T and size of N = T , thus with either gradient or prox oracles, the statistical term is dominant in Theorems 1 and 2. These lower bounds are matched by sequential stochastic gradient descent, yielding a tight complexity of Θ(L/ √ T ) and the familiar conclusion that SGD is (worst case) optimal in this setting.

Simple parallelism: the layer graph
We now turn to a model in which M oracle queries can be made in parallel, and the results are broadcast for use in making the next batch of M queries. This corresponds to synchronized parallelism and fast communication between processors. The model is captured by a layer graph of width M , depicted above for M = 3. The graph consists of T layers i = t, . . . , T each with M nodes v t,1 , . . . , v t,m whose ancestors include v t ,i for all t < t and i ∈ [M ]. The graph has a depth of D = T and size of N = M T . With a stochastic gradient oracle, Theorem 1 yields a lower bound of: which is matched by accelerated mini-batch SGD (A-MB-SGD) [10, 14], establishing the optimality of A-MB-SGD in this setting. For sufficiently smooth objectives, the same algorithm is also optimal even if prox access is allowed, since Theorem 2 implies a lower bound of: That is, for smooth objectives, having access to a prox oracle does not improve the optimal complexity over just using gradient access. However, for non-smooth or insufficiently smooth objectives, there is a gap between (11) and (12). An optimal algorithm, smoothed A-MB-SGD, uses the prox oracle in order to calculate gradients of the Moreau envelope of f (x; z) (cf. Proposition 12.29 of [5]), and then performs A-MB-SGD on the smoothed objectives. This yields a suboptimality guarantee that precisely matches (12), establishing that the lower bound from Theorem (2) is tight for the layer graph, and that smoothed A-MB-SGD is optimal. An analysis of the smoothed A-MB-SGD algorithm is provided in Appendix E.1.

Delayed updates
We now turn to a delayed computation model that is typical in many asynchronous parallelization and pipelined computation settings, e.g. when multiple processors or machines are working asynchronously, reading iterates, taking some time to perform the oracle accesses and computation, then communicating the results back (or updating the iterate accordingly) [1, 6, 16, 18, 24]. This is captured by a "delay graph" with T nodes v 1 , . . . , v T and delays τ t for the response to the oracle query performed at v t to become available. Hence, Ancestors(v t ) = {v s | s + τ s ≤ t}. Analysis is typically based on the delays being bounded, i.e. τ t ≤ τ for all t. The depiction above corresponds to τ t = 2, and τ t = 1 is simply the path graph. With constant delays τ t = τ , the delay graph has depth D ≤ T /τ and size N = T , so Theorem 1 gives the following lower bound when using a gradient oracle: , is a natural algorithm in this setting. Under the bounded delay assumption the best guarantee we are aware of for delayed update SGD is (see [11] improving over [1]) This result is significantly worse than the lower bound 13 and quite disappointing. It does not provide for a 1/T 2 accelerated optimization rate, but even worse, compared to non-accelerated SGD it suffers a slowdown quadratic in the delay, compared to the linear slowdown we would expect. In particular, the guarantee (14) only allows maximum delay of τ = O(T 1/4 ) in order to attain the optimal statistical rate Θ(L/ √ T ), whereas the lower bound allows a delay up to This raises the question of whether a different algorithm can match the lower bound (13). The answer is affirmative, but it requires using an "unnatural" algorithm, which simulates a mini-batch approach in what seems an unnecessarily wasteful way. We refer to this as a "wait-and-collect" approach: it works in T /(2τ ) stages, each stage consisting of 2τ iterations (i.e. nodes or oracle accesses). In stage i, τ iterations are used to obtain τ stochastic gradient estimates ∇f (x i ; z 2τ i+j ), j = 1..τ at the same point x i . For the remaining τ iterations, we wait for all the preceding oracle computations to become available and do not even use our allowed oracle access. We can then finally update the x i+1 using the minibatch of τ gradient estimates. This approach is also specified formally as Algorithm 2 in Appendix E.2. Using this approach, we can perform T /(2τ ) A-MB-SGD updates with a minibatch size of τ , yielding a suboptimality guarantee that precisely matches the lower bound (13).
Thus (13) indeed represents the tight complexity of the delay graph with a stochastic gradient oracle, and the wait-andcollect approach is optimal. However, this answer is somewhat disappointing and leaves an intriguing open question: can a more natural, and seemingly more efficient (no wasted oracle accesses) delayed update SGD algorithm also match the lower bound? An answer to this question has two parts: first, does the delayed update SGD truly suffer from a τ 2 slowdown as indicated by (14), or does it achieve linear degradation and a speculative guarantee of Second, can delayed update SGD be accelerated to achieve the optimal rate (13). We note that concurrent with our work there has been progress toward closing this gap: Arjevani et al.
[4] showed an improved bound matching the non-accelerated (15) for delayed updates (with a fixed delay) on quadratic objectives. It still remains to generalize the result to smooth non-quadratic objectives, handle non-constant bounded delays, and accelerate the procedure so as to improve the rate to (τ /T ) 2 .

Intermittent communication
We now turn to a parallel computation model which is relevant especially when parallelizing across disparate machines: in each of T iterations, there are M machines that, instead of just a single oracle access, perform K sequential oracle accesses before broadcasting to all other machines synchronously. This communication pattern is relevant in the realistic scenario where local computation is plentiful relative to communication costs (i.e. K is large). This may be the case with fast processors distributed across different machines, or in the setting of federated learning, where mobile devices collaborate to train a shared model while keeping their respective training datasets local [17]. This is captured by a graph consisting of M parallel chains of length T K, with cross connections between the chains every K nodes. Indexing the nodes as v t,m,k , the nodes v t,m,1 → · · · → v t,m,K form a chain, and v t,m,K is connected to v t+1,m ,1 for all m = 1..M . This graph generalizes the layer graph by allowing K sequential oracle queries between each complete synchronization; K = 1 recovers the layer graph, and the depiction above corresponds to K = M = 3. We refer to the computation between each synchronization step as a (communication) round.
The depth of this graph is D = T K and the size is N = T KM . Focusing on the stochastic gradient oracle (the situation is similar for the prox oracle, except with the potential of smoothing a non-smooth objective, as discussed in Section 4.2), Theorem 1 yields the lower bound: A natural algorithm for this graph is parallel SGD, where we run an SGD chain on each machine and average iterates during communication rounds, e.g.
[17]. The updates are then given by: (note that x t,m,0 does not correspond to any node in the graph, and is included for convenience of presentation). Unfortunately, we are not aware of any satisfying analysis of such a parallel SGD approach Instead, we consider two other algorithms in an attempt to match the lower bound (16). First, we can combine all KM oracle accesses between communication rounds in order to form a single mini-batch, giving up on the possibility of sequential computation along the "local" K node sub-paths. Using all KM nodes to obtain stochastic gradient estimates at the same point, we can perform T iterations of A-MB-SGD with a mini-batch size of KM , yielding an upper bound of This is a reasonable and common approach, and it is optimal (up to constant factors) when KM = O( L 2 H 2 T 3 ) so that the statistical term is limiting. However, comparing (18) to the lower bound (16) we see a gap by a factor of K 2 in the optimization term, indicating the possibility for significant gains when K is large (i.e. when we can process a large number of examples on each machine at each round). Improving the optimization term by this K 2 factor would allow statistical optimality as long as M = O(T 3 K 3 )--this is a very significant difference. In many scenarios we would expect a modest number of machines, but the amount of data on each machine could easily be much more than the number of communication rounds, especially if communication is across a wide area network.
In fact, when K is large, a different approach is preferable: we can ignore all but a single chain and simply execute KT iterations of sequential SGD, offering an upper bound of Although this approach seems extremely wasteful, it actually yields a better guarantee than (18) when K ≥ Ω(T 3 L 2 /H). This is a realistic regime, e.g. in federated learning when computation is distributed across devices, communication is limited and sporadic and so only a relatively small number of rounds T are possible, but each device already posses a large amount of data. Furthermore, for non-smooth functions, (19) matches the lower bound (16).
Our upper bound on the complexity is therefore obtained by selecting either A-MB-SGD or single-machine sequential SGD, yielding a combined upper bound of For smooth functions, there is still a significant gap between this upper bound and the lower bound (16). Furthermore, this upper bound is not achieved by a single algorithm, but rather a combination of two separate algorithms, covering two different regimes. This raises the question of whether there is a single, natural algorithm, perhaps an accelerated variant of the parallel SGD updates (17), that at the very least matches (20), and preferably also improves over them in the intermediate regime or even matches the lower bound (16).
Active querying and SVRG All methods discussed so far used fully stochastic oracles, requesting a gradient (or prox computation) with respect to an independently and randomly drawn z ∼ P. We now turn to methods that also make active queries, i.e. draw samples from P and then repeatedly query the oracle, at different points x, but on the same samples z. Recall that all of our lower bounds are valid also in this setting.
With an active query gradient oracle, we can implement SVRG [13, 15] on an intermittent communication graph. More specifically, for an appropriate choice of n and λ, we apply SVRG to the regularized empirical objective: To do so, we first pick a sample {z 1 , . . . z n } (without actually querying the oracle). As indicated by Algorithm 1, we then alternate between computing full gradients on {z 1 , . . . z n } in parallel ( * ), and sequential variance-reduced Algorithm 1 SVRG Parameters: n, S, I Sample z 1 , . . . , z n ∼ P Initialize x 0 = 0 . . , I} end for Return x S stochastic gradient updates in between ( * * ). The full gradientg is computed using n active queries to the gradient oracle. Since all of these oracle accesses are made at the same pointx, this can be fully parallelized across the M parallel chains of length K thus requiring n/KM rounds. The sequential variance-reduced stochastic gradient updates cannot be parallelized in this way, and must be performed using queries to the gradient oracle in just one of the M available parallel chains, requiring I/K rounds of synchronization. Consequently, each outer iteration of SVRG requires n KM + I K rounds. We analyze this method using λ = Θ L These guarantees improve over sequential SGD (17) as soon as M > log 2 (T KM/L) and K > H 2 /L 2 , i.e. L/ √ T K < L 2 /H. This is a very wide regime: we require only a moderate number of machines, and the second condition will typically hold for a smooth loss. Intuitively, SVRG does roughly the same number (up to a factor of two) of sequential updates as in the sequential SGD approach but it uses better, variance reduced updates. The price we pay is in the smaller total sample size since we keep calling the oracle on the same samples. Nevertheless, since SVRG only needs to calculate the "batch" gradient a logarithmic number of times, this incurs only an additional logarithmic factor.
Comparing (18) and (22), we see that SVRG also improves over A-MB-SGD as soon as K > T log(T KM/L), that is if the number of points we are processing on each machine each round is slightly more then the total number of rounds, which is also a realistic scenario.
To summarize, the best known upper bound for optimizing with intermittent communication using a pure stochastic oracle is (20), which combines two different algorithms. However, with active oracle accesses, SVRG is also possible and the upper bound becomes:

Summary
Our main contributions in this paper are: (1) presenting a precise formal oracle framework for studying parallel stochastic optimization; (2) establishing tight oracle lower bounds in this framework that can then be easily applied to particular instances of parallel optimization; and (3) using the framework to study specific settings, obtaining optimality guarantees, understanding where additional assumptions would be needed to break barriers, and, perhaps most importantly, identifying gaps in our understanding that highlight possibilities for algorithmic improvement.
Specifically, we highlight the following gaps: • For non-smooth objectives and a stochastic prox oracle, it is possible to improve performance in the layer graph setting using smoothing and acceleration. It is not clear whether one can match the same optimal performance using a more direct algorithm, e.g. one that averages the answers from the prox oracle.
• In the delay graph setting, delayed update SGD's guarantee is not optimal. We suggest an alternative optimal algorithm, but it would be interesting and beneficial to understand the true behavior of delayed update SGD and to improve it as necessary to attain optimality.
• With intermittent communication, we show how different methods are better in different regimes, but even combining these methods does not match our lower bound. This sets the stage for studying the optimal complexity in this setting: is our lower bound achievable? Are current methods optimal? Is the true optimal complexity somewhere in between? Even just obtaining a single method that matches the current best performance in all regimes would be a significant advance here.
• With intermittent communication, active queries allow us to obtain better performance in a certain regime. Can we match this performance using pure stochastic queries or is there a real gap between active and pure stochastic queries?
The investigation into optimizing over F L,H,B in our framework indicates that there is no advantage to the prox oracle for optimizing (sufficiently) smooth functions. This raises the question of what additional assumptions might allow us to leverage the prox oracle, which is intuitively much stronger as it allows global access to f (·; z). One option is to assume a bound on the variance of the stochastic oracle i.e. E z [ ∇f (x; z) − ∇F (x) 2 ] ≤ σ 2 which captures the notion that the functions f (·; z) are somehow related and not arbitrarily different. In particular, if each stochastic oracle access, in each node, is based on a sample of b data points (thus, a prox operation optimizes a sub-problem of size b), we have that σ 2 ≤ L 2 /b. Initial investigation into the complexity of optimizing over the restricted class F L,H,B,σ (where we also require the above variance bound), reveals a significant theoretical advantage for the prox oracle over the gradient oracle, even for smooth functions. This is an example of how formalizing the optimization problem gives insight into additional assumptions, in this case low variance, that are necessary for realizing the benefits of a stronger oracle.
[3] Yossi Arjevani and Ohad Shamir. Communication complexity of distributed convex learning and optimization. In Advances in Neural Information Processing Systems, pages 1756-1764, 2015.
[8] Mark Braverman, Ankit Garg, Tengyu Ma, Huy L Nguyen, and David P Woodruff. Communication lower bounds for statistical estimation problems via a distributed data processing inequality. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 1011-1020. ACM, 2016.

A Main lower bound lemma
This analysis closely follows that of previous work, specifically the proof of Theorem 1 in [26] and the proof of Lemma 4 in [9]. There are slight differences in the problem setup between this work and that of previous papers, thus we include the following analysis for completeness and to ensure that all of our results can be verified. We do not claim any technical novelty within this section.
Let V = {v 1 , . . . , v k } be a uniformly random orthonormal set of vectors in R m . All of the probabilities referred to in Appendix A will be over the randomness in the selection of V . Let X = {x 1 , x 2 , . . . , x N } be a set of vectors in R m where x i ≤ 1 for all i ≤ N . Let these vectors be organized into disjoint subsets X 1 ∪ X 2 ∪ · · · ∪ X k = X. Furthermore, suppose that for each t ≤ k, the set X t is a deterministic function X t = X t (X <t , V ), so it can also be expressed as X t = X t (V ).
Let S t = X ≤t ∪ V ≤t , let P t be the projection operator onto the span of S t and let P ⊥ t be the projection onto the orthogonal complement of the span of S t . As in [9, 26], define Finally, suppose that for each t, X t is of the form: i.e. conditioned on the event G <t , it is a deterministic function of V <t only (and not v t , ..., v k ). We say that P [G <1 ] = 1, so X 1 is always independent of V .
First, we connect the events G t to a more immediately useful condition The proof of Lemma 1 involves straightforward linear algebra, and we defer it to Appendix A.1. By Lemma 1, G <t ⊆ G <t , therefore the property (25) is implied by Now, we state the main result which allows us to prove our lower bounds: Lemma 2. [cf. Lemma 4 [9], Lemma 4 [26]] For any k ≥ 1, N ≥ 1, c ∈ (0, 1), and dimension if the sets X 1 , . . . , X k satisfy the property (26) then The proof of Lemma 2 relies upon the following, whose proof we defer to Appendix A.1.
Lemma 3. [cf. Lemma 11 [9], Lemma 3 [26]] Let R be any rotation operator, R R = I, that preserves S t−1 , that is Rw = R w = w for any w ∈ Span (S t−1 ). Then the following conditional densities are equal Proof of Lemma 2. This closely follows the proof of Lemma 4 [9] and Lemma 4 [26], with small modifications to account for the different setting.
. Then by Lemma 1, since X 1 , . . . , X k satisfy the property (26) Focus on a single term in this product, For any particular V <t , Conditioned on G <t and V <t , the set X t = X t (V <t ) is fixed, as is the set S t−1 and therefore P ⊥ t−1 , so the first term in the inner product is a fixed unit vector. By Lemma 3, the conditional density of v j | G <t , V <t is spherically symmetric within the span onto which P ⊥ t−1 projects. Therefore, The probability of a fixed vector and a uniform random vector on the unit sphere in R m having inner product more than α is proportional to the surface area of the "end caps" of the sphere lying above and below circles of radius √ 1 − α 2 , which is strictly smaller than the surface area of a full sphere of radius √ 1 − α 2 . Therefore, for a given x, v j P where we used that 1 − x ≤ exp(−x). Finally, this holds for each t, x ∈ X t , and j ≥ t, so Where we used that m ≥ k + N + max 32N 2 , 8(1+ √ 2N ) 2 c 2 log 2k 2 N for (37). For (38), recall that we chose A.
Proof. This closely follows the proof of Lemma 9 [9], with slight modification to account for the different problem setup.
For t ≤ k assume G ≤t . For any x ∈ X t and j ≥ t First, we decomposed v j into its S t−1 and S ⊥ t−1 components and applied the triangle inequality. Next we used that x ≤ 1 and that the orthogonal projection operator P ⊥ t−1 is self-adjoint. Finally, we used that the projection operator is non-expansive and the definition of G t . Next, we prove by induction on t that for all t ≤ k and j ≥ t, the event G ≤t implies that P t−1 v j 2 ≤ 2α 2 t−1 r=1 |X r |. As a base case (t = 1), observe that, trivially, P t−1 v j 2 = 0v j 2 = 0. For the inductive step, fix any t ≤ k and j ≥ t and suppose that G ≤t =⇒ P t −1 v j 2 ≤ 2α 2 t −1 r=1 |X r | for all t < t and j ≥ t . LetP t project onto Span (S t ∪ X t+1 ) (this includes X t+1 in contrast with P t ) and letP ⊥ t project onto the orthogonal subspace. Since Span (X 1 ∪ X 2 ∪ · · · ∪ X t−1 ∪ V ≤t−1 ) = S t−1 , is a (potentially over-complete) basis for S t−1 . Using the triangle inequality and G <t , we can therefore expand We must now bound the second term of (45). Focusing on the inner product in the numerator for one particular r < t: First, we used thatP ⊥ r−1 = I −P r−1 , then that v r ⊥ v j . Next, we applied the definition ofP r−1 and the triangle inequality. To get (49) we use the Cauchy-Schwarz inequality on the first term, and the definition of G r for the second. Finally, we use the inductive hypothesis and that α ≤ 1 4N . We have now upper bounded the inner products in the second term of (45), and it remains to lower bound the norm in the denominator. We can rewrite Here we again usedP ⊥ r−1 = I −P r−1 followed by an (over)expansion ofP r−1 . The remaining steps follow from the inductive hypothesis and fact that α ≤ 1 4N . Combining (57) with (51) and returning to (45), we have that Therefore, for each t ≤ k and j ≥ t an upper bound P t−1 v j 2 ≤ 2α 2 t−1 r=1 |X r |. Returning now to (42), we have that for any t ≤ k, x ∈ X t , and j ≥ t the event G ≤t implies Lemma 3. [cf. Lemma 11 [9], Lemma 3 [26]] Let R be any rotation operator, R R = I, that preserves S t−1 , that is Rw = R w = w for any w ∈ Span (S t−1 ). Then the following conditional densities are equal Proof. This closely follows the proof of Lemma 11 [9].
First, we apply Bayes' rule to each density and use the fact that RV <t = V <t : Since V has a spherically symmetric marginal distribution, p(V ) = p(RV ). Therefore, it only remains to show that The event G <t is determined by V or by RV , thus both probabilities are either 0 or 1, so it suffices to show P [G <t | V ] = 1 ⇐⇒ P [G <t | RV ] = 1.
Assume first P [G <t | V ] = 1. Then for each r < t, x ∈ X r , and j ≥ r P ⊥ r−1 x P ⊥ r−1 x , v j ≤ α, and each set X r is a deterministic function of V <r . Also, observe that for any x ∈ X r and j ≥ r, where we used that P ⊥ r−1 x ∈ Span(S r ) ⊆ Span(S t−1 ) so R P ⊥ r−1 x = P ⊥ r−1 x. Therefore, it suffices to show that the sequence X 1 (RV ), ..., X t (RV ) = X 1 (V ), ..., X t (V ) when P [G <t | V ] = 1. We prove this by induction.
For the base case, by definition X 1 (RV ) = X 1 = X 1 (V ). For the inductive step, suppose now that X r (RV ) = X r (V ) for each r < r. This, plus the fact that P [G <t | V ] = 1 =⇒ P [G <r | V ] = 1 together imply that P [G <r | RV ] = 1. Thus, X r (RV ) = X r (RV <r ) = X r (V <r ). Therefore, we conclude that P [G <t | V ] = 1 =⇒ P [G <t | RV ] = 1, the reverse implication can be proven with a similar argument. and consider the following -Lipschitz function: where the vectors v 1 , . . . , v D+1 are an orthonormal set drawn uniformly at random from the unit sphere in R m . We use the η-Moreau envelope [5] of this function in order to prove our lower bound: The random draw of V defines a distribution over functions f . We will lower bound the expected suboptimality of any deterministic optimization algorithm's output and apply Yao's minimax principle at the end of the proof.
This function has the following properties: Lemma 4. The function f is convex, -Lipschitz, and η-smooth, with ≤ L and η ≤ H.
Furthermore, optimizing f is equivalent to "finding" the vectors v 1 , . . . , v D+1 . In particular, until a point that has a substantial inner product with all of v 1 , . . . , v D+1 is found, the algorithm will remain far from the minimum: Lemma 5. For any H, L > 0, D ≥ 1, and orthonormal v 1 , ..., v D+1 , for any The function also has the property that if x has a small inner product with v t , . . . , v D+1 , then the gradient oracle will reveal little information about f when queried at x: Lemma 6. For any x with | x, v r | ≤ η for all r ≥ t, both the function value f (x) and gradient ∇f (x) can be calculated from v 1 , . . . , v t only.
In Appendix A, we studied the situation where orthonormal v 1 , . . . , v D+1 are chosen uniformly at random and a sequence of sets of vectors X 1 , . . . , X D+1 are generated as Take c = 2 η and consider the dependency graph. Let X 1 be the set of queries made in vertices at depth 1 in the graph (i.e. they have no parents). Let X 2 be the set of queries made in vertices at depth 2 in the graph (i.e. their parents correspond to the queries in X 1 ). Continue in this way for each t ≤ D, and let X D+1 = {x} correpond to the algorithm's output, which is allowed to depend on all queries and oracle responses in the graph, and thus has depth D + 1.
Supposing G <t , for all queries x ∈ X 1 ∪ · · · ∪ X t−1 and for all r ≥ t − 1 we have | x, v r | ≤ c 2 = η . Therefore, by Lemma 6 all of the function evaluations and gradients returned by the stochastic gradient oracle are calculable from v 1 , . . . , v t−1 only. Therefore, all of the queries in X t are a deterministic function of V <t (since we are currently considering only deterministic optimization algorithms), so X t satisfies the required decomposition property (70). Finally, the queries are required to be in the domain of f , thus they will have norm bounded by 1.
Proof. Sincef is the maximum of -Lipschitz affine functions, it is convex and -Lipschitz. Furthermore, by Proposition 12.29 [5], f , the η-Moreau Envelope off is η-smooth and The minimizing y satisfies that η(x − y) ∈ ∂f (y) (where ∂f (y) denotes the set of subgradients off at y), and sincef is -Lipschitz this implies that ∇f (x) ≤ .
Proof. Without loss of generality, assume B = 1, the lower bound can be proven for other values of B by scaling inputs to our construction by 1/B. Let Define the following scalar function It is straightforward to confirm that φ c is convex, 2γ-Lipschitz continuous, and 4-smooth. Let P be the uniform distribution over {1, 2}. Let v 1 , v 2 , . . . , v 2D be a set of orthonormal vectors drawn uniformly at random and define The random choice of V determines a distribution over functions f (·; 1) and f (·; 2). We will lower bound the expectation (over V ) of the suboptimality of any deterministic algorithm's output, and then apply Yao's minimax principle.
In Appendix A, we studied the situation where orthonormal v 1 , . . . , v 2D are chosen uniformly at random and a sequence of sets of vectors X 1 , . . . , X 2D are generated as Consider the dependency graph, and let X 1 be the set of queries made in vertices at depth 1 in the graph (i.e. they have no parents). Let X 2 be the set of queries made in vertices at depth 2 in the graph (i.e. their parents correspond to the queries in X 1 ). Continue in this way for each t ≤ D, and then let X D+1 = {x} correpond to the output of the optimization algorithm, which for now is deterministic.
Suppose G <t . Then for all of the queries x ∈ X 1 ∪ · · · ∪ X t−1 and for all r ≥ t − 1 we have | x, v r | ≤ c 2 . Therefore, by Lemma 9 the function values, gradients, and proxs of f (·; 1) and f (·; 2) are calculable based only on the query points and v 1 , . . . , v t−1 . Therefore, all of the queries in X t are a deterministic function of V <t only so X t satisfies the required decomposition property (99). Finally, the queries are required to be in the domain of f , thus they will have norm bounded by B.
Therefore, by Lemma 2 for with probability 1/2 for every x ∈ X 1 ∪ · · · ∪ X D+1 which includesx, | x, v r | ≤ c 2 for r > D, so by Lemma 8 Therefore, so by Yao's minimax principle, for any randomized algorithm A The statistical term LB 8 √ N follows from Lemma 10.
Lemma 8. For any H, L ≥ 0, D ≥ 1, and orthonormal v 1 , ..., v 2D , and with η, γ, a, and c chosen as in (93), for any x such that v r x ≤ c 2 for all r > D Proof. First, we upper bound min x: x ≤1 F (x). Recalling that a = 1 √ 8D 3 , define For this x * , v r−1 x * − v r x * = v 2D x * = a and with our choice of parameters (93), 2c = a < γ, so that φ c (a) = 2a, thus thus, Since x * ≤ 1 and ∇F (x * ) = 0, we conclude We will now lower bound Introducing dual variables λ D+1 , ..., λ 2D ≥ 0, solving (116) amounts to finding an x ∈ X D and a set of non-negative λs such that ∇F (x) = − 2D r=D+1 λ r sign v r x v r and such that λ r v r x − c 2 = 0 for each r. Let Since a (D + 1 − r) + c 2 < a (2D + 1 − r) for r ≤ D + 1 and x * ≤ 1 it follows that x D ≤ 1. Furthermore, since v r−1 x D − v r x D = a for 2 ≤ r ≤ D + 1 and 2c = a < γ, the gradient Therefore, Combining (115) and (122) we have that Lemma 9.
Now, we consider the proxs at such a point x. Let t = t if t is odd, and t = t − 1 if t is even. Let P be the projection operator onto S = Span (v 1 , . . . , v t ) and let P ⊥ be the projection onto the orthogonal subspace, S ⊥ . Then, since f (x; 1) = f (P x; 1) + f (P ⊥ x; 1), we can decompose the prox: prox f (·;1) (x, β) = arg min Where we used that v r P ⊥ x = v r x ≤ c 2 for all r > t , so setting y 2 = P ⊥ x achieves the minimum since every term in the expression is zero and function is non-negative. The vector P ⊥ x is calculable from x, v 1 , . . . , v t ⊆ x, v 1 , . . . , v t , and similarly the second term is a minimization depends only on β, x, v 1 , . . . , v t ⊆ β, x, v 1 , . . . , v t . A nearly identical argument shows that prox f (·;2) (x, β) has the same property. Then, let f (x; z) = zLx, so E z∼Pp [f (x; z)] = (2p − 1)Lx. When p = p 1 , (2p − 1) > 0 so the minimizer is x = −B with value −LB(2p − 1) = −LB , and when p = p −1 , (2p − 1) < 0 so the minimizer is x = B, also with value −LB . Furthermore, if p = p 1 and x ≥ 0 then it is at least LB -suboptimal, and if p = p 2 and x ≤ 0 then it is also at least LB -suboptimal. Now consider any deterministic optimization algorithm which accesses the gradient or prox oracle N times. Each gradient or prox oracle response can be simulated using a single z ∼ P p , so the algorithm's output isx =x(z 1 , . . . , z N ) ∈ [−B, B]. Consider Furthermore, the Bayes optimal estimatex of sign(2p − 1) iŝ x(z 1 , . . . , z N ) = 1 so P p∼Uniform{p1,p−1},z∼Pp sign(X(z 1 , . . . , z N )) = sign(2p − 1) z 1 , . . . , z N This simply requires lower bounding the tail of the Binomial N, 1− 2 distribution. Using Theorem 2.1 in [23], where Φ is the distribution function of the standard normal. Let = 1 2 √ N , then √ N √ 1− 2 < 3 5 and

E Supplement to Section 4 E.1 Smoothed accelerated mini-batch SGD
Smoothed accelerated mini-batch SGD is the composition of two ingredients. First, we approximate the non-smooth f with a smooth surrogate, and then perform accelerated mini-batch SGD on the surrogate [10,14]. In particular, we use the β-Moreau envelope f (β) of f : Since f is L-Lipschitz, f (β) has the following properties (Proposition 12.29 [5]): We use the prox oracle to execute A-MB-SGD on the L-Lipschitz and β-smooth f (β) , with updates The A-MB-SGD algorithm will converge on f (β) at a rate (see [10,14])  and we obtain the desired result.