2
$\begingroup$

Is it "safe" to say that natural phenomena in the real world are often characterized and modelled by functions exhibiting irregular and complicated behaviors, and such functions are almost never convex?

Just as an example, if we take the functional form of the "loss functions" that are optimized in Neural Networks (popular class of Machine Learning Algorithms) - these "loss functions" are often multidimensional and are said to have highly complicated and irregular shapes and forms. Below are some visualizations of the "loss functions" from a Convolutional Neural Network (CNN), used in image recognition:

enter image description here

I have heard people make such claims, such as the "loss functions" of real-world Neural Networks are often so complicated that it is almost "pointless" to write them out in "implicit function form" (e.g. f(x,y,z) ). This being said, given their complexity and the bulk of research that is specifically being conducted regarding the "convergence of optimization algorithms (such as gradient descent) on non-convex functions" - is it "safe" to say that such types of "loss functions" from Neural Networks are almost never convex?

Thanks!

References:

EDIT Note: Take the classic forms of loss functions for Neural Networks:

enter image description here

Is it possible to tell in general if these functions are convex or non-convex?

$\endgroup$
7
  • $\begingroup$ Good question, but hard to answer (for me at least). Any problem that has more than one local extremum is not convex. $\endgroup$
    – copper.hat
    Jan 16, 2022 at 4:27
  • 4
    $\begingroup$ Categorizing functions as either convex and non-convex is like categorizing objects in the universe as either chairs or non-chairs. $\endgroup$
    – JimmyK4542
    Jan 16, 2022 at 5:05
  • $\begingroup$ @ copper.hat : thank you for your reply! $\endgroup$ Jan 16, 2022 at 5:06
  • 1
    $\begingroup$ @JimmyK4542 I think it's a quite useful categorization for optimization problems. "the great watershed in optimization isn't between linearity and nonlinearity, but convexity and nonconvexity." - R. Tyrrell Rockafellar $\endgroup$
    – littleO
    Jan 16, 2022 at 20:54
  • 1
    $\begingroup$ It is true that loss functions for neural networks are almost never convex. An exception is the simplest case where our neural network has just one node, in which case we're doing linear regression or logistic regression. (And linear regression and logistic regression are extremely fundamental and useful models, of course.) $\endgroup$
    – littleO
    Jan 16, 2022 at 20:57

2 Answers 2

2
$\begingroup$

When researchers say something as inflammatory and unscientific as "Most Functions in the 'Real World' are Non-Convex", they are pushing back against the shared assumptions of a research field, not trying to make a rigorous statement.

In this case, the speaker is making a statement about convexity in optimization. To understand the speaker's perspective it helps to understand the history of research in mathematical programming/optimization. This additional context allows one to interpret the speaker's claim for what it is; a critique of current research culture.

The foundation of mathematical programming is linear programming, introduced alongside the simplex method of George Dantzig for solving such problems in the 1940s and 50s. It's not a coincidence that these dates overlap with World War 2. George Dantzig was solving Operations Research problems for the US Armed Forces when he made these contributions. The simplex method was a very big deal, but it had its weaknesses as well. In particular, there are certain problems for which the simplex method requires an exponential number of operations as a function of its input dimensions (see the Klee-Minty cube).

However, linear programs are in fact polynomially time solvable, and in the late 1980 and 1990s there was revised interest in alternative methods which attain these bounds, such as the ellipsoid method. Interior point methods, which are an alternative method for solving linear programs, also became a very hot topic. People realized that interior point methods can be fairly easily extended to any conic program (a class of optimization problems slightly more restricted than the more general convex programs). From this point until the 2010s optimizers focused almost exclusively on convex optimization problems. The theory of convex optimization is very attractive from a theoretical point of view, so there was a strong desire to stay within this class of problems as often as possible. As an example which you are likely already aware, neural networks were viewed as inferior to support vector machines for a long time. The fact that fitting a support vector machine is a convex optimization problem was likely a major reason why. But In 2012 there was an important breakthrough that began to change the optimization landscape; the neural network AlexNet, the fitting of which is nonconvex, won ILSVRC 2012 (aka imagenet). This kicked off a flurry of research activity on variants of stochastic gradient descent, the primary method used for fitting neural networks.

