論文の概要: A Stochastic Alternating Balance $k$-Means Algorithm for Fair Clustering
- arxiv url: http://arxiv.org/abs/2105.14172v1
- Date: Sat, 29 May 2021 01:47:15 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-01 17:41:43.606487
- Title: A Stochastic Alternating Balance $k$-Means Algorithm for Fair Clustering
- Title（参考訳）: フェアクラスタリングのための確率的交互バランス$k$-meansアルゴリズム
- Authors: Suyun Liu, Luis Nunes Vicente
- Abstract要約: ローン申請や広告などの人間中心の意思決定システムへのデータクラスタリングの適用において、クラスタリングの結果は異なる人口集団の人々に対して差別される可能性がある。
そこで我々は,$k$-meansの更新とグループスワップ更新を併用した,新たな交代バランス型$k$-means (SAKM) アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the application of data clustering to human-centric decision-making
systems, such as loan applications and advertisement recommendations, the
clustering outcome might discriminate against people across different
demographic groups, leading to unfairness. A natural conflict occurs between
the cost of clustering (in terms of distance to cluster centers) and the
balance representation of all demographic groups across the clusters, leading
to a bi-objective optimization problem that is nonconvex and nonsmooth. To
determine the complete trade-off between these two competing goals, we design a
novel stochastic alternating balance fair $k$-means (SAfairKM) algorithm, which
consists of alternating classical mini-batch $k$-means updates and group swap
updates. The number of $k$-means updates and the number of swap updates
essentially parameterize the weight put on optimizing each objective function.
Our numerical experiments show that the proposed SAfairKM algorithm is robust
and computationally efficient in constructing well-spread and high-quality
Pareto fronts both on synthetic and real datasets. Moreover, we propose a novel
companion algorithm, the stochastic alternating bi-objective gradient descent
(SA2GD) algorithm, which can handle a smooth version of the considered
bi-objective fair $k$-means problem, more amenable for analysis. A sublinear
convergence rate of $\mathcal{O}(1/T)$ is established under strong convexity
for the determination of a stationary point of a weighted sum of the two
functions parameterized by the number of steps or updates on each function.
- Abstract（参考訳）: ローン申請や広告レコメンデーションなどの人間中心の意思決定システムへのデータクラスタリングの適用においては、クラスタリングの結果は異なる人口集団の人々に対して差別され、不公平につながる可能性がある。
クラスター化のコスト(クラスタ中心までの距離)と、クラスタ全体のすべての人口集団群のバランス表現との間に自然な衝突が発生し、非凸かつ非滑らかな二目的最適化問題に繋がる。
これら2つの競合する目標間の完全なトレードオフを決定するために、従来のミニバッチである$k$-meansの更新とグループスワップの更新を交互に行う、新しい確率交互バランスフェア$k$-means (SAfairKM) アルゴリズムを設計する。
k$-meansの更新数とswapの更新数は、基本的に各目的関数の最適化にかかる重みをパラメータ化する。
我々の数値実験により,SAfairKMアルゴリズムは,合成データと実データの両方をベースとして,より広範かつ高品質なParetoフロントを構築する上で,堅牢かつ計算効率が高いことが示された。
さらに,提案アルゴリズムは, 対物的二目的勾配勾配勾配(SA2GD)アルゴリズムと, 対物的二目的勾配勾配勾配(SA2GD)アルゴリズムを併用し, 対物的二目的勾配勾配勾配勾配(SA2GD)と対物的二目的勾配勾配勾配(SA2GD)を対応づける手法を提案する。
半線型収束率$\mathcal{O}(1/T)$は、各関数のステップ数や更新数によってパラメータ化された2つの関数の重み付き和の定常点を決定するために強い凸性の下で確立される。
関連論文リスト
- Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights [16.120911591795295]
一部のアプリケーションでは、すべてのデータポイントをセンターとして選択できるが、一般的な設定では、施設またはサプライヤーと呼ばれる一連のポイントからセンターを選択する必要がある。
そこで本研究では,複数のグループから構成されるデータに対して,各グループから最小限のセンタを選択する必要がある,公平な$k$-supplier問題としてモデル化された公平なデータ要約に焦点を当てる。
論文 参考訳（メタデータ） (2024-10-16T18:00:19Z) - SP$^2$OT: Semantic-Regularized Progressive Partial Optimal Transport for Imbalanced Clustering [14.880015659013681]
本稿では,トランスポートをベースとした新しい擬似ラベル学習フレームワークを提案する。
本フレームワークは,擬似ラベル生成をセマンティック正規化プログレッシブ部分最適輸送問題として定式化する。
我々は、SP$2$OT問題をプログレッシブ部分最適輸送問題に再構成するために、偏化戦略を採用する。
論文 参考訳（メタデータ） (2024-04-04T13:46:52Z) - Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
モデルフリーのステージベースQ-ラーニングアルゴリズムはモデルベースアルゴリズムと同じ$H$依存の最適性を享受できることを示す。
本アルゴリズムは,楽観的値関数と悲観的値関数のペアとして参照値関数を更新するキーとなる新しい設計を特徴とする。
論文 参考訳（メタデータ） (2023-08-17T08:34:58Z) - Local Stochastic Bilevel Optimization with Momentum-Based Variance
Reduction [104.41634756395545]
具体的には、まず、決定論的勾配に基づくアルゴリズムであるFedBiOを提案する。
FedBiOの複雑性は$O(epsilon-1.5)$である。
本アルゴリズムは数値実験において,他のベースラインと比較して優れた性能を示す。
論文 参考訳（メタデータ） (2022-05-03T16:40:22Z) - A framework for bilevel optimization that enables stochastic and global
variance reduction algorithms [17.12280360174073]
双レベル最適化は、他の関数のarg最小値を含む値関数を最小化する問題である。
本稿では, 内部問題の解, 線形系の解, 主変数を同時に発展させる新しい枠組みを提案する。
我々のフレームワークにおけるSAGAアルゴリズムの適応であるSABAは$O(frac1T)$収束率を持ち、Polyak-Lojasciewicz仮定の下で線形収束を達成することを示した。
論文 参考訳（メタデータ） (2022-01-31T18:17:25Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳（メタデータ） (2021-07-02T16:21:52Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Tackling the Objective Inconsistency Problem in Heterogeneous Federated
Optimization [93.78811018928583]
本稿では、フェデレートされた異種最適化アルゴリズムの収束性を分析するためのフレームワークを提供する。
我々は,高速な誤差収束を保ちながら,客観的な矛盾を解消する正規化平均化手法であるFedNovaを提案する。
論文 参考訳（メタデータ） (2020-07-15T05:01:23Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Efficient Clustering for Stretched Mixtures: Landscape and Optimality [4.2111286819721485]
本稿では,2つの楕円分布の平衡混合から抽出された未ラベルのサンプルを受信する正準クラスタリング問題について考察する。
非最適クラスタリング関数は、サンプルサイズが一定の統計的目標を超えると、望ましい幾何学的性質を示す。
論文 参考訳（メタデータ） (2020-03-22T17:57:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。