American Institute of Mathematical Sciences

Advanced
February  2019, 2(1): 1-9. doi: 10.3934/mfc.2019001

Kernel-based online gradient descent using distributed approach

Xiaming Chen ,

Shantou University, No. 243 Daxue Rd., Shantou, Guangdong, China

* Corresponding author: Xiaming Chen

Published  March 2019

Fund Project: The first author is supported by STU Scientific Research Foundation for Talents grant (NTF-18022).

In this paper we study the kernel-based online gradient descent with least squares loss without an explicit regularization term. Our approach is novel by controlling the expectation of the K-norm of $ f_t $ using an iterative process. Then we use distributed learning to improve our result.

Keywords: Learning theory, distributed learning, online gradient descent.
Mathematics Subject Classification: Primary: 68Q32, 68T05; Secondary: 62J02.
Citation: Xiaming Chen. Kernel-based online gradient descent using distributed approach. Mathematical Foundations of Computing, 2019, 2 (1) : 1-9. doi: 10.3934/mfc.2019001
References:
[1]

X. Chen and Y. Lei, Refined Bounds for online pairwise learning algorithm, Neurocomputing, 275 (2018), 2656-2665.  doi: 10.1016/j.neucom.2017.11.049.  Google Scholar

[2]

F. Cucker and S. Smale, On the mathematical foundations of learning, Bull. Amer. Math. Soc., 39 (2001), 1-49.  doi: 10.1090/S0273-0979-01-00923-5.  Google Scholar

[3]

J. Duchi, E. Hazan and Y. Singer, Adaptive subgradient methods for online learning and stochastic optimization, Journal of Machine Learning Research, 12 (2011), 2121-2159.   Google Scholar

[4]

T. Hu, Online regression with varying gaussians and non-identical distributions, Analysis and Applications, 9 (2011), 395-408.  doi: 10.1142/S0219530511001923.  Google Scholar

[5]

J. Kiefer and J. Wolfowitz, Stochastic estimation of the maximum of a regression function, Ann. Math. Statist., 23 (1952), 462-466.  doi: 10.1214/aoms/1177729392.  Google Scholar

[6]

S. B. Lin, X Guo and D. X. Zhou, Distributed learning with regularized least squares, Journal of Machine Learning Research, 18 (2017), Paper No. 92, 31 pp.  Google Scholar

[7]

M. Pontil, Y. Ying and D. X. Zhou, Error analysis for online gradient descent algorithms in reproducing kernel Hilbert space, Technical Report, Department of Computer Science, University College London, (2005). Google Scholar

[8]

H. Robbins and S. Monro, A stochastic approximation method, Ann. Math. Statist., 22 (1951), 400-407.  doi: 10.1214/aoms/1177729586.  Google Scholar

[9]

S. Smale and Y. Yao, Online learning algorithms, Found. Comput. Math., 6 (2006), 145-170.  doi: 10.1007/s10208-004-0160-z.  Google Scholar

[10]

S. Smale and D. X. Zhou, Online learning with Markov sampling, Analysis and Applications, 7 (2009), 87-113.  doi: 10.1142/S0219530509001293.  Google Scholar

[11]

S. Vijayakumar, A. D'Souza and S. Schaal, Incremental online learning in high dimensions, Neural Computation, 17 (2005), 2602-2634.  doi: 10.1162/089976605774320557.  Google Scholar

[12]

C. Wang and T Hu, Online minimum error entropy algorithm with unbounded sampling, Analysis and Applications, 17 (2019), 293-322.  doi: 10.1142/S0219530518500148.  Google Scholar

[13]

J. Xu, Z. Zheng, Z. Fan and W. Liu, Online personalized QoS prediction approach for cloud services, 4th International Conference on Cloud Computing and Intelligence Systems, 2016. doi: 10.1109/CCIS.2016.7790220.  Google Scholar

[14]

Y. Yao, L. Losasco and A. Caponnetto, Early stopping in gradient descent boosting, Constr. Approx., 26 (2007), 289-315.  doi: 10.1007/s00365-006-0663-2.  Google Scholar

[15]

Y. Ying and M. Pontil, Online pairwise learning algorithms, Found. Comput. Math., 28 (2016), 743-777.  doi: 10.1162/NECO_a_00817.  Google Scholar

[16]

