A duality approach to regularized learning problems in Banach spaces. (English) Zbl 07805473
Summary: Regularized learning problems in Banach spaces, which often minimize the sum of a data fidelity term in one Banach norm and a regularization term in another Banach norm, is challenging to solve. We construct a direct sum space based on the Banach spaces for the fidelity term and the regularization term, and recast the objective function as the norm of a quotient space of the direct sum space. We then express the original regularized problem as an optimization problem in the dual space of the direct sum space. It is to find the maximum of a linear function on a convex polytope, which may be solved by linear programming. A solution of the original problem is then obtained by using related extremal properties of norming functionals from a solution of the dual problem. Numerical experiments demonstrate that the proposed duality approach is effective for solving the regularization learning problems.
MSC:
| 68Q32 | Computational learning theory |
| 41A05 | Interpolation in approximation theory |
| 46B45 | Banach sequence spaces |
Software:
PDCOReferences:
| [1] | Argyriou, A.; Micchelli, C. A.; Pontil, M., When is there a representer theorem? Vector versus matrix regularizers. J. Mach. Learn. Res., 2507-2529 (2009) · Zbl 1235.68128 |
| [2] | Aziznejad, S.; Unser, M., Multikernel regression with sparsity constraint. SIAM J. Math. Data Sci., 201-224 (2021) · Zbl 1479.46026 |
| [3] | Barbu, V.; Precupanu, T., Convexity and Optimization in Banach Spaces (2012), Springer: Springer Dordrecht · Zbl 1244.49001 |
| [4] | Bi, J.; Bennett, K. P.; Embrechts, M.; Breneman, C. M.; Song, M., Dimensionality reduction via sparse support vector machines. J. Mach. Learn. Res., 1229-1243 (2003) · Zbl 1102.68531 |
| [5] | Boche, H.; Pohl, V., The stability and continuity behavior of the spectral factorization in the Wiener algebra with applications in Wiener filtering. IEEE Trans. Circuits Syst. I, Regul. Pap., 3063-3076 (2008) |
| [6] | Candés, E. J.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory, 489-509 (2006) · Zbl 1231.94017 |
| [7] | Chen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decomposition by basis pursuit. SIAM Rev., 129-159 (2001) · Zbl 0979.94010 |
| [8] | Cheng, R., On the prediction of \(p\)-stationary processes. Period. Math. Hung., 481-505 (2022) · Zbl 1524.60079 |
| [9] | Cheng, R.; Ross, W. T., Weak parallelogram laws on Banach spaces and applications to prediction. Period. Math. Hung., 45-58 (2015) · Zbl 1363.46013 |
| [10] | Cheng, R.; Ross, W. T., An inner-outer factorization in \(\ell^p\) with applications to ARMA processes. J. Math. Anal. Appl., 396-418 (2016) · Zbl 1336.47072 |
| [11] | Cheng, R.; Xu, Y., Minimum norm interpolation in the \(\ell_1(\mathbb{N})\) space. Anal. Appl., 21-42 (2021) · Zbl 1462.41001 |
| [12] | Conway, J., A Course in Functional Analysis (1985), Springer-Verlag: Springer-Verlag New York · Zbl 0558.46001 |
| [13] | Cucker, F.; Smale, S., On the mathematical foundations of learning. Bull. Am. Math. Soc., 1-49 (2002) · Zbl 0983.68162 |
| [14] | Donoho, D. L., Compressed sensing. IEEE Trans. Inf. Theory, 1289-1306 (2006) · Zbl 1288.94016 |
| [15] | Evgeniou, T.; Pontil, M.; Poggio, T., Regularization networks and support vector machines. Adv. Comput. Math., 1-50 (2000) · Zbl 0939.68098 |
| [16] | Huang, L.; Liu, C.; Tan, L.; Ye, Q., Generalized representer theorems in Banach spaces. Anal. Appl., 1, 125-146 (2021) · Zbl 1462.68156 |
| [17] | Kuruog̋lu, E. E., Nonlinear least \(\ell^p\) norm filters for nonlinear autoregressive \(α\)-stable processes. Digit. Signal Process., 119-142 (2002) |
| [18] | Li, Q.; Shen, L.; Xu, Y.; Zhang, N., Multi-step fixed-point proximity algorithms for solving a class of optimization problems arising from image processing. Adv. Comput. Math., 387-422 (2015) · Zbl 1326.65069 |
| [19] | Li, Z.; Song, G.; Xu, Y., A two-step fixed-point proximity algorithm for a class of non-differentiable optimization models in machine learning. J. Sci. Comput., 923-940 (2019) · Zbl 1423.68382 |
| [20] | Lin, R.; Song, G.; Zhang, H., Multi-task learning in vector-valued reproducing kernel Banach spaces with the \(\ell_1\) norm. J. Complex. (2021) · Zbl 1471.68221 |
| [21] | Liu, Q.; Wang, R.; Xu, Y.; Yan, M., Parameter choices for sparse regularization with the \(\ell_1\) norm. Inverse Probl. (2023) |
| [22] | Lu, S.; Pereverzev, S. V., Regularization Theory for Ill-Posed Problems. Selected Topics (2013), De Gruyter: De Gruyter Berlin, Boston · Zbl 1282.47001 |
| [23] | Megginson, R. E., An Introduction to Banach Space Theory. Graduate Texts in Mathematics (1998), Springer-Verlag: Springer-Verlag New York · Zbl 0910.46008 |
| [24] | Micchelli, C. A.; Shen, L.; Xu, Y., Proximity algorithms for image models: denoising. Inverse Probl. (2011) |
| [25] | Micchelli, C. A.; Xu, Y.; Ye, P., Cucker Smale learning theory in Besov spaces, 47-68 |
| [26] | Parhi, R.; Nowak, R. D., Banach space representer theorems for neural networks and ridge splines. J. Mach. Learn. Res., 43 (2021) · Zbl 1507.68250 |
| [27] | Rudin, L. I.; Osher, S.; Fatemi, E., Nonlinear total variation based noise removal algorithms. Phys. D, Nonlinear Phenom., 259-268 (1992) · Zbl 0780.49028 |
| [28] | Schölkopf, B.; Smola, A. J., Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond (2002), MIT Press: MIT Press Cambridge |
| [29] | Schölkopf, B.; Herbrich, R.; Smola, A. J., A generalized representer theorem, 416-426 · Zbl 0992.68088 |
| [30] | Schuster, T.; Kaltenbacher, B.; Hofmann, B.; Kazimierski, K. S., Regularization Methods in Banach Spaces (2012), Springer: Springer Berlin · Zbl 1259.65087 |
| [31] | Song, G.; Zhang, H., Reproducing kernel Banach spaces with the \(\ell^1\) norm II: error analysis for regularized least square regression. Neural Comput., 2713-2729 (2011) · Zbl 1231.68219 |
| [32] | Song, G.; Zhang, H.; Hickernell, F. J., Reproducing kernel Banach spaces with the \(\ell^1\) norm. Appl. Comput. Harmon. Anal., 96-116 (2013) · Zbl 1269.46020 |
| [33] | Sriperumbudur, B. K.; Fukumizu, K.; Lanckriet, G. R.G., Learning in Hilbert vs. Banach spaces: a measure embedding viewpoint · Zbl 1280.68198 |
| [34] | Tibshirani, R., Regression shrinkage and selection via the lasso. J. R. Stat. Soc., Ser. B, Methodol., 267-288 (1996) · Zbl 0850.62538 |
| [35] | Tibshirani, R. J.; Taylor, J., The solution path of the generalized lasso. Ann. Stat., 1335-1371 (2011) · Zbl 1234.62107 |
| [36] | Unser, M., A unifying representer theorem for inverse problems and machine learning. Found. Comput. Math., 941-960 (2021) · Zbl 1479.46088 |
| [37] | Unser, M.; Fageot, J.; Gupta, H., Representer theorems for sparsity-promoting \(\ell_1\) regularization. IEEE Trans. Inf. Theory, 5167-5180 (2016) · Zbl 1359.94185 |
| [38] | Ubhaya, V. A.; Weinstein, S. E.; Xu, Y., Best piecewise monotone uniform approximation. J. Approx. Theory, 375-383 (1990) · Zbl 0732.41028 |
| [39] | Viola, C.; Z̆ivný, S., The combined basic \(L^p\) and affine \(\ell^p\) relaxation for promise VCSPs on infinite domains. ACM Trans. Algorithms (2021), 23 pp. · Zbl 07475101 |
| [40] | Wang, R.; Xu, Y., Functional reproducing kernel Hilbert spaces for non-point-evaluation functional data. Appl. Comput. Harmon. Anal., 569-623 (2019) · Zbl 1423.46046 |
| [41] | Wang, R.; Xu, Y., Representer theorems in Banach spaces: minimum norm interpolation, regularized learning and semi-discrete inverse problems. J. Mach. Learn. Res., 225 (2021) · Zbl 1507.68261 |
| [42] | Wang, R.; Xu, Y., Regularization in a functional reproducing kernel Hilbert space. J. Complex. (2021) · Zbl 07390177 |
| [43] | Weinstein, S. E.; Xu, Y., Best quasi-convex uniform approximation. J. Math. Anal. Appl., 240-251 (1990) · Zbl 0729.41026 |
| [44] | Weinstein, S. E.; Xu, Y., A duality approach to best uniform convex approximation. J. Math. Anal. Appl., 314-322 (1991) · Zbl 0764.41035 |
| [45] | Xu, Y., Sparse machine learning in Banach spaces. Appl. Numer. Math., 138-157 (2023) · Zbl 07705768 |
| [46] | Xu, Y.; Ye, Q., Generalized Mercer kernels and reproducing kernel Banach spaces. Mem. Am. Math. Soc., 1243 (2019) · Zbl 1455.68009 |
| [47] | Zeng, W. J.; So, H. C.; Zoubir, A. M., An \(\ell_p\)-norm minimization approach to time delay estimation in impulsive noise. Digit. Signal Process., 1247-1254 (2013) |
| [48] | Zhang, H.; Xu, Y.; Zhang, J., Reproducing kernel Banach spaces for machine learning. J. Mach. Learn. Res., 2741-2775 (2009) · Zbl 1235.68217 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
