Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Giải quyết bài toán tối thiểu hóa chuẩn phân rã với thuật toán homotopy gradient gần nhất
Tóm tắt
Chúng tôi nghiên cứu tốc độ hội tụ của thuật toán homotopy gradient gần nhất được áp dụng cho các bài toán bình phương nhỏ nhất tuyến tính được điều chỉnh bởi chuẩn, cho một loại chuẩn tổng quát. Thuật toán homotopy giảm tham số điều chỉnh theo một chuỗi các bước, và sử dụng thuật toán gradient gần nhất để giải quyết bài toán ở mỗi bước. Thuật toán gradient gần nhất có tốc độ hội tụ tuyến tính với điều kiện hàm mục tiêu là lồi mạnh, và đạo hàm của thành phần trơn của hàm mục tiêu là liên tục Lipschitz. Trong nhiều ứng dụng, hàm mục tiêu trong loại bài toán này không phải là lồi mạnh, đặc biệt là khi bài toán có nhiều biến và lựa chọn các quy chuẩn gây ra tính thưa thớt hoặc độ thấp. Chúng tôi chỉ ra rằng nếu ma trận mẫu tuyến tính thỏa mãn một số giả định nhất định và chuẩn điều chỉnh có thể phân rã, thì thuật toán homotopy gradient gần nhất hội tụ với tốc độ tuyến tính mặc dù hàm mục tiêu không phải là lồi mạnh. Kết quả của chúng tôi tổng quát hóa kết quả về tốc độ hội tụ tuyến tính của thuật toán homotopy cho các bài toán bình phương nhỏ nhất được điều chỉnh bởi chuẩn $$\ell _1$$. Các thí nghiệm số cũng được trình bày nhằm hỗ trợ phân tích tốc độ hội tụ lý thuyết.
Từ khóa
#thuật toán homotopy gradient gần nhất #bình phương nhỏ nhất tuyến tính #chuẩn điều chỉnh #tốc độ hội tụ tuyến tính #lồi mạnhTài liệu tham khảo
Agarwal, A., Negahban, S., Wainwright, M.J.: Fast global convergence rates of gradient methods for high-dimensional statistical recovery. In: NIPS, vol. 23, pp. 37–45 (2010)
Bunea, F., Tsybakov, A., Wegkamp, M., et al.: Sparsity oracle inequalities for the lasso. Electron. J. Stat. 1, 169–194 (2007)
Cai, J.F., Candès, E.J., Shen, Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20(4), 1956–1982 (2010)
Candes, E., Plan, Y.: Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements. IEEE Trans. Inf. Theory 57(4), 2342–2359 (2011)
Candès, E., Recht, B.: Simple bounds for recovering low-complexity models. Math. Program. 141(1–2), 577–589 (2013)
Candes, E., Tao, T.: Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE Trans. Inf. Theory 52(12), 5406–5425 (2006)
Candes, E., Tao, T.: he dantzig selector: statistical estimation when \(p\) is much larger than \(n\). Ann. Stat. 35(6), 2313–2351 (2007)
Candes, E.J., Romberg, J.K., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207–1223 (2006)
Chandrasekaran, V., Recht, B., Parrilo, P.A., Willsky, A.S.: The convex geometry of linear inverse problems. Found. Comput. Math. 12(6), 805–849 (2012)
Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52(4), 1289–1306 (2006)
Gordon, Y.: Some inequalities for gaussian processes and applications. Israel J. Math. 50(4), 265–289 (1985)
Gross, D.: Recovering low-rank matrices from few coefficients in any basis. IEEE Trans. Inf. Theory 57(3), 1548–1566 (2011)
Hale, E.T., Yin, W., Zhang, Y.: Fixed-point continuation for \(\ell _1\)-minimization: methodology and convergence. SIAM J. Optim. 19(3), 1107–1130 (2008)
Hou, K., Zhou, Z., So, A.M., Luo, Z.q.: On the linear convergence of the proximal gradient method for trace norm regularization. In: Advances in Neural Information Processing Systems, pp. 710–718 (2013)
Jain, P., Meka, R., Dhillon, I.S.: Guaranteed rank minimization via singular value projection. NIPS 23, 937–945 (2010)
Jin, R., Yang, T., Zhu, S.: A new analysis of compressive sensing by stochastic proximal gradient descent. CoRR abs/1304.4680 (2013)
Ledoux, M., Talagrand, M.: Probability in Banach Spaces: Isoperimetry and Processes, vol. 23. Springer, New York (2013)
Liu, Z., Vandenberghe, L.: Interior-point method for nuclear norm approximation with application to system identification. SIAM J. Matrix Anal. Appl. 31(3), 1235–1256 (2009)
Lounici, K., Pontil, M., Van De Geer, S., Tsybakov, A.B., et al.: Oracle inequalities and optimal inference under group sparsity. Ann. Stat. 39(4), 2164–2204 (2011)
Lu, Z., Xiao, L.: On the complexity analysis of randomized block-coordinate descent methods. Math. Program. 152(1–2), 615–642 (2015)
Luo, Z.Q., Tseng, P.: On the linear convergence of descent methods for convex essentially smooth minimization. SIAM J. Control Optim. 30(2), 408–425 (1992)
Ma, S., Goldfarb, D., Chen, L.: Fixed point and bregman iterative methods for matrix rank minimization. Math. Program. 128(1), 321–353 (2011)
Mazumder, R., Hastie, T., Tibshirani, R.: Spectral regularization algorithms for learning large incomplete matrices. J. Mach. Learn. Res. 11, 2287–2322 (2010)
Mendelson, S., Pajor, A., Tomczak-Jaegermann, N.: Reconstruction and subgaussian operators in asymptotic geometric analysis. Geom. Funct. Anal. 17(4), 1248–1282 (2007)
Moreau, J.J.: Fonctions convexes duales et points proximaux dans un espace hilbertien (french). CR Acad. Sci. Paris 255, 2897–2899 (1962)
Needell, D., Tropp, J.A.: Cosamp: Iterative signal recovery from incomplete and inaccurate samples. Appl. Comput. Harm. Anal. 26(3), 301–321 (2009)
Negahban, S.N., Ravikumar, P., Wainwright, M.J., Yu, B.: A unified framework for high-dimensional analysis of \(m\)-estimators with decomposable regularizers. Stat. Sci. 27(4), 538–557 (2012)
Nesterov, Y.: Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22(2), 341–362 (2012)
Nesterov, Y.: Gradient methods for minimizing composite functions. Math. Program. 140(1), 125–161 (2013)
Nesterov, Y., Nemirovski, A.: On first-order algorithms for \(\ell _1\)/nuclear norm minimization. Acta Numer. 22, 509–575 (2013)
Nesterov, Y., Nesterov, I.E.: Introductory Lectures on Convex Optimization: A Basic Course, vol. 87. Springer, Amsterdam (2004)
Nguyen, N., Needell, D., Woolf, T.: Linear convergence of stochastic iterative greedy algorithms with sparse constraints. arXiv preprint arXiv:1407.0088 (2014)
Raskutti, G., Wainwright, M.J., Yu, B.: Minimax rates of estimation for high-dimensional linear regression over-balls. IEEE Trans. Inf. Theory 57(10), 6976–6994 (2011)
Recht, B., Fazel, M., Parrilo, P.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3), 471–501 (2010)
Richtárik, P., Takáč, M.: Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function. Math. Program. 144(1–2), 1–38 (2014)
Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5), 877–898 (1976)
Rohde, A., Tsybakov, A.B., et al.: Estimation of high-dimensional low-rank matrices. Ann. Stat. 39(2), 887–930 (2011)
Shalev-Shwartz, S., Gonen, A., Shamir, O.: Large-scale convex minimization with a low-rank constraint. arXiv preprint arXiv:1106.1622 (2011)
Shalev-Shwartz, S., Srebro, N., Zhang, T.: Trading accuracy for sparsity in optimization problems with sparsity constraints. SIAM J. Optim. 20(6), 2807–2832 (2010)
Talagrand, M.: The Generic Chaining, vol. 154. Springer, Berlin (2005)
Toh, K.C., Yun, S.: An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems. Pac. J. Optim. 6(615–640), 15 (2010)
Van De Geer, S.A., Bühlmann, P., et al.: On the conditions used to prove oracle results for the lasso. Electron. J. Stat. 3, 1360–1392 (2009)
Wen, Z., Yin, W., Goldfarb, D., Zhang, Y.: A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization, and continuation. SIAM J. Sci. Comput. 32(4), 1832–1857 (2010)
Wright, S.J., Nowak, R.D., Figueiredo, M.A.: Sparse reconstruction by separable approximation. IEEE Trans. Signal Process. 57(7), 2479–2493 (2009)
Xiao, L., Zhang, T.: A proximal-gradient homotopy method for the sparse least-squares problem. SIAM J. Optim. 23(2), 1062–1091 (2013)
Zhang, H., Jiang, J., Luo, Z.Q.: On the linear convergence of a proximal gradient method for a class of nonsmooth convex minimization problems. Journal of the Operations Research Society of China 1(2), 163–186 (2013)