More Like this

1. Statistically optimal firstorder algorithms: a proof via orthogonalization

   https://doi.org/10.1093/imaiai/iaae027  

   Montanari, Andrea ; Wu, Yuchen ( October 2024 , Information and Inference: A Journal of the IMA)

   We consider a class of statistical estimation problems in which we are given a random data matrix ${\boldsymbol{X}}\in{\mathbb{R}}^{n\times d}$ (and possibly some labels ${\boldsymbol{y}}\in{\mathbb{R}}^{n}$) and would like to estimate a coefficient vector ${\boldsymbol{\theta }}\in{\mathbb{R}}^{d}$ (or possibly a constant number of such vectors). Special cases include low-rank matrix estimation and regularized estimation in generalized linear models (e.g. sparse regression). Firstorder methods proceed by iteratively multiplying current estimates by ${\boldsymbol{X}}$ or its transpose. Examples include gradient descent or its accelerated variants. Under the assumption that the data matrix ${\boldsymbol{X}}$ is standard Gaussian, Celentano, Montanari, Wu (2020, Conference on Learning Theory, pp. 1078–1141. PMLR) proved that for any constant number of iterations (matrix vector multiplications), the optimal firstorder algorithm is a specific approximate message passing algorithm (known as ‘Bayes AMP’). The error of this estimator can be characterized in the high-dimensional asymptotics $n,d\to \infty $, $n/d\to \delta $, and provides a lower bound to the estimation error of any firstorder algorithm. Here we present a simpler proof of the same result, and generalize it to broader classes of data distributions and of firstorder algorithms, including algorithms with non-separable nonlinearities. Most importantly, the new proof is simpler, does not require to construct an equivalent tree-structured estimation problem, and is therefore susceptible of a broader range of applications.

    

   more » « less
2. Learning Two-Layer Neural Networks with Symmetric Inputs

   Ge, Rong ; Kuditipudi, Rohith ; Li, Zhize ; Wang, Xiang ( July 2019 , International Conference on Learning Representations)

   We give a new algorithm for learning a two-layer neural network under a general class of input distributions. Assuming there is a ground-truth two-layer network y = Aσ(Wx) + ξ, where A,W are weight matrices, ξ represents noise, and the number of neurons in the hidden layer is no larger than the input or output, our algorithm is guaranteed to recover the parameters A,W of the ground-truth network. The only requirement on the input x is that it is symmetric, which still allows highly complicated and structured input. Our algorithm is based on the method-of-moments framework and extends several results in tensor decompositions. We use spectral algorithms to avoid the complicated non-convex optimization in learning neural networks. Experiments show that our algorithm can robustly learn the ground-truth neural network with a small number of samples for many symmetric input distributions. 

   more » « less
3. High dimensional, tabular deep learning with an auxiliary knowledge graph

   Ruiz, Camilo ; Ren, Hongyu ; Huang, Kexin ; Leskovec, Jure ( December 2023 , Advances in neural information processing systems)

   Machine learning models exhibit strong performance on datasets with abundant labeled samples. However, for tabular datasets with extremely high d-dimensional features but limited n samples (i.e. d ≫ n), machine learning models struggle to achieve strong performance due to the risk of overfitting. Here, our key insight is that there is often abundant, auxiliary domain information describing input features which can be structured as a heterogeneous knowledge graph (KG). We propose PLATO, a method that achieves strong performance on tabular data with d ≫ n by using an auxiliary KG describing input features to regularize a multilayer perceptron (MLP). In PLATO, each input feature corresponds to a node in the auxiliary KG. In the MLP’s first layer, each input feature also corresponds to a weight vector. PLATO is based on the inductive bias that two input features corresponding to similar nodes in the auxiliary KG should have similar weight vectors in the MLP’s first layer. PLATO captures this inductive bias by inferring the weight vector for each input feature from its corresponding node in the KG via a trainable message-passing function. Across 6 d ≫ n datasets, PLATO outperforms 13 state-of-the-art baselines by up to 10.19%. 

   more » « less
4. Hidden Symmetries of ReLU Networks

   Grigsby, Elisenda ; Lindsey, Kathryn ; Rolnick, David ( July 2023 , Proceedings of Machine Learning Research)

   Krause, Andreas ; Brunskill, Emma ; Cho, Kyunghyun ; Engelhardt, Barbara ; Sabato, Sivan ; Scarlett, Jonathan. (Ed.)

   The parameter space for any fixed architecture of feedforward ReLU neural networks serves as a proxy during training for the associated class of functions - but how faithful is this representation? It is known that many different parameter settings $\theta$ can determine the same function $f$. Moreover, the degree of this redundancy is inhomogeneous: for some networks, the only symmetries are permutation of neurons in a layer and positive scaling of parameters at a neuron, while other networks admit additional hidden symmetries. In this work, we prove that, for any network architecture where no layer is narrower than the input, there exist parameter settings with no hidden symmetries. We also describe a number of mechanisms through which hidden symmetries can arise, and empirically approximate the functional dimension of different network architectures at initialization. These experiments indicate that the probability that a network has no hidden symmetries decreases towards 0 as depth increases, while increasing towards 1 as width and input dimension increase. 

   more » « less
5. Fundamental limits for rank-one matrix estimation with groupwise heteroskedasticity

   Behne, J. ( January 2022 , International Conference on Artificial Intelligence and Statistics)

   Low-rank matrix recovery problems involving high-dimensional and heterogeneous data appear in applications throughout statistics and machine learning. The contribution of this paper is to establish the fundamental limits of recovery for a broad class of these problems. In particular, we study the problem of estimating a rank-one matrix from Gaussian observations where different blocks of the matrix are observed under different noise levels. In the setting where the number of blocks is fixed while the number of variables tends to infinity, we prove asymptotically exact formulas for the minimum mean-squared error in estimating both the matrix and underlying factors. These results are based on a novel reduction from the low-rank matrix tensor product model (with homogeneous noise) to a rank-one model with heteroskedastic noise. As an application of our main result, we show that show recently proposed methods based on applying principal component analysis (PCA) to weighted combinations of the data are optimal in some settings but sub-optimal in others. We also provide numerical results comparing our asymptotic formulas with the performance of methods based weighted PCA, gradient descent, and approximate message passing. 

   more » « less