論文の概要: Better Algorithms for Individually Fair $k$-Clustering
- arxiv url: http://arxiv.org/abs/2106.12150v1
- Date: Wed, 23 Jun 2021 04:16:46 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-24 23:32:37.122268
- Title: Better Algorithms for Individually Fair $k$-Clustering
- Title（参考訳）: 個人別$k$-Clusteringのためのより良いアルゴリズム
- Authors: Deeparnab Chakrabarty and Maryam Negahbani
- Abstract要約: Jung, Kannan, Lutz [FORC 2020]は、$ell_infty$または$k$-Centerの目的に対して、証明可能な(近似的な)フェアネスと客観的保証を備えたクラスタリングアルゴリズムを導入した。Mahabadi氏とVakilian氏(ICML 2020)は、この問題を再考して、すべての$ell_p$-normsに対してローカル検索アルゴリズムを提供する。
我々は、既知のLPラウンドリング技術を変更することで、MV20よりもはるかに優れた目標に対して最悪のケースを保証できることを実証的に証明し、この目標が最適に非常に近いことを実証した。
- 参考スコア（独自算出の注目度）: 4.936817539835045
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study data clustering problems with $\ell_p$-norm objectives (e.g.
$k$-Median and $k$-Means) in the context of individual fairness. The dataset
consists of $n$ points, and we want to find $k$ centers such that (a) the
objective is minimized, while (b) respecting the individual fairness constraint
that every point $v$ has a center within a distance at most $r(v)$, where
$r(v)$ is $v$'s distance to its $(n/k)$th nearest point. Jung, Kannan, and Lutz
[FORC 2020] introduced this concept and designed a clustering algorithm with
provable (approximate) fairness and objective guarantees for the $\ell_\infty$
or $k$-Center objective. Mahabadi and Vakilian [ICML 2020] revisited this
problem to give a local-search algorithm for all $\ell_p$-norms. Empirically,
their algorithms outperform Jung et. al.'s by a large margin in terms of cost
(for $k$-Median and $k$-Means), but they incur a reasonable loss in fairness.
In this paper, our main contribution is to use Linear Programming (LP)
techniques to obtain better algorithms for this problem, both in theory and in
practice. We prove that by modifying known LP rounding techniques, one gets a
worst-case guarantee on the objective which is much better than in MV20, and
empirically, this objective is extremely close to the optimal. Furthermore, our
theoretical fairness guarantees are comparable with MV20 in theory, and
empirically, we obtain noticeably fairer solutions. Although solving the LP
{\em exactly} might be prohibitive, we demonstrate that in practice, a simple
sparsification technique drastically improves the run-time of our algorithm.
- Abstract（参考訳）: データクラスタリングの問題を$\ell_p$-normの目的(例)で研究する。
$k$-Median と $k$-Means) は、個々のフェアネスの文脈における。
データセットは$n$ポイントで構成されており、(a)目的が最小化されるような$k$センターを探したいが、(b)各点$v$が最大$r(v)$の範囲内で中心を持つという個々の公正性制約を尊重する一方で、$r(v)$はその$(n/k)$から最寄りの点まで$v$sの距離である。
Jung, Kannan, Lutz [FORC 2020]は、この概念を導入し、$\ell_\infty$または$k$-Centerの目的に対して、証明可能な(近似的な)フェアネスと客観的保証を備えたクラスタリングアルゴリズムを設計した。
MahabadiとVakilian(ICML 2020)はこの問題を再考し、すべての$\ell_p$-normsに対してローカル検索アルゴリズムを提供した。
経験上、アルゴリズムはjungなどよりも優れている。
アル
コスト面では大きな差($k$-Medianと$k$-Meansは$k$-Means)がありますが、フェアネスでは合理的な損失をもたらします。
本稿では,Linear Programming (LP) 技術を用いて,理論と実践の両方において,この問題に対するより良いアルゴリズムを得る。
我々は、既知のLPラウンドリング技術を変更することで、MV20よりもはるかに優れた目標に対して最悪のケースを保証できることを実証的に証明し、この目標が最適に非常に近いことを実証した。
さらに、理論上の公平性保証は理論上mv20と同等であり、経験上、より公平な解が得られる。
lp {\em exactly} を解くことは禁止されるかもしれないが、実際には単純なスパーシフィケーション手法がアルゴリズムの実行時間を大幅に改善することを示している。
関連論文リスト
- Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems [8.74967598360817]
複数のグループからなるデータセットが与えられた場合、公正性制約は各クラスタに各グループからのポイントの割合を含む必要がある。
我々はRelax と Merge' のフレームワークを提案し、$rho$ は既製のvanilla $k$-means アルゴリズムの近似比である。
PTASが$k$-meansである場合、我々の解は、フェアネス制約にわずかに違反するだけで、$(5+O(epsilon))$の近似比を達成できる。
論文 参考訳（メタデータ） (2024-11-02T02:50:12Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Improved Approximation Algorithms for Individually Fair Clustering [9.914246432182873]
16p +varepsilon,3)$-bicriteria approximation for the fair $k$-clustering with $ell_p$-norm cost。
我々のアプローチは、Kleindessnerらによって提案されたグループフェアネス要件により、個別に公平なクラスタリングからクラスタリングに還元されることを示唆している。
論文 参考訳（メタデータ） (2021-06-26T15:22:52Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - A New Notion of Individually Fair Clustering: $\alpha$-Equitable
$k$-Center [31.936733991407134]
本稿では,クラスタリング問題に対する公平性の新たな定義を提案する。
我々のモデルでは、各点$j$ は他の点の集合 $mathcalS_j$ を持ち、それ自身と似ていると知覚する。
我々は、$k$-centerの目的に対して、効率的かつ容易に実装可能な近似アルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-06-09T22:52:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Individual Fairness for $k$-Clustering [16.988236398003068]
ローカル検索に基づく$k$-medianと$k$-meansのアルゴリズム。
公平な$k$-clusteringのために、bicriteria近似の取得方法を示す。
論文 参考訳（メタデータ） (2020-02-17T02:31:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。