Serving the Quantitative Finance Community

 
User avatar
MartinGale7
Topic Author
Posts: 70
Joined: April 1st, 2011, 7:42 am

Which solver to use?

January 3rd, 2018, 12:06 pm

Apologies if this question is a bit basic. Hopefully that means a quick answer ;)

I have a large matrix of constants M [100000x1000]. I seek to find values for P [1000x1] which minimise the MSE between constant Y [100000x1] and Yhat [100000x1]. I am doing it using 64bit floating points, so an algorithm which ensures stability/rounding would be helpful. Speed is less important.

Yhat = M*P

MSE = (Y - Yhat)'*(Y - Yhat) = (Y - M*P)'*(Y - M*P)

I was considering Gradient Descent. Once again, apologies in advance for what is probably quite a simple question.
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Which solver to use?

January 3rd, 2018, 12:22 pm

I use the term Steepest Descent but it's the same as GD (used by AI). If it works go for it, but it does not always work. And to a local minimum. Lots  of tweaking needed.

For robustness, Differenitial Evolution (DE) for least squares is worth investigation, for sure.

More to the point here..

Looking at your non-TEX formulae it looks like you are solving normal equations. Your problem is linear.

[$]Ax = b[$]

least squares solution solve

[$]A^{\rm T} Ax = A^{\rm T}b[$]

in your case K = A, P = x, Y = x, yes?
 
User avatar
MartinGale7
Topic Author
Posts: 70
Joined: April 1st, 2011, 7:42 am

Re: Which solver to use?

January 3rd, 2018, 12:49 pm

Thank you. Yes, that is the problem. It is a least squares solution. The system is linear and the error is a quadratic. Is inversion or a factoring too expensive? Or would you use Steepest Descent / DE still?
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Which solver to use?

January 3rd, 2018, 2:12 pm

You're welcome. I'm not sure what is better but solving the normal equations via matrix methods is probably more efficient but I have not tried it. AFAIR GD reduces to some form of conjugate gradient method which is iterative  but converges in a finite number of steps.

I would say this article by Ivar  Gustafsson would be definitive

http://www.math.chalmers.se/Math/Resear ... 014/24.pdf

If the structure of M is known it might be possible to take advantage of this property.

It would be a good experiment DE versus CG to see which is faster,  Are you using Matlab?
 
User avatar
outrun
Posts: 4573
Joined: January 1st, 1970, 12:00 am

Re: Which solver to use?

January 3rd, 2018, 4:08 pm

This is linear least squares regression. A common method is to solve the Gramian matrix via a Cholesky

See section "Inverting the matrix of the normal equations" in https://en.m.wikipedia.org/wiki/Linear_ ... thematics)

Edit: note that there are no local minima, it's well known that linear least squares regression is convex.
 
User avatar
MartinGale7
Topic Author
Posts: 70
Joined: April 1st, 2011, 7:42 am

Re: Which solver to use?

January 3rd, 2018, 5:07 pm

Hi @outrun. Thanks. Two questions.

1) As I understand this, in this example the matrix to be factored or inverted isn't square.
2) While it is linear with error squared, I may add weightings to the errors in the future, so keeping generic is good.

I am trying to get around the size limitation with GPR. Specifically:

