the very big difference is in allocations: this is due to the fact that
A and b are not scaled in-place in IndAffine
but of course in that case one is modifying user-provided data
I'll try to see if I can find the problematic example
note that the docs automatically deploy: each time something is pushed to
master (or merged) then one of the Travis processes writes the compiled docs on the gh-pages branch upon test completion
also: the “stable” version of the docs keeps track of the last tagged commit, while the “latest” refers to what’s currently on
master
(so for now the “stable” one is not there: we will create a new tag very soon I guess)
The vector is supposed to store the off-diagonal elements multiplied with sqrt(2) if we want it to be compatible with for example Convex.jl and MathProgBase
This means that we have to multiply all off-diagonal elements by 1/sqrt(2) before we treat the elements as elements of a matrix, i.e. in prox_naive the line
X, v = prox_naive(f, Symmetric(X), gamma)should be replaced by
#scale off-diagonal by 1/sqrt(2)
X, v = prox_naive(f, Symmetric(X), gamma)
#scale off-diagonal by sqrt(2)or equivalently (more efficient), working with sqrt(2)*X and scaling back
for i = 1:n
X[i,i] .*= sqrt(2)
end
X, v = prox_naive(f, Symmetric(X), gamma)
for i = 1:n
X[i,i] ./= sqrt(2)
end
you’re right
let’s see if we can find a more modular way to do all this though
because a long list of dictionaries is not really handy :D
as long as we test with prox_test, we could add additional functionality in prox_test that benchmarks and logs for example
- for a given function
fand inputx, computef(x),y = prox(f, x)(andgfx = gradient(f, x)if defined) and verify that they satisfy some prescribed properties
prescribed properties can be whatever
y being equal to some point, f(x) or f(y) having some value
or
y satisfying some optimality condition (approximately)
now for each constructor one should be able to describe the whole suite of test cases
in a modular way, and then have a script run through the union of all suits of test cases
So one it become modular, but still uses common framework functions like
prox_test and etc
"one" was a type :smile:
Typo...
Possibly, the randomization is different, so the complex matrix generated in linux is different. But anyway - the
f(prox(f,c)) == Inf which is not good
I was looking at the paper Giselsson et al. (2016) where a line search is suggested for the ADMM algorithm. I would be very interested to see an example of how this is implemented, for example in the ADMM lasso. It looks straightforward, but there are some sign differences compared to the example here that I don't understand. Does Mattias have any code available?
I will take a look and see if I have any code ready for that line search. My plan is that this and other things will be available in https://github.com/mfalt/FirstOrderSolvers.jl if it is not already.
But that package is currently under development
@patwa67 I don't think there is a good implementation out there yet, but it is worth mentioning that the article is mainly about presenting the possibility of doing line search, is is not necessarily best to do line search in the residual direction as proposed. We are still trying to evaluate what the best way to do it is. I'm happy to anwer any questions though. Also, take a look at the SuperMann algorithm, another way of doing line search with Quasi-Newton directions:
https://arxiv.org/abs/1609.06955
I have one implementation here:
https://github.com/mfalt/FirstOrderSolvers.jl/blob/supermann/src/solvers/supermann.jl
but it is not tested properly (the whole package is under development, and this is on a separate branch)
https://arxiv.org/abs/1609.06955
I have one implementation here:
https://github.com/mfalt/FirstOrderSolvers.jl/blob/supermann/src/solvers/supermann.jl
but it is not tested properly (the whole package is under development, and this is on a separate branch)
I have used the following code for the ADMM lasso:
#Line search
c = 0.5
lr = 1.0
loss(z) = 0.5*norm(A*z-b)^2
grad = A'*(A*x-b)
while loss(z) > (loss(x) + grad'*(-x) + (1.0/(2.0*lr))*norm(-x)^2)
lr = lr * c
println(lr)
endIt seems to work, but I don't know if it is theoretically correct. It is based on the Armijo rule for projected gradient ideas in Bertsekas (2016).