مقاله یادگیری چند جمله ای های سلسله مراتبی با شبکه های عصبی سه لایه

چکیده

We study the problem of learning hierarchical polynomials over the standard Gaussian distribution with three-layer neural networks. We specifically consider target functions of the form $h = g \circ p$ where $p : \mathbb{R}^d \rightarrow \mathbb{R}$ is a degree $k$ polynomial and $g: \mathbb{R} \rightarrow \mathbb{R}$ is a degree $q$ polynomial. This function class generalizes the single-index model, which corresponds to $k=1$, and is a natural class of functions possessing an underlying hierarchical structure. Our main result shows that for a large subclass of degree $k$ polynomials $p$, a three-layer neural network trained via layerwise gradient descent on the square loss learns the target $h$ up to vanishing test error in $\widetilde{\mathcal{O}}(d^k)$ samples and polynomial time. This is a strict improvement over kernel methods, which require $\widetilde Θ(d^{kq})$ samples, as well as existing guarantees for two-layer networks, which require the target function to be low-rank. Our result also generalizes prior works on three-layer neural networks, which were restricted to the case of $p$ being a quadratic. When $p$ is indeed a quadratic, we achieve the information-theoretically optimal sample complexity $\widetilde{\mathcal{O}}(d^2)$, which is an improvement over prior work~\citep{nichani2023provable} requiring a sample size of $\widetildeΘ(d^4)$. Our proof proceeds by showing that during the initial stage of training the network performs feature learning to recover the feature $p$ with $\widetilde{\mathcal{O}}(d^k)$ samples. This work demonstrates the ability of three-layer neural networks to learn complex features and as a result, learn a broad class of hierarchical functions.

چکیده به فارسی (ترجمه ماشینی)

ما مسئله یادگیری چند جمله ای سلسله مراتبی را بر روی توزیع استاندارد گاوسی با شبکه های عصبی سه لایه مطالعه می کنیم.ما به طور خاص توابع هدف فرم $ h = g \ circ p $ را در نظر می گیریم که در آن $ p: \ mathbb {r}^d \ rightarrow \ mathbb {r} $ یک درجه $ $ چند جمله ای و $ g: \ mathbb {r} \ RightArrow \ Mathbb {r} $ درجه $ q $ چند جمله ای است.این کلاس عملکرد مدل تک شاخصی را که مطابق با $ k = 1 $ است ، تعمیم می دهد و یک کلاس طبیعی از توابع است که دارای یک ساختار سلسله مراتبی اساسی است.نتیجه اصلی ما نشان می دهد که برای یک زیر کلاس بزرگ درجه $ k $ چند جمله ای $ p $ ، یک شبکه عصبی سه لایه که از طریق نزول شیب لایه ای آموزش دیده در ضرر مربع آموزش داده می شود ، هدف H $ H $ را تا خطای تست ناپدید شده در $ \ widetilde {می آموزد.\ mathcal {o}} (d^k) $ نمونه و زمان چند جمله ای.این یک پیشرفت دقیق نسبت به روشهای هسته است ، که به نمونه های $ $ \ widetilde θ (d^{kq}) $ و همچنین ضمانت های موجود برای شبکه های دو لایه نیاز دارند ، که نیاز به عملکرد هدف دارند.نتیجه ما همچنین کارهای قبلی را در شبکه های عصبی سه لایه تعمیم می دهد ، که محدود به پرونده P $ $ درجه دوم است.هنگامی که $ p $ در واقع یک درجه دوم است ، ما به پیچیدگی نمونه اطلاعاتی بهینه $ \ widetilde {\ mathcal {o}}} (d^2) $ دست می یابیم ، که این یک بهبود در کار قبلی است \ citep {nichani2023Provable} نیاز به یک نیاز بهاندازه نمونه $ \ widetildeθ (d^4) $.اثبات ما با نشان دادن اینكه در مرحله اولیه آموزش شبکه یادگیری ویژگی را برای بازیابی ویژگی $ p $ با $ \ widetilde {\ mathcal {o}} (d^k) $ انجام می دهد.این کار توانایی شبکه های عصبی سه لایه برای یادگیری ویژگی های پیچیده را نشان می دهد و در نتیجه ، طبقه گسترده ای از عملکردهای سلسله مراتبی را یاد بگیرید.