Talip7/scikit-learn-issues-multilabel huggingface dataset:
Formula for dual gap of elastic net in coordinate descent solver

### Describe the bug
The computation of the dual gap for the elastic net in the coordinate descent solver (`enet_coordinate_descent`) might be wrong.

The elastic net minimizes
```
Primal(w) = (1/2) * ||y - X w||_2^2 + alpha * ||w||_1 + beta/2 * ||w||_2^2
```

### Lasso
For the pure Lasso, i.e. `beta=0`, the dual becomes [1]
```
Dual(nu) = -1/2 * ||nu||_2^2 - nu'y   if ||X'nu||_∞ = max(abs(X'nu)) <= alpha   else -∞
```
with `nu = Xw - y` (=minus the residual `R`) as possible dual point. This yields the Lasso dual gap
```
Primal(w) - Dual(nu)
```
In case of `||X'nu||_∞ > alpha`, one uses a down-scaled variable `nu` in the dual.

### Elastic Net
For the elastic net, the dual, see section 5.2.3 in [2], becomes
```
Dual(nu) = -1/2 * ||nu||_2^2 - nu'y - 1/(2*beta) * sum_j (|X_j'nu| - alpha)_+^2
```
with `X_j` the j-th column of `X` and `x_+ = max(0, x)` the positive part.

