Unbiased least squares regression via averaged stochastic gradient descent
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912713754542080 |
|---|---|
| author | Kahalé, Nabil |
| author_facet | Kahalé, Nabil |
| contents | We consider an on-line least squares regression problem with optimal solution $θ^*$ and Hessian matrix H, and study a time-average stochastic gradient descent estimator of $θ^*$. For $k\ge2$, we provide an unbiased estimator of $θ^*$ that is a modification of the time-average estimator, runs with an expected number of time-steps of order k, with O(1/k) expected excess risk. The constant behind the O notation depends on parameters of the regression and is a poly-logarithmic function of the smallest eigenvalue of H. We provide both a biased and unbiased estimator of the expected excess risk of the time-average estimator and of its unbiased counterpart, without requiring knowledge of either H or $θ^*$. We describe an "average-start" version of our estimators with similar properties. Our approach is based on randomized multilevel Monte Carlo. Our numerical experiments confirm our theoretical findings. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_18623 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Unbiased least squares regression via averaged stochastic gradient descent Kahalé, Nabil Machine Learning Methodology 62Jxx 65K05 65C05 We consider an on-line least squares regression problem with optimal solution $θ^*$ and Hessian matrix H, and study a time-average stochastic gradient descent estimator of $θ^*$. For $k\ge2$, we provide an unbiased estimator of $θ^*$ that is a modification of the time-average estimator, runs with an expected number of time-steps of order k, with O(1/k) expected excess risk. The constant behind the O notation depends on parameters of the regression and is a poly-logarithmic function of the smallest eigenvalue of H. We provide both a biased and unbiased estimator of the expected excess risk of the time-average estimator and of its unbiased counterpart, without requiring knowledge of either H or $θ^*$. We describe an "average-start" version of our estimators with similar properties. Our approach is based on randomized multilevel Monte Carlo. Our numerical experiments confirm our theoretical findings. |
| title | Unbiased least squares regression via averaged stochastic gradient descent |
| topic | Machine Learning Methodology 62Jxx 65K05 65C05 |
| url | https://arxiv.org/abs/2406.18623 |