Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2207.08437 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917948731424768 |
|---|---|
| author | Chou, Hung-Hsu Maly, Johannes Verdun, Claudio Mayrink da Costa, Bernardo Freitas Paulo Mirandola, Heudson |
| author_facet | Chou, Hung-Hsu Maly, Johannes Verdun, Claudio Mayrink da Costa, Bernardo Freitas Paulo Mirandola, Heudson |
| contents | Over the past years, there has been significant interest in understanding the implicit bias of gradient descent optimization and its connection to the generalization properties of overparametrized neural networks. Several works observed that when training linear diagonal networks on the square loss for regression tasks (which corresponds to overparametrized linear regression) gradient descent converges to special solutions, e.g., non-negative ones. We connect this observation to Riemannian optimization and view overparametrized GD with identical initialization as a Riemannian GD. We use this fact for solving non-negative least squares (NNLS), an important problem behind many techniques, e.g., non-negative matrix factorization. We show that gradient flow on the reparametrized objective converges globally to NNLS solutions, providing convergence rates also for its discretized counterpart. Unlike previous methods, we do not rely on the calculation of exponential maps or geodesics. We further show accelerated convergence using a second-order ODE, lending itself to accelerated descent methods. Finally, we establish the stability against negative perturbations and discuss generalization to other constrained optimization problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2207_08437 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Get rid of your constraints and reparametrize: A study in NNLS and implicit bias Chou, Hung-Hsu Maly, Johannes Verdun, Claudio Mayrink da Costa, Bernardo Freitas Paulo Mirandola, Heudson Optimization and Control Numerical Analysis Over the past years, there has been significant interest in understanding the implicit bias of gradient descent optimization and its connection to the generalization properties of overparametrized neural networks. Several works observed that when training linear diagonal networks on the square loss for regression tasks (which corresponds to overparametrized linear regression) gradient descent converges to special solutions, e.g., non-negative ones. We connect this observation to Riemannian optimization and view overparametrized GD with identical initialization as a Riemannian GD. We use this fact for solving non-negative least squares (NNLS), an important problem behind many techniques, e.g., non-negative matrix factorization. We show that gradient flow on the reparametrized objective converges globally to NNLS solutions, providing convergence rates also for its discretized counterpart. Unlike previous methods, we do not rely on the calculation of exponential maps or geodesics. We further show accelerated convergence using a second-order ODE, lending itself to accelerated descent methods. Finally, we establish the stability against negative perturbations and discuss generalization to other constrained optimization problems. |
| title | Get rid of your constraints and reparametrize: A study in NNLS and implicit bias |
| topic | Optimization and Control Numerical Analysis |
| url | https://arxiv.org/abs/2207.08437 |