Y. Ying and D. X. Zhou, Online regularized classification algorithm, IEEE, trans. Inform. Theory, 52 (2006), 4775-4788.  doi: 10.1109/TIT.2006.883632.  Google Scholar

[17]

Z. H. Zhou, N. V. Chawla, Y. Jin and G. J. Williams, Big data opportunities and challenges: Discussions from data analytics perspective, IEEE Computational Intelligence Magazine, 9 (2014), 62-74.   Google Scholar

show all references

References:
[1]

X. Chen and Y. Lei, Refined Bounds for online pairwise learning algorithm, Neurocomputing, 275 (2018), 2656-2665.  doi: 10.1016/j.neucom.2017.11.049.  Google Scholar

[2]

F. Cucker and S. Smale, On the mathematical foundations of learning, Bull. Amer. Math. Soc., 39 (2001), 1-49.  doi: 10.1090/S0273-0979-01-00923-5.  Google Scholar

[3]

J. Duchi, E. Hazan and Y. Singer, Adaptive subgradient methods for online learning and stochastic optimization, Journal of Machine Learning Research, 12 (2011), 2121-2159.   Google Scholar

[4]

T. Hu, Online regression with varying gaussians and non-identical distributions, Analysis and Applications, 9 (2011), 395-408.  doi: 10.1142/S0219530511001923.  Google Scholar

[5]

J. Kiefer and J. Wolfowitz, Stochastic estimation of the maximum of a regression function, Ann. Math. Statist., 23 (1952), 462-466.  doi: 10.1214/aoms/1177729392.  Google Scholar

[6]

S. B. Lin, X Guo and D. X. Zhou, Distributed learning with regularized least squares, Journal of Machine Learning Research, 18 (2017), Paper No. 92, 31 pp.  Google Scholar

[7]

M. Pontil, Y. Ying and D. X. Zhou, Error analysis for online gradient descent algorithms in reproducing kernel Hilbert space, Technical Report, Department of Computer Science, University College London, (2005). Google Scholar

[8]

H. Robbins and S. Monro, A stochastic approximation method, Ann. Math. Statist., 22 (1951), 400-407.  doi: 10.1214/aoms/1177729586.  Google Scholar

[9]

S. Smale and Y. Yao, Online learning algorithms, Found. Comput. Math., 6 (2006), 145-170.  doi: 10.1007/s10208-004-0160-z.  Google Scholar

[10]

S. Smale and D. X. Zhou, Online learning with Markov sampling, Analysis and Applications, 7 (2009), 87-113.  doi: 10.1142/S0219530509001293.  Google Scholar

[11]

S. Vijayakumar, A. D'Souza and S. Schaal, Incremental online learning in high dimensions, Neural Computation, 17 (2005), 2602-2634.  doi: 10.1162/089976605774320557.  Google Scholar

[12]

C. Wang and T Hu, Online minimum error entropy algorithm with unbounded sampling, Analysis and Applications, 17 (2019), 293-322.  doi: 10.1142/S0219530518500148.  Google Scholar

[13]

J. Xu, Z. Zheng, Z. Fan and W. Liu, Online personalized QoS prediction approach for cloud services, 4th International Conference on Cloud Computing and Intelligence Systems, 2016. doi: 10.1109/CCIS.2016.7790220.  Google Scholar

[14]

Y. Yao, L. Losasco and A. Caponnetto, Early stopping in gradient descent boosting, Constr. Approx., 26 (2007), 289-315.  doi: 10.1007/s00365-006-0663-2.  Google Scholar

[15]

Y. Ying and M. Pontil, Online pairwise learning algorithms, Found. Comput. Math., 28 (2016), 743-777.  doi: 10.1162/NECO_a_00817.  Google Scholar

[16]

Y. Ying and D. X. Zhou, Online regularized classification algorithm, IEEE, trans. Inform. Theory, 52 (2006), 4775-4788.  doi: 10.1109/TIT.2006.883632.  Google Scholar

[17]

Z. H. Zhou, N. V. Chawla, Y. Jin and G. J. Williams, Big data opportunities and challenges: Discussions from data analytics perspective, IEEE Computational Intelligence Magazine, 9 (2014), 62-74.   Google Scholar

[1]

Ning Zhang, Qiang Wu. Online learning for supervised dimension reduction. Mathematical Foundations of Computing, 2019, 2 (2) : 95-106. doi: 10.3934/mfc.2019008
[2]

