Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization
Theoretical paper establishing sharp lower bounds for higher-order smooth nonconvex optimization. Authors prove ε^(-7/4) rate under Lipschitz Hessians and ε^(-5/3) rate under third-order smoothness are optimal in first-order oracle complexity. Hard instance uses block-chain mechanism for blockwise oracle revelation.