7
$\begingroup$

I am trying to understand gradient descent algorithm by plotting the error vs value of parameters in the function. What would be an example of a simple function of the form y = f(x) with just just one input variable x and two parameters w1 and w2 such that it has a non-convex(has multiple minima) loss function ? What i am trying to achieve is something similar to this : enter image description here

How does one know if the function has a non-convex loss function without plotting the graph ?

$\endgroup$
  • 1
    $\begingroup$ It seems (following your latest edit) you strongly associate non-convexity with the presence of multiple local minima; this is not a very coherent idea. I would suggest you keep the question in its original form (asking about convexity) and ask a second question directly on the matter of multiple local minima. $\endgroup$ – usεr11852 May 13 '17 at 17:48
  • $\begingroup$ done. stats.stackexchange.com/questions/279363/… $\endgroup$ – melwin_jose May 13 '17 at 18:05
  • $\begingroup$ Saw it. Sorted. $\endgroup$ – usεr11852 May 13 '17 at 18:24
11
$\begingroup$

We know "if a function is a non-convex loss function without plotting the graph" by using Calculus. To quote Wikipedia's convex function article: "If the function is twice differentiable, and the second derivative is always greater than or equal to zero for its entire domain, then the function is convex." If the second derivative is always greater than zero then it is strictly convex.

Therefore if we can prove that the second derivatives of our selected cost function are always positive the function is convex.

We care about convexity because the minimum of a convex function is also a global minimum. If the function is strictly convex function then it will have at most one global minimum which is also convenient; we prove the global optimality of particular solution. Please see the thread here as why we generally want an objective function to be a convex function and here on whether gradient descent can be applied to non-convex functions, for some more information on the matter.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thanks for the answering the 2nd question. What about the 1st one : What would be an example of a simple function of the form y = f(x) with just just one input variable x and two parameters w1 and w2 such that it has a non-convex loss function ? $\endgroup$ – melwin_jose May 13 '17 at 12:48
  • 1
    $\begingroup$ Sorry I missed that! Simplest form I can think of is: $\log(x)$ as a non-convex loss function example. The 2nd derivative of it is $\frac{-1}{x^2}$. So say $f(x)=\log(w_1x+w_2)$. Then $f''(x)= \frac{-w_1^2}{(w_1x+w_2)^2}$. $\endgroup$ – usεr11852 May 13 '17 at 14:56
  • $\begingroup$ here is the code and plot that i got, it doesn't look like non-convex. $\endgroup$ – melwin_jose May 13 '17 at 16:43
  • $\begingroup$ What is shown in the plot you attached is a non-convex function, $\log(x)$ is a concave function (or convex-upwards if you wish). From an optimisation stand-point you can always turn a concave function $f(x)$ to concave by simply optimising $-f(x)$. The problem when optimising a loss function relates to the presence of (potentially multiple) local minima and flatness. Curvature information allows us to prove certain vital properties of $f(x)$. $\endgroup$ – usεr11852 May 13 '17 at 17:23
  • 1
    $\begingroup$ No probs. I suspected that there was some misunderstanding involved... :D The idea is the same though. Using calculus, multiple local minima would relate to multiple instances of first derivatives being zero and second derivatives being positive. Take $x \sin(w1x+w2)$ for example; it has infinite on them. $\endgroup$ – usεr11852 May 13 '17 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.