Before revision:   To the best of our knowledge, this is the first work considering SBO with many lower level problems and establishing state-of-the-art sample complexity  .
After revision:  Lastly, we establish even faster convergence results for gradient-dominant functions. To the best of our knowledge, this is the first work considering SBO with many lower level problems and establishing state-of-the-art sample complexity .