The speaker is now suggesting that optimizers need to move more firmly beyond the neat and tidy theory of convex optimization, because there are important problems that fall outside of this class (like fitting neural nets or matrix completion models). But research fields have inertia, and it's difficult for a speaker to get an entire research community to move beyond the convexity that they likely studied in their PhD theses. Hence the speaker resorted to something inflammatory, attention-grabbing, and unverifiable. The speaker did this as a way to get people talking and thinking about their claims. The existence of this question suggests that he/she has at least partially succeeded.

My opinion is that there are important problems to solve in both convex and nonconvex optimization. I don't fault researchers for using a theoretically attractive class of problems as often as they can. I also don't think the speaker's assertion is particularly novel or insightful anymore, since at this point AlexNet's revolutionary success was a decade ago.

$\endgroup$
3
  • $\begingroup$ @ Robert Bassett: thank you so much for your very detailed answer! Do you know what kind of problems related to world war 2 that dantzig was trying to solve with optimization? $\endgroup$ Jan 22, 2022 at 1:16
  • $\begingroup$ I have always heard that he was moving aircraft around bases belonging to the US and its allies, but I have only been able to find sources which confirm that he was working on planning problems for the US Air Force. Here's a source: informs.org/Explore/History-of-O.R.-Excellence/… $\endgroup$ Jan 22, 2022 at 3:20
  • $\begingroup$ @ Robert Bassett: Thank you so much for your answer! I really liked reading about the Klee-Minty Cube and I was curious why this is such a problem for the Simplex Algorithm. I even posted a question about this over here - can you please take a look at it if you have time? Thanks! math.stackexchange.com/questions/4363772/… $\endgroup$ Jan 23, 2022 at 3:04
1
$\begingroup$

I can’t speak for ML stuff as I’m no expert on it, and it’s generally a marginal subject compared to the vast amount of nonlinear problems arising in all other disciplines.

In my experience, in many real life problems you can’t even write down your objective function(s): in quite a few cases, their value may be the result of extremely complex numerical simulations coming from black boxes, proprietary tools. Which may take hours or days per function evaluation. And those functions can be horrendous (even in a very low dimensional problem), multimodal (with thousands of local minima/maxima). Sometimes they can be discontinuous, or non differentiable.

There has to be a reason why gradient descent is so popular in the ML disciplines. Maybe for some obscure miracles it works acceptably well for ML problems. This is definitely not the case in any other problem I’ve ever encountered in other disciplines: gradient descent is possibly the worst optimization algorithm you can think of when optimizing a nonlinear function.

Unless of course “gradient descent” has a different meaning in the ML world compared to the textbook definition of it.

$\endgroup$
7
  • $\begingroup$ Thank you for your answer! Can you please clarify what you mean by "you can't write down your objective functions"? I thought the objective function in ml problems is a "noisy function", because it is modelling a random variable instead of a deterministic variable... but you can still usually write the general form of the objective function. Shouldn't this be enough to understand if a specific loss function is convex or non convex in its general form? Thank you! $\endgroup$ Jan 16, 2022 at 20:16
  • $\begingroup$ I will post an example... please wait! $\endgroup$ Jan 16, 2022 at 20:17
  • $\begingroup$ You can certainly write down stuff like objective = (simulated - observed)**2.0 or stuff like that, but that tells you nothing about the convexity or even the actual analytical form of your objective function, as it depends on what the “simulated” part of it means. That “simulated” part of your objective function can come from a closed source, numerically heavy simulator that calculates it using millions of lines of code. In days of computing time. $\endgroup$
    – Infinity77
    Jan 16, 2022 at 20:38
  • $\begingroup$ i.stack.imgur.com/hZOud.png , i.stack.imgur.com/aq6MB.png $\endgroup$ Jan 16, 2022 at 20:43
  • $\begingroup$ @ Infinity77 : please see the updates! thank you! $\endgroup$ Jan 16, 2022 at 20:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .