ElasticNetRegression with FISTA/ISTA gives wrong coefficients: smooth_fg! does not scale the L2 penalty by n
Nobody has claimed this yet.
Assessment
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Newbie friendliness
- 78/100
- Issue type
- Bug
- Clarity
- Clearly specified
- Activity status
- Active
- Tech stack
- julia
- Domain
- machine-learning
Research direction
Start with smooth_fg! in src/glr/d_l2loss.jl and src/glr/d_robust.jl, comparing their returned values with smooth_objective in src/glr/utils.jl. Then inspect smooth_gram_fg! in src/glr/d_l2loss.jl and the ProxGrad path in src/fit/proxgrad.jl. Add tests for matching objective values and for scaled/unscaled and gram/non-gram fits producing the same coefficients.
Written by the indexing model from the issue text.
Description
Problem
ElasticNetRegression with FISTA() or ISTA() stops early with a backtracking warning and gives wrong coefficients. This happens with the default scale_penalty_with_samples=true. LassoRegression is not affected.
Cause
In each iteration, ProxGrad compares two values of the smooth objective to find a step size:
smooth_objective(glr, n)(src/glr/utils.jl:38) multiplies the L2 penalty byn. This is correct.smooth_fg!(src/glr/d_l2loss.jl:72andsrc/glr/d_robust.jl:183) does not. Its gradient usesget_penalty_scale_l2, so the gradient is correct and only the value is wrong.
The two values disagree, so the backtracking condition is true at every step size, and the solver hits max_inner and stops.
ProxGrad implements FISTA with backtracking from Beck and Teboulle (2009), section 4, and cites page 193 in src/fit/proxgrad.jl:40-43. The backtracking test is F(p_L(y)) ≤ Q_L(p_L(y), y), with Q_L(x, y) = f(y) + ⟨x - y, ∇f(y)⟩ + (L/2)|x - y|² + g(x). The test needs f(y) and ∇f(y) from the same function f. Here ∇f(y) is the gradient of the scaled objective, f(y) is the value of the unscaled objective, and F(p_L(y)) comes from smooth_objective and is scaled. So Q_L is too low by (n - 1)·λ|y|²/2, and the test never passes.
Commit c130543a added scale_penalty_with_samples and scaled the gradient and smooth_objective, but not the return value of smooth_fg!. #112 fixed the L1 side of ProxGrad for the same flag; its test uses a lasso, which has no L2 term, so it could not catch this.
Affected models
| Model | Affected |
|---|---|
LassoRegression |
No. It has no L2 penalty. |
ElasticNetRegression |
Yes, with the default scale_penalty_with_samples=true |
Robust regression with penalty=:en (for example HuberRegression) |
Yes, with the default |
Any model with scale_penalty_with_samples=false |
No |
LogisticRegression with :l1 or :en |
No. Its smooth_fg! goes through fgh!, which scales the value. |
Reproduction
The two models below have the same objective, so they must give the same coefficients.
using MLJLinearModels, Random
Random.seed!(0)
n, p = 1_000, 5
X = randn(n, p)
y = X * randn(p) .+ 0.1 .* randn(n)
a = fit(ElasticNetRegression(0.3, 0.5), X, y; solver=FISTA())
b = fit(ElasticNetRegression(0.3n, 0.5n; scale_penalty_with_samples=false), X, y; solver=FISTA())
println("scaled : ", round.(a; digits=4))
println("unscaled : ", round.(b; digits=4))
Output on Julia 1.10.2, dev at 1071e68:
┌ Warning: No appropriate stepsize found via backtracking; interrupting. The reason could be input data that is not standardized.
└ @ MLJLinearModels src/fit/proxgrad.jl:59
┌ Warning: Proximal GD did not converge in 1000 iterations.
└ @ MLJLinearModels src/fit/proxgrad.jl:73
scaled : [-0.0, -0.0, -0.0, -0.8226, -0.0, -0.0359]
unscaled : [-0.0, -0.0, -0.0, -0.8448, -0.0, -0.0246]
The value mismatch is direct to check:
const R = MLJLinearModels
glr = ElasticNetRegression(0.3, 0.5)
fg! = R.smooth_fg!(glr, X, y, R.scratch(X; i=true))
f = R.smooth_objective(glr, X, y)
θ = randn(p + 1)
fg!(similar(θ), θ), f(θ) # (3156.6, 3493.7); equal with scale_penalty_with_samples=false
A finite-difference check shows the gradient from smooth_fg! matches smooth_objective to 1.6e-6, and does not match the value that smooth_fg! returns. So the gradient is right and the value is wrong.
A second defect in smooth_gram_fg!
smooth_gram_fg! (src/glr/d_l2loss.jl:81) returns θ'*_g, which is θ'XXθ - θ'Xy. smooth_gram_objective returns θ'XXθ/2 - θ'Xy. So the value is too high by θ'XXθ/2. It also does not scale the L2 penalty by n. This affects gram=true for lasso and for elastic net, also with scale_penalty_with_samples=false.
With a correct value, the gram and non-gram objectives differ only by the constant |y|²/2, so FISTA must give identical iterates on both paths. On 20 random problems (n=500, p=8, fit_intercept=false, column scales between 1 and 2):
| Model | Current gram fit vs non-gram fit | Fixed gram fit vs non-gram fit |
|---|---|---|
LassoRegression(0.5) |
Higher objective in 2 of 20 seeds | Identical to 1e-16 in 20 of 20 |
ElasticNetRegression(0.3, 0.5; scale_penalty_with_samples=false) |
Diverges to Inf in 3 of 20 seeds |
Identical to 1e-16 in 20 of 20 |
This is the same backtracking test with the sign reversed. f(y) is too high by y'XXy/2, so Q_L is too high, the test never fires, and the step size does not shrink when it must. The momentum steps then blow up.
Fix
- In
smooth_fg!forL2LossandRobustLoss, scale the L2 penalty bynwhenscale_penalty_with_samples=true, assmooth_objective(glr, n)does. - In
smooth_gram_fg!, returnθ'*XX*θ/2 - θ'*Xyplus the same scaled L2 penalty. - Add tests:
- the value from
smooth_fg!and fromsmooth_gram_fg!equals the value fromsmooth_objectiveandsmooth_gram_objective; - the scaled and unscaled elastic net fits above agree;
- the gram and non-gram fits agree for lasso and for elastic net.
- the value from
I have a fix ready and can open a PR. Related: #140 asks for more ProxGrad test coverage.
Reference
Beck, A. and Teboulle, M. (2009). "A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems." SIAM Journal on Imaging Sciences 2(1), 183–202. https://doi.org/10.1137/080716542
- Dominant language
- Julia
- Stars
- 86
- Forks
- 16
- PR merge metrics
- No merged PRs in 30d
Getting set up
This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from JuliaAI/MLJLinearModels.jl
-
Difficulty 4/5 3-5 days Newbie friendliness 58/100
JuliaAI/MLJLinearModels.jl#180 ·
-
help wanted
Difficulty 5/5 Over a week Newbie friendliness 25/100
JuliaAI/MLJLinearModels.jl#163 · 4 comments ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 45/100
JuliaAI/MLJLinearModels.jl#160 · 1 comment ·
-
Difficulty 3/5 1-2 days Newbie friendliness 42/100
JuliaAI/MLJLinearModels.jl#159 · 3 comments ·
-
multiobjective OLSOpen
Difficulty 5/5 Over a week Newbie friendliness 25/100
JuliaAI/MLJLinearModels.jl#157 ·
All issues in JuliaAI/MLJLinearModels.jl
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 79/100
Sienna-Platform/PowerSimulations.jl#1737 ·
Maintainers usually reply within 4 days
-
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
FluxML/Optimisers.jl#254 ·
-
Minor: floodplain warning percentage, scalar output error message and a never-true identity checkOpenbug
Difficulty 2/5 1-3 hours Newbie friendliness 82/100
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
JuliaAI/MLJTransforms.jl#101 ·
Maintainers usually reply within 1 day
-
@contents blocks fail to render on Julia 1.14Possibly taken @sbfnk claimed this 1 day ago. Open
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
LuxDL/DocumenterVitepress.jl#410 ·