More Like this

1. Neural Networks can Learn Representations with Gradient Descent

   Damian, Alexandru; Lee, Jason D.; Soltanolkotabi, Mahdi (July 2022, Proceedings of Thirty Fifth Conference on Learning Theory)

   Loh, Po-ling; Raginsky, Maxim (Ed.)

   Significant theoretical work has established that in specific regimes, neural networks trained by gradient descent behave like kernel methods. However, in practice, it is known that neural networks strongly outperform their associated kernels. In this work, we explain this gap by demonstrating that there is a large class of functions which cannot be efficiently learned by kernel methods but can be easily learned with gradient descent on a two layer neural network outside the kernel regime by learning representations that are relevant to the target task. We also demonstrate that these representations allow for efficient transfer learning, which is impossible in the kernel regime. Specifically, we consider the problem of learning polynomials which depend on only a few relevant directions, i.e. of the form f⋆(x)=g(Ux) where U:\Rd→\Rr with d≫r. When the degree of f⋆ is p, it is known that n≍dp samples are necessary to learn f⋆ in the kernel regime. Our primary result is that gradient descent learns a representation of the data which depends only on the directions relevant to f⋆. This results in an improved sample complexity of n≍d2 and enables transfer learning with sample complexity independent of d. 

   more » « less
2. Neural Networks can Learn Representations with Gradient Descent

   Damian, Alex; Lee, Jason; Soltanolkotabi, Mahdi (January 2022, Advances in neural information processing systems)

   Significant theoretical work has established that in specific regimes, neural networks trained by gradient descent behave like kernel methods. However, in practice, it is known that neural networks strongly outperform their associated kernels. In this work, we explain this gap by demonstrating that there is a large class of functions which cannot be efficiently learned by kernel methods but can be easily learned with gradient descent on a two layer neural network outside the kernel regime by learning representations that are relevant to the target task. We also demonstrate that these representations allow for efficient transfer learning, which is impossible in the kernel regime. Specifically, we consider the problem of learning polynomials which depend on only a few relevant directions, i.e. of the form $f(x)=g(Ux)$ where $$U: \R^d \to \R^r$$ with $d≫r$. When the degree of f⋆ is p, it is known that n≍dp samples are necessary to learn f⋆ in the kernel regime. Our primary result is that gradient descent learns a representation of the data which depends only on the directions relevant to f. This results in an improved sample complexity of n≍d2r+drp. Furthermore, in a transfer learning setup where the data distributions in the source and target domain share the same representation U but have different polynomial heads we show that a popular heuristic for transfer learning has a target sample complexity independent of d. 

   more » « less
3. Beyond Lazy Training for Over-parameterized Tensor Decomposition

   Wang, Xiang; Wu, Chenwei; Lee, Jason D; Ma, Tengyu; Ge, Rong (January 2020, NeurIPS)

   Over-parametrization is an important technique in training neural networks. In both theory and practice, training a larger network allows the optimization algorithm to avoid bad local optimal solutions. In this paper we study a closely related tensor decomposition problem: given an l-th order tensor in (Rd)⊗l of rank r (where r≪d), can variants of gradient descent find a rank m decomposition where m>r? We show that in a lazy training regime (similar to the NTK regime for neural networks) one needs at least m=Ω(dl−1), while a variant of gradient descent can find an approximate tensor when m=O∗(r2.5llogd). Our results show that gradient descent on over-parametrized objective could go beyond the lazy training regime and utilize certain low-rank structure in the data. 

   more » « less
4. Hopper flows of deformable particles

   https://doi.org/10.1039/d2sm01079h  

   Cheng, Yuxuan; Treado, John D.; Lonial, Benjamin F.; Habdas, Piotr; Weeks, Eric R.; Shattuck, Mark D.; O'Hern, Corey S. (November 2022, Soft Matter)

   Numerous experimental and computational studies show that continuous hopper flows of granular materials obey the Beverloo equation that relates the volume flow rate Q and the orifice width w : Q ∼ ( w / σ avg − k ) β , where σ avg is the average particle diameter, kσ avg is an offset where Q ∼ 0, the power-law scaling exponent β = d − 1/2, and d is the spatial dimension. Recent studies of hopper flows of deformable particles in different background fluids suggest that the particle stiffness and dissipation mechanism can also strongly affect the power-law scaling exponent β . We carry out computational studies of hopper flows of deformable particles with both kinetic friction and background fluid dissipation in two and three dimensions. We show that the exponent β varies continuously with the ratio of the viscous drag to the kinetic friction coefficient, λ = ζ / μ . β = d − 1/2 in the λ → 0 limit and d − 3/2 in the λ → ∞ limit, with a midpoint λ c that depends on the hopper opening angle θ w . We also characterize the spatial structure of the flows and associate changes in spatial structure of the hopper flows to changes in the exponent β . The offset k increases with particle stiffness until k ∼ k max in the hard-particle limit, where k max ∼ 3.5 is larger for λ → ∞ compared to that for λ → 0. Finally, we show that the simulations of hopper flows of deformable particles in the λ → ∞ limit recapitulate the experimental results for quasi-2D hopper flows of oil droplets in water. 

   more » « less
5. On Single-Index Models beyond Gaussian Data

   Bruna, Joan; Pillaud-Vivien, Loucas; Zweig, Aaron (December 2023, Neural Information Processing Systems)

   Sparse high-dimensional functions have arisen as a rich framework to study the behavior of gradient-descent methods using shallow neural networks, showcasing their ability to perform feature learning beyond linear models. Amongst those functions, the simplest are single-index models f(x) = φ(x · θ∗), where the labels are generated by an arbitrary non-linear scalar link function φ applied to an unknown one-dimensional projection θ∗ of the input data. By focusing on Gaussian data, several recent works have built a remarkable picture, where the so-called information exponent (related to the regularity of the link function) controls the required sample complexity. In essence, these tools exploit the stability and spherical symmetry of Gaussian distributions. In this work, building from the framework of [Ben Arous et al., 2021], we explore extensions of this picture beyond the Gaussian setting, where both stability or symmetry might be violated. Focusing on the planted setting where φ is known, our main results establish that Stochastic Gradient Descent can efficiently recover the unknown direction θ∗ in the high- dimensional regime, under assumptions that extend previous works [Yehudai and Shamir, 2020, Wu, 2022] 

   more » « less