Fair and Accurate Regression: Strong Formulations and Algorithms

References

• Agarwal A, Dudík M, Wu ZS (2019) Fair regression: Quantitative definitions and reduction-based algorithms. Proc. 36th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 97 (PMLR, New York), 120–129.Google Scholar
• Agarwal A, Beygelzimer A, Dudík M, Langford J, Wallach H (2018) A reductions approach to fair classification. Proc. 35th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 80 (PMLR, New York), 60–69.Google Scholar
• Aghaei S, Azizi MJ, Vayanos P (2019) Learning optimal and fair decision trees for non-discriminative decision-making. Proc. AAAI Conf. Artificial Intelligence 33(01):1418–1426.Google Scholar
• Amaldi E, Kann V (1995) The complexity and approximability of finding maximum feasible subsystems of linear relations. Theoretical Comput. Sci. 147(1–2):181–210.Google Scholar
• Atamtürk A, Gómez A (2020) Safe screening rules for ℓ0-regression from perspective relaxations. Proc. 37th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 119 (PMLR, New York), 421–430.Google Scholar
• Atamtürk A, Gómez A (2025) Rank-one convexification for sparse regression. J. Machine Learn. Res. 26(35):1–50.Google Scholar
• Atamtürk A, Nemhauser GL, Savelsbergh MWP (2000) The mixed vertex packing problem. Math. Programming 89:35–53.Google Scholar
• Barocas S, Selbst AD (2016) Big data’s disparate impact. California Law Rev. 104:671.Google Scholar
• Beale EML, Tomlin JA (1970) Special facilities in a general mathematical programming system for non-convex problems using ordered sets of variables. Proc. 5th Internat. Conf. Oper. Res., vol. 69 (Tavistock Publications, London), 99.Google Scholar
• Becker B, Kohavi R (1996) Adult. UCI machine learning repository. Accessed September 2024, https://doi.org/10.24432/C5XW20.Google Scholar
• Berk R, Heidari H, Jabbari S, Joseph M, Kearns M, Morgenstern J, Neel S, et al. (2017) A convex framework for fair regression. Preprint, submitted June 7, https://arxiv.org/abs/1706.02409.Google Scholar
• Bertsimas D, Van Parys B (2020) Sparse high-dimensional regression. Ann. Statist. 48(1):300–323.Google Scholar
• Calders T, Karim A, Kamiran F, Ali W, Zhang X (2013) Controlling attribute effect in linear regression. Proc. IEEE 13th Internat. Conf. Data Mining (IEEE, Piscataway, NJ), 71–80.Google Scholar
• Caton S, Haas C (2024) Fairness in machine learning: A survey. ACM Comput. Survey 56(7):1–38.Google Scholar
• Chouldechova A (2017) Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big Data 5(2):153–163.Google Scholar
• Cotter A, Jiang H, Gupta M, Wang S, Narayan T, You S, Sridharan K (2019) Optimization with non-differentiable constraints with applications to fairness, recall, churn, and other goals. J. Machine Learn. Res. 20(172):1–59.Google Scholar
• Deza A, Atamtürk A (2022) Safe screening for logistic regression with ℓ0-regularization. Proc. 14th Internat. Joint Conf. Knowledge Discovery Knowledge Engrg. Knowledge Management (SciTePress, Setúbal, Portugal), 119–126.Google Scholar
• Do H, Putzel P, Martin AS, Smyth P, Zhong J (2022) Fair generalized linear models with a convex penalty. Proc. 39th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 162 (PMLR, New York), 5286–5308.Google Scholar
• Dong H, Chen K, Linderoth J (2015) Regularization vs. relaxation: A conic optimization perspective of statistical variable selection. Preprint, submitted October 20, https://arxiv.org/abs/1510.06083.Google Scholar
• Donini M, Oneto L, Ben-David S, Shawe-Taylor JS, Pontil M (2018) Empirical risk minimization under fairness constraints. Proc. 32nd Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 31.Google Scholar
• Günlük O, Pochet Y (2001) Mixing mixed-integer inequalities. Math. Programming 90:429–457.Google Scholar
• Han S, Gómez A, Atamtürk A (2023) 2 × 2-convexifications for convex quadratic optimization with indicator variables. Math. Programming 202(1):95–134.Google Scholar
• Hazimeh H, Mazumder R, Saab A (2022) Sparse regression at scale: Branch-and-bound rooted in first-order optimization. Math. Programming 196(1):347–388.Google Scholar
• Hoerl AE, Kennard RW (1970) Ridge regression: Biased estimation for nonorthogonal problems. Technometrics 12(1):55–67.Google Scholar
• Hort M, Chen Z, Zhang JM, Harman M, Sarro F (2024) Bias mitigation for machine learning classifiers: A comprehensive survey. ACM J. Responsible Comput. 1(2):1–52.Google Scholar
• Jo N, Aghaei S, Benson J, Gomez A, Vayanos P (2023) Learning optimal fair decision trees: Tradeoffs between interpretability, fairness, and accuracy. Proc. AAAI/ACM Conf. AI Ethics Soc. (ACM, New York), 181–192.Google Scholar
• Kamishima T, Akaho S, Asoh H, Sakuma J (2012) Fairness-aware classifier with prejudice remover regularizer. Proc. Eur. Conf. Machine Learn. Knowledge Discovery Databases (Springer, Berlin, Heidelberg), 35–50.Google Scholar
• Komiyama J, Takeda A, Honda J, Shimao H (2018) Nonconvex optimization for regression with fairness constraints. Proc. 35th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 80 (PMLR, New York), 2737–2746.Google Scholar
• Lawless C, Günlük O (2021) Fair decision rules for binary classification. Preprint, submitted July 3, https://arxiv.org/abs/2107.01325.Google Scholar
• Le Quy T, Roy A, Iosifidis V, Zhang W, Ntoutsi E (2022) A survey on data sets for fairness-aware machine learning. WIREs Data Mining Knowledge Discovery 12(3):e1452.Google Scholar
• Lohaus M, Perrot M, Von Luxburg U (2020) Too relaxed to be fair. Proc. 37th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 119 (PMLR, New York), 6360–6369.Google Scholar
• Nelder JA, Wedderburn RW (1972) Generalized linear models. J. Roy. Statist. Soc. Ser. A Statist. Soc. 135(3):370–384.Google Scholar
• Olfat M, Aswani A (2018) Spectral algorithms for computing fair support vector machines. Proc. 21st Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 84 (PMLR, New York), 1933–1942.Google Scholar
• Oneto L, Chiappa S (2020) Fairness in machine learning. Recent Trends in Learning from Data (Springer, Cham, Switzerland), 155–196.Google Scholar
• Pessach D, Shmueli E (2022) A review on fairness in machine learning. ACM Comput. Surveys 55(3):1–44.Google Scholar
• Redmond M (2009) Communities and crime. UCI machine learning repository. Accessed September 2024, https://doi.org/10.24432/C53W3X.Google Scholar
• Rockafellar RT (1970) Convex Analysis (Princeton University Press, Princeton, NJ).Google Scholar
• Rychener Y, Taskesen B, Kuhn D (2022) Metrizing fairness. Preprint, submitted May 30, https://arxiv.org/abs/2205.15049.Google Scholar
• Tibshirani R (1996) Regression shrinkage and selection via the lasso. J. Roy. Statist. Soc. Ser. B Statist. Methodology 58(1):267–288.Google Scholar
• Trindade RS, d’Ambrosio C, Frangioni A, Gentile C (2023) Comparing perspective reformulations for piecewise-convex optimization. Oper. Res. Lett. 51(6):702–708.Google Scholar
• Veale M, Van Kleek M, Binns R (2018) Fairness and accountability design needs for algorithmic support in high-stakes public sector decision-making. Proc. Chi Conf. Human Factors Comput. Systems (Association for Computing Machinery, New York), 1–14.Google Scholar
• Wei L, Atamtürk A, Gómez A, Küçükyavuz S (2024) On the convex hull of convex quadratic optimization problems with indicators. Math. Programming 204:703–737.Google Scholar
• Wightman LF (1998) LSAC national longitudinal bar passage study. LSAC research report series, 37. Retrieved from https://archive.lawschooltransparency.com/reform/projects/investigations/2015/documents/NLBPS.pdf.Google Scholar
• Woodworth B, Gunasekar S, Ohannessian MI, Srebro N (2017) Learning non-discriminatory predictors. Proc. Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 65 (PMLR, New York), 1920–1953.Google Scholar
• Wu Y, Zhang L, Wu X (2019) On convexity and bounds of fairness-aware classification. Proc. World Wide Web Conf. (ACM, New York), 3356–3362.Google Scholar
• Xie W, Deng X (2020) Scalable algorithms for the sparse ridge regression. SIAM J. Optim. 30(4):3359–3386.Google Scholar
• Ye Q, Xie W (2020) Unbiased subdata selection for fair classification: A unified framework and scalable algorithms. Preprint, submitted December 22, https://arxiv.org/abs/2012.12356.Google Scholar
• Ye Q, Hanasusanto GA, Xie W (2024) Distributionally fair stochastic optimization using Wasserstein distance. Preprint, submitted February 2, https://arxiv.org/abs/2402.01872.Google Scholar
• Zafar MB, Valera I, Rogriguez MG, Gummadi KP (2017) Fairness constraints: Mechanisms for fair classification. Proc. 20th Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 54 (PMLR, New York), 962–970.Google Scholar
• Zhang CH (2010) Nearly unbiased variable selection under minimax concave penalty. Ann. Statist. 38:894–942.Google Scholar