Novel Bounds for Incremental Hessian Estimation With Application to Zeroth-Order Federated Learning
The Hessian matrix conveys important information about the curvature, spectrum and partial derivatives of a function, and is required in a variety of tasks. However, computing the exact Hessian is prohibitively expensive for high-dimensional input spaces, and is just impossible in zeroth-order optim...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2024-01-01
|
| Series: | IEEE Open Journal of Control Systems |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10499850/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850148363665670144 |
|---|---|
| author | Alessio Maritan Luca Schenato Subhrakanti Dey |
| author_facet | Alessio Maritan Luca Schenato Subhrakanti Dey |
| author_sort | Alessio Maritan |
| collection | DOAJ |
| description | The Hessian matrix conveys important information about the curvature, spectrum and partial derivatives of a function, and is required in a variety of tasks. However, computing the exact Hessian is prohibitively expensive for high-dimensional input spaces, and is just impossible in zeroth-order optimization, where the objective function is a black-box of which only input-output pairs are known. In this work we address this relevant problem by providing a rigorous analysis of an Hessian estimator available in the literature, allowing it to be used as a provably accurate replacement of the true Hessian matrix. The Hessian estimator is randomized and incremental, and its computation requires only point function evaluations. We provide non-asymptotic convergence bounds on the estimation error and derive the minimum number of function queries needed to achieve a desired accuracy with arbitrarily high probability. In the second part of the paper we show a practical application of our results, introducing a novel optimization algorithm suitable for non-convex and black-box federated learning. The algorithm only requires clients to evaluate their local functions at certain input points, and builds a sufficiently accurate estimate of the global Hessian matrix in a distributed way. The algorithm exploits inexact cubic regularization to escape saddle points and guarantees convergence with optimal iteration complexity and high probability. Numerical results show that the proposed algorithm outperforms the existing zeroth-order federated algorithms in both convex and non-convex problems. Furthermore, we achieve similar performance to state-of-the-art algorithms for federated convex optimization that use exact gradients and Hessian matrices. |
| format | Article |
| id | doaj-art-e6ed8656371a4013965fbd49f7b93854 |
| institution | OA Journals |
| issn | 2694-085X |
| language | English |
| publishDate | 2024-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Open Journal of Control Systems |
| spelling | doaj-art-e6ed8656371a4013965fbd49f7b938542025-08-20T02:27:16ZengIEEEIEEE Open Journal of Control Systems2694-085X2024-01-01317318910.1109/OJCSYS.2024.338837410499850Novel Bounds for Incremental Hessian Estimation With Application to Zeroth-Order Federated LearningAlessio Maritan0https://orcid.org/0009-0004-1143-2623Luca Schenato1https://orcid.org/0000-0003-2544-2553Subhrakanti Dey2https://orcid.org/0000-0003-0762-5743Department of Information Engineering, University of Padova, Padova, ItalyDepartment of Information Engineering, University of Padova, Padova, ItalyDepartment of Electrical Engineering, Uppsala University, Uppsala, SwedenThe Hessian matrix conveys important information about the curvature, spectrum and partial derivatives of a function, and is required in a variety of tasks. However, computing the exact Hessian is prohibitively expensive for high-dimensional input spaces, and is just impossible in zeroth-order optimization, where the objective function is a black-box of which only input-output pairs are known. In this work we address this relevant problem by providing a rigorous analysis of an Hessian estimator available in the literature, allowing it to be used as a provably accurate replacement of the true Hessian matrix. The Hessian estimator is randomized and incremental, and its computation requires only point function evaluations. We provide non-asymptotic convergence bounds on the estimation error and derive the minimum number of function queries needed to achieve a desired accuracy with arbitrarily high probability. In the second part of the paper we show a practical application of our results, introducing a novel optimization algorithm suitable for non-convex and black-box federated learning. The algorithm only requires clients to evaluate their local functions at certain input points, and builds a sufficiently accurate estimate of the global Hessian matrix in a distributed way. The algorithm exploits inexact cubic regularization to escape saddle points and guarantees convergence with optimal iteration complexity and high probability. Numerical results show that the proposed algorithm outperforms the existing zeroth-order federated algorithms in both convex and non-convex problems. Furthermore, we achieve similar performance to state-of-the-art algorithms for federated convex optimization that use exact gradients and Hessian matrices.https://ieeexplore.ieee.org/document/10499850/Data privacyestimationfederated learningfinite difference methodsoptimization |
| spellingShingle | Alessio Maritan Luca Schenato Subhrakanti Dey Novel Bounds for Incremental Hessian Estimation With Application to Zeroth-Order Federated Learning IEEE Open Journal of Control Systems Data privacy estimation federated learning finite difference methods optimization |
| title | Novel Bounds for Incremental Hessian Estimation With Application to Zeroth-Order Federated Learning |
| title_full | Novel Bounds for Incremental Hessian Estimation With Application to Zeroth-Order Federated Learning |
| title_fullStr | Novel Bounds for Incremental Hessian Estimation With Application to Zeroth-Order Federated Learning |
| title_full_unstemmed | Novel Bounds for Incremental Hessian Estimation With Application to Zeroth-Order Federated Learning |
| title_short | Novel Bounds for Incremental Hessian Estimation With Application to Zeroth-Order Federated Learning |
| title_sort | novel bounds for incremental hessian estimation with application to zeroth order federated learning |
| topic | Data privacy estimation federated learning finite difference methods optimization |
| url | https://ieeexplore.ieee.org/document/10499850/ |
| work_keys_str_mv | AT alessiomaritan novelboundsforincrementalhessianestimationwithapplicationtozerothorderfederatedlearning AT lucaschenato novelboundsforincrementalhessianestimationwithapplicationtozerothorderfederatedlearning AT subhrakantidey novelboundsforincrementalhessianestimationwithapplicationtozerothorderfederatedlearning |