### References
[1] Kim, Seung-Jean et al. “An Interior-Point Method for Large-Scale $\ell_1$-Regularized Least Squares.” IEEE Journal of Selected Topics in Signal Processing 1 (2007): 606-617. [pdf link](http://stanford.edu/~boyd/papers/pdf/l1_ls.pdf)
[2] Mendler-Dünner, Celestine et al. “Primal-Dual Rates and Certificates.” ICML (2016). [arxiv link](https://arxiv.org/pdf/1602.05205.pdf)

### Expected Results

```python
if beta > =0:
    R = y - X @ w  # note: R = -nu
    R_norm2 = R @ R
    gap = R_norm2 - R @ y + alpha * l1_norm + beta/2 * l2_norm
    gap += 1/(2*beta) * np.sum(np.max(0, np.abs(X.T @ R) - alpha)**2)
```
At least a test for it, similar to the pure Lasso case in https://github.com/scikit-learn/scikit-learn/blob/2c2f31d68c21b7647557b2f776e86c05954d80bf/sklearn/linear_model/tests/test_coordinate_descent.py#L292

### Actual Results

I start to be rattled by the `-beta * w` term in line 205.
https://github.com/scikit-learn/scikit-learn/blob/2c2f31d68c21b7647557b2f776e86c05954d80bf/sklearn/linear_model/_cd_fast.pyx#L205-L236

COMMENT:
Beware when you see the blue curve suddenly dropping at the end (`figures[-2]`), it is because the solver did not converge and we infer the optimal value as `np.min(primals)`. Also I'd feel safer if the code I wrote was proofread.
  
Yes it makes sense to take the highest dual objective across formulations, as you say the cost of computation is that of `X.T @ R` which can be reused from one formulation to the other.

What is new to me is that the yellow curve seems to have the same slope as the primal subopt (with a fixed offset in log scale), while the green one starts roughly at the same point but with a weaker slope (as I am very used to seeing for the Lasso, i.e. Fig 2 in https://arxiv.org/pdf/1802.07481.pdf)

Labels: Bug, module:linear_model
Formula for dual gap of elastic net in coordinate descent solver

### Describe the bug
The computation of the dual gap for the elastic net in the coordinate descent solver (`enet_coordinate_descent`) might be wrong.

The elastic net minimizes
```
Primal(w) = (1/2) * ||y - X w||_2^2 + alpha * ||w||_1 + beta/2 * ||w||_2^2
```

### Lasso
For the pure Lasso, i.e. `beta=0`, the dual becomes [1]
```
Dual(nu) = -1/2 * ||nu||_2^2 - nu'y   if ||X'nu||_∞ = max(abs(X'nu)) <= alpha   else -∞
```
with `nu = Xw - y` (=minus the residual `R`) as possible dual point. This yields the Lasso dual gap
```
Primal(w) - Dual(nu)
```
In case of `||X'nu||_∞ > alpha`, one uses a down-scaled variable `nu` in the dual.

### Elastic Net
For the elastic net, the dual, see section 5.2.3 in [2], becomes
```
Dual(nu) = -1/2 * ||nu||_2^2 - nu'y - 1/(2*beta) * sum_j (|X_j'nu| - alpha)_+^2
```
with `X_j` the j-th column of `X` and `x_+ = max(0, x)` the positive part.

### References
[1] Kim, Seung-Jean et al. “An Interior-Point Method for Large-Scale $\ell_1$-Regularized Least Squares.” IEEE Journal of Selected Topics in Signal Processing 1 (2007): 606-617. [pdf link](http://stanford.edu/~boyd/papers/pdf/l1_ls.pdf)
[2] Mendler-Dünner, Celestine et al. “Primal-Dual Rates and Certificates.” ICML (2016). [arxiv link](https://arxiv.org/pdf/1602.05205.pdf)

### Expected Results

```python
if beta > =0:
    R = y - X @ w  # note: R = -nu
    R_norm2 = R @ R
    gap = R_norm2 - R @ y + alpha * l1_norm + beta/2 * l2_norm
    gap += 1/(2*beta) * np.sum(np.max(0, np.abs(X.T @ R) - alpha)**2)
```
At least a test for it, similar to the pure Lasso case in https://github.com/scikit-learn/scikit-learn/blob/2c2f31d68c21b7647557b2f776e86c05954d80bf/sklearn/linear_model/tests/test_coordinate_descent.py#L292

### Actual Results

I start to be rattled by the `-beta * w` term in line 205.
https://github.com/scikit-learn/scikit-learn/blob/2c2f31d68c21b7647557b2f776e86c05954d80bf/sklearn/linear_model/_cd_fast.pyx#L205-L236

COMMENT:
> Also I'd feel safer if the code I wrote was proofread.

I did and checked results with `ElasticNet` and `enet_coordinate_descent`. Looks good.

Labels: Bug, module:linear_model
Formula for dual gap of elastic net in coordinate descent solver

### Describe the bug
The computation of the dual gap for the elastic net in the coordinate descent solver (`enet_coordinate_descent`) might be wrong.

The elastic net minimizes
```
Primal(w) = (1/2) * ||y - X w||_2^2 + alpha * ||w||_1 + beta/2 * ||w||_2^2
```

### Lasso
For the pure Lasso, i.e. `beta=0`, the dual becomes [1]
```
Dual(nu) = -1/2 * ||nu||_2^2 - nu'y   if ||X'nu||_∞ = max(abs(X'nu)) <= alpha   else -∞
```
with `nu = Xw - y` (=minus the residual `R`) as possible dual point. This yields the Lasso dual gap
```
Primal(w) - Dual(nu)
```
In case of `||X'nu||_∞ > alpha`, one uses a down-scaled variable `nu` in the dual.

### Elastic Net
For the elastic net, the dual, see section 5.2.3 in [2], becomes
```
Dual(nu) = -1/2 * ||nu||_2^2 - nu'y - 1/(2*beta) * sum_j (|X_j'nu| - alpha)_+^2
```
with `X_j` the j-th column of `X` and `x_+ = max(0, x)` the positive part.

### References
[1] Kim, Seung-Jean et al. “An Interior-Point Method for Large-Scale $\ell_1$-Regularized Least Squares.” IEEE Journal of Selected Topics in Signal Processing 1 (2007): 606-617. [pdf link](http://stanford.edu/~boyd/papers/pdf/l1_ls.pdf)
[2] Mendler-Dünner, Celestine et al. “Primal-Dual Rates and Certificates.” ICML (2016). [arxiv link](https://arxiv.org/pdf/1602.05205.pdf)

### Expected Results

```python
if beta > =0:
    R = y - X @ w  # note: R = -nu
    R_norm2 = R @ R
    gap = R_norm2 - R @ y + alpha * l1_norm + beta/2 * l2_norm
    gap += 1/(2*beta) * np.sum(np.max(0, np.abs(X.T @ R) - alpha)**2)
```
At least a test for it, similar to the pure Lasso case in https://github.com/scikit-learn/scikit-learn/blob/2c2f31d68c21b7647557b2f776e86c05954d80bf/sklearn/linear_model/tests/test_coordinate_descent.py#L292

### Actual Results

I start to be rattled by the `-beta * w` term in line 205.
https://github.com/scikit-learn/scikit-learn/blob/2c2f31d68c21b7647557b2f776e86c05954d80bf/sklearn/linear_model/_cd_fast.pyx#L205-L236

COMMENT:
It seems that when the unrestricted formulation is bad, the "L2" term dominates, i.e. `sum_j (|X_j'nu| - alpha)_+^2`. This is particular true at the first iterations when most coefficients are still zero such that `nu=R~y`.
If the unrestricted fomulation gives tighter bounds, then the `||y+nu||_2` is smaller than the `||y+nu/scale||` term of the restricted formulation.

Labels: Bug, module:linear_model
Formula for dual gap of elastic net in coordinate descent solver

### Describe the bug
The computation of the dual gap for the elastic net in the coordinate descent solver (`enet_coordinate_descent`) might be wrong.

The elastic net minimizes
```
Primal(w) = (1/2) * ||y - X w||_2^2 + alpha * ||w||_1 + beta/2 * ||w||_2^2
```

### Lasso
For the pure Lasso, i.e. `beta=0`, the dual becomes [1]
```
Dual(nu) = -1/2 * ||nu||_2^2 - nu'y   if ||X'nu||_∞ = max(abs(X'nu)) <= alpha   else -∞
```
with `nu = Xw - y` (=minus the residual `R`) as possible dual point. This yields the Lasso dual gap
```
Primal(w) - Dual(nu)
```
In case of `||X'nu||_∞ > alpha`, one uses a down-scaled variable `nu` in the dual.

### Elastic Net
For the elastic net, the dual, see section 5.2.3 in [2], becomes
```
Dual(nu) = -1/2 * ||nu||_2^2 - nu'y - 1/(2*beta) * sum_j (|X_j'nu| - alpha)_+^2
```
with `X_j` the j-th column of `X` and `x_+ = max(0, x)` the positive part.

### References
[1] Kim, Seung-Jean et al. “An Interior-Point Method for Large-Scale $\ell_1$-Regularized Least Squares.” IEEE Journal of Selected Topics in Signal Processing 1 (2007): 606-617. [pdf link](http://stanford.edu/~boyd/papers/pdf/l1_ls.pdf)
[2] Mendler-Dünner, Celestine et al. “Primal-Dual Rates and Certificates.” ICML (2016). [arxiv link](https://arxiv.org/pdf/1602.05205.pdf)

### Expected Results

```python
if beta > =0:
    R = y - X @ w  # note: R = -nu
    R_norm2 = R @ R
    gap = R_norm2 - R @ y + alpha * l1_norm + beta/2 * l2_norm
    gap += 1/(2*beta) * np.sum(np.max(0, np.abs(X.T @ R) - alpha)**2)
```
At least a test for it, similar to the pure Lasso case in https://github.com/scikit-learn/scikit-learn/blob/2c2f31d68c21b7647557b2f776e86c05954d80bf/sklearn/linear_model/tests/test_coordinate_descent.py#L292

### Actual Results

I start to be rattled by the `-beta * w` term in line 205.
https://github.com/scikit-learn/scikit-learn/blob/2c2f31d68c21b7647557b2f776e86c05954d80bf/sklearn/linear_model/_cd_fast.pyx#L205-L236

COMMENT:
I think this still fails for `alpha=0, beta>0` (i.e. when `l1_ratio=0`). In this case, because `const=0` [here](https://github.com/scikit-learn/scikit-learn/blob/02e09e3d10c635094a88db41bede022106d9da48/sklearn/linear_model/_cd_fast.pyx#L239) `gap` is 0.5 * ((R**2).sum() + beta * (w**2).sum()). Or am I misreading the code?

 I also don't think the "stacking" trick works properly for `alpha=0`. Because in this case (using the same Lagrangian function) the dual function is infinite unless `np.allclose(X.T.dot(R),0)` so there are no meaningful lower bounds for inexact solutions.

Labels: Bug, module:linear_model
Formula for dual gap of elastic net in coordinate descent solver

### Describe the bug
The computation of the dual gap for the elastic net in the coordinate descent solver (`enet_coordinate_descent`) might be wrong.

The elastic net minimizes
```
Primal(w) = (1/2) * ||y - X w||_2^2 + alpha * ||w||_1 + beta/2 * ||w||_2^2
```

### Lasso
For the pure Lasso, i.e. `beta=0`, the dual becomes [1]
```
Dual(nu) = -1/2 * ||nu||_2^2 - nu'y   if ||X'nu||_∞ = max(abs(X'nu)) <= alpha   else -∞
```
with `nu = Xw - y` (=minus the residual `R`) as possible dual point. This yields the Lasso dual gap
```
Primal(w) - Dual(nu)
```
In case of `||X'nu||_∞ > alpha`, one uses a down-scaled variable `nu` in the dual.

### Elastic Net
For the elastic net, the dual, see section 5.2.3 in [2], becomes
```
Dual(nu) = -1/2 * ||nu||_2^2 - nu'y - 1/(2*beta) * sum_j (|X_j'nu| - alpha)_+^2
```
with `X_j` the j-th column of `X` and `x_+ = max(0, x)` the positive part.

### References
[1] Kim, Seung-Jean et al. “An Interior-Point Method for Large-Scale $\ell_1$-Regularized Least Squares.” IEEE Journal of Selected Topics in Signal Processing 1 (2007): 606-617. [pdf link](http://stanford.edu/~boyd/papers/pdf/l1_ls.pdf)
[2] Mendler-Dünner, Celestine et al. “Primal-Dual Rates and Certificates.” ICML (2016). [arxiv link](https://arxiv.org/pdf/1602.05205.pdf)

### Expected Results

```python
if beta > =0:
    R = y - X @ w  # note: R = -nu
    R_norm2 = R @ R
    gap = R_norm2 - R @ y + alpha * l1_norm + beta/2 * l2_norm
    gap += 1/(2*beta) * np.sum(np.max(0, np.abs(X.T @ R) - alpha)**2)
```
At least a test for it, similar to the pure Lasso case in https://github.com/scikit-learn/scikit-learn/blob/2c2f31d68c21b7647557b2f776e86c05954d80bf/sklearn/linear_model/tests/test_coordinate_descent.py#L292

### Actual Results

I start to be rattled by the `-beta * w` term in line 205.
https://github.com/scikit-learn/scikit-learn/blob/2c2f31d68c21b7647557b2f776e86c05954d80bf/sklearn/linear_model/_cd_fast.pyx#L205-L236

COMMENT:
Using a  Lagrangian from this constrained problem always (i.e. regardless of whether or not alpha,beta is 0) gives non-trivial lower bounds

minimize_(w,v subject to v=Xw) 0.5 * \|y-v\|^2_2 + \alpha \|w\|_1 + 0.5 * \beta \|w\|^2_2

The Lagrangian with dual variable r is

L(w,v;r) = 0.5 * \|y-v\|^2_2 + \alpha \|w\|_1 + 0.5 * \beta \|w\|^2_2 + r'(v-Xw)

When \beta > 0, any `r` gives a non-trivial bound.

Labels: Bug, module:linear_model
Formula for dual gap of elastic net in coordinate descent solver

### Describe the bug
The computation of the dual gap for the elastic net in the coordinate descent solver (`enet_coordinate_descent`) might be wrong.

The elastic net minimizes
```
Primal(w) = (1/2) * ||y - X w||_2^2 + alpha * ||w||_1 + beta/2 * ||w||_2^2
```

### Lasso
For the pure Lasso, i.e. `beta=0`, the dual becomes [1]
```
Dual(nu) = -1/2 * ||nu||_2^2 - nu'y   if ||X'nu||_∞ = max(abs(X'nu)) <= alpha   else -∞
```
with `nu = Xw - y` (=minus the residual `R`) as possible dual point. This yields the Lasso dual gap
```
Primal(w) - Dual(nu)
```
In case of `||X'nu||_∞ > alpha`, one uses a down-scaled variable `nu` in the dual.

### Elastic Net
For the elastic net, the dual, see section 5.2.3 in [2], becomes
```
Dual(nu) = -1/2 * ||nu||_2^2 - nu'y - 1/(2*beta) * sum_j (|X_j'nu| - alpha)_+^2
```
with `X_j` the j-th column of `X` and `x_+ = max(0, x)` the positive part.

### References
[1] Kim, Seung-Jean et al. “An Interior-Point Method for Large-Scale $\ell_1$-Regularized Least Squares.” IEEE Journal of Selected Topics in Signal Processing 1 (2007): 606-617. [pdf link](http://stanford.edu/~boyd/papers/pdf/l1_ls.pdf)
[2] Mendler-Dünner, Celestine et al. “Primal-Dual Rates and Certificates.” ICML (2016). [arxiv link](https://arxiv.org/pdf/1602.05205.pdf)

### Expected Results

```python
if beta > =0:
    R = y - X @ w  # note: R = -nu
    R_norm2 = R @ R
    gap = R_norm2 - R @ y + alpha * l1_norm + beta/2 * l2_norm
    gap += 1/(2*beta) * np.sum(np.max(0, np.abs(X.T @ R) - alpha)**2)
```
At least a test for it, similar to the pure Lasso case in https://github.com/scikit-learn/scikit-learn/blob/2c2f31d68c21b7647557b2f776e86c05954d80bf/sklearn/linear_model/tests/test_coordinate_descent.py#L292

### Actual Results

I start to be rattled by the `-beta * w` term in line 205.
https://github.com/scikit-learn/scikit-learn/blob/2c2f31d68c21b7647557b2f776e86c05954d80bf/sklearn/linear_model/_cd_fast.pyx#L205-L236

COMMENT:
Shouldn't  ElasticNet.fit() raise a warning or an error saying to use RidgeRegression when `l1_ratio` is equal to 0 ?

Labels: Bug, module:linear_model
Formula for dual gap of elastic net in coordinate descent solver

### Describe the bug
The computation of the dual gap for the elastic net in the coordinate descent solver (`enet_coordinate_descent`) might be wrong.

The elastic net minimizes
```
Primal(w) = (1/2) * ||y - X w||_2^2 + alpha * ||w||_1 + beta/2 * ||w||_2^2
```

### Lasso
For the pure Lasso, i.e. `beta=0`, the dual becomes [1]
```
Dual(nu) = -1/2 * ||nu||_2^2 - nu'y   if ||X'nu||_∞ = max(abs(X'nu)) <= alpha   else -∞
```
with `nu = Xw - y` (=minus the residual `R`) as possible dual point. This yields the Lasso dual gap
```
Primal(w) - Dual(nu)
```
In case of `||X'nu||_∞ > alpha`, one uses a down-scaled variable `nu` in the dual.

### Elastic Net
For the elastic net, the dual, see section 5.2.3 in [2], becomes
```
Dual(nu) = -1/2 * ||nu||_2^2 - nu'y - 1/(2*beta) * sum_j (|X_j'nu| - alpha)_+^2
```
with `X_j` the j-th column of `X` and `x_+ = max(0, x)` the positive part.

### References
[1] Kim, Seung-Jean et al. “An Interior-Point Method for Large-Scale $\ell_1$-Regularized Least Squares.” IEEE Journal of Selected Topics in Signal Processing 1 (2007): 606-617. [pdf link](http://stanford.edu/~boyd/papers/pdf/l1_ls.pdf)
[2] Mendler-Dünner, Celestine et al. “Primal-Dual Rates and Certificates.” ICML (2016). [arxiv link](https://arxiv.org/pdf/1602.05205.pdf)

### Expected Results

```python
if beta > =0:
    R = y - X @ w  # note: R = -nu
    R_norm2 = R @ R
    gap = R_norm2 - R @ y + alpha * l1_norm + beta/2 * l2_norm
    gap += 1/(2*beta) * np.sum(np.max(0, np.abs(X.T @ R) - alpha)**2)
```
At least a test for it, similar to the pure Lasso case in https://github.com/scikit-learn/scikit-learn/blob/2c2f31d68c21b7647557b2f776e86c05954d80bf/sklearn/linear_model/tests/test_coordinate_descent.py#L292

### Actual Results

I start to be rattled by the `-beta * w` term in line 205.
https://github.com/scikit-learn/scikit-learn/blob/2c2f31d68c21b7647557b2f776e86c05954d80bf/sklearn/linear_model/_cd_fast.pyx#L205-L236

COMMENT:
Not sure why it should raise a warning. Coordinate descent works fine on this problem (it's strongly convex). Also, the issue raises a huge number of warnings in the `ElasticNet.path`. For a single value, sure `RidgeRegression` is fine. 

I guess my point is that the solver is not necessarily failing, it is the convergence check that is failing. There are other valid dual problems that would work fine, it's just this trick of using a dual from writing an ENet with `l1_ratio>0` fails here because the dual function is infinite unless X'r==0.

Labels: Bug, module:linear_model
Change how KNeighborsClassifier handles tiebreakers

### Describe the workflow you want to enable

I see that KNeighborsClassifier handles tiebreakers by taking the mode of the classes contained with the tie. What about using the sum of the distances as the tiebreaker instead (of using the mode.)

I feel that taking the least sum of distances is a better educated guess with minimal changes to the code.

### Describe your proposed solution

Create two dictionaries to keep a count of the Class count and the sum of Class distances.
If there is no tie return the Class value that won the vote (as normal).
If there is a tie return the Class that has the minimum sum of distances (instead of what scipy.stats.mode yields which I believe will always be the smallest Class value from the Classes within the tie.)

```
    dict_count = {}
    dict_dist = {}
    
    for i in range(num_neighbors):
        
        # Get the class from the i-th neighbor - here my Class value is at offset 13
        c = neighbors[i][13]
        
        # Keep a dictionary of Class counts
        if c in dict_count:
            dict_count[c] = dict_count[c] + 1
        else:
            dict_count[c] = 1
          
     # Keep a dictionary of total Class distances 
        if c in dict_dist:
            dict_dist[c] = dict_dist[c] + distances[i]
        else:
            dict_dist[c] = distances[i]
    
    # Return the key within the dictionary that has the largest value
    best_keys = [key for key, value in dict_count.items() if value == max(dict_count.values())]

    if len(best_keys) == 1:
        prediction = best_keys[0]

    else:   # There was a tie
        tie_dict = {}
        for b in best_keys:
            tie_dict[b] = dict_dist[b]
            
        prediction = min(tie_dict, key=tie_dict.get)

    return prediction
```

### Describe alternatives you've considered, if relevant

Writing my own _k_-NN algorithm 🙁

### Additional context

_No response_

COMMENT:
Related to https://github.com/scikit-learn/scikit-learn/issues/21006

We should as well think about the choice of the tie-breaking that could hurt the performance gain that we got during the work driven by @jjerphan.

Labels: New Feature, module:neighbors, Needs Investigation
Change how KNeighborsClassifier handles tiebreakers

### Describe the workflow you want to enable

I see that KNeighborsClassifier handles tiebreakers by taking the mode of the classes contained with the tie. What about using the sum of the distances as the tiebreaker instead (of using the mode.)

I feel that taking the least sum of distances is a better educated guess with minimal changes to the code.

### Describe your proposed solution

Create two dictionaries to keep a count of the Class count and the sum of Class distances.
If there is no tie return the Class value that won the vote (as normal).
If there is a tie return the Class that has the minimum sum of distances (instead of what scipy.stats.mode yields which I believe will always be the smallest Class value from the Classes within the tie.)

```
    dict_count = {}
    dict_dist = {}
    
    for i in range(num_neighbors):
        
        # Get the class from the i-th neighbor - here my Class value is at offset 13
        c = neighbors[i][13]
        
        # Keep a dictionary of Class counts
        if c in dict_count:
            dict_count[c] = dict_count[c] + 1
        else:
            dict_count[c] = 1
          
     # Keep a dictionary of total Class distances 
        if c in dict_dist:
            dict_dist[c] = dict_dist[c] + distances[i]
        else:
            dict_dist[c] = distances[i]
    
    # Return the key within the dictionary that has the largest value
    best_keys = [key for key, value in dict_count.items() if value == max(dict_count.values())]

    if len(best_keys) == 1:
        prediction = best_keys[0]

    else:   # There was a tie
        tie_dict = {}
        for b in best_keys:
            tie_dict[b] = dict_dist[b]
            
        prediction = min(tie_dict, key=tie_dict.get)

    return prediction
```

### Describe alternatives you've considered, if relevant

Writing my own _k_-NN algorithm 🙁

### Additional context

_No response_

COMMENT:
Hi @raymondj-pace, you can use `weights="distance"` for your instance. See the documentation of [`sklearn.neighbors.KNeighborsClassifier`](https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html)

Labels: New Feature, module:neighbors, Needs Investigation