Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phương pháp xấp xỉ ngẫu nhiên bậc không hiệu quả cho các vấn đề đen hộp không bao giờ lồi
Machine Learning - Trang 1-24 - 2023
Tóm tắt
Phương pháp gradient xấp xỉ có vai trò quan trọng trong việc giải quyết các bài toán tối ưu hóa tổng hợp không mượt mà. Tuy nhiên, trong một số vấn đề học máy liên quan đến các mô hình tối ưu hóa đen hộp, phương pháp gradient xấp xỉ không thể được tận dụng do việc tính toán các gradient rõ ràng rất khó khăn hoặc hoàn toàn không khả thi. Gần đây, một số biến thể của phương pháp giảm phương sai ngẫu nhiên bậc không (ZO) như các thuật toán ZO-SVRG và ZO-SPIDER đã được nghiên cứu cho các bài toán tối ưu không lồi. Tuy nhiên, hầu hết các thuật toán loại ZO hiện có đều gặp phải tình trạng chậm lại và tăng độ phức tạp truy vấn hàm lên đến một đa thức bậc thấp của kích thước bài toán. Để lấp đầy khoảng trống này, chúng tôi đề xuất một phân tích mới cho thuật toán gradient ngẫu nhiên nhằm tối ưu hóa các bài toán tổng hợp hữu hạn không lồi và không mượt mà, được gọi là ZO-PSVRG+ và ZO-PSPIDER+. Mục tiêu chính của công trình này là trình bày một phân tích mang lại sự đồng nhất trong việc phân tích hội tụ cho ZO-PSVRG+ và ZO-PSPIDER+, phục hồi một số kết quả hội tụ hiện có cho kích thước minibatch tùy ý trong khi cải thiện độ phức tạp của các cuộc gọi oracle ZO và oracle xấp xỉ của chúng. Chúng tôi chứng minh rằng các thuật toán ZO đã nghiên cứu theo điều kiện Polyak-Łojasiewicz trái ngược với các phương pháp loại ZO hiện tại đạt được sự hội tụ tuyến tính toàn cục cho một loạt kích thước minibatch khi các phần lặp vào một vùng PL cục bộ mà không cần khởi động lại và sửa đổi thuật toán. Phân tích hiện tại trong tài liệu chủ yếu bị giới hạn ở kích thước minibatch lớn, khiến các phương pháp hiện có trở nên không thực tiễn cho các vấn đề thực tế do hạn chế về khả năng tính toán. Trong các thí nghiệm thực nghiệm cho các mô hình đen hộp, chúng tôi cho thấy rằng phân tích mới cung cấp hiệu suất vượt trội và hội tụ nhanh hơn đến một giải pháp của các bài toán không lồi và không mượt mà so với các phương pháp loại ZO hiện có vì chúng gặp khó với các kích thước bước nhỏ. Như một sản phẩm phụ, phân tích được đề xuất là chung và có thể được khai thác cho các biến thể khác của các phương pháp giảm phương sai không gradient nhằm làm cho chúng hiệu quả hơn.
Từ khóa
#Phương pháp gradient xấp xỉ #tối ưu hóa không lồi #phương pháp bậc không #phân tích hội tụ #phương pháp giảm phương saiTài liệu tham khảo
Allen-Zhu, Z., Yuan, Y. (2016). Improved svrg for non-strongly-convex or sum-of-non-convex objectives. In: International conference on machine learning, pp 1080–1089.
Chen, P.Y., Zhang, H., Sharma, Y., et al. (2017). Zoo: Zeroth order optimization based black-box attacks to deep neural networks without training substitute models. In: Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, ACM, pp. 15–26.
Chen, X., Liu, S., Xu, K., et al. (2019). Zo-adamm: Zeroth-order adaptive momentum method for black-box optimization. In: Advances in Neural Information Processing Systems, pp 7202–7213.
Defazio, A., Bach, F., Lacoste-Julien, S. (2014). Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In: Advances in neural information processing systems, pp 1646–1654.
Duchi, J. C., Jordan, M. I., Wainwright, M. J., et al. (2015). Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory, 61(5), 2788–2806.
Fang, C., Li, C.J., Lin, Z., et al. (2018). Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In: Advances in Neural Information Processing Systems, pp 689–699.
Flaxman, A.D., Kalai, A.T., McMahan, H.B. (2005). Online convex optimization in the bandit setting: gradient descent without a gradient. In: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, pp 385–394.
Gao, X., Jiang, B., & Zhang, S. (2018). On the information-adaptive variants of the admm: An iteration complexity perspective. Journal of Scientific Computing, 76(1), 327–363.
Ghadimi, S., & Lan, G. (2013). Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4), 2341–2368.
Ghadimi, S., & Lan, G. (2016). Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1–2), 59–99.
Ghadimi, S., Lan, G., & Zhang, H. (2016). Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1), 267–305.
Gu B, Huo Z, Deng C, et al (2018a) Faster derivative-free stochastic algorithm for shared memory machines. In: International Conference on Machine Learning, pp 1807–1816
Gu, B., Wang, D., Huo, Z., et al. (2018b). Inexact proximal gradient methods for non-convex and non-smooth optimization. In: Thirty-Second AAAI Conference on Artificial Intelligence.
Hajinezhad, D., Hong, M., Garcia, A. (2019). Zone: Zeroth order nonconvex multi-agent optimization over networks. IEEE Transactions on Automatic Control.
Horváth, S., Richtárik, P. (2019). Nonconvex variance reduced optimization with arbitrary sampling. In: International Conference on Machine Learning, PMLR, pp 2781–2789.
Huang, F., Gu, B., Huo, Z., et al (2019). Faster gradient-free proximal stochastic methods for nonconvex nonsmooth optimization. In: AAAI.
Huang, F., Tao, L., Chen, S. (2020). Accelerated stochastic gradient-free and projection-free methods. arXiv preprint arXiv:2007.12625.
Ji, K., Wang, Z., Zhou, Y., et al. (2019). Improved zeroth-order variance reduced algorithms and analysis for nonconvex optimization. In: International Conference on Machine Learning, pp 3100–3109.
Ji, K., Wang, Z., Weng, B., et al. (2020). History-gradient aided batch size adaptation for variance reduced algorithms. In: International Conference on Machine Learning, PMLR, pp 4762–4772.
Johnson, R., Zhang, T. (2013). Accelerating stochastic gradient descent using predictive variance reduction. In: Advances in neural information processing systems, pp 315–323.
Karimi, H., Nutini, J., Schmidt, M. (2016). Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Springer, pp 795–811.
Lei, L., Ju, C., Chen, J., et al. (2017). Non-convex finite-sum optimization via scsg methods. Advances in Neural Information Processing Systems, pp 2348–2358.
Li, Z., Li, J. (2018). A simple proximal stochastic gradient method for nonsmooth nonconvex optimization. Advances in Neural Information Processing Systems, pp 5564–5574.
Lian, X., Zhang, H., Hsieh, C.J., et al. (2016). A comprehensive linear speedup analysis for asynchronous stochastic parallel optimization from zeroth-order to first-order. In: Advances in Neural Information Processing Systems, pp 3054–3062.
Liu, L., Cheng, M., Hsieh, C.J., et al. (2018a). Stochastic zeroth-order optimization via variance reduction method. arXiv preprint arXiv:1805.11811.
Liu, S., Chen, J., Chen, P.Y., et al. (2017) Zeroth-order online alternating direction method of multipliers: Convergence analysis and applications. arXiv preprint arXiv:1710.07804.
Liu, S., Kailkhura, B., Chen, P.Y., et al. (2018b). Zeroth-order stochastic variance reduction for nonconvex optimization. Advances in Neural Information Processing Systems, pp 3727–3737.
Nesterov, Y., & Spokoiny, V. (2011). Random gradient-free minimization of convex functions. Tech. rep.: Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
Nesterov, Y., & Spokoiny, V. (2017). Random gradient-free minimization of convex functions. Foundations of Computational Mathematics, 17(2), 527–566.
Nguyen, L.M., Liu, J., Scheinberg, K., et al. (2017a). Sarah: A novel method for machine learning problems using stochastic recursive gradient. In: International Conference on Machine Learning, PMLR, pp 2613–2621.
Nguyen, L.M., Liu, J., Scheinberg, K., et al. (2017b). Stochastic recursive gradient algorithm for nonconvex optimization. arXiv preprint arXiv:1705.07261.
Nitanda, A. (2016). Accelerated stochastic gradient descent for minimizing finite sums. Artificial Intelligence and Statistics, pp 195–203.
Parikh, N., Boyd, S., et al. (2014). Proximal algorithms. Foundations and Trends ® in Optimization, 1(3), 127–239.
Polyak, B. T. (1963). Gradient methods for minimizing functionals. Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 3(4), 643–653.
Reddi, S.J., Hefny, A., Sra, S., et al. (2016a). Stochastic variance reduction for nonconvex optimization. In: International conference on machine learning, pp 314–323.
Reddi, S.J., Sra, S., Póczos, B., et al. (2016b). Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization. Advances in Neural Information Processing Systems, pp 1145–1153.
Sahu AK, Zaheer M, Kar S (2019) Towards gradient free and projection free stochastic optimization. In: The 22nd International Conference on Artificial Intelligence and Statistics, pp 3468–3477
Shamir, O. (2017). An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. Journal of Machine Learning Research, 18(52), 1–11.
Wang, Z., Ji, K., Zhou, Y., et al. (2019). Spiderboost and momentum: Faster variance reduction algorithms. Advances in Neural Information Processing Systems, pp 2406–2416.
Wibisono, A., Wainwright, M.J., Jordan, M.I., et al (2012). Finite sample convergence rates of zero-order stochastic optimization methods. Advances in Neural Information Processing Systems, pp 1439–1447.
Xiao, L., & Zhang, T. (2014). A proximal stochastic gradient method with progressive variance reduction. SIAM Journal on Optimization, 24(4), 2057–2075.