Due to the difficulties encountered in finding the global optima of non-convex problems, approximation or local optimization algorithms have been a key component of the non-convex literature. Recently, there has been a spurt of interest in non-convex optimization methods that can guarantee the quality of their approximate solutions. The central goal of our work is to establish the theoretical foundations required to build novel optimization frameworks that overcome the limitations of traditional methods in producing high-quality guarantees, with a focus on optimization problems of immense significance in signal/information processing.