These are chat archives for elemental/chat

11th
Mar 2017
Jack Poulson
@poulson
Mar 11 2017 07:27
Hurrah, the "regularization path" idea of the following paper seems to explain a fix for the forplan solution norms growing as precision increases: http://web.mat.bham.ac.uk/Y.Zhao/My%20publication/least-SIAM.pdf
the basic idea is to think of a Tikhonov-regularization that decreases as a function of the barrier parameter
Ryan H. Lewis
@rhl-
Mar 11 2017 15:56
?
Yay?
Jack Poulson
@poulson
Mar 11 2017 17:28
yes, starting with large Tikhonov and decreasing it as the IPM converges seems to stabilize the solver by leading to smaller norm solutions
Jack Poulson
@poulson
Mar 11 2017 17:41
e.g., it was previously the case that with 512-bit precision El::BigFloat, attempting to solve the netlib test LP forplan would lead to dual solution norms on the order of 10^71
now they are something like ~10^6 and all of the convergence problems went away
Ryan H. Lewis
@rhl-
Mar 11 2017 21:51
Yeah this is standard stuff
Check out sklearn
Jack Poulson
@poulson
Mar 11 2017 21:52
huh?
Tikhonov is standard, but I'm not sure how standard it is for people to discuss driving down the Tikhonov regularization as a function of the barrier parameter
Ryan H. Lewis
@rhl-
Mar 11 2017 22:08
Look up lasso path
And ridge path
In sklearn
And enet path
Jack Poulson
@poulson
Mar 11 2017 22:08
yes, I am aware of those
there is no barrier parameter
Ryan H. Lewis
@rhl-
Mar 11 2017 22:09
Oh I thought you meant the regularizing parameter
Oh, well, that's cool. Something about reusing data between IPMs
Jack Poulson
@poulson
Mar 11 2017 22:10
I mean that within a single IPM, it is extremely helpful as the barrier parameter is driven down to zero to set the Tikhonov regularization to be a function of the barrier parameter at said iteration
so the actual solution ends up being that of a small regularization parameter, but one might not have achieved convergence if the regularization parameter was small the entire time
as tiny regularization parameters allow giant solutions, but large regularization parameters potentially change the solution
so one can get the best of both worlds with such an approach and have a precise small-norm solution
Jack Poulson
@poulson
Mar 11 2017 22:18
the solution norms of LPs are unfortunately highly non-unique in general
Jack Poulson
@poulson
Mar 11 2017 23:11
hmm, picking the exact function seems a bit delicate if Delsarte bounds are also to be computed