QuantileRegressor unable to allocate memory for large datasets

[bharatkrishna]

Describe the bug

I am using sklearn.linear_model.QuantileRegressor for a dataset with ~2.9 million datapoints.
When I use it as follows, I get a memory error.

MemoryError: Unable to allocate 61.6 TiB for an array with shape (2909376, 2909376) and data type float64

When I do the same with statsmodel library, I don't encounter any issues.

Would this be a known limitation of the sklarn implementation? What would be the biggest size of dataframe it can take? Or is it a bug?

I was choosing to do it in sklearn rather than statsmodel because the sklearn API provides ability to add regularization which the other library doesn't.

Steps/Code to Reproduce

from sklearn.linear_model import QuantileRegressor
reg = QuantileRegressor(quantile=0.8).fit(X, y)

Expected Results

The data is fit without errors.

Actual Results

---------------------------------------------------------------------------
MemoryError                               Traceback (most recent call last)
/tmp/ipykernel_53907/1165686720.py in <module>
      1 from sklearn.linear_model import QuantileRegressor
      2 
----> 3 reg = QuantileRegressor(quantile=0.8).fit(X, y)
      4 print_analysis(reg, X, y, flyte_type)

/anaconda3/lib/python3.7/site-packages/sklearn/linear_model/_quantile.py in fit(self, X, y, sample_weight)
    239                     -np.ones((n_mask, 1)),
    240                     -X[mask],
--> 241                     np.eye(n_mask),
    242                     -np.eye(n_mask),
    243                 ],

/anaconda3/lib/python3.7/site-packages/numpy/lib/twodim_base.py in eye(N, M, k, dtype, order)
    197     if M is None:
    198         M = N
--> 199     m = zeros((N, M), dtype=dtype, order=order)
    200     if k >= M:
    201         return m

MemoryError: Unable to allocate 61.6 TiB for an array with shape (2909376, 2909376) and data type float64

Versions

System:
    python: 3.7.7 (default, Mar 26 2020, 15:48:22)  [GCC 7.3.0]
executable: /anaconda3/bin/python
   machine: Linux-4.14.68-4.14.3-amd64-3adf3675665129fa-x86_64-with-debian-stretch-sid

Python dependencies:
          pip: 21.2.2
   setuptools: 58.0.4
      sklearn: 1.0.1
        numpy: 1.19.2
        scipy: 1.5.2
       Cython: 0.29.25
       pandas: 1.2.4
   matplotlib: 3.5.0
       joblib: 1.1.0
threadpoolctl: 2.2.0

Built with OpenMP: True

[glemaitre]

Could you convert your data into sparse format and see if it would be more memory efficient when building these matrices.

[glemaitre]

The estimator does not use the same approach in scikit-learn and statsmodels: in scikit-learn we used a linear programming solver while statsmodels uses iterative reweighted least squares.

@agramfort @lorentzenchr what are the pros/cons of linear programming vs. IRLS?

[lorentzenchr]

Would this be a known limitation of the sklarn implementation?

For the time being: Yes.
As @glemaitre pointed out, if your data is sparse, it might help to work with sparse data only. Also, with newer scipy versions, you might want to use QuantileRegressor(solver="highs").

what are the pros/cons of linear programming vs. IRLS?

Linear quantile regression is a harder problem than OLS. The underlying optimization problem is a linear programming problem. As it is a non-smooth problem, any approach using gradients (and hessians) need to deal with this in some way which typical leads to less precise results.

[agramfort]

I just wrote a proof of concept IRLS solver at:

benchopt/benchmark_quantile_regression#4

you can see the benchmark result at:

https://benchopt.github.io/results/benchmark_quantile_regression_benchmark_quantile_regression_benchopt_run_2022-03-26_15h44m40.html

[bharatkrishna]

As @glemaitre pointed out, if your data is sparse, it might help to work with sparse data only.
My data has multiple columns.

X.shape
(2903970, 12)

I wouldn't say my data has too many 0s but it could have quite some number of them.

Also, with newer scipy versions, you might want to use QuantileRegressor(solver="highs").

I upgraded to scipy to 1.7.3 (since solver="highs" needed >=1.6.0) and I still get the same Unable to allocate memory error.

[glemaitre]

I propose to form a sparse matrix because we are going to create a sparse eye instead of a dense eye and thus not blow up the memory. I would try it even if your data are not sparse.

…

Sent from my iPhone

On 27 Mar 2022, at 04:05, Bharat Krishna ***@***.***> wrote:  As @glemaitre pointed out, if your data is sparse, it might help to work with sparse data only. My data has multiple columns. X.shape (2903970, 12) I wouldn't say my data has too many 0s but it could have quite some number of them. Also, with newer scipy versions, you might want to use QuantileRegressor(solver="highs"). I upgraded to scipy to 1.7.3 (since solver="highs" needed >=1.6.0) and I still get the same Unable to allocate memory error. — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you were mentioned.

[bharatkrishna]

I'm not entirely sure how to form a sparse matrix. This is what I tried:

sdf_X = X.astype(pd.SparseDtype("float", np.nan))
qr = QuantileRegressor(quantile=0.5, alpha=0.1, solver="highs")
qr.fit(sdf_X, y)

And it gave me the error:
TypeError: A sparse matrix was passed, but dense data is required. Use X.toarray() to convert to a dense numpy array.

Could someone guide me how to create a sparse matrix from my existing data, if the above is not the correct way to do it?

Following the suggestion in the error message, doing a toarray() didn't help.

qr.fit(sdf_X.toarray(), y)

This gave: AttributeError: 'DataFrame' object has no attribute 'toarray'.

[lorentzenchr]

from scipy import sparse

X_sparse = sparse.csc_matrix(X)

and then fit on X_sparse instead of X. This is only a hunch that is likely to fail, too - but worth a try.

[bharatkrishna]

Tried it and failed with the same TypeError:

X_sparse = sparse.csc_matrix(X)
qr = QuantileRegressor(quantile=0.5, alpha=0.1, solver="highs")
qr.fit(X_sparse, y)

TypeError: A sparse matrix was passed, but dense data is required. Use X.toarray() to convert to a dense numpy array.

[lorentzenchr]

@bharatkrishna Sparse data support for QuantileRegression comes in the upcoming release, see https://scikit-learn.org/dev/whats_new/v1.1.html.
In the meantime, you could install a nightly build, see https://scikit-learn.org/dev/developers/advanced_installation.html?highlight=nightly#installing-nightly-builds.

The original issue is not a bug of scikit-learn, but a known limitation. Therefore, I'll close.