optimize: Pass the problem dimension to getDefaultMethod() and use it there

[vladimir-ch]

No description provided.

[vladimir-ch]

I was thinking about using the dimension to decide whether BFGS or L-BFGS should be returned. What would be a suitable borderline value?

[btracey]

Somewhere between 10 and 10000? If the Hessian is basically stationary, and the problem is "small", then BFGS is much preferred. Once BFGS starts to take up a significant amount of the update time (due to the matrix multiplications), then LBFGS is preferred. In theory, if the hessian varies significantly, LBFGS is better because it can adapt to the changing hessian better. In practice, neural networks have a highly non-stationary Hessian, and I have not noticed much difference between the two. A reasonable plan may be to see where the computational time crossover is between BFGS and LBFGS. We still have some optimizations to make in BFGS (using srk2 and dsymv) which should have significant speedups.

[vladimir-ch]

Between 10 and 10000, nice :-) OK, let's wait until BFGS is optimized and then run some benchmarks.

[btracey]

Given that the range is the scope of "int", I think I narrowed it down quite a bit.

[vladimir-ch]

Has BFGS' use of symmetric matrices been already optimized? Running a small comparison between BFGS and LBFGS gives this:

Dim:    10, BFGS:        94.627µs (20), LBFGS:        61.527µs (20)
Dim:    20, BFGS:       258.911µs (26), LBFGS:         60.82µs (26)
Dim:    30, BFGS:       677.251µs (29), LBFGS:          91.5µs (29)
Dim:    40, BFGS:      1.158941ms (31), LBFGS:       112.179µs (31)
Dim:    50, BFGS:      1.827951ms (33), LBFGS:       134.843µs (33)
Dim:    60, BFGS:      2.626826ms (34), LBFGS:       148.206µs (34)
Dim:    70, BFGS:      3.639132ms (35), LBFGS:       240.221µs (35)
Dim:    80, BFGS:      4.778698ms (36), LBFGS:       202.861µs (36)
Dim:    90, BFGS:      6.130425ms (37), LBFGS:        216.07µs (37)
Dim:   100, BFGS:      7.799486ms (38), LBFGS:       238.968µs (38)
Dim:   200, BFGS:     34.148876ms (43), LBFGS:       448.894µs (43)
Dim:   300, BFGS:      82.53817ms (46), LBFGS:       694.344µs (46)
Dim:   400, BFGS:    156.652703ms (48), LBFGS:      1.359277ms (48)
Dim:   500, BFGS:    273.878261ms (51), LBFGS:      1.233659ms (51)

Objective function is functions.VariablyDimensioned which is nice because both BFGS and LBFGS need exactly the same number of function evaluations (the number in parentheses).

[btracey]

Is that with cblas or native? The BFGS code has been optimized as far as it is concerned, though some of the routines are slower than they could be in native. I'd guess the right number is somewhere in the 10-30 range, as beyond that the memory requirements go up significantly (and it doesn't seem like speed is much different at the small scales)

[vladimir-ch]

That was with native. With OpenBLAS the number are like this:

Dim:    10, BFGS:       151.359µs (20), LBFGS:        59.928µs (20)
Dim:    20, BFGS:       279.296µs (26), LBFGS:        57.422µs (26)
Dim:    30, BFGS:       665.442µs (29), LBFGS:        85.797µs (29)
Dim:    40, BFGS:      1.109582ms (31), LBFGS:       117.449µs (31)
Dim:    50, BFGS:      1.720677ms (33), LBFGS:       129.995µs (33)
Dim:    60, BFGS:      2.433621ms (34), LBFGS:       149.964µs (34)
Dim:    70, BFGS:      3.341203ms (35), LBFGS:       187.494µs (35)
Dim:    80, BFGS:      4.994706ms (36), LBFGS:       205.709µs (36)
Dim:    90, BFGS:      5.673993ms (37), LBFGS:       213.211µs (37)
Dim:   100, BFGS:      7.146321ms (38), LBFGS:       244.066µs (38)
Dim:   200, BFGS:      31.30622ms (43), LBFGS:       487.792µs (43)
Dim:   300, BFGS:     76.301817ms (46), LBFGS:       686.751µs (46)
Dim:   400, BFGS:    145.283187ms (48), LBFGS:       953.991µs (48)
Dim:   500, BFGS:    235.555473ms (51), LBFGS:      1.223314ms (51)

I hope that I did it right because the numbers are almost the same (ok, slightly lower with OpenBLAS). I think that it would be useful if blas/README.md included a simple example on how to use it and how to switch between various implementations. What I did:

package main
import (
    "github.com/gonum/blas/blas64"
    "github.com/gonum/blas/cgo"
)
func init() {
    blas64.Use(cgo.Implementation{})
}
func main() {...}

That's correct, isn't it?

[vladimir-ch]

So what about 20?

[kortschak]

Yes, that is correct.