Figure 1.
Numerical results of models (12) and (13) for Tai Chi data set are illustrated in Figure 1(a) and Figure 1(b), respectively.
- Previous Article
- MFC Home
- This Issue
-
Next Article
The nonexistence of global solution for system of q-difference inequalities
August
2020, 3(3): 205-218.
doi: 10.3934/mfc.2020020
Sparse regularized learning in the reproducing kernel banach spaces with the $ \ell^1 $ norm
| 1. | School of Mathematical Sciences, South China Normal University, Guangzhou, Guangdong 510631, China |
| 2. | School of Data and Computer Science, Sun Yat-sen University, Guangzhou, Guangdong 510006, China |
We present a sparse representer theorem for regularization networks in a reproducing kernel Banach space with the $ \ell^1 $ norm by the theory of convex analysis. The theorem states that extreme points of the solution set of regularization networks in such a sparsity-promoting space belong to the span of kernel functions centered on at most $ n $ adaptive points of the input space, where $ n $ is the number of training data. Under the Lebesgue constant assumptions on reproducing kernels, we can recover the relaxed representer theorem and the exact representer theorem in that space in the literature. Finally, we perform numerical experiments for synthetic data and real-world benchmark data in the reproducing kernel Banach spaces with the $ \ell^1 $ norm and the reproducing kernel Hilbert spaces both with Laplacian kernels. The numerical performance demonstrates the advantages of sparse regularized learning.
Keywords:
Sparse representer theorems,
reproducing kernel banach spaces,
Laplacian kernels,
$ \ell^1 $ norm.
Mathematics Subject Classification:
Primary: 46E22, 62G08; Secondary: 68Q32.
Citation:
Ying Lin, Rongrong Lin, Qi Ye. Sparse regularized learning in the reproducing kernel banach spaces with the $ \ell^1 $ norm. Mathematical Foundations of Computing,
2020, 3
(3)
: 205-218.
doi: 10.3934/mfc.2020020
![]()
References:
| [1] |
S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein,
Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3 (2011), 1-122.
doi: 10.1561/2200000016. |
| [2] |
C. Boyer, A. Chambolle, Y. De Castro, V. Duval, F. de Gournay and P. Weiss,
On representer theorems and convex regularization, SIAM J. Optim., 29 (2019), 1260-1281.
doi: 10.1137/18M1200750. |
| [3] |
O. Christensen, An Introduction to Frames and Riesz Bases, 2nd edition, Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, [Cham], 2016.
doi: 10.1007/978-3-319-25613-9. |
| [4] |
H. G. Dales, F. K. Dashiell Jr., A. T.-M. Lau and D. Strauss, Banach Spaces of Continuous Functions as Dual Spaces, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, Springer, Cham, 2016.
doi: 10.1007/978-3-319-32349-7. |
| [5] |
S. De Marchi and R. Schaback,
Stability of kernel-based interpolation, Adv. Comput. Math., 32 (2010), 155-161.
doi: 10.1007/s10444-008-9093-4. |
| [6] |
D. L. Donoho,
For most large underdetermined systems of equations, the minimal $l_1$-norm near-solution approximates the sparsest near-solution, Comm. Pure Appl. Math., 59 (2006), 907-934.
doi: 10.1002/cpa.20131. |
| [7] |
G. Fasshauer and M. McCourt, Kernel-Based Approximation Methods using MATLAB, Interdisciplinary Mathematical Sciences. Vol. 19, World Scientific, 2015. Google Scholar |
| [8] |
Z.-C. Guo and L. Shi,
Learning with coefficient-based regularization and $\ell^1$-penalty, Adv. Comput. Math., 39 (2013), 493-510.
doi: 10.1007/s10444-012-9288-6. |
| [9] |
T. Hangelbroek, F. J. Narcowich and J. D. Ward,
Kernel approximation on manifolds I: bounding the Lebesgue constant, SIAM J. Math. Anal., 42 (2010), 1732-1760.
doi: 10.1137/090769570. |
| [10] |
L. Huang, C. Liu, L. Tan and Q. Ye, Generalized representer theorems in Banach spaces, Anal. Appl. (Singap.), (2019).
doi: 10.1142/S0219530519410100. |
| [11] |
V. Klee,
On a theorem of Dubins, J. Math. Anal. Appl., 7 (1963), 425-427.
doi: 10.1016/0022-247X(63)90063-5. |
| [12] |
Z. Li, Y. Xu and Q. Ye, Sparse support vector machines in reproducing kernel banach spaces, Contemporary Computational Mathematics-A Celebration of the 80th Birthday of Ian Sloan, Springer, Cham, 1 (2018), 869–887. |
| [13] |
R. Lin, G. Song and H. Zhang, Multi-task learning in vector-valued reproducing kernel Banach spaces with the $\ell^1$ norm, https://arXiv.org/abs/1901.01036. Google Scholar |
| [14] |
R. Lin, H. Zhang and J. Zhang, On reproducing kernel Banach spaces: Generic definitions and unified framework of constructions, https://arXiv.org/abs/1901.01002. Google Scholar |
| [15] |
A. Rudi, R. Camoriano and L. Rosasco, Less is more: Nyström computational regularization, in Advances in Neural Information Processing Systems, (2015), 1657–1665. Google Scholar |
| [16] |
K. Schlegel,
When is there a representer theorem? Nondifferentiable regularisers and Banach spaces, J. Global Optim., 74 (2019), 401-415.
doi: 10.1007/s10898-019-00767-0. |
| [17] | B. Schölkopf and A. J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, The MIT Press, Cambridge, 2001. Google Scholar |
| [18] |
B. Simon, Convexity: An Analytic Viewpoint, vol. 187 of Cambridge Tracts in Mathematics, Cambridge University Press, Cambridge, 2011.
doi: 10.1017/CBO9780511910135.
Google Scholar
|
| [19] |
G. Song and H. Zhang,
Reproducing kernel Banach spaces with the $\ell^1$ norm ii: Error analysis for regularized least square regression, Neural Comput., 23 (2011), 2713-2729.
doi: 10.1162/NECO_a_00178. |
| [20] |
G. Song, H. Zhang and F. J. Hickernell,
Reproducing kernel Banach spaces with the $\ell^1$ norm, Appl. Comput. Harmon. Anal., 34 (2013), 96-116.
doi: 10.1016/j.acha.2012.03.009. |
| [21] |
B. K. Sriperumbudur, K. Fukumizu and G. R. G. Lanckriet,
Universality, characteristic kernels and RKHS embedding of measures, J. Mach. Learn. Res., 12 (2011), 2389-2410.
|
| [22] |
I. Steinwart and A. Christmann, Support Vector Machines, Information Science and Statistics, Springer, New York, 2008. |
| [23] |
M. Unser, J. Fageot and H. Gupta,
Representer theorems for sparsity-promoting $\ell_1$ regularization, IEEE Trans. Inform. Theory, 62 (2016), 5167-5180.
doi: 10.1109/TIT.2016.2590421. |
| [24] |
Y. Xu and Q. Ye, Generalized Mercer kernels and reproducing kernel Banach spaces, Mem. Amer. Math. Soc., 258 (2019), no. 1243,122 pp.
doi: 10.1090/memo/1243. |
| [25] |
H. Zhang, Y. Xu and J. Zhang,
Reproducing kernel Banach spaces for machine learning, J. Mach. Learn. Res., 10 (2009), 2741-2775.
doi: 10.1109/IJCNN.2009.5179093. |
| [26] |
H. Zhang and L. Zhao, On the inclusion relation of reproducing kernel Hilbert spaces, Anal. Appl. (Singap.), 11 (2013), 1350014, 31pp.
doi: 10.1142/S0219530513500140. |
show all references
References:
| [1] |
S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein,
Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3 (2011), 1-122.
doi: 10.1561/2200000016. |
| [2] |
C. Boyer, A. Chambolle, Y. De Castro, V. Duval, F. de Gournay and P. Weiss,
On representer theorems and convex regularization, SIAM J. Optim., 29 (2019), 1260-1281.
doi: 10.1137/18M1200750. |
| [3] |
O. Christensen, An Introduction to Frames and Riesz Bases, 2nd edition, Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, [Cham], 2016.
doi: 10.1007/978-3-319-25613-9. |
| [4] |
H. G. Dales, F. K. Dashiell Jr., A. T.-M. Lau and D. Strauss, Banach Spaces of Continuous Functions as Dual Spaces, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, Springer, Cham, 2016.
doi: 10.1007/978-3-319-32349-7. |
| [5] |
S. De Marchi and R. Schaback,
Stability of kernel-based interpolation, Adv. Comput. Math., 32 (2010), 155-161.
doi: 10.1007/s10444-008-9093-4. |
| [6] |
D. L. Donoho,
For most large underdetermined systems of equations, the minimal $l_1$-norm near-solution approximates the sparsest near-solution, Comm. Pure Appl. Math., 59 (2006), 907-934.
doi: 10.1002/cpa.20131. |
| [7] |
G. Fasshauer and M. McCourt, Kernel-Based Approximation Methods using MATLAB, Interdisciplinary Mathematical Sciences. Vol. 19, World Scientific, 2015. Google Scholar |
| [8] |
Z.-C. Guo and L. Shi,
Learning with coefficient-based regularization and $\ell^1$-penalty, Adv. Comput. Math., 39 (2013), 493-510.
doi: 10.1007/s10444-012-9288-6. |
| [9] |
T. Hangelbroek, F. J. Narcowich and J. D. Ward,
Kernel approximation on manifolds I: bounding the Lebesgue constant, SIAM J. Math. Anal., 42 (2010), 1732-1760.
doi: 10.1137/090769570. |
| [10] |
L. Huang, C. Liu, L. Tan and Q. Ye, Generalized representer theorems in Banach spaces, Anal. Appl. (Singap.), (2019).
doi: 10.1142/S0219530519410100. |
| [11] |
V. Klee,
On a theorem of Dubins, J. Math. Anal. Appl., 7 (1963), 425-427.
doi: 10.1016/0022-247X(63)90063-5. |
| [12] |
Z. Li, Y. Xu and Q. Ye, Sparse support vector machines in reproducing kernel banach spaces, Contemporary Computational Mathematics-A Celebration of the 80th Birthday of Ian Sloan, Springer, Cham, 1 (2018), 869–887. |
| [13] |
R. Lin, G. Song and H. Zhang, Multi-task learning in vector-valued reproducing kernel Banach spaces with the $\ell^1$ norm, https://arXiv.org/abs/1901.01036. Google Scholar |
| [14] |
R. Lin, H. Zhang and J. Zhang, On reproducing kernel Banach spaces: Generic definitions and unified framework of constructions, https://arXiv.org/abs/1901.01002. Google Scholar |
| [15] |
A. Rudi, R. Camoriano and L. Rosasco, Less is more: Nyström computational regularization, in Advances in Neural Information Processing Systems, (2015), 1657–1665. Google Scholar |
| [16] |
K. Schlegel,
When is there a representer theorem? Nondifferentiable regularisers and Banach spaces, J. Global Optim., 74 (2019), 401-415.
doi: 10.1007/s10898-019-00767-0. |
| [17] | B. Schölkopf and A. J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, The MIT Press, Cambridge, 2001. Google Scholar |
| [18] |
B. Simon, Convexity: An Analytic Viewpoint, vol. 187 of Cambridge Tracts in Mathematics, Cambridge University Press, Cambridge, 2011.
doi: 10.1017/CBO9780511910135.
Google Scholar
|
| [19] |
G. Song and H. Zhang,
Reproducing kernel Banach spaces with the $\ell^1$ norm ii: Error analysis for regularized least square regression, Neural Comput., 23 (2011), 2713-2729.
doi: 10.1162/NECO_a_00178. |
| [20] |
G. Song, H. Zhang and F. J. Hickernell,
Reproducing kernel Banach spaces with the $\ell^1$ norm, Appl. Comput. Harmon. Anal., 34 (2013), 96-116.
doi: 10.1016/j.acha.2012.03.009. |
| [21] |
B. K. Sriperumbudur, K. Fukumizu and G. R. G. Lanckriet,
Universality, characteristic kernels and RKHS embedding of measures, J. Mach. Learn. Res., 12 (2011), 2389-2410.
|
| [22] |
I. Steinwart and A. Christmann, Support Vector Machines, Information Science and Statistics, Springer, New York, 2008. |
| [23] |
M. Unser, J. Fageot and H. Gupta,
Representer theorems for sparsity-promoting $\ell_1$ regularization, IEEE Trans. Inform. Theory, 62 (2016), 5167-5180.
doi: 10.1109/TIT.2016.2590421. |
| [24] |
Y. Xu and Q. Ye, Generalized Mercer kernels and reproducing kernel Banach spaces, Mem. Amer. Math. Soc., 258 (2019), no. 1243,122 pp.
doi: 10.1090/memo/1243. |
| [25] |
H. Zhang, Y. Xu and J. Zhang,
Reproducing kernel Banach spaces for machine learning, J. Mach. Learn. Res., 10 (2009), 2741-2775.
doi: 10.1109/IJCNN.2009.5179093. |
| [26] |
H. Zhang and L. Zhao, On the inclusion relation of reproducing kernel Hilbert spaces, Anal. Appl. (Singap.), 11 (2013), 1350014, 31pp.
doi: 10.1142/S0219530513500140. |
Figure 2.
Numerical results of models (12) and (13) for the second data set are illustrated in Figure 2(a) and Figure 2(b), respectively
Table 1.
Lebesgue constants of the Laplacian kernel $ e^{-\|x-x'\|_2} $ on a set of $ n $ grid points of $ [-1, 1]^2 $
| n=100 | n=400 | n=900 | n=1600 | n=2500 |
| 1.237204 | 1.244770 | 1.249653 | 1.246516 | 1.246808 |
| n=100 | n=400 | n=900 | n=1600 | n=2500 |
| 1.237204 | 1.244770 | 1.249653 | 1.246516 | 1.246808 |
Table 2.
Lebesgue constants of the Laplacian kernel $ e^{-\|x-x'\|_2} $ , $ x, x'\in{\mathbb R}^3 $ on a set of $ n $ grid points of $ [-1, 1]^3 $
| n=125 | n=1000 | n=1728 | n=2197 | n=3375 |
| 1.624012 | 1.705158 | 1.709775 | 1.711243 | 1.712867 |
| n=125 | n=1000 | n=1728 | n=2197 | n=3375 |
| 1.624012 | 1.705158 | 1.709775 | 1.711243 | 1.712867 |
| [1] |
Chaoqian Li, Yajun Liu, Yaotang Li. Note on $ Z $-eigenvalue inclusion theorems for tensors. Journal of Industrial & Management Optimization, 2021, 17 (2) : 687-693. doi: 10.3934/jimo.2019129 |
| [2] |
Federico Rodriguez Hertz, Zhiren Wang. On $ \epsilon $-escaping trajectories in homogeneous spaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 329-357. doi: 10.3934/dcds.2020365 |
| [3] |
Sugata Gangopadhyay, Constanza Riera, Pantelimon Stănică. Gowers $ U_2 $ norm as a measure of nonlinearity for Boolean functions and their generalizations. Advances in Mathematics of Communications, 2021, 15 (2) : 241-256. doi: 10.3934/amc.2020056 |
| [4] |
Chandra Shekhar, Amit Kumar, Shreekant Varshney, Sherif Ibrahim Ammar. $ \bf{M/G/1} $ fault-tolerant machining system with imperfection. Journal of Industrial & Management Optimization, 2021, 17 (1) : 1-28. doi: 10.3934/jimo.2019096 |
| [5] |
El Haj Laamri, Michel Pierre. Stationary reaction-diffusion systems in $ L^1 $ revisited. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 455-464. doi: 10.3934/dcdss.2020355 |
| [6] |
Yichen Zhang, Meiqiang Feng. A coupled $ p $-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075 |
| [7] |
Lihong Zhang, Wenwen Hou, Bashir Ahmad, Guotao Wang. Radial symmetry for logarithmic Choquard equation involving a generalized tempered fractional $ p $-Laplacian. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020445 |
| [8] |
Mokhtar Bouloudene, Manar A. Alqudah, Fahd Jarad, Yassine Adjabi, Thabet Abdeljawad. Nonlinear singular $ p $ -Laplacian boundary value problems in the frame of conformable derivative. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020442 |
| [9] |
Shengbing Deng, Tingxi Hu, Chun-Lei Tang. $ N- $Laplacian problems with critical double exponential nonlinearities. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 987-1003. doi: 10.3934/dcds.2020306 |
| [10] |
Fuensanta Andrés, Julio Muñoz, Jesús Rosado. Optimal design problems governed by the nonlocal $ p $-Laplacian equation. Mathematical Control & Related Fields, 2021, 11 (1) : 119-141. doi: 10.3934/mcrf.2020030 |
| [11] |
Raffaele Folino, Ramón G. Plaza, Marta Strani. Long time dynamics of solutions to $ p $-Laplacian diffusion problems with bistable reaction terms. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020403 |
| [12] |
Zaizheng Li, Qidi Zhang. Sub-solutions and a point-wise Hopf's lemma for fractional $ p $-Laplacian. Communications on Pure & Applied Analysis, 2021, 20 (2) : 835-865. doi: 10.3934/cpaa.2020293 |
| [13] |
Waixiang Cao, Lueling Jia, Zhimin Zhang. A $ C^1 $ Petrov-Galerkin method and Gauss collocation method for 1D general elliptic problems and superconvergence. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 81-105. doi: 10.3934/dcdsb.2020327 |
| [14] |
Wenqiang Zhao, Yijin Zhang. High-order Wong-Zakai approximations for non-autonomous stochastic $ p $-Laplacian equations on $ \mathbb{R}^N $. Communications on Pure & Applied Analysis, 2021, 20 (1) : 243-280. doi: 10.3934/cpaa.2020265 |
| [15] |
Beom-Seok Han, Kyeong-Hun Kim, Daehan Park. A weighted Sobolev space theory for the diffusion-wave equations with time-fractional derivatives on $ C^{1} $ domains. Discrete & Continuous Dynamical Systems - A, 2021 doi: 10.3934/dcds.2021002 |
| [16] |
Dmitry Dolgopyat. The work of Sébastien Gouëzel on limit theorems and on weighted Banach spaces. Journal of Modern Dynamics, 2020, 16: 351-371. doi: 10.3934/jmd.2020014 |
| [17] |
Martin Heida, Stefan Neukamm, Mario Varga. Stochastic homogenization of $ \Lambda $-convex gradient flows. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 427-453. doi: 10.3934/dcdss.2020328 |
| [18] |
Jiahao Qiu, Jianjie Zhao. Maximal factors of order $ d $ of dynamical cubespaces. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 601-620. doi: 10.3934/dcds.2020278 |
| [19] |
Mathew Gluck. Classification of solutions to a system of $ n^{\rm th} $ order equations on $ \mathbb R^n $. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5413-5436. doi: 10.3934/cpaa.2020246 |
| [20] |
Luca Battaglia, Francesca Gladiali, Massimo Grossi. Asymptotic behavior of minimal solutions of $ -\Delta u = \lambda f(u) $ as $ \lambda\to-\infty $. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 681-700. doi: 10.3934/dcds.2020293 |
Impact Factor:
Tools
Article outline
Figures and Tables
[Back to Top]