A theory on the absence of spurious solutions for nonconvex and nonsmooth optimization
We study the set of continuous functions that admit no spurious local optima (i.e. local minima that are not global minima) which we term global functions. They satisfy various powerful properties for analyzing nonconvex and nonsmooth optimization problems. For instance, they satisfy a theorem akin to the fundamental uniform limit theorem in the analysis regarding continuous functions. Global functions are also endowed with useful properties regarding the composition of functions and change of variables. Using these new results, we show that a class of nonconvex and nonsmooth optimization problems arising in tensor decomposition applications are global functions. This is the first result concerning nonconvex methods for nonsmooth objective functions. Our result provides a theoretical guarantee for the widely-used 1 norm to avoid outliers in nonconvex optimization.
This paper studies the condition for absence of spurious optimality. In particular, the authors introduce 'global functions' to define the set of continuous functions that admit no spurious local optima (in the sense of sets), and develop some corresponding definitions and propositions for an extending characterization of continuous functions that admit no spurious strict local optima. The authors also apply their theory to l1-norm minimization in tensor decomposition.   Pros: In my opinion, the main contribution of this paper is to establish a general math result and apply it to study the absence of spurious optimality for a specific problem.     I also find some mathematical discoveries on global functions interesting, which include:     -- In section 2, the paper provides two examples to show that: (i). there exist global functions that are nowhere differentiable; (ii). there may not exist a strictly decreasing path from any point to a global minimum for a coercive global function defined on compact sets. These two non-trivial examples imply that 'global function' may have bad properties.     -- From definition 2.4 to definition 2.6, the paper introduces 'minimum in the sense of sets' and 'weakly global functions'. These definitions are non-trivial in the sense that the crucial property of 'all strict local minima are global minima' is not consistent in the sense of points and sets. This non-equivalence means that the set of 'weakly global functions' is a proper subset of functions whose strict local minima are all global minima, which implies that we may expect more detailed characterization of weakly global functions.  Cons: There are a few places that can be improved. See detailed comments below.  (1) Although the mathematical tools and examples are interesting, the studied problem is not as interesting as the math part. Often we expect a powerful theory to solve a general class of problems, but I find it a bit disappointing that this paper only solves a relatively narrow and less interesting problem. The significance of the main general theorem Proposition 2.7 would be much more appreciated if there are other interesting examples.   (2) Algorithm. In Line 61, the paper claims that one can minimize the function in proposition 1.1 using a local search algorithm. Which local search algorithm can guarantee local optimality for a non-smooth function? To my knowledge, at least subgradient method and coordinate descent method can not.    It is clearly an issue that classical methods cannot guarantee local optimality in general. Thus proving a non-smooth function is a global function is not enough. Whether this is a big issue or not is debatable, but it is misleading to claim local minima of non-smooth functions are easy to find in general.   (3) Some comments on the wording.    (i) The title “A theory on the absence of spurious optimality” is a bit too general. This is not the first theoretical paper that studies spurious optimality, and not the first one that attempts a general theory. It is also not a comprehensive study. Something more specific may be more accurate (perhaps something related to Prop. 2.7?)   (ii) The authors claim “This is the first result concerning nonconvex methods for nonsmooth objective functions”. This claim is questionable as there are quite a few previous papers that analyze neural networks with ReLU activations.    (iii) The statement “It has received a lot of attention recently due to the discovery in [25, 10] stating that the problem generally admits no spurious local minima (i.e. local minima that are not global minima)” is not true. [25] requires extra regularizers (which is crucial), and [10] requires RIP assumption. But the statement seems to imply (2) is a global function, given that the whole paper is about global functions. This is misleading. In fact, without extra restrictions (2) can be a non-global function.   (4) Some technical comments.   --The description of proposition 2.4 is a bit confusing. According to definition 2.4, the global minimum for a set is defined with respect to a particular function f. However, the conclusion focuses on the set of global functions over some particular sets. The assumption and conclusion don't match perfectly. I guess what you intend to claim is that: if f is a global function on X_alpha for some alpha in some index set A, and X_alpha are global minima of f on the union of X_alpha, then f is a global function on the union of X_alpha. This claim is true.    --A point in the proof of lemma 3.2 and proposition 2.3: to utilize proposition 2.3, you need to show that S'' is a global minimum of f_odd on S'. This is not proven in the proof. However, I guess this is implicitly true due to the continuity of f_odd. Correspondingly, is assumption 1 really needed in proposition 2.3?  (5) Some typos. -- Line 411: alpha should be alpha/2. -- Line 473: the term in the beginning should be corrected. Same is it with equation (37). -- In the first equation of (42): 0 in the right hand side should be |yi|. --Equation (4): It is not the clear to me where matrices A in (2) are. Do you assume here that A=I?