Before revision:  We consider three settings for the objective function: (i) deterministic and smooth , (ii) stochastic and smooth , and (iii) composition of smooth and non-smooth parts. For each of the setting , we characterize the oracle complexity of our algorithm to obtain appropriately defined notions of \epsilon-stationary points . Notably, our complexities are independent of the ambient dimension of the Euclidean space in which the manifold is embedded in, and only depend on the intrinsic dimension of the manifold .
After revision:  We consider three settings for the objective function: (i) deterministic and smooth , (ii) stochastic and smooth , and (iii) Hessian-Lipschitz. For these settings , we characterize the oracle complexity of our algorithm to obtain appropriately defined notions of \epsilon-stationary points . Notably, our complexities are independent of the ambient dimension of the Euclidean space in which the manifold is embedded in, and only depend on the intrinsic dimension of the manifold .