2 Search Results for "Friedler, Sorelle"

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.18
On the Cost of Essentially Fair Clusterings

Authors: Ioana O. Bercea, Martin Groß, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R. Schmidt, and Melanie Schmidt

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
Clustering is a fundamental tool in data mining and machine learning. It partitions points into groups (clusters) and may be used to make decisions for each point based on its group. However, this process may harm protected (minority) classes if the clustering algorithm does not adequately represent them in desirable clusters - especially if the data is already biased. At NIPS 2017, Chierichetti et al. [Flavio Chierichetti et al., 2017] proposed a model for fair clustering requiring the representation in each cluster to (approximately) preserve the global fraction of each protected class. Restricting to two protected classes, they developed both a 4-approximation for the fair k-center problem and a O(t)-approximation for the fair k-median problem, where t is a parameter for the fairness model. For multiple protected classes, the best known result is a 14-approximation for fair k-center [Clemens Rösner and Melanie Schmidt, 2018]. We extend and improve the known results. Firstly, we give a 5-approximation for the fair k-center problem with multiple protected classes. Secondly, we propose a relaxed fairness notion under which we can give bicriteria constant-factor approximations for all of the classical clustering objectives k-center, k-supplier, k-median, k-means and facility location. The latter approximations are achieved by a framework that takes an arbitrary existing unfair (integral) solution and a fair (fractional) LP solution and combines them into an essentially fair clustering with a weakly supervised rounding scheme. In this way, a fair clustering can be established belatedly, in a situation where the centers are already fixed.
Cite as

Ioana O. Bercea, Martin Groß, Samir Khuller, Aounon Kumar, Clemens Rösner, Daniel R. Schmidt, and Melanie Schmidt. On the Cost of Essentially Fair Clusterings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 18:1-18:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bercea_et_al:LIPIcs.APPROX-RANDOM.2019.18,
  author =	{Bercea, Ioana O. and Gro{\ss}, Martin and Khuller, Samir and Kumar, Aounon and R\"{o}sner, Clemens and Schmidt, Daniel R. and Schmidt, Melanie},
  title =	{{On the Cost of Essentially Fair Clusterings}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{18:1--18:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.18},
  URN =		{urn:nbn:de:0030-drops-112337},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.18},
  annote =	{Keywords: approximation, clustering, fairness, LP rounding}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.SWAT.2018.2
Optimizing Society? Ensuring Fairness in Automated Decision-Making (Invited Talk)

Authors: Sorelle Friedler

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
Algorithms are increasingly used to make high-stakes decisions about people; who goes to jail, what neighborhoods police deploy to, and who should be hired for a job. But if we want these decisions to be fair, this means we must take societal notions of fairness and express them using the language of math. What is a fair decision and how can it be guaranteed? In this talk, we'll discuss recent work from the new and growing field of Fairness, Accountability, and Transparency. We will examine technical definitions of fairness and non-discrimination that have been proposed and their societal counterparts. We'll also discuss methods for ensuring that algorithms are making decisions as desired, from methods to audit black-box algorithms to white-box interpretability techniques. This important field necessitates societally informed and mathematically rigorous work; we'll discuss open problems in this light.
Cite as

Sorelle Friedler. Optimizing Society? Ensuring Fairness in Automated Decision-Making (Invited Talk). In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{friedler:LIPIcs.SWAT.2018.2,
  author =	{Friedler, Sorelle},
  title =	{{Optimizing Society? Ensuring Fairness in Automated Decision-Making}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.2},
  URN =		{urn:nbn:de:0030-drops-88282},
  doi =		{10.4230/LIPIcs.SWAT.2018.2},
  annote =	{Keywords: algorithmic fairness}
}
  • Refine by Author
  • 1 Bercea, Ioana O.
  • 1 Friedler, Sorelle
  • 1 Groß, Martin
  • 1 Khuller, Samir
  • 1 Kumar, Aounon
  • Show More...

  • Refine by Classification
  • 1 Security and privacy → Social aspects of security and privacy
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Facility location and clustering
  • 1 Theory of computation → Rounding techniques
  • 1 Theory of computation → Unsupervised learning and clustering

  • Refine by Keyword
  • 1 LP rounding
  • 1 algorithmic fairness
  • 1 approximation
  • 1 clustering
  • 1 fairness

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2019

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact