We introduce general tools for designing efficient private estimation algorithms, in the high-dimensional settings, whose statistical guarantees almost match those of the best known non-private algorithms. To illustrate our techniques, we consider two problems: recovery of stochastic block models and learning mixtures of spherical Gaussians. For the former, we present the first efficient $(\epsilon, \delta)$-differentially private algorithm for both weak recovery and exact recovery. Previously known algorithms achieving comparable guarantees required quasi-polynomial time. For the latter, we design an $(\epsilon, \delta)$-differentially private algorithm that recovers the centers of the $k$-mixture when the minimum separation is at least $ O(k^{1/t}\sqrt{t})$. For all choices of $t$, this algorithm requires sample complexity $n\geq k^{O(1)}d^{O(t)}$ and time complexity $(nd)^{O(t)}$. Prior work required minimum separation at least $O(\sqrt{k})$ as well as an explicit upper bound on the Euclidean norm of the centers.
相關內容
In this paper, we are concerned about the lattice Boltzmann methods (LBMs) based on vector-kinetic models for hyperbolic partial differential equations. In addition to usual lattice Boltzmann equation (LBE) derived by explicit discretisation of vector-kinetic equation (VKE), we also consider LBE derived by semi-implicit discretisation of VKE and compare the relaxation factors of both. We study the properties such as H-inequality, total variation boundedness and positivity of both the LBEs, and infer that the LBE due to semi-implicit discretisation naturally satisfies all the properties while the LBE due to explicit discretisation requires more restrictive condition on relaxation factor compared to the usual condition obtained from Chapman-Enskog expansion. We also derive the macroscopic finite difference form of the LBEs, and utilise it to establish the consistency of LBEs with the hyperbolic system. Further, we extend this LBM framework to hyperbolic conservation laws with source terms, such that there is no spurious numerical convection due to imbalance between convection and source terms. We also present a D$2$Q$9$ model that allows upwinding even along diagonal directions in addition to the usual upwinding along coordinate directions. The different aspects of the results are validated numerically on standard benchmark problems.
Within Bayesian nonparametrics, dependent Dirichlet process mixture models provide a highly flexible approach for conducting inference about the conditional density function. However, several formulations of this class make either rather restrictive modelling assumptions or involve intricate algorithms for posterior inference, thus preventing their widespread use. In response to these challenges, we present a flexible, versatile, and computationally tractable model for density regression based on a single-weights dependent Dirichlet process mixture of normal distributions model for univariate continuous responses. We assume an additive structure for the mean of each mixture component and incorporate the effects of continuous covariates through smooth nonlinear functions. The key components of our modelling approach are penalised B-splines and their bivariate tensor product extension. Our proposed method also seamlessly accommodates parametric effects of categorical covariates, linear effects of continuous covariates, interactions between categorical and/or continuous covariates, varying coefficient terms, and random effects, which is why we refer our model as a Dirichlet process mixture of normal structured additive regression models. A noteworthy feature of our method is its efficiency in posterior simulation through Gibbs sampling, as closed-form full conditional distributions for all model parameters are available. Results from a simulation study demonstrate that our approach successfully recovers true conditional densities and other regression functionals in various challenging scenarios. Applications to a toxicology, disease diagnosis, and agricultural study are provided and further underpin the broad applicability of our modelling framework. An R package, \texttt{DDPstar}, implementing the proposed method is publicly available at \url{//bitbucket.org/mxrodriguez/ddpstar}.
The theory of generalized locally Toeplitz (GLT) sequences is a powerful apparatus for computing the asymptotic spectral distribution of matrices $A_n$ arising from numerical discretizations of differential equations. Indeed, when the mesh fineness parameter $n$ tends to infinity, these matrices $A_n$ give rise to a sequence $\{A_n\}_n$, which often turns out to be a GLT sequence. In this paper, we extend the theory of GLT sequences in several directions: we show that every GLT sequence enjoys a normal form, we identify the spectral symbol of every GLT sequence formed by normal matrices, and we prove that, for every GLT sequence $\{A_n\}_n$ formed by normal matrices and every continuous function $f:\mathbb C\to\mathbb C$, the sequence $\{f(A_n)\}_n$ is again a GLT sequence whose spectral symbol is $f(\kappa)$, where $\kappa$ is the spectral symbol of $\{A_n\}_n$. In addition, using the theory of GLT sequences, we prove a spectral distribution result for perturbed normal matrices.
It is known that standard stochastic Galerkin methods encounter challenges when solving partial differential equations with high-dimensional random inputs, which are typically caused by the large number of stochastic basis functions required. It becomes crucial to properly choose effective basis functions, such that the dimension of the stochastic approximation space can be reduced. In this work, we focus on the stochastic Galerkin approximation associated with generalized polynomial chaos (gPC), and explore the gPC expansion based on the analysis of variance (ANOVA) decomposition. A concise form of the gPC expansion is presented for each component function of the ANOVA expansion, and an adaptive ANOVA procedure is proposed to construct the overall stochastic Galerkin system. Numerical results demonstrate the efficiency of our proposed adaptive ANOVA stochastic Galerkin method for both diffusion and Helmholtz problems.
In designing external validation studies of clinical prediction models, contemporary sample size calculation methods are based on the frequentist inferential paradigm. One of the widely reported metrics of model performance is net benefit (NB), and the relevance of conventional inference around NB as a measure of clinical utility is doubtful. Value of Information methodology quantifies the consequences of uncertainty in terms of its impact on clinical utility of decisions. We introduce the expected value of sample information (EVSI) for validation as the expected gain in NB from conducting an external validation study of a given size. We propose algorithms for EVSI computation, and in a case study demonstrate how EVSI changes as a function of the amount of current information and future study's sample size. Value of Information methodology provides a decision-theoretic lens to the process of planning a validation study of a risk prediction model and can complement conventional methods when designing such studies.
In a topology optimization setting, design-dependent fluidic pressure loads pose several challenges as their direction, magnitude, and location alter with topology evolution. This paper offers a compact 100-line MATLAB code, TOPress, for topology optimization of structures subjected to fluidic pressure loads using the method of moving asymptotes. The code is intended for pedagogical purposes and aims to ease the beginners' and students' learning toward topology optimization with design-dependent fluidic pressure loads. TOPress is developed per the approach first reported in Kumar et al. (Struct Multidisc Optim 61(4):1637-1655, 2020). The Darcy law, in conjunction with the drainage term, is used to model the applied pressure load. The consistent nodal loads are determined from the obtained pressure field. The employed approach facilitates inexpensive computation of the load sensitivities using the adjoint-variable method. Compliance minimization subject to volume constraint optimization problems are solved. The success and efficacy of the code are demonstrated by solving benchmark numerical examples involving pressure loads, wherein the importance of load sensitivities is also demonstrated. TOPress contains six main parts, is described in detail, and is extended to solve different problems. Steps to include a projection filter are provided to achieve loadbearing designs close to~0-1. The code is provided in Appendix~B and can also be downloaded along with its extensions from \url{//github.com/PrabhatIn/TOPress}.
We propose a framework to solve non-linear and history-dependent mechanical problems based on a hybrid classical computer -- quantum annealer approach. Quantum Computers are anticipated to solve particular operations exponentially faster. The available possible operations are however not as versatile as with a classical computer. However, quantum annealers (QAs) are well suited to evaluate the minimum state of a Hamiltonian quadratic potential. Therefore, we reformulate the elasto-plastic finite element problem as a double-minimisation process framed at the structural scale using the variational updates formulation. In order to comply with the expected quadratic nature of the Hamiltonian, the resulting non-linear minimisation problems are iteratively solved with the suggested Quantum Annealing-assisted Sequential Quadratic Programming (QA-SQP): a sequence of minimising quadratic problems is performed by approximating the objective function by a quadratic Taylor's series. Each quadratic minimisation problem of continuous variables is then transformed into a binary quadratic problem. This binary quadratic minimisation problem can be solved on quantum annealing hardware such as the D-Wave system. The applicability of the proposed framework is demonstrated with one- and two-dimensional elasto-plastic numerical benchmarks. The current work provides a pathway of performing general non-linear finite element simulations assisted by quantum computing.
Linear codes are widely studied in coding theory as they have nice applications in distributed storage, combinatorics, lattices, cryptography and so on. Constructing linear codes with desirable properties is an interesting research topic. In this paper, based on the augmentation technique, we present two families of linear codes from some functions over finite fields. The first family of linear codes is constructed from monomial functions over finite fields. The locality of them is determined and the weight distributions of two subfamilies of the codes are also given. An infinite family of locally recoverable codes which are at least almost optimal and some optimal recoverable codes are obtained from the linear codes. In particular, the two subfamilies of the codes are proved to be both optimally or almost optimally extendable and self-orthogonal. The second family of linear codes is constructed from weakly regular bent functions over finite fields and their weight distribution is determined. This family of codes is proved to have locality 3 for some cases and is conjectured to have locality 2 for other cases. Particularly, two families of optimal locally recoverable codes are derived from the linear codes. Besides, this family of codes is also proved to be both optimally or almost optimally extendable and self-orthogonal.
Gradient-enhanced Kriging (GE-Kriging) is a well-established surrogate modelling technique for approximating expensive computational models. However, it tends to get impractical for high-dimensional problems due to the size of the inherent correlation matrix and the associated high-dimensional hyper-parameter tuning problem. To address these issues, a new method, called sliced GE-Kriging (SGE-Kriging), is developed in this paper for reducing both the size of the correlation matrix and the number of hyper-parameters. We first split the training sample set into multiple slices, and invoke Bayes' theorem to approximate the full likelihood function via a sliced likelihood function, in which multiple small correlation matrices are utilized to describe the correlation of the sample set rather than one large one. Then, we replace the original high-dimensional hyper-parameter tuning problem with a low-dimensional counterpart by learning the relationship between the hyper-parameters and the derivative-based global sensitivity indices. The performance of SGE-Kriging is finally validated by means of numerical experiments with several benchmarks and a high-dimensional aerodynamic modeling problem. The results show that the SGE-Kriging model features an accuracy and robustness that is comparable to the standard one but comes at much less training costs. The benefits are most evident for high-dimensional problems with tens of variables.
We derive information-theoretic generalization bounds for supervised learning algorithms based on the information contained in predictions rather than in the output of the training algorithm. These bounds improve over the existing information-theoretic bounds, are applicable to a wider range of algorithms, and solve two key challenges: (a) they give meaningful results for deterministic algorithms and (b) they are significantly easier to estimate. We show experimentally that the proposed bounds closely follow the generalization gap in practical scenarios for deep learning.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191