First Order Methods take Exponential Time to Converge to Global Minimizers of Non-Convex Functions
Machine learning algorithms typically perform optimization over a class of non-convex functions. In this work, we provide bounds on the fundamental hardness of identifying the global minimizer of a non convex function. Specifically, we design a family of parametrized non-convex functions and employ statistical lower bounds for parameter estimation. We show that the parameter estimation problem is equivalent to the problem of function identification in the given family. We then claim that non convex optimization is at least as hard as function identification. Jointly, we prove that any first order method can take exponential time to converge to a global minimizer.
Code (0)
등록된 구현이 없습니다.
Tasks
BIG-bench Machine Learningparameter estimationSimilar Papers 제목 키워드 기반
Exponential Kernels with Latency in Hawkes Processes: Applications in Finance
The Tick library allows researchers in market microstructure to simulate and learn Hawkes process in high-frequency data, with optimized parametric and non-parametric learners. But one challenge is to take into account t…
Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networks
Shapley additive explanations (SHAP) are widely recognised as computationally intractable for neural networks, since they induce an exponential search space over the input features. In this work, we take a first step tow…
Intervention Strategies for Epidemics: Does Ignoring Time Delay Lead to Incorrect Predictions?
Our paper investigates distributions of exposed and infectious time periods in an epidemic model and how applying a disease control strategy affects the model's accuracy. While ordinary differential equations are widely …
The Information Geometry of Mirror Descent
Information geometry applies concepts in differential geometry to probability and statistics and is especially useful for parameter estimation in exponential families where parameters are known to lie on a Riemannian man…
parameter estimationQuantum algorithm for finding the negative curvature direction
We present an efficient quantum algorithm aiming to find the negative curvature direction for escaping the saddle point, which is a critical subroutine for many second-order non-convex optimization algorithms. We prove t…