Merit-Based Sortition in Decentralized Systems

• URL: http://arxiv.org/abs/2411.07302v1
• Date: Mon, 11 Nov 2024 19:00:31 GMT
• Title: Merit-Based Sortition in Decentralized Systems
• Authors: J. M. Diederik Kruijssen, Renata Valieva, Kenneth Peluso, Nicholas Emmons, Steven N. Longmore,
• Abstract summary: We introduce a simple algorithm for'merit-based sortition' We show that our algorithm boosts the quality metric describing the performance of the active set by $>2$ times the intrinsicity. This implies that merit-based sortition ensures a statistically significant performance boost to the drafted, 'active' set.
• Score: 0.0
• License:
• Abstract: In decentralized systems, it is often necessary to select an 'active' subset of participants from the total participant pool, with the goal of satisfying computational limitations or optimizing resource efficiency. This selection can sometimes be made at random, mirroring the sortition practice invented in classical antiquity aimed at achieving a high degree of statistical representativeness. However, the recent emergence of specialized decentralized networks that solve concrete coordination problems and are characterized by measurable success metrics often requires prioritizing performance optimization over representativeness. We introduce a simple algorithm for 'merit-based sortition', in which the quality of each participant influences its probability of being drafted into the active set, while simultaneously retaining representativeness by allowing inactive participants an infinite number of chances to be drafted into the active set with non-zero probability. Using a suite of numerical experiments, we demonstrate that our algorithm boosts the quality metric describing the performance of the active set by $>2$ times the intrinsic stochasticity. This implies that merit-based sortition ensures a statistically significant performance boost to the drafted, 'active' set, while retaining the property of classical, random sortition that it enables upward mobility from a much larger 'inactive' set. This way, merit-based sortition fulfils a key requirement for decentralized systems in need of performance optimization.

Related papers

• LoRA-Ensemble: Efficient Uncertainty Modelling for Self-attention Networks [52.46420522934253]
  We introduce LoRA-Ensemble, a parameter-efficient deep ensemble method for self-attention networks. By employing a single pre-trained self-attention network with weights shared across all members, we train member-specific low-rank matrices for the attention projections. Our method exhibits superior calibration compared to explicit ensembles and achieves similar or better accuracy across various prediction tasks and datasets.
  arXiv  Detail & Related papers  (2024-05-23T11:10:32Z)
• LOQA: Learning with Opponent Q-Learning Awareness [1.1666234644810896]
  We introduce Learning with Opponent Q-Learning Awareness (LOQA), a decentralized reinforcement learning algorithm tailored to optimize an agent's individual utility. LOQA achieves state-of-the-art performance in benchmark scenarios such as the Iterated Prisoner's Dilemma and the Coin Game.
  arXiv  Detail & Related papers  (2024-05-02T06:33:01Z)
• Enhancing Neural Subset Selection: Integrating Background Information into Set Representations [53.15923939406772]
  We show that when the target value is conditioned on both the input set and subset, it is essential to incorporate an textitinvariant sufficient statistic of the superset into the subset of interest. This ensures that the output value remains invariant to permutations of the subset and its corresponding superset, enabling identification of the specific superset from which the subset originated.
  arXiv  Detail & Related papers  (2024-02-05T16:09:35Z)
• Fed-CBS: A Heterogeneity-Aware Client Sampling Mechanism for Federated Learning via Class-Imbalance Reduction [76.26710990597498]
  We show that the class-imbalance of the grouped data from randomly selected clients can lead to significant performance degradation. Based on our key observation, we design an efficient client sampling mechanism, i.e., Federated Class-balanced Sampling (Fed-CBS) In particular, we propose a measure of class-imbalance and then employ homomorphic encryption to derive this measure in a privacy-preserving way.
  arXiv  Detail & Related papers  (2022-09-30T05:42:56Z)
• Sequential Attention for Feature Selection [12.89764845700709]
  We propose a feature selection algorithm called Sequential Attention that achieves state-of-the-art empirical results for neural networks. We give theoretical insights into our algorithm for linear regression by showing that an adaptation to this setting is equivalent to the classical Orthogonal Matching Pursuit (OMP) algorithm.
  arXiv  Detail & Related papers  (2022-09-29T15:49:06Z)
• Quantization enabled Privacy Protection in Decentralized Stochastic Optimization [34.24521534464185]
  Decentralized optimization can be used in areas as diverse as machine learning, control, and sensor networks. Privacy protection has emerged as a crucial need in the implementation of decentralized optimization. We propose an algorithm that is able to guarantee provable convergence accuracy even in the presence of aggressive quantization errors.
  arXiv  Detail & Related papers  (2022-08-07T15:17:23Z)
• Decentralized Stochastic Optimization with Inherent Privacy Protection [103.62463469366557]
  Decentralized optimization is the basic building block of modern collaborative machine learning, distributed estimation and control, and large-scale sensing. Since involved data, privacy protection has become an increasingly pressing need in the implementation of decentralized optimization algorithms.
  arXiv  Detail & Related papers  (2022-05-08T14:38:23Z)
• Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
  We introduce the emphregularized online allocation problem, a variant that includes a non-linear regularizer acting on the total resource consumption. In this problem, requests repeatedly arrive over time and, for each request, a decision maker needs to take an action that generates a reward and consumes resources. The objective is to simultaneously maximize additively separable rewards and the value of a non-separable regularizer subject to the resource constraints.
  arXiv  Detail & Related papers  (2020-07-01T14:24:58Z)
• Stochastic batch size for adaptive regularization in deep network optimization [63.68104397173262]
  We propose a first-order optimization algorithm incorporating adaptive regularization applicable to machine learning problems in deep learning framework. We empirically demonstrate the effectiveness of our algorithm using an image classification task based on conventional network models applied to commonly used benchmark datasets.
  arXiv  Detail & Related papers  (2020-04-14T07:54:53Z)
• Optimistic Exploration even with a Pessimistic Initialisation [57.41327865257504]
  Optimistic initialisation is an effective strategy for efficient exploration in reinforcement learning (RL) In particular, in scenarios with only positive rewards, Q-values are initialised at their lowest possible values. We propose a simple count-based augmentation to pessimistically initialised Q-values that separates the source of optimism from the neural network.
  arXiv  Detail & Related papers  (2020-02-26T17:15:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.