0
$\begingroup$

My goal is to find the local minimums of a smooth multivariate function $f_t(\vec y)$ for multiple values of $t$. I have created an algorithm $foo(t,\vec x)$ which returns the results of Newton's Method (by "results", I mean that $foo(t,\vec x)$ returns $\vec a$, where $\vec a$ is a local minimum for $f_t(\vec y)$) on $f_t(\vec y)$, where the initial guess is $\vec x$. I have 1,000 values of $t$ to solve for, and for each $t$, I try half-million values of $\vec x$. I then push all the return values of $foo(t,\vec x)$ into an array.

Essentially, I need to run $foo(t,\vec x)$ about half-billion times for different $t$ and $\vec x$. Currently, I have split the computations into four threads, each running $foo(t,\vec x)$ about 125,000,000 times. On my laptop this takes around 2 hours. I would like to shorten the running time as much as possible. What can I possibly do to achieve this?

Here are some details about $f_t(\vec y)$ and $foo(t,\vec x)$:

  • $f_t: \mathbb R^4 \to \mathbb R$, so this is a very low dimensional optimization problem.

  • $f_t$ is a radical function.

  • $foo(t,\vec x)$ uses a standard Newton's Method, i.e. tries to find the roots of the gradient $\nabla f_t$. It finds the descent direction $\vec p_{n+1} = -H_n^{-1}\nabla f_t$, where $H_n$ is the hessian matrix, and using inexact line search finds descent length $\alpha$. Then it sets $x_{n+1}=x_n+\alpha p_n$.

I have heard that machine learning uses GPU. Would my program also be able to utilize the GPU in some way? Maybe run $foo(t,\vec x)$ on each core of a GPU?

$\endgroup$
4
  • 1
    $\begingroup$ It's hard to say without knowing more about the function being evaluated, but as a general comment, if computation can't be shared between evaluations of $f_t$, then throwing a GPU at it might make sense. Vector instructions, to do multiple evaluations in parallel, might also help. $\endgroup$
    – Pseudonym
    Commented Jun 1, 2023 at 3:49
  • $\begingroup$ As an example, Newton's method requires computing both the function and its Jacobian at a point. Presumably you can save some computation there. If this is a high-dimensional problem, you might also consider Gauss-Newton, which uses the Moore-Penrose pseudoinverse of the Jacobian and so exploits sparsity. It might be worth trying gradient descent, too. $\endgroup$
    – Pseudonym
    Commented Jun 1, 2023 at 4:23
  • $\begingroup$ From what little I know of GPU programming, GPU's are very inefficient at serial computations and are bad with memory. Would it be possible for a GPU core to calculate $foo(t,\vec x)$ in a reasonable amount of time? $foo(t,\vec x)$ itself consists of hundreds of iterations of loops. $\endgroup$
    – folo polo
    Commented Jun 2, 2023 at 4:37
  • $\begingroup$ What a GPU would buy you, if anything, is the ability to evaluate $f$ many times with different arguments in a SIMD manner. $\endgroup$
    – Pseudonym
    Commented Jun 2, 2023 at 5:07

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.