Shuhua Wang, Zhenlong Chen, Baohuai Sheng. Convergence of online pairwise regression learning with quadratic loss. Communications on Pure & Applied Analysis, 2020, 19 (8) : 4023-4054. doi: 10.3934/cpaa.2020178
[3]

Soheila Garshasbi, Brian Yecies, Jun Shen. Microlearning and computer-supported collaborative learning: An agenda towards a comprehensive online learning system. STEM Education, 2021, 1 (4) : 225-255. doi: 10.3934/steme.2021016
[4]

Aude Hofleitner, Tarek Rabbani, Mohammad Rafiee, Laurent El Ghaoui, Alex Bayen. Learning and estimation applications of an online homotopy algorithm for a generalization of the LASSO. Discrete & Continuous Dynamical Systems - S, 2014, 7 (3) : 503-523. doi: 10.3934/dcdss.2014.7.503
[5]

Roberto C. Alamino, Nestor Caticha. Bayesian online algorithms for learning in discrete hidden Markov models. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 1-10. doi: 10.3934/dcdsb.2008.9.1
[6]

Marc Bocquet, Alban Farchi, Quentin Malartic. Online learning of both state and dynamics using ensemble Kalman filters. Foundations of Data Science, 2021, 3 (3) : 305-330. doi: 10.3934/fods.2020015
[7]

G. Calafiore, M.C. Campi. A learning theory approach to the construction of predictor models. Conference Publications, 2003, 2003 (Special) : 156-166. doi: 10.3934/proc.2003.2003.156
[8]

Ran Ma, Lu Zhang, Yuzhong Zhang. A best possible algorithm for an online scheduling problem with position-based learning effect. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021144
[9]

Yudong Li, Yonggang Li, Bei Sun, Yu Chen. Zinc ore supplier evaluation and recommendation method based on nonlinear adaptive online transfer learning. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021193
[10]

D. Warren, K Najarian. Learning theory applied to Sigmoid network classification of protein biological function using primary protein structure. Conference Publications, 2003, 2003 (Special) : 898-904. doi: 10.3934/proc.2003.2003.898
[11]

Alan Beggs. Learning in monotone bayesian games. Journal of Dynamics & Games, 2015, 2 (2) : 117-140. doi: 10.3934/jdg.2015.2.117
[12]

Yangyang Xu, Wotao Yin, Stanley Osher. Learning circulant sensing kernels. Inverse Problems & Imaging, 2014, 8 (3) : 901-923. doi: 10.3934/ipi.2014.8.901
[13]

Christian Soize, Roger Ghanem. Probabilistic learning on manifolds. Foundations of Data Science, 2020, 2 (3) : 279-307. doi: 10.3934/fods.2020013
[14]

Mauro Maggioni, James M. Murphy. Learning by active nonlinear diffusion. Foundations of Data Science, 2019, 1 (3) : 271-291. doi: 10.3934/fods.2019012
[15]

Nicolás M. Crisosto, Christopher M. Kribs-Zaleta, Carlos Castillo-Chávez, Stephen Wirkus. Community resilience in collaborative learning. Discrete & Continuous Dynamical Systems - B, 2010, 14 (1) : 17-40. doi: 10.3934/dcdsb.2010.14.17
[16]

Gernot Holler, Karl Kunisch. Learning nonlocal regularization operators. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021003
[17]

Minlong Lin, Ke Tang. Selective further learning of hybrid ensemble for class imbalanced increment learning. Big Data & Information Analytics, 2017, 2 (1) : 1-21. doi: 10.3934/bdia.2017005
[18]

Ziju Shen, Yufei Wang, Dufan Wu, Xu Yang, Bin Dong. Learning to scan: A deep reinforcement learning approach for personalized scanning in CT imaging. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021045
[19]

Prashant Shekhar, Abani Patra. Hierarchical approximations for data reduction and learning at multiple scales. Foundations of Data Science, 2020, 2 (2) : 123-154. doi: 10.3934/fods.2020008
[20]

Mikhail Langovoy, Akhilesh Gotmare, Martin Jaggi. Unsupervised robust nonparametric learning of hidden community properties. Mathematical Foundations of Computing, 2019, 2 (2) : 127-147. doi: 10.3934/mfc.2019010

 Impact Factor: 

Tools

Metrics

  • PDF downloads (225)
  • HTML views (761)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy