論文の概要: How to Solve Fair $k$-Center in Massive Data Models
- arxiv url: http://arxiv.org/abs/2002.07682v2
- Date: Mon, 24 Feb 2020 16:55:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-30 19:52:28.746288
- Title: How to Solve Fair $k$-Center in Massive Data Models
- Title（参考訳）: 大規模データモデルにおける$k$-Centerの解決法
- Authors: Ashish Chiplunkar, Sagar Kale, Sivaramakrishnan Natarajan Ramamoorthy
- Abstract要約: 我々は、$k$-center問題に対して、新しいストリーミングおよび分散アルゴリズムを設計する。
主な貢献は、(a)最初の分散アルゴリズム、(b)証明可能な近似保証付き2パスストリーミングアルゴリズムである。
- 参考スコア（独自算出の注目度）: 5.3283669037198615
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Fueled by massive data, important decision making is being automated with the
help of algorithms, therefore, fairness in algorithms has become an especially
important research topic. In this work, we design new streaming and distributed
algorithms for the fair $k$-center problem that models fair data summarization.
The streaming and distributed models of computation have an attractive feature
of being able to handle massive data sets that do not fit into main memory. Our
main contributions are: (a) the first distributed algorithm; which has provably
constant approximation ratio and is extremely parallelizable, and (b) a
two-pass streaming algorithm with a provable approximation guarantee matching
the best known algorithm (which is not a streaming algorithm). Our algorithms
have the advantages of being easy to implement in practice, being fast with
linear running times, having very small working memory and communication, and
outperforming existing algorithms on several real and synthetic data sets. To
complement our distributed algorithm, we also give a hardness result for
natural distributed algorithms, which holds for even the special case of
$k$-center.
- Abstract（参考訳）: 大量のデータにより、アルゴリズムの助けを借りて重要な意思決定が自動化されているため、アルゴリズムの公平性は特に重要な研究トピックとなっている。
本研究では,公平なデータ要約をモデル化した$k$-center問題に対して,新たなストリーミングおよび分散アルゴリズムを設計する。
ストリーミングおよび分散計算モデルは、メインメモリに収まらない巨大なデータセットを処理できるという魅力的な特徴を持っている。
私たちの主な貢献は
(a)最初の分散アルゴリズムで、確率的に一定の近似比を持ち、非常に並列化可能である
(b)最もよく知られたアルゴリズム(ストリーミングアルゴリズムではない)に適合する証明可能な近似を保証する2パスストリーミングアルゴリズム。
私たちのアルゴリズムは、実装が容易で、線形実行時間も速く、動作メモリと通信も非常に少なく、既存のアルゴリズムをいくつかの実データと合成データで上回っているという利点があります。
分散アルゴリズムを補完するために、自然分散アルゴリズムの難易度結果も提供します。
関連論文リスト
- A Weighted K-Center Algorithm for Data Subset Selection [70.49696246526199]
サブセット選択は、トレーニングデータの小さな部分を特定する上で重要な役割を果たす、基本的な問題である。
我々は,k中心および不確かさサンプリング目的関数の重み付け和に基づいて,サブセットを計算する新しい係数3近似アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-12-17T04:41:07Z) - Learning the hub graphical Lasso model with the structured sparsity via
an efficient algorithm [1.0923877073891446]
ハブグラフィカルモデルを推定する二相アルゴリズムを提案する。
提案アルゴリズムはまず,乗算器の2つの交互方向法を用いてよい初期点を生成する。
その後、半滑らかなニュートン(SSN)ベースの拡張ラグランジアン法(ALM)を温め、実用的なタスクに十分正確な解を計算する。
論文 参考訳（メタデータ） (2023-08-17T08:24:28Z) - ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate
Nearest Neighbor Search Algorithms [5.478671305092084]
本稿では,ParlayANNについて紹介する。ParlayANNは決定論的および並列グラフに基づく近接探索アルゴリズムのライブラリである。
我々は、数十億のデータセットにスケールする4つの最先端グラフベースのANNSアルゴリズムに対して、新しい並列実装を開発する。
論文 参考訳（メタデータ） (2023-05-07T19:28:23Z) - Dual Algorithmic Reasoning [9.701208207491879]
本稿では,基礎となるアルゴリズム問題の双対性を利用してアルゴリズムを学習することを提案する。
アルゴリズム学習における最適化問題の2つの定義を同時に学習することで、より良い学習が可能になることを実証する。
次に、難易度の高い脳血管分類タスクにデプロイすることで、二元アルゴリズム推論の現実的な実用性を検証する。
論文 参考訳（メタデータ） (2023-02-09T08:46:23Z) - Streaming Algorithms for High-Dimensional Robust Statistics [43.106438224356175]
ほぼ最適なメモリ要件を持つ高次元ロバスト統計のための,最初の効率的なストリーミングアルゴリズムを開発した。
本研究の主な成果は,ハマー汚染モデルにおける高次元ロバスト平均推定の課題である。
論文 参考訳（メタデータ） (2022-04-26T15:57:07Z) - Practical, Provably-Correct Interactive Learning in the Realizable
Setting: The Power of True Believers [12.09273192079783]
我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。
我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-11-09T02:33:36Z) - Learning to Hash Robustly, with Guarantees [79.68057056103014]
本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。
理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。
我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
論文 参考訳（メタデータ） (2021-08-11T20:21:30Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity
to Non-IID Data [59.50904660420082]
フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。
クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
論文 参考訳（メタデータ） (2020-05-22T23:07:42Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。