More Like this

1. Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs

   Afonso S Bandeira, Jess Banks ( October 2021 , Proceedings of Machine Learning Research)

   null (Ed.)

   Abstract We study the problem of efficiently refuting the k-colorability of a graph, or equivalently, certifying a lower bound on its chromatic number. We give formal evidence of average-case computational hardness for this problem in sparse random regular graphs, suggesting that there is no polynomial-time algorithm that improves upon a classical spectral algorithm. Our evidence takes the form of a "computationally-quiet planting": we construct a distribution of d-regular graphs that has significantly smaller chromatic number than a typical regular graph drawn uniformly at random, while providing evidence that these two distributions are indistinguishable by a large class of algorithms. We generalize our results to the more general problem of certifying an upper bound on the maximum k-cut. This quiet planting is achieved by minimizing the effect of the planted structure (e.g. colorings or cuts) on the graph spectrum. Specifically, the planted structure corresponds exactly to eigenvectors of the adjacency matrix. This avoids the pushout effect of random matrix theory, and delays the point at which the planting becomes visible in the spectrum or local statistics. To illustrate this further, we give similar results for a Gaussian analogue of this problem: a quiet version of the spiked model, where we plant an eigenspace rather than adding a generic low-rank perturbation. Our evidence for computational hardness of distinguishing two distributions is based on three different heuristics: stability of belief propagation, the local statistics hierarchy, and the low-degree likelihood ratio. Of independent interest, our results include general-purpose bounds on the low-degree likelihood ratio for multi-spiked matrix models, and an improved low-degree analysis of the stochastic block model. 

   more » « less
2. A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits

   https://doi.org/10.1145/3543685  

   Volk, Ben Lee ; Kumar, Mrinal ( June 2022 , ACM Transactions on Computation Theory)

   We show that there is an equation of degree at most poly( n ) for the (Zariski closure of the) set of the non-rigid matrices: That is, we show that for every large enough field 𝔽, there is a non-zero n 2 -variate polynomial P ε 𝔽[ x 1, 1 , ..., x n, n ] of degree at most poly( n ) such that every matrix M that can be written as a sum of a matrix of rank at most n /100 and a matrix of sparsity at most n 2 /100 satisfies P(M) = 0. This confirms a conjecture of Gesmundo, Hauenstein, Ikenmeyer, and Landsberg [ 9 ] and improves the best upper bound known for this problem down from exp ( n 2 ) [ 9 , 12 ] to poly( n ). We also show a similar polynomial degree bound for the (Zariski closure of the) set of all matrices M such that the linear transformation represented by M can be computed by an algebraic circuit with at most n 2 /200 edges (without any restriction on the depth). As far as we are aware, no such bound was known prior to this work when the depth of the circuits is unbounded. Our methods are elementary and short and rely on a polynomial map of Shpilka and Volkovich [ 21 ] to construct low-degree “universal” maps for non-rigid matrices and small linear circuits. Combining this construction with a simple dimension counting argument to show that any such polynomial map has a low-degree annihilating polynomial completes the proof. As a corollary, we show that any derandomization of the polynomial identity testing problem will imply new circuit lower bounds. A similar (but incomparable) theorem was proved by Kabanets and Impagliazzo [ 11 ]. 

   more » « less
3. High‐dimensional limit theorems for SGD: Effective dynamics and critical scaling

   https://doi.org/10.1002/cpa.22169  

   Arous, Gérard Ben ; Gheissari, Reza ; Jagannath, Aukosh ( October 2023 , Communications on Pure and Applied Mathematics)

   We study the scaling limits of stochastic gradient descent (SGD) with constant step‐size in the high‐dimensional regime. We prove limit theorems for the trajectories of summary statistics (i.e., finite‐dimensional functions) of SGD as the dimension goes to infinity. Our approach allows one to choose the summary statistics that are tracked, the initialization, and the step‐size. It yields both ballistic (ODE) and diffusive (SDE) limits, with the limit depending dramatically on the former choices. We show a critical scaling regime for the step‐size, below which the effective ballistic dynamics matches gradient flow for the population loss, but at which, a new correction term appears which changes the phase diagram. About the fixed points of this effective dynamics, the corresponding diffusive limits can be quite complex and even degenerate. We demonstrate our approach on popular examples including estimation for spiked matrix and tensor models and classification via two‐layer networks for binary and XOR‐type Gaussian mixture models. These examples exhibit surprising phenomena including multimodal timescales to convergence as well as convergence to sub‐optimal solutions with probability bounded away from zero from random (e.g., Gaussian) initializations. At the same time, we demonstrate the benefit of overparametrization by showing that the latter probability goes to zero as the second layer width grows.

    

   more » « less
