Many modern machine learning algorithms are composed of simple private algorithms; thus, an increasingly important problem is to efficiently compute the overall privacy loss under composition. In this study, we introduce the Edgeworth Accountant, an analytical approach to composing differential privacy guarantees of private algorithms. The Edgeworth Accountant starts by losslessly tracking the privacy loss under composition using the $f$-differential privacy framework, which allows us to express the privacy guarantees using privacy-loss log-likelihood ratios (PLLRs). As the name suggests, this accountant next uses the Edgeworth expansion to the upper and lower bounds the probability distribution of the sum of the PLLRs. Moreover, by relying on a technique for approximating complex distributions using simple ones, we demonstrate that the Edgeworth Accountant can be applied to the composition of any noise-addition mechanism. Owing to certain appealing features of the Edgeworth expansion, the $(\epsilon, \delta)$-differential privacy bounds offered by this accountant are non-asymptotic, with essentially no extra computational cost, as opposed to the prior approaches in, wherein the running times increase with the number of compositions. Finally, we demonstrate that our upper and lower $(\epsilon, \delta)$-differential privacy bounds are tight in federated analytics and certain regimes of training private deep learning models.
相關內容
In this study we approach the complexity of the vaccine debate from a new and comprehensive perspective. Focusing on the Italian context, we examine almost all the online information produced in the 2016-2021 timeframe by both sources that have a reputation for misinformation and those that do not. Although reliable sources can rely on larger newsrooms and cover more news than misinformation ones, the transfer entropy analysis of the corresponding time series reveals that the former have not always informationally dominated the latter on the vaccine subject. Indeed, the pre-pandemic period sees misinformation establish itself as leader of the process, even in causal terms, and gain dramatically more user engagement than news from reliable sources. Despite this information gap was filled during the Covid-19 outbreak, the newfound leading role of reliable sources as drivers of the information ecosystem has only partially had a beneficial effect in reducing user engagement with misinformation on vaccines. Our results indeed show that, except for effectiveness of vaccination, reliable sources have never adequately countered the anti-vax narrative, specially in the pre-pandemic period, thus contributing to exacerbate science denial and belief in conspiracy theories. At the same time, however, they confirm the efficacy of assiduously proposing a convincing counter-narrative to misinformation spread. Indeed, effectiveness of vaccination turns out to be the least engaging topic discussed by misinformation during the pandemic period, when compared to other polarising arguments such as safety concerns, legal issues and vaccine business. By highlighting the strengths and weaknesses of institutional and mainstream communication, our findings can be a valuable asset for improving and better targeting campaigns against misinformation on vaccines.
We consider to model matrix time series based on a tensor CP-decomposition. Instead of using an iterative algorithm which is the standard practice for estimating CP-decompositions, we propose a new and one-pass estimation procedure based on a generalized eigenanalysis constructed from the serial dependence structure of the underlying process. To overcome the intricacy of solving a rank-reduced generalized eigenequation, we propose a further refined approach which projects it into a lower-dimensional full-ranked eigenequation. This refined method improves significantly the finite-sample performance of the estimation. The asymptotic theory has been established under a general setting without the stationarity. It shows, for example, that all the component coefficient vectors in the CP-decomposition are estimated consistently with certain convergence rates. The proposed model and the estimation method are also illustrated with both simulated and real data; showing effective dimension-reduction in modelling and forecasting matrix time series.
The convex rope problem is to find a counterclockwise or clockwise convex rope starting at the vertex a and ending at the vertex b of a simple polygon P, where a is a vertex of the convex hull of P and b is visible from infinity. The convex rope mentioned is the shortest path joining a and b that does not enter the interior of P. In this paper, the problem is reconstructed as the one of finding such shortest path in a simple polygon and solved by the method of multiple shooting. We then show that if the collinear condition of the method holds at all shooting points, then these shooting points form the shortest path. Otherwise, the sequence of paths obtained by the update of the method converges to the shortest path. The algorithm is implemented in C++ for numerical experiments.
This paper is a short summery of results announced in a previous paper on a new universal method for Cryptanalysis which uses a Black Box linear algebra approach to computation of local inversion of nonlinear maps in finite fields. It is shown that one local inverse $x$ of the map equation $y=F(x)$ can be computed by using the minimal polynomial of the sequence $y(k)$ defined by iterates (or recursion) $y(k+1)=F(y(k))$ with $y(0)=y$ when the sequence is periodic. This is the only solution in the periodic orbit of the map $F$. Further, when the degree of the minimal polynomial is of polynomial order in number of bits of the input of $F$ (called low complexity case), the solution can be computed in polynomial time. The method of computation only uses the forward computations $F(y)$ for given $y$ which is why this is called a Black Box approach. Application of this approach is then shown for cryptanalysis of several maps arising in cryptographic primitives. It is shown how in the low complexity cases maps defined by block and stream ciphers can be inverted to find the symmetric key under known plaintext attack. Then it is shown how RSA map can be inverted to find the plaintext as well as an equivalent private key to break the RSA algorithm without factoring the modulus. Finally it is shown that the discrete log computation in finite field and elliptic curves can be formulated as a local inversion problem and the low complexity cases can be solved in polynomial time.
Causal effect estimation from observational data is a challenging problem, especially with high dimensional data and in the presence of unobserved variables. The available data-driven methods for tackling the problem either provide an estimation of the bounds of a causal effect (i.e. nonunique estimation) or have low efficiency. The major hurdle for achieving high efficiency while trying to obtain unique and unbiased causal effect estimation is how to find a proper adjustment set for confounding control in a fast way, given the huge covariate space and considering unobserved variables. In this paper, we approach the problem as a local search task for finding valid adjustment sets in data. We establish the theorems to support the local search for adjustment sets, and we show that unique and unbiased estimation can be achieved from observational data even when there exist unobserved variables. We then propose a data-driven algorithm that is fast and consistent under mild assumptions. We also make use of a frequent pattern mining method to further speed up the search of minimal adjustment sets for causal effect estimation. Experiments conducted on extensive synthetic and real-world datasets demonstrate that the proposed algorithm outperforms the state-of-the-art criteria/estimators in both accuracy and time-efficiency.
We study the performance -- and specifically the rate at which the error probability converges to zero -- of Machine Learning (ML) classification techniques. Leveraging the theory of large deviations, we provide the mathematical conditions for a ML classifier to exhibit error probabilities that vanish exponentially, say $\sim \exp\left(-n\,I + o(n) \right)$, where $n$ is the number of informative observations available for testing (or another relevant parameter, such as the size of the target in an image) and $I$ is the error rate. Such conditions depend on the Fenchel-Legendre transform of the cumulant-generating function of the Data-Driven Decision Function (D3F, i.e., what is thresholded before the final binary decision is made) learned in the training phase. As such, the D3F and, consequently, the related error rate $I$, depend on the given training set, which is assumed of finite size. Interestingly, these conditions can be verified and tested numerically exploiting the available dataset, or a synthetic dataset, generated according to the available information on the underlying statistical model. In other words, the classification error probability convergence to zero and its rate can be computed on a portion of the dataset available for training. Coherently with the large deviations theory, we can also establish the convergence, for $n$ large enough, of the normalized D3F statistic to a Gaussian distribution. This property is exploited to set a desired asymptotic false alarm probability, which empirically turns out to be accurate even for quite realistic values of $n$. Furthermore, approximate error probability curves $\sim \zeta_n \exp\left(-n\,I \right)$ are provided, thanks to the refined asymptotic derivation (often referred to as exact asymptotics), where $\zeta_n$ represents the most representative sub-exponential terms of the error probabilities.
Motivated by comparing the convergence behavior of Gegenbauer projections and best approximations, we study the optimal rate of convergence for Gegenbauer projections in the maximum norm. We show that the rate of convergence of Gegenbauer projections is the same as that of best approximations under conditions of the underlying function is either analytic on and within an ellipse and $\lambda\leq0$ or differentiable and $\lambda\leq1$, where $\lambda$ is the parameter in Gegenbauer projections. If the underlying function is analytic and $\lambda>0$ or differentiable and $\lambda>1$, then the rate of convergence of Gegenbauer projections is slower than that of best approximations by factors of $n^{\lambda}$ and $n^{\lambda-1}$, respectively. An exceptional case is functions with endpoint singularities, for which Gegenbauer projections and best approximations converge at the same rate for all $\lambda>-1/2$. For functions with interior or endpoint singularities, we provide a theoretical explanation for the error localization phenomenon of Gegenbauer projections and for why the accuracy of Gegenbauer projections is better than that of best approximations except in small neighborhoods of the critical points. Our analysis provides fundamentally new insight into the power of Gegenbauer approximations and related spectral methods.
The Heuristic Rating Estimation Method enables decision-makers to decide based on existing ranking data and expert comparisons. In this approach, the ranking values of selected alternatives are known in advance, while these values have to be calculated for the remaining ones. Their calculation can be performed using either an additive or a multiplicative method. Both methods assumed that the pairwise comparison sets involved in the computation were complete. In this paper, we show how these algorithms can be extended so that the experts do not need to compare all alternatives pairwise. Thanks to the shortening of the work of experts, the presented, improved methods will reduce the costs of the decision-making procedure and facilitate and shorten the stage of collecting decision-making data.
We introduce a neural implicit framework that exploits the differentiable properties of neural networks and the discrete geometry of point-sampled surfaces to approximate them as the level sets of neural implicit functions. To train a neural implicit function, we propose a loss functional that approximates a signed distance function, and allows terms with high-order derivatives, such as the alignment between the principal directions of curvature, to learn more geometric details. During training, we consider a non-uniform sampling strategy based on the curvatures of the point-sampled surface to prioritize points with more geometric details. This sampling implies faster learning while preserving geometric accuracy when compared with previous approaches. We also present the analytical differential geometry formulas for neural surfaces, such as normal vectors and curvatures.
Boosting is one of the most significant developments in machine learning. This paper studies the rate of convergence of $L_2$Boosting, which is tailored for regression, in a high-dimensional setting. Moreover, we introduce so-called \textquotedblleft post-Boosting\textquotedblright. This is a post-selection estimator which applies ordinary least squares to the variables selected in the first stage by $L_2$Boosting. Another variant is \textquotedblleft Orthogonal Boosting\textquotedblright\ where after each step an orthogonal projection is conducted. We show that both post-$L_2$Boosting and the orthogonal boosting achieve the same rate of convergence as LASSO in a sparse, high-dimensional setting. We show that the rate of convergence of the classical $L_2$Boosting depends on the design matrix described by a sparse eigenvalue constant. To show the latter results, we derive new approximation results for the pure greedy algorithm, based on analyzing the revisiting behavior of $L_2$Boosting. We also introduce feasible rules for early stopping, which can be easily implemented and used in applied work. Our results also allow a direct comparison between LASSO and boosting which has been missing from the literature. Finally, we present simulation studies and applications to illustrate the relevance of our theoretical results and to provide insights into the practical aspects of boosting. In these simulation studies, post-$L_2$Boosting clearly outperforms LASSO.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191