{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T07:01:03Z","timestamp":1760598063112,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T00:00:00Z","timestamp":1626652800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T00:00:00Z","timestamp":1626652800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005714","name":"Technische Universit\u00e4t Darmstadt","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005714","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Convex optimizers have known many applications as differentiable layers within deep neural architectures. One application of these convex layers is to project points into a convex set. However, both forward and backward passes of these convex layers are significantly more expensive to compute than those of a typical neural network. We investigate in this paper whether an inexact, but cheaper projection, can drive a descent algorithm to an optimum. Specifically, we propose an interpolation-based projection that is computationally cheap and easy to compute given a convex, domain defining, function. We then propose an optimization algorithm that follows the gradient of the composition of the objective and the projection and prove its convergence for linear objectives and arbitrary convex and Lipschitz domain defining inequality constraints. In addition to the theoretical contributions, we demonstrate empirically the practical interest of the interpolation projection when used in conjunction with neural networks in a reinforcement learning and a supervised learning setting.<\/jats:p>","DOI":"10.1007\/s10994-021-06037-z","type":"journal-article","created":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T21:02:46Z","timestamp":1626728566000},"page":"2267-2289","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Convex optimization with an interpolation-based projection and its application to deep learning"],"prefix":"10.1007","volume":"110","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8735-6960","authenticated-orcid":false,"given":"Riad","family":"Akrour","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Asma","family":"Atamna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Peters","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,19]]},"reference":[{"unstructured":"Agrawal, A., Amos, B., Barratt, S. T., Boyd, S. P., Diamond, S., & Kolter, J. Z. (2019). Differentiable convex optimization layers. In Advances in neural information processing systems (NeurIPS) (pp. 9558\u20139570).","key":"6037_CR1"},{"unstructured":"Akrour, R., Pajarinen, J., Neumann, G., & Peters, J. (2019). Projections for approximate policy iteration algorithms. In International conference on machine learning (ICML).","key":"6037_CR2"},{"unstructured":"Amos, B., & Kolter, J. Z. (2017). OptNet: Differentiable optimization as a layer in neural networks. In International conference on machine learning (ICML), proceedings of machine learning research (Vol.\u00a070, pp. 136\u2013145).","key":"6037_CR3"},{"unstructured":"Amos, B., Rodriguez, I. D. J., Sacks, J., Boots, B., & Kolter, J. Z. (2018). Differentiable MPC for end-to-end planning and control. In International conference on neural information processing systems (NeurIPS) (pp. 8299\u20138310).","key":"6037_CR4"},{"doi-asserted-by":"crossref","unstructured":"Barratt, S., & Boyd, S. (2019). Fitting a Kalman smoother to data. arXiv:1910.08615.","key":"6037_CR6","DOI":"10.23919\/ACC45564.2020.9147485"},{"unstructured":"Bertinetto, L., Henriques, J. F., Torr, P., & Vedaldi, A. (2019). Meta-learning with differentiable closed-form solvers. In International conference on learning representations (ICLR).","key":"6037_CR7"},{"issue":"3","key":"6037_CR8","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/s11768-011-1005-3","volume":"9","author":"DP Bertsekas","year":"2011","unstructured":"Bertsekas, D. P. (2011). Approximate policy iteration: A survey and some new methods. Journal of Control Theory and Applications, 9(3), 310\u2013335.","journal-title":"Journal of Control Theory and Applications"},{"key":"6037_CR9","volume-title":"Convex optimization algorithms","author":"DP Bertsekas","year":"2015","unstructured":"Bertsekas, D. P. (2015). Convex optimization algorithms. Singapore: Athena Scientific."},{"key":"6037_CR10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., & Vandenberghe, L. (2004). Convex optimization. Cambridge: Cambridge University Press."},{"unstructured":"Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., & Zaremba, W. (2016). Openai gym.","key":"6037_CR11"},{"doi-asserted-by":"crossref","unstructured":"Bubeck, S. (2014). Convex Optimization: Algorithms and Complexity. arXiv:1405.4980.","key":"6037_CR12","DOI":"10.1561\/9781601988614"},{"unstructured":"Catto, E. (2007). Box2d. box2d.org.","key":"6037_CR13"},{"doi-asserted-by":"crossref","unstructured":"Combettes, P. L. (1997). Convex set theoretic image recovery by extrapolated iterations of parallel subgradient projections. IEEE Transactions on Image Processing.","key":"6037_CR14","DOI":"10.1109\/83.563316"},{"unstructured":"de\u00a0Avila Belbute-Peres, F., Smith, K., Allen, K., Tenenbaum, J., & Kolter, J. Z. (2018). End-to-end differentiable physics for learning and control. In Advances in neural information processing systems (NeurIPS) (pp. 7178\u20137189).","key":"6037_CR5"},{"issue":"1\u20132","key":"6037_CR15","first-page":"388","volume":"2","author":"MP Deisenroth","year":"2013","unstructured":"Deisenroth, M. P., Neumann, G., & Peters, J. (2013). A survey on policy search for robotics. Foundations and Trends in Robotics, 2(1\u20132), 388\u2013403.","journal-title":"Foundations and Trends in Robotics"},{"issue":"1","key":"6037_CR16","first-page":"2909","volume":"17","author":"S Diamond","year":"2016","unstructured":"Diamond, S., & Boyd, S. (2016). CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(1), 2909\u20132913.","journal-title":"Journal of Machine Learning Research"},{"key":"6037_CR17","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1002\/nav.3800030109","volume":"3","author":"M Frank","year":"1956","unstructured":"Frank, M., & Wolfe, P. (1956). An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3, 95\u2013110.","journal-title":"Naval Research Logistics Quarterly"},{"key":"6037_CR18","doi-asserted-by":"publisher","first-page":"109099","DOI":"10.1016\/j.jcp.2019.109099","volume":"406","author":"Z Geng","year":"2019","unstructured":"Geng, Z., Johnson, D., & Fedkiw, R. (2019). Coercing machine learning to output physically accurate results. Journal of Computational Physics, 406, 109099.","journal-title":"Journal of Computational Physics"},{"unstructured":"Grant, M., & Boyd, S. (2014). CVX: Matlab software for disciplined convex programming, version 2.1. http:\/\/cvxr.com\/cvx.","key":"6037_CR19"},{"doi-asserted-by":"crossref","unstructured":"Grant, M., Boyd, S., & Ye, Y. (2006). Disciplined convex programming. In: Global optimization: From theory to implementation (pp. 155\u2013210).","key":"6037_CR20","DOI":"10.1007\/0-387-30528-9_7"},{"doi-asserted-by":"crossref","unstructured":"Grant, M. C., & Boyd, S. P. (2008). Graph implementations for nonsmooth convex programs. In Recent advances in learning and control (pp. 95\u2013110).","key":"6037_CR21","DOI":"10.1007\/978-1-84800-155-8_7"},{"unstructured":"Hansen, N., Auger, A., Mersmann, O., Tu\u0161ar, T., & Brockhoff, D. (2016). COCO: A platform for comparing continuous optimizers in a black-box setting. ArXiv e-prints. arXiv:1603.08785.","key":"6037_CR22"},{"doi-asserted-by":"publisher","unstructured":"Hansen, N., Brockhoff, D., Mersmann, O., Tu\u0161ar, T., Tu\u0161ar, D., ElHara, O. A., et al. (2019). COmparing Continuous Optimizers: numbbo\/COCO on Github.https:\/\/doi.org\/10.5281\/zenodo.2594848.","key":"6037_CR23","DOI":"10.5281\/zenodo.2594848"},{"doi-asserted-by":"crossref","unstructured":"Karmarkar, N. (1984). A new polynomial-time algorithm for linear programming. In Proceedings of the sixteenth annual ACM symposium on theory of computing (pp. 302\u2013311).","key":"6037_CR24","DOI":"10.1145\/800057.808695"},{"unstructured":"Kingma, D. P., & Ba, J. (2015). Adam: A method for stochastic optimization. In International conference on learning representations (ICLR).","key":"6037_CR25"},{"doi-asserted-by":"crossref","unstructured":"Kuhn, H. W., & Tucker, A. W. (1951). Nonlinear programming. In Proceedings of the second Berkeley symposium on mathematical statistics and probability (pp. 481\u2013492). University of California Press.","key":"6037_CR26","DOI":"10.1525\/9780520411586-036"},{"unstructured":"Lan, G., & Zhou, Z. (2016). Algorithms for stochastic optimization with functional or expectation constraints. arXiv:1604.03887.","key":"6037_CR27"},{"issue":"2","key":"6037_CR28","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/0377-2217(94)00200-2","volume":"88","author":"T Larsson","year":"1996","unstructured":"Larsson, T., Patriksson, M., & Str\u00f6mberg, A. B. (1996). Conditional subgradient optimization\u2014Theory and applications. European Journal of Operational Research, 88(2), 382\u2013403.","journal-title":"European Journal of Operational Research"},{"doi-asserted-by":"crossref","unstructured":"Lee, K., Maji, S., Ravichandran, A., & Soatto, S. (2019). Meta-learning with differentiable convex optimization. In IEEE conference on computer vision and pattern recognition (CVPR) (pp 10657\u201310665).","key":"6037_CR29","DOI":"10.1109\/CVPR.2019.01091"},{"issue":"1","key":"6037_CR30","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1137\/070704575","volume":"20","author":"J Malick","year":"2009","unstructured":"Malick, J., Povh, J., Rendl, F., & Wiegele, A. (2009). Regularization methods for semidefinite programming. SIAM Journal on Optimization, 20(1), 336\u2013356.","journal-title":"SIAM Journal on Optimization"},{"doi-asserted-by":"crossref","unstructured":"Nesterov, Y. E., & Nemirovskii, A. (1994). Interior-point polynomial algorithms in convex programming, Siam studies in applied mathematics (Vol.\u00a013). SIAM.","key":"6037_CR31","DOI":"10.1137\/1.9781611970791"},{"key":"6037_CR32","volume-title":"Numerical optimization. Springer Series in Operations Research and Financial Engineering","author":"J Nocedal","year":"2006","unstructured":"Nocedal, J., & Wright, S. (2006). Numerical optimization. Springer Series in Operations Research and Financial Engineering. New York: Springer."},{"issue":"7\u20139","key":"6037_CR33","doi-asserted-by":"publisher","first-page":"1180","DOI":"10.1016\/j.neucom.2007.11.026","volume":"71","author":"J Peters","year":"2008","unstructured":"Peters, J., & Schaal, S. (2008). Natural actor-critic. Neurocomputation, 71(7\u20139), 1180\u20131190.","journal-title":"Neurocomputation"},{"unstructured":"Rajeswaran, A., Lowrey, K., Todorov, E., & Kakade, S. M. (2017). Towards generalization and simplicity in continuous control. In Conference on neural information processing systems (NIPS).","key":"6037_CR34"},{"issue":"1","key":"6037_CR35","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0108011","volume":"8","author":"JB Rosen","year":"1960","unstructured":"Rosen, J. B. (1960). The gradient projection method for nonlinear programming. Journal of the Society for Industrial and Applied Mathematics, 8(1), 181\u2013217.","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"unstructured":"Scherrer, B. (2014). Approximate policy iteration schemes: A comparison. In International conference on machine learning (ICML).","key":"6037_CR36"},{"unstructured":"Schulman, J., Levine, S., Jordan, M., & Abbeel, P. (2015). Trust region policy optimization. In International conference on machine learning (ICML) (p.\u00a016).","key":"6037_CR37"},{"key":"6037_CR38","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-82118-9","volume-title":"Minimization methods for non-differentiable functions","author":"NZ Shor","year":"1985","unstructured":"Shor, N. Z., Kiwiel, K. C., & Ruszczy\u0144ski, A. (1985). Minimization methods for non-differentiable functions. Berlin: Springer."},{"unstructured":"Xu, Y. (2018). Primal\u2013dual stochastic gradient method for convex programs with many functional constraints. arXiv:1802.02724.","key":"6037_CR39"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06037-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-021-06037-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06037-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:46:58Z","timestamp":1725461218000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-021-06037-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,19]]},"references-count":39,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["6037"],"URL":"https:\/\/doi.org\/10.1007\/s10994-021-06037-z","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"type":"print","value":"0885-6125"},{"type":"electronic","value":"1573-0565"}],"subject":[],"published":{"date-parts":[[2021,7,19]]},"assertion":[{"value":"16 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 May 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 June 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 July 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}