0
$\begingroup$

I have $F_i \in \mathbb{R}^{m}$, $y_i \in \mathbb{R}$, $\beta_i \in (1,\infty)$ for $i = 1,\ldots, n$. I would like to solve the following convex optimization problem $$\min_{x} \sum_{i = 0}^n |F_i\cdot x - y_i|^{\beta_i}$$.

Since it is convex, I have tried Newton's method with Wolfe condition line search. This would be good enough for standard use cases. However, $m$ is around 1,000 and $n$ is around 10,000 to 100,000. I would like the optimization routine to finish in less than 100 milliseconds (or fastest possible).

Is there a way to speed things up? Is there a smarter search method for this type of problem, or is there a way to parallelize the problem?

$\endgroup$
8
  • 1
    $\begingroup$ Do you have a sample dataset or an example implementation? Do you have access to a GPU? $\endgroup$
    – Richard
    Aug 24 at 2:55
  • $\begingroup$ @Richard I can't really upload the dataset. The implementation is the standard Newton's method. (Since calculating gradient and hessian is easy for this loss function). I would prefer not to use a GPU, but if using a GPU helps, I can do that. $\endgroup$
    – JEK
    Aug 24 at 3:06
  • 3
    $\begingroup$ Are you values of $\beta_{i}$ limited to ones that keep $F$ twice continuously differentiable with bounded second derivatives? How long did your implementation of Newton's method take to solve the instance you tried it on? Have you considered using a limited memory BFGS method instead of full Newton's method? In your implementation of Newton's method did you use an efficient multithreaded BLAS/LAPACK library? $\endgroup$ Aug 24 at 4:02
  • $\begingroup$ Majority of $\beta_i$ are greater than 2. But a few are between 1 and 2. My newton's method took about 10 seconds to converge. I used numpy. I'm not sure if it multithreads the solving of linear systems. I will try limited memory BFGS as well. $\endgroup$
    – JEK
    Aug 24 at 4:13
  • 1
    $\begingroup$ Re "I would like the optimization routine to finish in less than 100 milliseconds": Please update the question what performance you are currently seeing and with what kind of hardware and software. If you use high-performance compilers and libraries (that means using C++ and/or Fortran), and a high-end workstation (e.g. based on AMD Threadripper 3970X with quad-channel DDR4-3200, or Intel Xeon W-3175X with hexa-channel DDR4-2666) you could be almost there (speculation based on my back-of-the-envelope calculation). $\endgroup$
    – njuffa
    Aug 24 at 23:28

1 Answer 1

4
$\begingroup$

Some problems just can't be solved in the time one wishes they take.

In your case, consider that modern processors have memory bandwidths of around 40 GB/s. (Give or take a small integer factor that isn't particularly important to the argument.) If you have $n=10,000, m=1,000$, then just loading all of the $F$ vectors into the processor requires accessing $8nm=80 MB$ of data in double precision. So just a single access to all of the data is going to take around 2 milliseconds. But you need to do that more than once per iteration, at least once for the computation of the right hand side of the Newton system and once for the computation of the matrix. You also need to write to these matrices and vectors. So it isn't unreasonable to say that all of this is going to cost you ten times the time of just one read-though, or 20 ms per iteration (again give or take a small factor). Then you also have to solve a linear system of size $1000\times 1000$, which takes 8MB to store, equivalent to another 0.2 ms. Solving a linear system surely takes many memory accesses, so at least another several milliseconds.

Then you have your Newton direction, at a cost of maybe 30 or 40 ms at the minimum, and you need to do a line search -- which requires computing multiple right hand side vectors which will again take 2 ms just to read the data for every residual evaluation, plus dots products, norm computations, etc. So maybe that gets you to maybe 50 ms per iteration just with data transfers.

If your problem had only $\beta_i=2$, then a Newton method would converge in one step, but for your problem it likely takes many more iterations -- say 20 or 40, and so you're already in the range of several seconds. That's not actually all that far away from what you see in practice.

$\endgroup$
2
  • $\begingroup$ I understand that you are trying to establish a rough bound, but there are some arguments that don't seem right to me. For example, you state that the line search will be expensive. But once we have direction $p$, we can precompute $b = Fx - y$ and $v = Fp$, and you just need to calculate $\sum |b + tv|^\beta$ which is O(n) arithmetic operations. Also, this argument doesn't seem to account for the fact we can use multiple processors / GPUs. For example, matrix multiplication can be distributed. $\endgroup$
    – JEK
    Aug 25 at 2:32
  • $\begingroup$ @JEK Sure, maybe you can optimize some things here and there. But you can't expect to solve the problem in 20 ms and you likely can't expect to solve it in 100 ms. (I also used the smaller of the given numbers for $n$, $10,000$. The OP stated it may also be up to ten times larger.) -- -- As for multi-cores: Most machines today have multiple cores, but only one processor and one memory interface. The 40 GB/s I quoted are for the entire processor. Using multiple cores just leads to congestion on the memory bus. $\endgroup$ Aug 25 at 12:53

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.