1
$\begingroup$

I am new to machine learning and statistical analysis and am having trouble figuring how I should go about a problem I have. I believe that I understand the gradient descent algorithm and how it optimizes the parameters of a function.

However, so far I am have mostly seen examples of gradient descent being applied to, univariate and multivariate, first order linear equations. For linear regression models, numpy vector operations are an easy choice for computing the few components used in gradient descent, i.e. the hypothesis, loss, gradient, etc. However what if I want to apply gradient descent to a multivariate nonlinear equation, specifically one that has different functions across its input variables. Here is an example of such a function:

$$f(x_1, x_2) = \theta_1 x_1 + \theta_2 x_2^{\theta_3}$$

In this case the first term is linear but the second is not and requires its own gradient function. The various gradient descent functions I have seen would not be able to optimize this function without hard changes.

I suppose my question is, how do I generalize a gradient descent algorithm so that it can optimize multivariate nonlinear functions?

My approach so far has been to allow a list of gradient functions (matching the number of parameters) to be passed to my gradient descent function and to apply these gradients, in parallel, to their respective parameters assuming the order is correct.

Does this seem like a sound approach to what I am trying to accomplish? Or perhaps is what I am trying to accomplish unnecessary and reveals a fundamental misunderstanding on my part?

$\endgroup$
  • $\begingroup$ Are you sure your function is correct? I don't see $x_3$ anywhere in the RHS. $\endgroup$ – edwinksl Jul 14 '16 at 23:31
  • 2
    $\begingroup$ All you need for a gradient descent minimization method is a function that returns for given $x$ the vector of partial derivatives $\nabla f(\theta) = (f_{\theta_1}(\theta),f_{\theta_2}(\theta),\dots)$. Any routine I'm familiar with accepts such a function as input. For the example you give, you can calculate the derivatives by hand (or ask sympy). If you can't calculate the derivative, you need to use a finite difference approximation, but that can severely limit the performance of the gradient method. $\endgroup$ – Christian Clason Jul 15 '16 at 6:12
  • $\begingroup$ Also, no need to write your own; look at scipy.optimize. $\endgroup$ – Christian Clason Jul 15 '16 at 6:14
  • $\begingroup$ Ok, thanks Ill look into the scipy implementation. $\endgroup$ – Dan Jul 15 '16 at 12:52
1
$\begingroup$

Gradient descent (sometimes also called steepest descent) for the minimization of a function $f:\mathbb{R}^n\to\mathbb{R}$ consists in picking $x^0\in\mathbb{R}^n$ and then setting for $k=0,\dots$ $$x^{k+1} = x^k - \sigma_k \nabla f(x^k),$$ where $\sigma_k>0$ is a suitable step length (e.g., chosen via Armijo line search) and $\nabla f(x)\in\mathbb{R}^n$ is the gradient of $f$ evaluated in $x$, i.e., the vector $$\nabla f(x) = (\partial_{x_1} f(x),\dots,\partial_{x_n} f(x))^T,$$ where $\partial_{x_i}f$ denotes the partial derivative of $f$ with respect to $x_i$.

Most black-box optimization routines such as Matlab's fminunc or scipy.optimize accept as input a function that

  • takes as input the current point $x$ and
  • outputs the value $f(x)$ (as a scalar) and the gradient $\nabla f(x)$ (as a vector of the same size and shape of $x$).

How you compute the value and the gradient is irrelevant for the optimizer (but, since this will be done often, you should try to do it as efficiently as possible). In many cases, you can calculate the derivatives by hand (or ask sympy) to get an explicit formula. If you can't calculate the derivative, you need to use a finite difference approximation, but that can severely limit the performance of the gradient method.

In your case, you're likely minimizing a loss function, so you have a bunch of pairs $(x_j,y_j)$ and wish to minimize $$f(\theta) = \sum_{j} (\theta_1 x_{j,1} + \theta_2 x_{j,2}^{\theta_3}-y_j)^2$$ over $\theta=(\theta_1,\theta_2,\theta_3)^T\in\mathbb{R}^3$. Here, the gradient is given by $$\nabla f(\theta) = \begin{pmatrix} \sum_{j}2x_{j,1} (\theta_1 x_{j,1} + \theta_2 x_{j,2}^{\theta_3}-y_j)\\ \sum_{j}2x_{j,2}^{\theta_3}(\theta_1 x_{j,1} + \theta_2 x_{j,2}^{\theta_3}-y_j)\\ \sum_j 2\theta_2 x_{j,2}^{\theta_3}\log x_{j,2}(\theta_1 x_{j,1} + \theta_2 x_{j,2}^{\theta_3}-y_j) \end{pmatrix} \in \mathbb{R}^3. $$

$\endgroup$
  • $\begingroup$ Great, thanks for this write up. This helps clear my understanding of what exactly is passed to scipy's optimize function. I do have a question though, what is the the final expression in the gradient function? Wouldn't there be only two partials, one for both thetas? $\endgroup$ – Dan Jul 18 '16 at 14:24
  • $\begingroup$ Glad it's helpful! Regarding your question: Aren't there three thetas? (Each gets its own partial derivative -- otherwise an expression like $\theta - \nabla f(\theta)$ wouldn't make sense.) $\endgroup$ – Christian Clason Jul 18 '16 at 14:31
  • $\begingroup$ You are absolutely correct! I was used to one coefficient per variable and I incorrectly tied the number of inputs to the number of parameters for the cost function. $\endgroup$ – Dan Jul 18 '16 at 15:39

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.