153 citations · 1k across the 72 of their papers we have counts for
6 papers · 1 filter
Stationary Points of Shallow Neural Networks with Quadratic Activation Function
David Gamarnik, Eren C. Kızıldağ, Ilias Zadik
We consider the teacher-student setting of learning shallow neural networks with quadratic activations and planted weight matrix , where is the wi…
The Overlap Gap Property and Approximate Message Passing Algorithms for -spin models
David Gamarnik, Aukosh Jagannath
We consider the algorithmic problem of finding a near ground state (near optimal solution) of a -spin model. We show that for a class of algorithms broadly defined as Approximat…
Inference in High-Dimensional Linear Regression via Lattice Basis Reduction and Integer Relation Detection
David Gamarnik, Eren C. Kızıldağ, Ilias Zadik
We focus on the high-dimensional linear regression problem, where the algorithmic goal is to efficiently infer an unknown feature vector from its linear measur…
The Overlap Gap Property in Principal Submatrix Recovery
David Gamarnik, Aukosh Jagannath, Subhabrata Sen
We study support recovery for a principal submatrix with elevated mean , hidden in an symmetric mean zero Gaussian matrix. Here is a universal c…
Sparse High-Dimensional Isotonic Regression
David Gamarnik, Julia Gaudio
We consider the problem of estimating an unknown coordinate-wise monotone function given noisy measurements, known as the isotonic regression problem. Often, only a small subset of…
The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
David Gamarnik, Ilias Zadik
In this paper we study the computational-statistical gap of the planted clique problem, where a clique of size is planted in an Erdos Renyi graph resulting i…