Phương pháp thích nghi không dùng phép chiếu cho bài toán bất đẳng thức biến phân có ràng buộc trong học máy
Nội dung chính của bài viết
Tóm tắt
Chúng tôi đề xuất Phương pháp Gradient Ràng buộc Thích nghi với Điều chuẩn Phạt (PR-A-CGM), một thuật toán không chiếu cho việc giải các bài toán bất đẳng thức biến phân với toán tử giả đơn điệu và các ràng buộc hàm lồi. Khác với các phương pháp dựa trên phép chiếu, PR-A-CGM đảm bảo tính khả thi bằng cách đưa thêm một hạng phạt trơn vào hướng cập nhật, qua đó tránh được các phép chiếu tốn kém hoặc bất khả thi, đồng thời vẫn giữ được bảo đảm hội tụ dưới điều kiện giả đơn điệu và trong điều kiện có nhiễu từ oracle. Chúng tôi chứng minh hội tụ yếu dưới các giả thiết tiêu chuẩn, thiết lập và chứng minh sự hội tụ mạnh và tốc độ hội tụ trong những điều kiện chặt chẽ hơn, và kiểm chứng phương pháp trên các ứng dụng học máy như phân loại với ràng buộc công bằng. Thực nghiệm cho thấy PR-A-CGM cải thiện khả năng thỏa mãn ràng buộc và tính ổn định so với các phương pháp không chiếu cơ sở, đồng thời thu hẹp khoảng cách với các phương pháp dựa trên phép chiếu. Các kết quả này nhấn mạnh vai trò của những phương pháp nguyên thủy với điều chuẩn phạt như những công cụ thực tiễn cho tối ưu hóa có ràng buộc trong bối cảnh học máy quy mô lớn hiện đại.
Chi tiết bài viết
Tài liệu tham khảo
[2] L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223–311, 2018.
[3] A. Chambolle and T. Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of Mathematical Imaging and Vision, 40(1):120–145, 2011.
[4] L. Cui, X. Chen, and J. Zhang. Projection-free stochastic optimization with complex constraints. NeurIPS, 2022.
[5] J. Diakonikolas, C. Daskalakis, and M. Jordan. Efficient methods for structured nonconvex-nonconcave min-max optimization. AISTATS, 2020.
[6] M. Donini, L. Oneto, S. Ben-David, J. Shawe-Taylor, and M. Pontil. Empirical risk minimization under fairness constraints. Advances in Neural Information Processing Systems (NeurIPS), 2018.
[7] E. Esser, X. Zhang, and T. F. Chan. A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM Journal on Imaging Sciences, 3(4):1015–1046, 2010.
[8] F. Facchinei and J.-S. Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, 2003.
[9] G. Gidel, H. Daneshmand, A. Liautard, and S. Lacoste-Julien. A variational inequality perspective on generative adversarial networks. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
[10] E. Gorbunov, M. Danilova, and D. Dobre. Near-optimal methods for stochastic variational inequalities. Advances in Neural Information Processing Systems (NeurIPS), 2022.
[11] A. Juditsky, A. Nemirovski, and C. Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17–58, 2011. DOI: 10.1214/10-SSY011.
[12] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Ekonomika i Matematicheskie Metody, 1976.
[13] G. Lan and R. D. C. Monteiro. Iteration-complexity of first-order penalty methods for convex programming. Mathematical Programming, 155(1):511–547, 2016. DOI: 10.1007/s10107-015-0896-1.
[14] T. Lin, C. Jin, and M. Jordan. On gradient descent ascent for nonconvex-concave minimax problems. ICML, 2020.
[15] T. Lin, C. Jin, and M. Jordan. Near-optimal algorithms for minimax optimization. Conference on Learning Theory (COLT), 2020.
[16] A. Mill´an, R. Iutzeler, and J. Malick. On pseudo-monotone variational inequalities and inexact projections. Mathematical Programming, 2024.
[17] M. Muehlebach and M. I. Jordan. On constraints in first-order optimization: a view from non-smooth dynamical systems. Journal of Machine Learning Research, 23(1):1–47, 2022.
[18] A. Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators. SIAM Journal on Optimization, 2004.
[19] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust
stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574–1609, 2009. DOI: 10.1137/070704277.
[20] S. Paternain, L. Chamon, M. Calvo-Fullana, and A. Ribeiro. Constrained reinforcement learning has zero duality gap. International Conference on Learning Representations (ICLR), 2022.
[21] R. T. Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 1976.