Checklist 1. For all authors (a)

Do the main claims made in the abstract and introduction accurately reflect the paper's If you ran experiments... (a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [Y es] See the Did you specify all the training details (e.g., data splits, hyperparameters, how they Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? Did you include the total amount of compute and the type of resources used (e.g., type If your work uses existing assets, did you cite the creators? Did you include any new assets either in the supplemental material or as a URL? [No] Did you discuss whether and how consent was obtained from people whose data you're If you used crowdsourcing or conducted research with human subjects... (a) Thus Lemma 2.4 implies that ψ Lemma 2.2 implies that ψ That is nearly the same as the proof of Proposition 4.1, but replacing By lemma C.3 we know that with probability at least 1 α T, λ Inequality (2) is due to the mathematical induction using the same technique in the equality (1). To prove the problem-dependent bound, we need only combine Lemma C.1 and Lemma C.2 together Given Lemma D.2, we need only show that for both the private OLS estimator and the private SGD estimator, we can find the corresponding s Then Theorem 4.1 follows from combining Lemma D.2, D.3 and D.4 .Remark. Notice that in the statement of Lemma D.3 and Lemma D.4, there exists a term The proof of Lemma D.3 and Lemma D.4 needs the following result: For a fixed On the other hand, we have by Markov's inequality λ Now we can claim our first result about the private OLS-estimator in the warm up stage: Lemma D.9.