Supplementary Material: Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem A Proof of Lemma 1 Lemma 1 F orpw, Zq PC, the functions f pw, Zq " x M1

We need to prove the following two inequalities. Thus, the inequality ( 19) holds trivially. Note that f p w, Z q " x M In this section, we will show that the MIQP presented in ( 4) is at least as hard to solve as a 0 1 Quadratic Program. It should be noted that MIQP ( 4) is stated for a fixed X. The Mixed Integer Quadratic Program (MIQP) ( 4) is NP-hard. " 0. Other cases will be at least as difficult as this case.