The diverse world of non-convex machine learning tasks have given rise to numerous non-convex optimization problems. Some of them are perhaps as hard as minimizing general non-convex objectives (such as deep learning), but some others may be only slightly harder than convex optimization (such as matrix completion, principal component analysis, dictionary learning, etc). Therefore, it is both interesting and challenging to identify classes of optimization problems that interplay between non-convex and convex optimization, and (hopefully) optimally and practically solving them. At least tracing back to 2015, Shalev-Shwartz [27] identified a class of functions that are convex, but can be written as finite average of non-convex functions.