Automatic Differentiation of Some First-Order Methods in Parametric Optimization

Sheheryar Mehmood, Peter Ochs
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:1584-1594, 2020.

Abstract

We aim at computing the derivative of the solution to a parametric optimization problem with respect to the involved parameters. For a class broader than that of strongly convex functions, this can be achieved by automatic differentiation of iterative minimization algorithms. If the iterative algorithm converges pointwise, then we prove that the derivative sequence also converges pointwise to the derivative of the minimizer with respect to the parameters. Moreover, we provide convergence rates for both sequences. In particular, we prove that the accelerated convergence rate of the Heavy-ball method compared to Gradient Descent also accelerates the derivative computation. An experiment with L2-Regularized Logistic Regression validates the theoretical results.

Cite this Paper


BibTeX
@InProceedings{pmlr-v108-mehmood20a, title = {Automatic Differentiation of Some First-Order Methods in Parametric Optimization}, author = {Mehmood, Sheheryar and Ochs, Peter}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {1584--1594}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/mehmood20a/mehmood20a.pdf}, url = {http://proceedings.mlr.press/v108/mehmood20a.html}, abstract = {We aim at computing the derivative of the solution to a parametric optimization problem with respect to the involved parameters. For a class broader than that of strongly convex functions, this can be achieved by automatic differentiation of iterative minimization algorithms. If the iterative algorithm converges pointwise, then we prove that the derivative sequence also converges pointwise to the derivative of the minimizer with respect to the parameters. Moreover, we provide convergence rates for both sequences. In particular, we prove that the accelerated convergence rate of the Heavy-ball method compared to Gradient Descent also accelerates the derivative computation. An experiment with L2-Regularized Logistic Regression validates the theoretical results.} }
Endnote
%0 Conference Paper %T Automatic Differentiation of Some First-Order Methods in Parametric Optimization %A Sheheryar Mehmood %A Peter Ochs %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-mehmood20a %I PMLR %P 1584--1594 %U http://proceedings.mlr.press/v108/mehmood20a.html %V 108 %X We aim at computing the derivative of the solution to a parametric optimization problem with respect to the involved parameters. For a class broader than that of strongly convex functions, this can be achieved by automatic differentiation of iterative minimization algorithms. If the iterative algorithm converges pointwise, then we prove that the derivative sequence also converges pointwise to the derivative of the minimizer with respect to the parameters. Moreover, we provide convergence rates for both sequences. In particular, we prove that the accelerated convergence rate of the Heavy-ball method compared to Gradient Descent also accelerates the derivative computation. An experiment with L2-Regularized Logistic Regression validates the theoretical results.
APA
Mehmood, S. & Ochs, P.. (2020). Automatic Differentiation of Some First-Order Methods in Parametric Optimization. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:1584-1594 Available from http://proceedings.mlr.press/v108/mehmood20a.html.

Related Material