論文の概要: Fast algorithms to improve fair information access in networks
- arxiv url: http://arxiv.org/abs/2409.03127v1
- Date: Wed, 4 Sep 2024 23:36:39 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-06 22:44:13.272013
- Title: Fast algorithms to improve fair information access in networks
- Title(参考訳): ネットワークにおける公正情報アクセス改善のための高速アルゴリズム
- Authors: Dennis Robert Windham, Caroline J. Wendt, Alex Crane, Sorelle A. Friedler, Blair D. Sullivan, Aaron Clauset,
- Abstract要約: ソーシャルネットワークにおける情報アクセスを改善するために,新しい10種類のスケーラブルアルゴリズムを開発し,評価する。
我々は,新しい性能指標とネットワークのベンチマークコーパスを導入する。
我々の新しいスケーラブルなアルゴリズムは、最先端のアルゴリズムと桁違いの速さで競合する。
- 参考スコア(独自算出の注目度): 3.837368936370829
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: When information spreads across a network via pairwise sharing, large disparities in information access can arise from the network's structural heterogeneity. Algorithms to improve the fairness of information access seek to maximize the minimum access of a node to information by sequentially selecting new nodes to seed with the spreading information. However, existing algorithms are computationally expensive. Here, we develop and evaluate a set of 10 new scalable algorithms to improve information access in social networks; in order to compare them to the existing state-of-the-art, we introduce both a new performance metric and a new benchmark corpus of networks. Additionally, we investigate the degree to which algorithm performance on minimizing information access gaps can be predicted ahead of time from features of a network's structure. We find that while no algorithm is strictly superior to all others across networks, our new scalable algorithms are competitive with the state-of-the-art and orders of magnitude faster. We introduce a meta-learner approach that learns which of the fast algorithms is best for a specific network and is on average only 20% less effective than the state-of-the-art performance on held-out data, while about 75-130 times faster. Furthermore, on about 20% of networks the meta-learner's performance exceeds the state-of-the-art.
- Abstract(参考訳): 情報がペア共有によってネットワーク全体に広まると、ネットワークの構造的不均一性から情報アクセスの大きな格差が発生する。
情報アクセスの公平性を向上させるアルゴリズムは、情報拡散によりシードする新しいノードを順次選択することにより、情報へのノードの最小アクセスを最大化する。
しかし、既存のアルゴリズムは計算コストが高い。
本稿では,ソーシャルネットワークにおける情報アクセスを改善するために,新しい10種類のスケーラブルアルゴリズムを開発し,評価する。
さらに,ネットワーク構造の特徴から,情報アクセスギャップを最小化するアルゴリズムの性能を事前に予測できる程度について検討した。
我々の新しいスケーラブルなアルゴリズムは、最先端のアルゴリズムと桁違いの速さで競合する。
我々は,高速アルゴリズムのどれが特定のネットワークに最適であるかを学習し,保持データに対する最先端のパフォーマンスよりも平均20%低い効率で,75~130倍高速なメタラーナアプローチを提案する。
さらに、ネットワークの約20%では、メタラーナーのパフォーマンスは最先端よりも高い。
関連論文リスト
- A Fast Algorithm for Moderating Critical Nodes via Edge Removal [19.130541561303293]
対象ノードの情報集中度を最小限に抑えるために,ネットワークから$k$エッジを除去する問題について検討する。
ランダムウォークに基づくシュア補数近似や高速和推定などの新しい手法を用いて、3つの近似グリードアルゴリズムを提案する。
理論的解析を補完するため、100万以上のノードを持つ合成および実ネットワークに関する包括的な実験を行う。
論文 参考訳(メタデータ) (2023-09-09T13:54:34Z) - Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。
疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。
後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
論文 参考訳(メタデータ) (2023-05-30T16:05:44Z) - Two Losses Are Better Than One: Faster Optimization Using a Cheaper
Proxy [6.170898159041277]
本稿では,関連関数をプロキシとして利用することにより,目的物を計算困難勾配で最小化するアルゴリズムを提案する。
我々のアルゴリズムは、$delta$-smooth目的の勾配降下に一致する速度で収束を保証する。
我々のアルゴリズムは機械学習に多くの可能性があり、合成データ、物理シミュレータ、混合公開データ、プライベートデータなどを活用するための原則化された手段を提供する。
論文 参考訳(メタデータ) (2023-02-07T15:50:49Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳(メタデータ) (2022-10-14T01:42:05Z) - FairGRAPE: Fairness-aware GRAdient Pruning mEthod for Face Attribute
Classification [4.909402570564468]
フェアネス対応型GRADient Pruning mEthod(FairGRAPE)を提案する。
本手法は,各モデルの重みの群ごとの重要度を算出し,プルーニングにおけるグループ間の総重要度を相対的に維持する重みのサブセットを選択する。
我々の手法は高い刈り取り率(99%)の設定において極めて効果的である。
論文 参考訳(メタデータ) (2022-07-22T05:44:03Z) - Efficient First-Order Contextual Bandits: Prediction, Allocation, and
Triangular Discrimination [82.52105963476703]
統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。
1次保証は統計的およびオンライン学習において比較的よく理解されている。
三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
論文 参考訳(メタデータ) (2021-07-05T19:20:34Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳(メタデータ) (2020-12-28T17:19:32Z) - Progressive Skeletonization: Trimming more fat from a network at
initialization [76.11947969140608]
本稿では,接続感度が最大となるスケルトン化ネットワークを提案する。
次に、目的を最大化する2つの近似手順を提案する。
提案手法は, 高い刈り込みレベルにおいて, 性能を著しく向上させる。
論文 参考訳(メタデータ) (2020-06-16T11:32:47Z) - Towards Deep Learning Models Resistant to Large Perturbations [0.0]
敵対的堅牢性は、機械学習アルゴリズムの必須特性であることが証明されている。
とよばれるアルゴリズムは、大きくても合理的で摂動のマグニチュードが与えられたディープニューラルネットワークのトレーニングに失敗することを示した。
論文 参考訳(メタデータ) (2020-03-30T12:03:09Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳(メタデータ) (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。