I have 100000 or more training patterns. There is a lot of noise in these. Instead of letting these be the model, I will choose 1000 points (I'll call these support points), perhaps using low discrepency numbers for their x vector coordinates. Their x positioning will be fixed, however I'll try to optimise the values of their y to give me an optimal objective function (in this case error squared) on the 100000 or more test points.

With GPR, the forecasting step is, yhat = k* inv(K) y. Now, if I keep the x vectors of my support points fixed, and optimise for their y, then k* and K will be constant. In my case, the dimensions will be:

100000x1 = 100000x1000 1000*1000 1000x1

I intent to replace inv(K) y with M. M is an unknown column vector of 1000 points. Given I know k, I can fit yhat to y by finding optimal M. Once I'm happy with this, I can factor M to give me the y values of my 1000 support points.

I suppose this is a combination of SVM and GPR. Use hundreds of thousands of data points and find the y values of a handful (hundred or thousand) of support points in order to fit the data best.

I know @outrun is across GPR. Think that would work? My initial prototyping looks ok. I am using ConjugateGradient so far.

Apologies for my non-Tex maths.
 
User avatar
outrun
Posts: 4573
Joined: January 1st, 1970, 12:00 am

Re: Which solver to use?

January 3rd, 2018, 5:25 pm

Cool. I think the terminology "support points" is clear.
It looks like you've discovered "sparse Gaussian Processes", no? 

http://www.gatsby.ucl.ac.uk/~snelson/SPGP_up.pdf
 
User avatar
MartinGale7
Topic Author
Posts: 70
Joined: April 1st, 2011, 7:42 am

Re: Which solver to use?

January 3rd, 2018, 5:27 pm

In other words, I am trying to find 1000 support points, which when used in a GPR will explain/forecast the 100000 test points optimally.
 
User avatar
MartinGale7
Topic Author
Posts: 70
Joined: April 1st, 2011, 7:42 am

Re: Which solver to use?

January 3rd, 2018, 5:29 pm

Yes. I've been playing around with mechanisms to remove points and add them one at a time too.

Up until now I was using binning to reduce my number of points down (ie doing GPR on the bins, not the points) however this wasn't really suitable past 2-3 dimensions.

Luckily I've got 64Gb of RAM too, so I can work with some quite large sets.

I am hoping this technique will get me there :)
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Which solver to use?

January 3rd, 2018, 5:34 pm

This is linear least squares regression. A common method is to solve the Gramian matrix via a Cholesky

See section "Inverting the matrix of the normal equations" in https://en.m.wikipedia.org/wiki/Linear_ ... thematics)

Edit: note that there are no local minima, it's well known that linear least squares regression is convex.
your link is broke.
regarding local minimum, more precisely

The convexity makes optimization easier than the general case since local minimum must be a global minimum, and first-order conditions are sufficient conditions for optimality.[1]

linear least squares regression 
i'm not sure this is the correct term in this context. So, if I do a google I get this

http://www.itl.nist.gov/div898/handbook ... pmd141.htm


which is a different ball-game. Maybe you mean linear regression.
 
User avatar
outrun
Posts: 4573
Joined: January 1st, 1970, 12:00 am

Re: Which solver to use?

January 3rd, 2018, 5:49 pm

Yes, proving that linear least square regression is convex is very basic linear algebra but it looks like you wasn't ware of convexity given your cryptic remark "If it works go for it, but it does not always work. And to a local minimum. Lots  of tweaking needed." right?

It's very easy to check for yourself.
 
User avatar
outrun
Posts: 4573
Joined: January 1st, 1970, 12:00 am

Re: Which solver to use?

January 3rd, 2018, 5:53 pm

Yes. I've been playing around with mechanisms to remove points and add them one at a time too.

Up until now I was using binning to reduce my number of points down (ie doing GPR on the bins, not the points) however this wasn't really suitable past 2-3 dimensions.

Luckily I've got 64Gb of RAM too, so I can work with some quite large sets.

I am hoping this technique will get me there :)
Binning was something I was going to suggest (I've used that myself for GP), buy you're right it won't scale to higher dimensions. 
Another option is selecting random subsets (bagging), and I've also heard about techniques where people first project on low dimensional manifolds.
 
User avatar
outrun
Posts: 4573
Joined: January 1st, 1970, 12:00 am

Re: Which solver to use?

January 3rd, 2018, 6:13 pm

Regarding the bagging approach, I found this:

https://www.google.nl/amp/s/www.researc ... ession/amp
 
User avatar
Cuchulainn
Posts: 20254
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: Which solver to use?

January 3rd, 2018, 6:47 pm

Yes, proving that linear least square regression is convex is very basic linear algebra but it looks like you wasn't ware of convexity given your cryptic remark "If it works go for it, but it does not always work. And to a local minimum. Lots  of tweaking needed." right?

It's very easy to check for yourself.
In this case it;s just a linear problem when I studied the non-TEX maths (in TEX you see immediately),
What about that broken link?
 
User avatar
outrun
Posts: 4573
Joined: January 1st, 1970, 12:00 am

Re: Which solver to use?

January 3rd, 2018, 6:51 pm

Its convex, .. because of least squares.

The link doesn't parse because the Wikipedia has () in the URL and this forum can't auto link that. It'll work if you copy paste the link if the address bar of your browser (at the top where it typically says http..)