Supplementary Material Outline

Such independent samples can be obtained by querying the SO at (x, y) for three times. A.2 Technical Lemmas for Lipschitz Properties and Hessian Inverse Estimation We first restate Lemmas 2.2 of (Ghadimi and Wang, 2018) to characterize the smoothness properties of y Lemma A.1 Suppose Assumptions 3.3 and 3.4 hold. Throughout this section, we assume Assumptions 3.1, 3.2, 3.3, and 3.4 hold and the step-sizes follow (5) that q q Therefore, under Assumption 3.3, for all t apple T, for all 1 apple j apple b, we have E[ku B.2 Lemma B.2 and Its Proof We quantify the convergence behavior of consensus errors under the choices of step-sizes (5) and (6) as follows. Lemma B.2 Suppose Assumptions 3.1, 3.2, 3.3, and 3.4 hold and the step-sizes satisfy Lemma B.3 Suppose Assumptions 3.1, 3.2, 3.3, and 3.4 hold. B.7 Proof of Theorem 5.1 Proof: We start our analysis by considering the term kȳ Throughout this subsection, we assume Assumptions 3.1, 3.2, 3.3, 3.4, and 5.2 hold. C.1 Lemma C.1 and Its Proof Lemma C.1 Suppose Assumptions 3.1, 3.2, 3.3, 3.4, and 5.2 hold and the objective F satisfies µ-PL Assumption 5.2 in addition.