Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Overlap Gap Property in Principal Submatrix Recovery
109
0
0.0
(
0
)
Added by
Aukosh Jagannath
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study support recovery for a $k times k$ principal submatrix with elevated mean $lambda/N$, hidden in an $Ntimes N$ symmetric mean zero Gaussian matrix. Here $lambda>0$ is a universal constant, and we assume $k = N rho$ for some constant $rho in (0,1)$. We establish that {there exists a constant $C>0$ such that} the MLE recovers a constant proportion of the hidden submatrix if $lambda {geq C} sqrt{frac{1}{rho} log frac{1}{rho}}$, {while such recovery is information theoretically impossible if $lambda = o( sqrt{frac{1}{rho} log frac{1}{rho}} )$}. The MLE is computationally intractable in general, and in fact, for $rho>0$ sufficiently small, this problem is conjectured to exhibit a emph{statistical-computational gap}. To provide rigorous evidence for this, we study the likelihood landscape for this problem, and establish that for some $varepsilon>0$ and $sqrt{frac{1}{rho} log frac{1}{rho} } ll lambda ll frac{1}{rho^{1/2 + varepsilon}}$, the problem exhibits a variant of the emph{Overlap-Gap-Property (OGP)}. As a direct consequence, we establish that a family of local MCMC based algorithms do not achieve optimal recovery. Finally, we establish that for $lambda > 1/rho$, a simple spectral method recovers a constant proportion of the hidden submatrix.
rate research
Read More
We study a variant of the sparse PCA (principal component analysis) problem in the hard regime, where the inference task is possible yet no polynomial-time algorithm is known to exist. Prior work, based on the low-degree likelihood ratio, has conjectured a precise expression for the best possible (sub-exponential) runtime throughout the hard regime. Following instead a statistical physics inspired point of view, we show bounds on the depth of free energy wells for various Gibbs measures naturally associated to the problem. These free energy wells imply hitting time lower bounds that corroborate the low-degree conjecture: we show that a class of natural MCMC (Markov chain Monte Carlo) methods (with worst-case initialization) cannot solve sparse PCA with less than the conjectured runtime. These lower bounds apply to a wide range of values for two tuning parameters: temperature and sparsity misparametrization. Finally, we prove that the Overlap Gap Property (OGP), a structural property that implies failure of certain local search algorithms, holds in a significant part of the hard regime.
We present AMPS, an augmented matrix approach to update the solution to a linear system of equations when the matrix is modified by a few elements within a principal submatrix. This problem arises in the dynamic security analysis of a power grid, where operators need to perform N - k contingency analysis, i.e., determine the state of the system when exactly k links from N fail. Our algorithms augment the matrix to account for the changes in it, and then compute the solution to the augmented system without refactoring the modified matrix. We provide two algorithms, a direct method, and a hybrid direct-iterative method for solving the augmented system. We also exploit the sparsity of the matrices and vectors to accelerate the overall computation. We analyze the time complexity of both algorithms, and show that it is bounded by the number of nonzeros in a subset of the columns of the Cholesky factor that are selected by the nonzeros in the sparse right-hand-side vector. Our algorithms are compared on three power grids with PARDISO, a parallel direct solver, and CHOLMOD, a direct solver with the ability to modify the Cholesky factors of the matrix. We show that our augmented algorithms outperform PARDISO (by two orders of magnitude), and CHOLMOD (by a factor of up to 5). Further, our algorithms scale better than CHOLMOD as the number of elements updated increases. The solutions are computed with high accuracy. Our algorithms are capable of computing N - k contingency analysis on a 778 thousand bus grid, updating a solution with k = 20 elements in 16 milliseconds on an Intel Xeon processor.
For some Maltsev conditions $Sigma$ it is enough to check if a finite algebra $mathbf A$ satisfies $Sigma$ locally on subsets of bounded size, in order to decide, whether $mathbf A$ satisfies $Sigma$ (globally). This local-global property is the main known source of tractability results for deciding Maltsev conditions. In this paper we investigate the local-global property for the existence of a $G$-term, i.e. an $n$-ary term that is invariant under permuting its variables according to a permutation group $G leq$ Sym($n$). Our results imply in particular that all cyclic loop conditions (in the sense of Bodirsky, Starke, and Vucaj) have the local-global property (and thus can be decided in polynomial time), while symmetric terms of arity $n>2$ fail to have it.
Data analyses based on linear methods constitute the simplest, most robust, and transparent approaches to the automatic processing of large amounts of data for building supervised or unsupervised machine learning models. Principal covariates regression (PCovR) is an underappreciated method that interpolates between principal component analysis and linear regression, and can be used to conveniently reveal structure-property relations in terms of simple-to-interpret, low-dimensional maps. Here we provide a pedagogic overview of these data analysis schemes, including the use of the kernel trick to introduce an element of non-linearity, while maintaining most of the convenience and the simplicity of linear approaches. We then introduce a kernelized version of PCovR and a sparsified extension, and demonstrate the performance of this approach in revealing and predicting structure-property relations in chemistry and materials science, showing a variety of examples including elemental carbon, porous silicate frameworks, organic molecules, amino acid conformers, and molecular materials.
We present an encoding of a polynomial system into vanishing and non-vanishing constraints on almost-principal minors of a symmetric, principally regular matrix, such that the solvability of the system over some field is equivalent to the satisfiability of the constraints over that field. This implies two complexity results about Gaussian conditional independence structures. First, all real algebraic numbers are necessary to construct inhabitants of non-empty Gaussian statistical models defined by conditional independence and dependence constraints. This gives a negative answer to a question of Petr v{S}imev{c}ek. Second, we prove that the implication problem for Gaussian CI is polynomial-time equivalent to the existential theory of the reals.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
