On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum Optimization

Nicolas Emmenegger, Rasmus Kyng, Ahad N. Zehmakan

We prove lower bounds for higher-order methods in smooth non-convex finite-sum optimization. Our contribution is threefold: We first show that a deterministic algorithm cannot prof…