ElasticNetRegression with FISTA/ISTA gives wrong coefficients: smooth_fg! does not scale the L2 penalty by n

Open
#187 0 comments 1 reaction 0 assignees View on GitHub

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

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 by n. This is correct.
  • smooth_fg! (src/glr/d_l2loss.jl:72 and src/glr/d_robust.jl:183) does not. Its gradient uses get_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

  1. In smooth_fg! for L2Loss and RobustLoss, scale the L2 penalty by n when scale_penalty_with_samples=true, as smooth_objective(glr, n) does.
  2. In smooth_gram_fg!, return θ'*XX*θ/2 - θ'*Xy plus the same scaled L2 penalty.
  3. Add tests:
    • the value from smooth_fg! and from smooth_gram_fg! equals the value from smooth_objective and smooth_gram_objective;
    • the scaled and unscaled elastic net fits above agree;
    • the gram and non-gram fits agree for lasso and for elastic net.

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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from JuliaAI/MLJLinearModels.jl

All issues in JuliaAI/MLJLinearModels.jl

Similar issues

More Julia issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.