July 15th (Monday), 14:00-17:30 (full schedule at L4DC)
This tutorial is geared towards researchers and practitioners interested in imposing requirements to ML systems, such as fairness, robustness, and safety. Typically, these statistical, data-driven constraints are induced by combining the learning objective and requirement violation metrics into a single training loss. To guarantee that the solution satisfies the requirements, however, this approach requires careful tuning of hyperparameters (penalty coefficients) using cross-validation, which can be computationally intensive and time consuming. Constrained learning incorporates requirements as statistical constraints rather than by modifying the training objective.
In this tutorial, we provide an overview of theoretical and algorithmic advances from the past 5 years that show when and how it is possible to learn under constraints and effectively impose constraints on ML systems, both during training and at test time. Specifically, we explore the role and impact of different types of requirements in supervised learning, robust learning, and RL:
Throughout the tutorial, we illustrate the effectiveness and flexibility of constrained learning in a diverse set of applications, such as fairness, federated learning, robust image classification, imitation learning, safe RL, and wireless communications. Ultimately, this tutorial provides a general tool that can be used to tackle a variety of problems in ML and sequential decision-making.
Prerequisite knowledge: only basic understanding of optimization, ML, and RL are expected. Specifically, familiarity with the basics of convex optimization and its algorithms (i.e., what are convex functions, mathematics of gradients, and gradient descent); fundamentals of empirical risk minimization (ERM) and the associated learning theory (i.e., basic notions of generalization and sample complexity); and familiarity with Markov decision processes (MDPs) and basic RL algorithms (policy gradient, e.g., REINFORCE).
Time | Topic |
---|---|
14:00 - 14:15 | Introduction (slides) |
14:15 - 15:00 | Constrained supervised learning |
(un)constrained learning and ERM | |
non-convex duality and constrained learning theory | |
constrained learning algorithms | |
resilient learning | |
15:00 - 15:30 | Robust learning |
robustness-constrained learning and semi-infinite optimization | |
sampling algorithms and MCMC | |
probabilistic robustness | |
15:30 - 16:00 | Break |
16:00 - 17:30 | Constrained reinforcement learning (slides) |
(C)MDPs and (C)RL | |
CRL duality | |
CRL algorithms |
We have provided a selected bibliography for the tutorial here.
In this module, we formalize statistical learning and empirical risk minimization (ERM), discuss different types of requirements that arise in ML, and show how these requirements are imposed using constrained optimization. We then introduce constrained learning theory and proceed to show a family of generalization bounds for constrained learning using not constrained ERM, but non-convex duality. Based on these results, we develop primal-dual training algorithms, discuss practical aspects of their implementation (step sizes, stopping criteria), and elucidate their convergence properties. We explore how these duality results can be used to adapt the trade-off between objective and requirements and balance the marginal costs and benefits of relaxing constraints. We dub these techniques "resilient learning," from the ecological concept that describes the ability of a system to adapt to changes in their environment.
Applications: We use fairness as an example of rate requirement (e.g., equality of odds, churn) and federated learning to illustrate how to tackle ML problems with simultaneous goals (e.g., heterogeneous data or heterogeneous performance targets). We then revisit this heterogeneous federated learning application to illustrate the use of resilient learning.
This is in contrast to robustness, which seeks to resist rather than adapt to disturbances. To tackle this problem, we introduce epigraph formulations of robustness that feature one constraint per sample and disturbance and extend previous duality results to this semi-infinite constrained learning problem. We then derive a practical algorithm for tackling robustness-constrained learning based on Markov Chain Monte Carlo (MCMC) and stochastic optimization, showing how it generalizes previous solutions based on adversarial training (e.g., "PGD") and penalty methods (e.g., TRADES). Additionally, we showcase how it achieves stronger guarantees, better compromises, and mitigate the challenges involved in computing worst-case perturbations during training.
Applications: We consider the issue of adversarial examples in image classification. We also explore how semi-infinite constrained learning can be use to tackle "non-robustness" applications, namely learning in the presence of invariances, where we show a mathematical equivalence between robustness and data augmentation, and semi-supervised learning, where we derive connections between robustness, Lipschitz regularization of neural networks, and manifold Laplacian regularization. We illustrate the latter in a navigation example.
The final module develops a parallel constrained learning theory in the dynamic setting of sequential decision-making problems. We start by introducing the MDP formalism and RL algorithms commonly used to tackle this setting. Using a different technique, we then derive non-convex duality results similar to the supervised case and use them to put forward a primal-dual algorithm for constrained RL. We then show how this algorithm can fail even on simple tasks and describe a systematic state augmentation procedure able to provably overcome this issue.
Applications: We consider the task of learning safe policies and wireless resource allocation to motivate and illustrate the results of this module. We then turn to a continuous monitoring problem to illustrate the limitations of unconstrained RL and show the need for state augmentation.
Miguel Calvo-Fullana received the B.Sc. degree in electrical engineering from the Universitat de les Illes Balears (UIB) in 2010 and the M.Sc. and Ph.D. degrees in electrical engineering from the Universitat Politècnica de Catalunya (UPC) in 2013 and 2017, respectively. He joined Universitat Pompeu Fabra (UPF) in 2023, where he is a Ramón y Cajal fellow. Prior to joining UPF, he held postdoctoral appointments at the University of Pennsylvania and the Massachusetts Institute of Technology and was a research assistant at the Centre Tecnològic de Telecomunicacions de Catalunya (CTTC). His research interests include learning, optimization, multi-agent systems, and wireless communication. He is the recipient of best paper awards at ICC 2015, IEEE GlobalSIP 2015, and IEEE ICASSP 2020.
Luiz F. O. Chamon received the B.Sc. and M.Sc. degrees in electrical engineering from the University of São Paulo, Brazil, in 2011 and 2015 and the Ph.D. degree in electrical and systems engineering from the University of Pennsylvania (Penn), USA, in 2020. Until 2022, he was a postdoctoral fellow at the Simons Institute of the University of California, Berkeley, USA. He is currently an independent research group leader at the University of Stuttgart, Germany. In 2009, he was an undergraduate exchange student of the Masters in Acoustics of the École Centrale de Lyon, France. He received both the best student paper and the best paper awards at IEEE ICASSP 2020 and was recognized by the IEEE Signal Processing Society for his distinguished work for the editorial board of the IEEE Transactions on Signal Processing in 2018. His research interests include optimization, signal processing, machine learning, statistics, and control.
Santiago Paternain received the B.Sc. degree in electrical engineering from Universidad de la República Oriental del Uruguay, Montevideo, Uruguay in 2012, the M.Sc. in Statistics from the Wharton School in 2018, and the Ph.D. in Electrical and Systems Engineering from the University of Pennsylvania in 2018. He is currently an Assistant Professor at the Rensselaer Polytechnic Institute (RPI). Prior to joining RPI, Dr. Paternain was a postdoctoral researcher at the University of Pennsylvania. His research interests lie at the intersection of machine learning and control of dynamical systems. Dr. Paternain was the recipient of the 2017 CDC Best Student Paper Award and the 2019 Joseph and Rosaline Wolfe Best Doctoral Dissertation Award from the Electrical and Systems Engineering Department at the University of Pennsylvania.
Alejandro Ribeiro received the B.Sc. degree in electrical engineering from the Universidad de la República Oriental del Uruguay in 1998 and the M.Sc. and Ph.D. degrees in electrical engineering from the University of Minnesota in 2005 and 2007. He joined the University of Pennsylvania (Penn) in 2008 where he is currently Professor of Electrical and Systems Engineering. His research is in wireless autonomous networks, machine learning on network data and distributed collaborative learning. Papers coauthored by Dr. Ribeiro received the 2022 IEEE Signal Processing Society Best Paper Award, the 2022 IEEE Brain Initiative Student Paper Award, the 2021 Cambridge Ring Publication of the Year Award, the 2020 IEEE Signal Processing Society Young Author Best Paper Award, the 2014 O. Hugo Schuck best paper award, and paper awards at EUSIPCO, IEEE ICASSP, IEEE CDC, IEEE SSP, IEEE SAM, Asilomar SSC Conference, and ACC. His teaching has been recognized with the 2017 Lindback award for distinguished teaching and the 2012 S. Reid Warren, Jr. Award presented by Penn’s undergraduate student body for outstanding teaching. Dr. Ribeiro received an Outstanding Researcher Award from Intel University Research Programs in 2019. He is a Penn Fellow class of 2015 and a Fulbright scholar class of 2003.
@Article{keywords, author = "{Calvo-Fullana}, M. and Paternain, S. and Chamon, L. F. O. and Ribeiro, A.", title = "State augmented constrained reinforcement learning: {O}vercoming the limitations of learning with rewards", journal = "IEEE Trans. on Autom. Control.", year = "2024", volume = "69[7]", pages = "4275--4290", arxiv = "\url{https://arxiv.org/abs/2102.11941}", keywords = "main" }
@Article{keywords, author = "Chamon, L. F. O. and Paternain, S. and {Calvo-Fullana}, M. and Ribeiro, A.", title = "Constrained Learning with Non-Convex Losses", journal = "IEEE Trans. on Inf. Theory", volume = "69[3]", pages = "1739--1760", year = "2023", arxiv = "\url{https://arxiv.org/abs/2103.05134}", keywords = "main" }
@InProceedings{keywords, author = "Robey*, A. and Chamon*, L. F. O. and Pappas, G. J. and Hassani, H. and Ribeiro, A.", title = "Adversarial Robustness with Semi-Infinite Constrained Learning", booktitle = "Conference on Neural Information Processing Systems\textasciitilde (NeurIPS)", year = "2021", pages = "", note = "{(* equal contribution)}", arxiv = "\url{https://arxiv.org/abs/2110.15767}", keywords = "main" }
@InProceedings{keywords, author = "Paternain, S. and Chamon, L. F. O. and {Calvo-Fullana}, M. and Ribeiro, A.", title = "Constrained reinforcement learning has zero duality gap", booktitle = "Conference on Neural Information Processing Systems\textasciitilde (NeurIPS)", year = "2019", pages = "7555--7565", arxiv = "\url{https://arxiv.org/abs/1910.13393}", keywords = "main" }
@InProceedings{keywords, author = "Elenter, J. and Chamon, L. F. O. and Ribeiro, A.", title = "Near-optimal solutions of constrained learning problems", booktitle = "International Conference on Learning Representations\textasciitilde (ICLR)", year = "2024", arxiv = "\url{https://arxiv.org/abs/2403.11844}", keywords = "csl" }
@InProceedings{keywords, author = "Hounie, I. and Ribeiro, A. and Chamon, L. F. O.", title = "Resilient Constrained Learning", booktitle = "Conference on Neural Information Processing Systems\textasciitilde (NeurIPS)", year = "2023", arxiv = "\url{https://arxiv.org/abs/2306.02426}", keywords = "csl" }
@InProceedings{keywords, author = "Cervino, J. and Chamon, L. F. O. and Haeffele, B. D. and Vidal, R. and Ribeiro, A.", title = "Learning Globally Smooth Functions on Manifolds", booktitle = "International Conference on Machine Learning\textasciitilde (ICML)", year = "2023", arxiv = "\url{https://arxiv.org/abs/2210.00301}", keywords = "csl" }
@InProceedings{keywords, author = "Hounie, I. and Chamon, L. F. O. and Ribeiro, A.", title = "Automatic Data Augmentation via Invariance-Constrained Learning", booktitle = "International Conference on Machine Learning\textasciitilde (ICML)", year = "2023", arxiv = "\url{https://arxiv.org/abs/2209.15031}", keywords = "csl" }
@InProceedings{keywords, author = "Shen, Zebang and Cervino, Juan and Hassani, Hamed and Ribeiro, Alejandro", title = "An Agnostic Approach to Federated Learning with Class Imbalance", booktitle = "International Conference on Learning Representations\textasciitilde (ICLR)", year = "2022", url = "\url{https://openreview.net/forum?id=Xo0lbDt975}", keywords = "csl" }
@InProceedings{keywords, author = "Robey, A. and Chamon, L. F. O. and Pappas, G. J. and Hassani, H.", title = "Probabilistically Robust Learning: {B}alancing Average- and Worst-case Performance", booktitle = "International Conference on Machine Learning\textasciitilde (ICML)", year = "2022", pages = "", award = "spotlight", arxiv = "\url{https://arxiv.org/abs/2202.01136}", keywords = "csl" }
@InProceedings{keywords, author = "Chamon, L. F. O. and Ribeiro, A.", title = "Probably approximately correct constrained learning", booktitle = "Conference on Neural Information Processing Systems\textasciitilde (NeurIPS)", year = "2020", pages = "", arxiv = "\url{https://arxiv.org/abs/2006.05487}", keywords = "csl" }
@InProceedings{keywords, author = "Chamon, L. F. O. and Paternain, S. and {Calvo-Fullana}, M. and Ribeiro, A.", title = "The empirical duality gap of constrained statistical learning", booktitle = "IEEE International Conference in Acoustic, Speech, and Signal Processing (ICASSP)", year = "2020", pages = "", award = "Best student paper award", arxiv = "\url{https://arxiv.org/abs/2002.05183}", keywords = "csl" }
@InProceedings{keywords, author = "Zhang, Hongyang and Yu, Yaodong and Jiao, Jiantao and Xing, Eric and Ghaoui, Laurent El and Jordan, Michael", title = "Theoretically Principled Trade-off between Robustness and Accuracy", booktitle = "International Conference on Machine Learning\textasciitilde (ICML)", year = "2019", url = "\url{http://proceedings.mlr.press/v97/zhang19p.html}", keywords = "csl" }
@Article{keywords, author = "Cotter, Andrew and Jiang, Heinrich and Gupta, Maya and Wang, Serena and Narayan, Taman and You, Seungil and Sridharan, Karthik", title = "Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals", journal = "Journal of Machine Learning Research", year = "2019", volume = "20", number = "172", pages = "1--59", keywords = "csl" }
@Article{keywords, author = "Eisen, M. and Zhang, C. and Chamon, L. F. O. and Lee, D. D. and Ribeiro, A.", title = "Learning optimal resource allocations in wireless systems", volume = "67[10]", journal = "IEEE Trans. on Signal Process.", year = "2019", pages = "2775--2790", award = "Top 50 most accessed articles in IEEE TSP: May, July, Sept, Oct 2019", arxiv = "\url{https://arxiv.org/abs/1807.08088}", keywords = "csl" }
@InProceedings{keywords, author = "Chen, Weiqin and Paternain, Santiago", title = "Generalized constraint for probabilistic safe reinforcement learning", booktitle = "Learning for Dynamics \\& Control Conference", pages = "1606--1618", year = "2024", keywords = "crl" }
@Article{keywords, author = "Chen, Weiqin and Subramanian, Dharmashankar and Paternain, Santiago", title = "Probabilistic constraint for safety-critical reinforcement learning", journal = "IEEE Trans. on Autom. Control.", year = "2024", keywords = "crl" }
@InProceedings{keywords, author = "Chen, Weiqin and Onyejizu, James and Vu, Long and Hoang, Lan and Subramanian, Dharmashankar and Kar, Koushik and Mishra, Sandipan and Paternain, Santiago", title = "Adaptive Primal-Dual Method for Safe Reinforcement Learning", booktitle = "International Conference on Autonomous Agents and Multiagent Systems", pages = "326--334", year = "2024", keywords = "crl" }
@InProceedings{keywords, author = "Jayarathne, Damsara and Paternain, Santiago and Mishra, Sandipan", title = "Safe residual reinforcement learning for helicopter aerial refueling", booktitle = "IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM)", pages = "263--269", year = "2023", keywords = "crl" }
@InProceedings{keywords, author = "Chowdhury, Arindam and Paternain, Santiago and Verma, Gunjan and Swami, Ananthram and Segarra, Santiago", title = "Learning Non-myopic Power Allocation in Constrained Scenarios", booktitle = "IEEE Asilomar Conference on Signals, Systems and Computers", year = "2023", pages = "804--808", arxiv = "\url{https://arxiv.org/abs/2401.10297}", keywords = "crl" }
@Article{keywords, author = "Paternain, S. and {Calvo-Fullana}, M. and Chamon, L. F. O. and Ribeiro, A.", title = "Safe policies for reinforcement learning via primal-dual methods", journal = "IEEE Trans. on Autom. Control.", year = "2023", volume = "68[3]", pages = "1321--1336", arxiv = "\url{https://arxiv.org/abs/1911.09101}", keywords = "crl" }
@Article{keywords, author = "NaderiAlizadeh, Navid and Eisen, Mark and Ribeiro, Alejandro", journal = "IEEE Trans. on Signal Process.", title = "State-Augmented Learnable Algorithms for Resource Management in Wireless Networks", year = "2022", volume = "70", pages = "5898--5912", arxiv = "\url{https://arxiv.org/abs/2207.02242}", keywords = "crl" }
@InProceedings{keywords, author = "Achiam, Joshua and Held, David and Tamar, Aviv and Abbeel, Pieter", title = "Constrained Policy Optimization", booktitle = "International Conference on Machine Learning\textasciitilde (ICML)", year = "2017", url = "\url{https://proceedings.mlr.press/v70/achiam17a.html}", keywords = "crl" }
@Book{keywords, author = "Altman, E.", publisher = "Chapman and Hall", title = "Constrained Markov Decision Processes", year = "1999", url = "\url{https://www-sop.inria.fr/members/Eitan.Altman/TEMP/h.pdf}", keywords = "crl" }
@Misc{keywords, author = "Chamon, L. F. O.", title = "csl: {L}earning under requirements with {PyTorch}", version = "1.0", year = "2021", url = "\url{https://github.com/lfochamon/csl}", keywords = "other" }
@Article{keywords, author = "Chamon, L. F. O. and Eldar, Y. C. and Ribeiro, A.", title = "Functional nonlinear sparse models", volume = "68[1]", journal = "IEEE Trans. on Signal Process.", year = "2020", pages = "2449--2463", arxiv = "\url{https://arxiv.org/abs/1811.00577}", keywords = "other" }