Supplementary Material for " Closing the Gap: Tighter Analysis of Alternating Stochastic Gradient Methods for Bilevel Problems "

A.1 Auxiliary Lemmas Throughout the proof, we use F We first present some results that will be used frequently in the proof. L 2η (52) where (a) uses (18a) in Lemma 3. Recall that the lower-level function for the min-max problem is g(x, y; φ) = f(x, y; ξ). B.2 Reduction from Theorem 1 to Proposition 3 In the min-max case, we apply Theorem 1 with η = 1. These assumptions are mostly common in analyzing actor-critic method with linear value function approximation [50-52]. Assumption 9 is common in analyzing TD with linear function approximation; see e.g., [54, 55, 50].