I have a question regarding the minimization of a neural network containing $Relu(x):=\max\{0,x\}$.

Since Relu is convex, the subgradient method can be used to minimize the Relu function.

However, Relu is part of a neural network $f$. Training a neural network means to minimize a function $L(W)= \sum_{i = 1}^{N} d(f(x_{i},W),g_{i})$, where we have $N$ training sample $x_{i}$ with corresponding label $g_{i}$ and $d$ is a metric.

How do we minimize $L$ with respect to $W$ if relu is non-differentiable, but $f$ non-convex?

In more detail, there are two subsequent questions:

  1. How is it optimized in practice ?
  2. What are the theoretical aspects to this question? In which case is convergence to a local optimum guaranteed (may be only almost sure).

Your observation is correct. The subgradient method only converges to a minimum for convex functions, hence there is a caveat here. However in practice, this is not a problem for several reasons. First, since the problem is not convex then we are looking for a local minimum, rather than global, to begin with. There is still a theoretical problem with the convergence of the algorithm in general (we want it to stop).

Recall that in practice, Stochastic Gradient Descent (and not subgradient) is used for optimization of neural networks. Indeed, using Gradient Descent with on a non-differentiable function can cause the algorithm to cycle, but this problem is more related to the step-size choice. But Stochastic Gradient Descent uses a different stepsize strategy that makes this problem less probable. Moreover, shuffling caused by the use of mini-batches further reduces the possibility of that to happen.

To conclude, neural networks have a problem with convergence and the consistency of results. However this is "ignored" and in practice algorithms converge, but not to an optimal solution as in the subgradient method with appropriate assumptions (which include convexity).

  • $\begingroup$ Thanks for your answer. I updated my question to make it more precise. I am interested in particular to a theoretic answer to this question. $\endgroup$ Sep 7 '20 at 16:18
  • $\begingroup$ How is SGD applied for functions which are not differentiable on a null set ? As far as I understand it needs to use the subgradient, which then would be the subgradient method. Am I right? $\endgroup$ Sep 7 '20 at 16:28
  • $\begingroup$ For a proper convex function $f:\mathbb{E}\to(-\infty,\infty]$, a subgradient at $\mathbf{x}$ is a vector $\mathbf{g}\in\mathbb{E}^*$ (the dual space) for which $f(\mathbf{y})\geq f(\mathbf{x})+\mathbf{g}^T(\mathbf{y}-\mathbf{x}), \forall \mathbf{y}\in\mathbb{E}$. The group of all subgradient at $\mathbf{x}$ is call the subdifferential set. If this set is a singleton (single element), then the subgradient and gradient (derivative) coincide. When using the subgradient method, then you can choose any element from the set, if more than a single subgradient exist (think of $|x|$ at $x=0$). $\endgroup$
    – iarbel84
    Sep 8 '20 at 9:10
  • $\begingroup$ You understand correctly that for non-differentiable functions we are supposed to use the subgradient method, not the gradient method. But since the subgradient method guarantees convergence to an optimal solution only on proper closed functions, it's not applicable for neural nets. Hence the convention is to use the gradient method (and specifically, stochastic gradient descent - SGD). Hence convergence is not guaranteed at all, not to a minimum or generally that the sequence will converge. But as I explained in the answer, in practice the algorithm converges (stops). $\endgroup$
    – iarbel84
    Sep 8 '20 at 9:14

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.