First Order Methods take Exponential Time to Converge to Global Minimizers of Non-Convex Functions

• URL: http://arxiv.org/abs/2002.12911v2
• Date: Mon, 8 Feb 2021 04:04:06 GMT
• Title: First Order Methods take Exponential Time to Converge to Global Minimizers of Non-Convex Functions
• Authors: Krishna Reddy Kesari and Jean Honorio
• Abstract summary: In this work, we provide bounds on the fundamental hardness of a non convex function. We show that the parameter estimation problem is equivalent to the problem of family identification.
• Score: 28.776950569604026
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• ADMM for Structured Fractional Minimization [7.9047096855236125]
  We consider a class of structured fractional problems, where the numerator includes a differentiable function. We introduce sf FADMM, the first Alternating Method of Multipliers for this class of problems.
  arXiv  Detail & Related papers  (2024-11-12T02:50:12Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• Kernel-based off-policy estimation without overlap: Instance optimality beyond semiparametric efficiency [53.90687548731265]
  We study optimal procedures for estimating a linear functional based on observational data. For any convex and symmetric function class $mathcalF$, we derive a non-asymptotic local minimax bound on the mean-squared error.
  arXiv  Detail & Related papers  (2023-01-16T02:57:37Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  Many real-world problems have complicated non functional constraints and use a large number of data points. Our proposed method outperforms an existing method with the previously best-known result.
  arXiv  Detail & Related papers  (2022-12-19T14:48:54Z)
• Super-Universal Regularized Newton Method [14.670197265564196]
  We introduce a family of problem classes characterized by H"older continuity of either the second or third derivative. We present the method with a simple adaptive search procedure allowing an automatic adjustment to the problem class with the best global complexity bounds.
  arXiv  Detail & Related papers  (2022-08-11T15:44:56Z)
• Coordinate Descent Methods for DC Minimization [12.284934135116515]
  Difference-of-Convex (DC) refers to the problem of minimizing the difference of two convex functions. This paper proposes a non-dimensional one-dimensional subproblem globally, and it is guaranteed to converge to a coordinatewise stationary point.
  arXiv  Detail & Related papers  (2021-09-09T12:44:06Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  We consider the global minimization of smooth functions based solely on function evaluations. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
  arXiv  Detail & Related papers  (2020-12-22T12:59:30Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  Motivated by recent increased interest in analysis of optimization algorithms for non- optimization in deep networks and other problems in data, we give an overview of recent results of theoretical optimization algorithms for non- optimization.
  arXiv  Detail & Related papers  (2020-12-11T08:28:51Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  We study the problem of zero-order optimization of a strongly convex function. We consider a randomized approximation of the projected gradient descent algorithm. Our results imply that the zero-order algorithm is nearly optimal in terms of sample complexity and the problem parameters.
  arXiv  Detail & Related papers  (2020-06-14T10:42:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.