Stochastic Multi-level Composition Optimization. Compositional optimization problems of the form in (REF ) have been considered as early as 1970s by [1]}. Recently, there has been a renewed interest on this problem. [2]} and [3]} considered a sample-average approximation approach for solving (REF ) and established several asymptotic results. For the case of \(T=2\) , [4]}, [5]} and [6]} proposed and analyzed stochastic gradient-type algorithms in the smooth setting. [7]} and [8]} considered the non-smooth setting and established oracle complexity results. Furthermore, [9]} proposed algorithms when the randomness between the two levels are not necessarily independent. For the general case of \(T\ge 1\) , [10]} proposed stochastic gradient-type algorithms and established oracle complexities established that depend exponentially on \(T\)  and are hence sub-optimal. Indeed, large deviation and Central Limit Theorem results established in [2]} and [3]}, respectively, show that in the sample-average approximation setting, the \(\operatornamewithlimits{arg\,min}\)  of the problem in (REF ) based on \(n\)  samples, converges at a level-independent rate (i.e., dependence of the convergence rate on the target accuracy is independent of \(T\) ) to the true minimizer, under suitable regularity conditions.