4. A study of optical scattering modelling for mixed-phase polar stratospheric clouds

   https://doi.org/10.5194/amt-16-419-2023  

   Cairo, Francesco ; Deshler, Terry ; Di Liberto, Luca ; Scoccione, Andrea ; Snels, Marcel ( January 2023 , Atmospheric Measurement Techniques)

   Abstract. Scattering codes are used to study the optical properties of polar stratospheric clouds (PSCs). Particle backscattering and depolarization coefficients can be computed with available scattering codes once the particle size distribution (PSD) is known and a suitable refractive index is assumed. However, PSCs often appear as external mixtures of supercooled ternary solution (STS) droplets, solid nitric acid trihydrate (NAT) and possibly ice particles, making the assumption of a single refractive index and a single morphology to model the scatterers questionable.Here we consider a set of 15 coincident measurements of PSCs above McMurdo Station, Antarctica, using ground-based lidar, a balloon-borne optical particle counter (OPC) and in situ observations taken by a laser backscattersonde and OPC during four balloon stratospheric flights from Kiruna, Sweden. This unique dataset of microphysical and optical observations allows us to test the performances of optical scattering models when both spherical and aspherical scatterers of different composition and, possibly, shapes are present. We consider particles as STS if their radius is below a certain threshold value Rth and NAT or possibly ice if it is above it. The refractive indices are assumed known from the literature. Mie scattering is used for the STS, assumed spherical. Scattering from NAT particles, considered spheroids of different aspect ratio (AR), is treated with T-matrix results where applicable. The geometric-optics–integral-equation approach is used whenever the particle size parameter is too large to allow for a convergence of the T-matrix method.The parameters Rth and AR of our model have been varied between 0.1 and 2 µm and between 0.3 and 3, respectively, and the calculated backscattering coefficient and depolarization were compared with the observed ones. The best agreement was found for Rth between 0.5 and 0.8 µm and for AR less than 0.55 and greater than 1.5.To further constrain the variability of AR within the identified intervals, we have sought an agreement with the experimental data by varying AR on a case-by-case basis and further optimizing the agreement by a proper choice of AR smaller than 0.55 and greater than 1.5 and Rth within the interval 0.5 and 0.8 µm. The ARs identified in this way cluster around the values 0.5 and 2.5.The comparison of the calculations with the measurements is presented and discussed. The results of this work help to set limits to the variability of the dimensions and asphericity of PSC solid particles, within the limits of applicability of our model based on the T-matrix theory of scattering and on assumptions on a common particle shape in a PSD and a common threshold radius for all the PSDs. 

   more » « less
5. Determinantal Generalizations of Instrumental Variables

   https://doi.org/10.1515/jci-2017-0009  

   Weihs, Luca ; Robinson, Bill ; Dufresne, Emilie ; Kenkel, Jennifer ; Kubjas Reginald McGee II, Kaie ; Reginald, McGee II ; Nguyen, Nhan ; Robeva, Elina ; Drton, Mathias ( March 2018 , Journal of Causal Inference)

   Abstract Linear structural equation models relate the components of a random vector using linear interdependencies and Gaussian noise. Each such model can be naturally associated with a mixed graph whose vertices correspond to the components of the random vector. The graph contains directed edges that represent the linear relationships between components, and bidirected edges that encode unobserved confounding. We study the problem of generic identifiability, that is, whether a generic choice of linear and confounding effects can be uniquely recovered from the joint covariance matrix of the observed random vector. An existing combinatorial criterion for establishing generic identifiability is the half-trek criterion (HTC), which uses the existence of trek systems in the mixed graph to iteratively discover generically invertible linear equation systems in polynomial time. By focusing on edges one at a time, we establish new sufficient and new necessary conditions for generic identifiability of edge effects extending those of the HTC. In particular, we show how edge coefficients can be recovered as quotients of subdeterminants of the covariance matrix, which constitutes a determinantal generalization of formulas obtained when using instrumental variables for identification. While our results do not completely close the gap between existing sufficient and necessary conditions we find, empirically, that our results allow us to prove the generic identifiability of many more mixed graphs than the prior state-of-the-art. 

   more » « less