2

In this answer I will explore two interesting and relevant papers that were brought up in the comments. Before doing so, I will attempt to formalize the problem and to shed some light on some of the assumptions and definitions. I begin with a 2016 paper by Lee et al. We seek to minimize a non-convex function $f: \mathbb{R}^d \to \mathbb{R}$ that is bounded ...


2

See appendix B1 in https://web.stanford.edu/~boyd/cvxbook/. The function and the constraint can be non-convex in a Quadratically Constrained Quadratic Program, and you can still see strong duality (it is guaranteed if a technical condition known as Slater's constraint qualifier holds) Strong duality in weak terms means that we can solve the optimization ...


2

It really depends on the function. For some functions you can compute the derivative to obtain the local minima, e.g. $\sin x$ is non-convex but it is straightforward to find all its minima ($k\pi, k\in \mathbb{Z}$). Gradient descent also works well on non-convex functions, but it will find a local minimum. There are techniques to "push" the gradient ...


2

No, usually the error function is not convex with respect to the weights. Algorithms like (stochastic) gradient descent do not assume convexity -- it's just that you can prove convergence in that case.


1

Let $\mathbb{R}^p$ be our ambient space. It is assumed that we use the Euclidean distance. A convex set $S \subseteq \mathbb{R}^p$ is one that contains every line segment that joins two of its element. Let $p_1,...,p_k$ be a set of points in $\mathbb{R}^p$ and let $r \neq s \in \{1,...,k\}$. What is the equation of the set of points in $\mathbb{R}^p$ ...


1

I will try and answer the "when does Gradient Descent convergence to a critical point" part of the question. The paper "Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods" by Attouch, Bolte and Svaiter, shows that if the objective function satisfies ...


Only top voted, non community-wiki answers of a minimum length are eligible