[1]} proposed a single time-scale Nested Averaged Stochastic Approximation (NASA) algorithm and established optimal rates for the cases of \(T=1,2\) . For the general case of \(T\ge 1\) , [2]} proposed a linearized NASA algorithm and established level-independent and optimal convergence rates. Concurrently, [3]} considered the case when the function \(f_i\)  are non-smooth and established asymptotic convergence results. [4]} also established non-asymptotic level-independent oracle complexities, however, under stronger assumptions than that in [2]}. Firstly, they assume that for a fixed batch of samples, one could query the oracle on different points, which is not suited for the general online stochastic optimization setup. Next, they assume a much stronger mean-square Lipschitz smoothness assumption on the individual functions \(f_i\)  and their gradients. Finally, they required mini-batches sizes that depend exponentially on \(T\) , which makes their method impractical. Concurrent to [2]}, level-independent rates were also obtained for unconstrained problems by [7]}, albeit, under the stronger assumption that the stochastic functions \(G_i(x,\xi _i)\)  are Lipschitz, almost surely. It is also worth mentioning that while some of the above papers considered constrained problems, the algorithms proposed and analyzed in the above works are not projection-free, which is the main focus of this work.
