Journal article
The statistical complexity of early-stopped mirror descent
- Abstract:
- Recently there has been a surge of interest in understanding implicit regularization properties of iterative gradient-based optimization algorithms. In this paper, we study the statistical guarantees on the excess risk achieved by early-stopped unconstrained mirror descent algorithms applied to the unregularized empirical risk. We consider the set-up of learning linear models and kernel methods for strongly convex and Lipschitz loss functions while imposing only boundedness conditions on the unknown data-generating mechanism. By completing an inequality that characterizes convexity for the squared loss, we identify an intrinsic link between offset Rademacher complexities and potential-based convergence analysis of mirror descent methods. Our observation immediately yields excess risk guarantees for the path traced by the iterates of mirror descent in terms of offset complexities of certain function classes depending only on the choice of the mirror map, initialization point, step size and the number of iterations. We apply our theory to recover, in a clean and elegant manner via rather short proofs, some of the recent results in the implicit regularization literature while also showing how to improve upon them in some settings.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 629.4KB, Terms of use)
-
- Publisher copy:
- 10.1093/imaiai/iaad047
Authors
- Publisher:
- Oxford University Press
- Journal:
- Information and Inference: A Journal of the IMA More from this journal
- Volume:
- 12
- Issue:
- 4
- Pages:
- 3010-3041
- Publication date:
- 2023-11-23
- Acceptance date:
- 2023-10-22
- DOI:
- EISSN:
-
2049-8772
- ISSN:
-
2049-8764
- Language:
-
English
- Keywords:
- Pubs id:
-
1588677
- Local pid:
-
pubs:1588677
- Deposit date:
-
2024-01-03
- ARK identifier:
Terms of use
- Copyright holder:
- Kanade et al.
- Copyright date:
- 2023
- Rights statement:
- © The Author(s) 2023. Published by Oxford University Press on behalf of the Institute of Mathematics and its Applications. All rights reserved. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted reuse, distribution, and reproduction in any medium, provided the original work is properly cited.
- Notes:
- For the purpose of open access, all the authors have applied the CC BY public copyright licence to any author accepted manuscript version arising from this submission.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record