論文の概要: Approximating Fair Clustering with Cascaded Norm Objectives

• arxiv url: http://arxiv.org/abs/2111.04804v1
• Date: Mon, 8 Nov 2021 20:18:10 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-11 01:41:34.692923
• Title: Approximating Fair Clustering with Cascaded Norm Objectives
• Title（参考訳）: カスケードノームオブジェクトによる公正クラスタリングの近似
• Authors: Eden Chlamt\'a\v{c}, Yury Makarychev, Ali Vakilian
• Abstract要約: ベクトルの $ell_q$-norm を $ell_p$-norms の $ell_p$-norm よりも小さくするクラスタリングが、中心から$P$ の点の重み付き距離の $ell_p$-norms より小さい。 これはSocially Fair $k$-Medianや$k$-Meansなど、さまざまなクラスタリング問題を一般化する。
• 参考スコア（独自算出の注目度）: 10.69111036810888
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce the $(p,q)$-Fair Clustering problem. In this problem, we are given a set of points $P$ and a collection of different weight functions $W$. We would like to find a clustering which minimizes the $\ell_q$-norm of the vector over $W$ of the $\ell_p$-norms of the weighted distances of points in $P$ from the centers. This generalizes various clustering problems, including Socially Fair $k$-Median and $k$-Means, and is closely connected to other problems such as Densest $k$-Subgraph and Min $k$-Union. We utilize convex programming techniques to approximate the $(p,q)$-Fair Clustering problem for different values of $p$ and $q$. When $p\geq q$, we get an $O(k^{(p-q)/(2pq)})$, which nearly matches a $k^{\Omega((p-q)/(pq))}$ lower bound based on conjectured hardness of Min $k$-Union and other problems. When $q\geq p$, we get an approximation which is independent of the size of the input for bounded $p,q$, and also matches the recent $O((\log n/(\log\log n))^{1/p})$-approximation for $(p, \infty)$-Fair Clustering by Makarychev and Vakilian (COLT 2021).
• Abstract（参考訳）: 我々は$(p,q)$-Fair Clustering問題を導入する。 この問題では、点の集合$P$と異なる重み関数の集合$W$が与えられる。 ベクトルの$\ell_q$-ノルムを最小化し、中心から$p$の点の重み付き距離の$w$の$\ell_p$-ノルムを最小化するクラスタリングを見つけたいと思っています。 これはSocially Fair $k$-Medianや$k$-Meansなどの様々なクラスタリング問題を一般化し、Densest $k$-SubgraphやMin $k$-Unionといった他の問題と密接に関連している。 凸プログラミング手法を用いて、$(p,q)$-Fair Clustering 問題を $p$ と $q$ の異なる値に対して近似する。 p\geq q$ のとき、$O(k^{(p-q)/(2pq)})$は$k^{\Omega((p-q)/(pq))} とほぼ一致する。 q\geq p$ のとき、有界な $p,q$ の入力のサイズに依存しない近似が得られ、mamaarychev と vakilian (colt 2021) による$(p, \infty)$-fairクラスタリングに対する最近の$o((\log n/(\log\log n))^{1/p}) と一致する。

関連論文リスト

• Clustering to Minimize Cluster-Aware Norm Objectives [0.3481985817302898]
  与えられたデータセットの$P$を$k$クラスタに分割し、$X$の$k$センターを見つける。 中心の$xin X$で表されるクラスタのコストは、x$に割り当てられた点の距離のベクトルの単調で対称なノルム$f$(インナーノルム)である。 目標は、クラスタコストのベクトルのノルム$g$(外部ノルム)を最小化することである。
  論文  参考訳（メタデータ） (2024-10-31T16:33:40Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• A Polynomial-Time Approximation for Pairwise Fair $k$-Median Clustering [10.697784653113095]
  すべてのクラスタ$C$とすべてのグループ$i in [ell]$に対して、$C$ from group $i$のポイント数は、他のグループ$j in [ell]$のポイントの数のt倍でなければならない。 私たちは、$ell=2$が一般的な均一容量$k$-medianに匹敵する難易度である場合にも、その問題を示します。
  論文  参考訳（メタデータ） (2024-05-16T18:17:44Z)
• 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)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• Approximation Algorithms for Fair Range Clustering [14.380145034918158]
  本稿では、データポイントが異なる人口集団のものであるフェアレンジクラスタリング問題について検討する。 目標は、各グループが少なくともセンターセットで最小限に表現されるように、最小クラスタリングコストで$k$センターを選択することである。 特に、fair range $ell_p$-clusteringは、特別なケースとして$k$-center、$k$-median、$k$-meansをキャプチャする。
  論文  参考訳（メタデータ） (2023-06-11T21:18:40Z)
• Fair Representation Clustering with Several Protected Classes [13.53362222844008]
  我々は、各クラスタが異なるグループから個人を公平に表現する必要があるフェア$k$-medianの問題を研究する。 我々は、$O(log k)$-approximationアルゴリズムを示し、$nO(ell)$で実行します。
  論文  参考訳（メタデータ） (2022-02-03T03:45:45Z)
• Local Correlation Clustering with Asymmetric Classification Errors [12.277755088736864]
  相関クラスタリング問題では、エッジを"similar"と"dissimilar"とラベルした完全な重み付きグラフ$G$が与えられる。 クラスタリングの$mathcalC$ of graph $G$の場合、同じエッジが$mathcalC$、エンドポイントが別のクラスタに属している場合は$mathcalC$、エンドポイントが同じクラスタに属している場合は$mathcalC$と一致しない。 我々は$pgeq 1$に対する不一致ベクトルの$ell_p$ノルムを最小化するクラスタリングを生成する。
  論文  参考訳（メタデータ） (2021-08-11T12:31:48Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。