Learning Orthogonal Multi-Index Models: A Fine-Grained Information Exponent Analysis
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912627760824320 |
|---|---|
| author | Ren, Yunwei Lee, Jason D. |
| author_facet | Ren, Yunwei Lee, Jason D. |
| contents | The information exponent ([BAGJ21]) and its extensions -- which are equivalent to the lowest
degree in the Hermite expansion of the link function (after a potential label transform) for Gaussian single-index
models -- have played an important role in predicting the sample complexity of online stochastic gradient descent
(SGD) in various learning tasks. In this work, we demonstrate that, for multi-index models, focusing solely on the
lowest degree can miss key structural details of the model and result in suboptimal rates.
Specifically, we consider the task of learning target functions of form $f_*(\mathbf{x}) = \sum_{k=1}^{P} ϕ(\mathbf{v}_k^* \cdot \mathbf{x})$,
where $P \ll d$, the ground-truth directions $\{ \mathbf{v}_k^* \}_{k=1}^P$ are orthonormal, and the information exponent of
$ϕ$ is $L$. Based on the theory of information exponent, when $L = 2$, only the relevant subspace (not the exact
directions) can be recovered due to the rotational invariance of the second-order terms, and when $L > 2$,
recovering the directions using online SGD require $\tilde{O}(P d^{L-1})$ samples. In this work, we show that by
considering both second- and higher-order terms, we can first learn the relevant space using the second-order
terms, and then the exact directions using the higher-order terms, and the overall sample and complexity of online
SGD is $\tilde{O}( d P^{L-1} )$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_09678 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Learning Orthogonal Multi-Index Models: A Fine-Grained Information Exponent Analysis Ren, Yunwei Lee, Jason D. Machine Learning The information exponent ([BAGJ21]) and its extensions -- which are equivalent to the lowest degree in the Hermite expansion of the link function (after a potential label transform) for Gaussian single-index models -- have played an important role in predicting the sample complexity of online stochastic gradient descent (SGD) in various learning tasks. In this work, we demonstrate that, for multi-index models, focusing solely on the lowest degree can miss key structural details of the model and result in suboptimal rates. Specifically, we consider the task of learning target functions of form $f_*(\mathbf{x}) = \sum_{k=1}^{P} ϕ(\mathbf{v}_k^* \cdot \mathbf{x})$, where $P \ll d$, the ground-truth directions $\{ \mathbf{v}_k^* \}_{k=1}^P$ are orthonormal, and the information exponent of $ϕ$ is $L$. Based on the theory of information exponent, when $L = 2$, only the relevant subspace (not the exact directions) can be recovered due to the rotational invariance of the second-order terms, and when $L > 2$, recovering the directions using online SGD require $\tilde{O}(P d^{L-1})$ samples. In this work, we show that by considering both second- and higher-order terms, we can first learn the relevant space using the second-order terms, and then the exact directions using the higher-order terms, and the overall sample and complexity of online SGD is $\tilde{O}( d P^{L-1} )$. |
| title | Learning Orthogonal Multi-Index Models: A Fine-Grained Information Exponent Analysis |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2410.09678 |