11 citations · 30 across the 12 of their papers we have counts for
6 papers · 1 filter
Cryptographic Hardness of Score Estimation
Min Jae Song
We show that -accurate score estimation, in the absence of strong assumptions on the data distribution, is computationally hard even when sample complexity is polynomial in th…
Learning Single-Index Models with Shallow Neural Networks
Alberto Bietti, Joan Bruna, Clayton Sanford +1
Single-index models are a class of functions given by an unknown univariate ``link'' function applied to an unknown one-dimensional projection of the input. These models are partic…
Lattice-Based Methods Surpass Sum-of-Squares in Clustering
Ilias Zadik, Min Jae Song, Alexander S. Wein +1
Clustering is a fundamental primitive in unsupervised learning which gives rise to a rich class of computationally-challenging inference tasks. In this work, we focus on the canoni…
On the Cryptographic Hardness of Learning Single Periodic Neurons
Min Jae Song, Ilias Zadik, Joan Bruna
We show a simple reduction which demonstrates the cryptographic hardness of learning a single periodic neuron over isotropic Gaussian distributions in the presence of noise. More p…
Evaluating representations by the complexity of learning low-loss predictors
William F. Whitney, Min Jae Song, David Brandfonbrener +2
We consider the problem of evaluating representations of data for use in solving a downstream task. We propose to measure the quality of a representation by the complexity of learn…
Rapid Structural Pruning of Neural Networks with Set-based Task-Adaptive Meta-Pruning
Minyoung Song, Jaehong Yoon, Eunho Yang +1
As deep neural networks are growing in size and being increasingly deployed to more resource-limited devices, there has been a recent surge of interest in network pruning methods,…