The majority of fault-tolerant distributed algorithms are designed assuming a nominal corruption model, in which at most a fraction $f_n$ of parties can be corrupted by the adversary. However, due to the infamous Sybil attack, nominal models are not sufficient to express the trust assumptions in open (i.e., permissionless) settings. Instead, permissionless systems typically operate in a weighted model, where each participant is associated with a weight and the adversary can corrupt a set of parties holding at most a fraction $f_w$ of the total weight. In this paper, we suggest a simple way to transform a large class of protocols designed for the nominal model into the weighted model. To this end, we formalize and solve three novel optimization problems, which we collectively call the weight reduction problems, that allow us to map large real weights into small integer weights while preserving the properties necessary for the correctness of the protocols. In all cases, we manage to keep the sum of the integer weights to be at most linear in the number of parties, resulting in extremely efficient protocols for the weighted model. Moreover, we demonstrate that, on weight distributions that emerge in practice, the sum of the integer weights tends to be far from the theoretical worst case and, sometimes, even smaller than the number of participants. While, for some protocols, our transformation requires an arbitrarily small reduction in resilience (i.e., $f_w = f_n - \epsilon$), surprisingly, for many important problems, we manage to obtain weighted solutions with the same resilience ($f_w = f_n$) as nominal ones. Notable examples include erasure-coded distributed storage and broadcast protocols, verifiable secret sharing, and asynchronous consensus.
相關內容
Random effects meta-analysis is widely used for synthesizing studies under the assumption that underlying effects come from a normal distribution. However, under certain conditions the use of alternative distributions might be more appropriate. We conducted a systematic review to identify articles introducing alternative meta-analysis models assuming non-normal between-study distributions. We identified 27 eligible articles suggesting 24 alternative meta-analysis models based on long-tail and skewed distributions, on mixtures of distributions, and on Dirichlet process priors. Subsequently, we performed a simulation study to evaluate the performance of these models and to compare them with the standard normal model. We considered 22 scenarios varying the amount of between-study variance, the shape of the true distribution, and the number of included studies. We compared 15 models implemented in the Frequentist or in the Bayesian framework. We found small differences with respect to bias between the different models but larger differences in the level of coverage probability. In scenarios with large between-study variance, all models were substantially biased in the estimation of the mean treatment effect. This implies that focusing only on the mean treatment effect of random effects meta-analysis can be misleading when substantial heterogeneity is suspected or outliers are present.
Most of the scientific literature on causal modeling considers the structural framework of Pearl and the potential-outcome framework of Rubin to be formally equivalent, and therefore interchangeably uses do-interventions and the potential-outcome subscript notation to write counterfactual outcomes. In this paper, we agnostically superimpose the two causal models to specify under which mathematical conditions structural counterfactual outcomes and potential outcomes need to, do not need to, can, or cannot be equal (almost surely or law). Our comparison reminds that a structural causal model and a Rubin causal model compatible with the same observations do not have to coincide, and highlights real-world problems where they even cannot correspond. Then, we examine common claims and practices from the causal-inference literature in the light of these results. In doing so, we aim at clarifying the relationship between the two causal frameworks, and the interpretation of their respective counterfactuals.
A new variant of the GMRES method is presented for solving linear systems with the same matrix and subsequently obtained multiple right-hand sides. The new method keeps such properties of the classical GMRES algorithm as follows. Both bases of the search space and its image are maintained orthonormal that increases the robustness of the method. Moreover there is no need to store both bases since they are effectively represented within a common basis. Along with it our method is theoretically equivalent to the GCR method extended for a case of multiple right-hand sides but is more numerically robust and requires less memory. The main result of the paper is a mechanism of adding an arbitrary direction vector to the search space that can be easily adopted for flexible GMRES or GMRES with deflated restarting.
For several types of information relations, the induced rough sets system RS does not form a lattice but only a partially ordered set. However, by studying its Dedekind-MacNeille completion DM(RS), one may reveal new important properties of rough set structures. Building upon D. Umadevi's work on describing joins and meets in DM(RS), we previously investigated pseudo-Kleene algebras defined on DM(RS) for reflexive relations. This paper delves deeper into the order-theoretic properties of DM(RS) in the context of reflexive relations. We describe the completely join-irreducible elements of DM(RS) and characterize when DM(RS) is a spatial completely distributive lattice. We show that even in the case of a non-transitive reflexive relation, DM(RS) can form a Nelson algebra, a property generally associated with quasiorders. We introduce a novel concept, the core of a relational neighborhood, and use it to provide a necessary and sufficient condition for DM(RS) to determine a Nelson algebra.
Principal component analysis (PCA) is a widely used dimension reduction method, but its performance is known to be non-robust to outliers. Recently, product-PCA (PPCA) has been shown to possess the efficiency-loss free ordering-robustness property: (i) in the absence of outliers, PPCA and PCA share the same asymptotic distributions; (ii), in the presence of outliers, PPCA is more ordering-robust than PCA in estimating the leading eigenspace. PPCA is thus different from the conventional robust PCA methods, and may deserve further investigations. In this article, we study the high-dimensional statistical properties of the PPCA eigenvalues via the techniques of random matrix theory. In particular, we derive the critical value for being distant spiked eigenvalues, the limiting values of the sample spiked eigenvalues, and the limiting spectral distribution of PPCA. Similar to the case of PCA, the explicit forms of the asymptotic properties of PPCA become available under the special case of the simple spiked model. These results enable us to more clearly understand the superiorities of PPCA in comparison with PCA. Numerical studies are conducted to verify our results.
Randomized iterative algorithms, such as the randomized Kaczmarz method, have gained considerable popularity due to their efficacy in solving matrix-vector and matrix-matrix regression problems. Our present work leverages the insights gained from studying such algorithms to develop regression methods for tensors, which are the natural setting for many application problems, e.g., image deblurring. In particular, we extend the randomized Kaczmarz method to solve a tensor system of the form $\mathbf{\mathcal{A}}\mathcal{X} = \mathcal{B}$, where $\mathcal{X}$ can be factorized as $\mathcal{X} = \mathcal{U}\mathcal{V}$, and all products are calculated using the t-product. We develop variants of the randomized factorized Kaczmarz method for matrices that approximately solve tensor systems in both the consistent and inconsistent regimes. We provide theoretical guarantees of the exponential convergence rate of our algorithms, accompanied by illustrative numerical simulations. Furthermore, we situate our method within a broader context by linking our novel approaches to earlier randomized Kaczmarz methods.
Sequential positivity is often a necessary assumption for drawing causal inferences, such as through marginal structural modeling. Unfortunately, verification of this assumption can be challenging because it usually relies on multiple parametric propensity score models, unlikely all correctly specified. Therefore, we propose a new algorithm, called "sequential Positivity Regression Tree" (sPoRT), to check this assumption with greater ease under either static or dynamic treatment strategies. This algorithm also identifies the subgroups found to be violating this assumption, allowing for insights about the nature of the violations and potential solutions. We first present different versions of sPoRT based on either stratifying or pooling over time. Finally, we illustrate its use in a real-life application of HIV-positive children in Southern Africa with and without pooling over time. An R notebook showing how to use sPoRT is available at github.com/ArthurChatton/sPoRT-notebook.
New proposals for causal discovery algorithms are typically evaluated using simulations and a few select real data examples with known data generating mechanisms. However, there does not exist a general guideline for how such evaluation studies should be designed, and therefore, comparing results across different studies can be difficult. In this article, we propose a common evaluation baseline by posing the question: Are we doing better than random guessing? For the task of graph skeleton estimation, we derive exact distributional results under random guessing for the expected behavior of a range of typical causal discovery evaluation metrics (including precision and recall). We show that these metrics can achieve very large values under random guessing in certain scenarios, and hence warn against using them without also reporting negative control results, i.e., performance under random guessing. We also propose an exact test of overall skeleton fit, and showcase its use on a real data application. Finally, we propose a general pipeline for using random controls beyond the skeleton estimation task, and apply it both in a simulated example and a real data application.
The multi-modal perception methods are thriving in the autonomous driving field due to their better usage of complementary data from different sensors. Such methods depend on calibration and synchronization between sensors to get accurate environmental information. There have already been studies about space-alignment robustness in autonomous driving object detection process, however, the research for time-alignment is relatively few. As in reality experiments, LiDAR point clouds are more challenging for real-time data transfer, our study used historical frames of LiDAR to better align features when the LiDAR data lags exist. We designed a Timealign module to predict and combine LiDAR features with observation to tackle such time misalignment based on SOTA GraphBEV framework.
Finite element discretization of Stokes problems can result in singular, inconsistent saddle point linear algebraic systems. This inconsistency can cause many iterative methods to fail to converge. In this work, we consider the lowest-order weak Galerkin finite element method to discretize Stokes flow problems and study a consistency enforcement by modifying the right-hand side of the resulting linear system. It is shown that the modification of the scheme does not affect the optimal-order convergence of the numerical solution. Moreover, inexact block diagonal and triangular Schur complement preconditioners and the minimal residual method (MINRES) and the generalized minimal residual method (GMRES) are studied for the iterative solution of the modified scheme. Bounds for the eigenvalues and the residual of MINRES/GMRES are established. Those bounds show that the convergence of MINRES and GMRES is independent of the viscosity parameter and mesh size. The convergence of the modified scheme and effectiveness of the preconditioners are verified using numerical examples in two and three dimensions.
小貼士
登錄享
相關主題
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191