The Sample Complexity of Gradient Descent in Stochastic Convex Optimization

Thank you very much for the review and detailed comments.

• This could be rewritten in a more concise way with all the improvements under which regimes spelled out explicitly (maybe a table would make sense).

A table is an excellent suggestion. We will follow it, thanks!

• It should be mentioned that Eq 16 will be proven in Appendix D.

Thanks for catching this. It will be mentioned.

Also thanks for catching typos!

• I'm really confused by the fact that all bounds and the proofs use 𝐹(0) for the gap. Why is this the case?

Thanks for pointing this out. As to the bounds, it will be a good idea to state the results in terms of $\min_{w\in W} F(w)$ and not $F(0)$. (clearly, $F(w)-F(0) \ge F(w)-min_{w\in W} F(w)$).

As for the proofs you are right. We get the excess error w.r.t initialization, which may seem strange. There is no contradiction here, as GD minimizes the empirical loss and the increase is w.r.t population loss. But overall it is strange that you start at an initialization that is better than where you end up with. This also happens, btw, in other similar constructions (see [3])

Yes, it's a typo, sorry for that. We have, $F(w)- \min_{w\in W} F(w) \ge F(w)- F(0)$ and not the other way around. This is also the direction we actually want.

So, any lower bound of the type $F(w)-F(0) = \Omega(f(m,\eta,T,d))$ automatically yields a lower bound of the type: $F(w)- \min_{w\in W} F(w)= \Omega(f(m,\eta,T,d))$. In particular, theorem 1 corollary 2 and corollary 3 can all be stated with respect to the minimizer instead of $F(0)$.

Does that answer your question?

Thank you very much for taking the time to review the manuscript.

• The conclusions are clearly presented in the manuscript, but are also present in the other reviews. If, after reading the other reviews, you still feel that certain contributions are not highlighted enough, please point concretely and we will gladly highlight them.
• As to notations, please share concrete examples to missing/confusing/non-standard notations. We will gladly fix any such confusion.
• As to organization, all proofs appear in the appendix. Main theorems and main Lemmas appear in the main text. This is a standard practice.

Unless there are strong reasons for rejection, we ask the reviewer to higher the score so it will not reflect negatively on the paper.

Thank you very much for the constructive comments and the positive score. Below are answers to concrete questions.

• For example, it's not clear to me why the oracle 𝑂(𝑡) defined in Eq. 11 satisfies the zero-chain property depicted in Figure 1.

Notice that figure 1 refers to eq. 16 and not eq. 11. The figure depicts the specific dynamics of choice and the subdifferentials as appear above eq. 16. The caption of the figure should be rephrased as: “Depiction of the dynamics depicted above Eq. (16)”. Or to refer to the main text instead ““Depiction of the dynamics depicted below Eq. (9)”.

Frames 3,6,7 depict the case of item 1 (below eq. 9), and frames 1,2,4,5 the case of item 2 (below eq. 9) and last frame is the last item (partial = 0). Is that more clear?

• should the lower bound actually be $\min ( \frac{1}{\sqrt{m}},1)\cdot \min(\frac{d^{3/2}}{m^{3/4}},1)$ [[as opposed to $1/\sqrt{m}$]]

Notice that the $\Omega(1/\sqrt{m})$ term does not follow from thm 1 but, as stated in the manuscript, “is a well known-information theoretic lower bound for learning”. A citation will be added to the manuscript to clarify. For example, this lower bound can be found in lecture notes: https://optmlclass.github.io/notes/optforml_notes.pdf (theorem 16.7) where it is proven that there are two instances of stochastic convex optimization where every algorithm “fails” on one of them with excess error $1/\sqrt{T}$ unless more than $T$ examples are observed (in our notation $T=m$)

• Could the authors elaborate why this new oracle defined in 214-218 only activates $O(d)$ coordinates in $O(d^3)$ iterations?

Roughly, to increase coordinate $k$ you need to increase each previous coordinate by $+1$. Increasing coordinate t requires k-t iterations (increasing $k$ and propagating it back). So overall $\sum_{t=0}^1 k-t= O(k^2)$ iterations in order to increase the $k$’th iteration by 1. So overall $O(1+2^2+3^2….. + d^2)$ to increase all coordinates by one. Which amounts to $O(d^3)$.

Regarding minor comments, thanks for the suggestions and for catching typos. We will follow the reviewers' advice and corrections.

Thank you very much for taking the time to review the manuscript, and particularly for the positive review.

• Can you explain how this analysis restricts to full-batch GD and what makes it impossible to obtain results for SGD? I recommend adding a bit of discussion to the paper regarding this.

Thank you for the question. First, just to clarify, the results cannot be obtained for SGD as SGD has dimension-independent sample complexity and this is discussed in the paper. But the question remains how SGD circumvent the construction. A discussion about that will be added to the paper as follows:

The main issue with the proof is that it relies on a reduction to sample dependent oracle (defined in section 4.1). SGD circumvent the reduction (Lemma 9). In more detail, the Lemma assumes the update is given by eq. 12 (the full-batch update rule). Because of this full-batch update rule, we can "encode" the whole sample in the trajectory. This allows the reduction, because the oracle that depends on the parameter can "decipher" the sample and behave like sample dependent oracle. If the sample points are coming one-by-one, as the case in SGD, then we do not know the sample in the first steps, hence we cannot reduce to a sample-dependent first order oracle.