Mini-batch cutting plane method for regularized risk minimization

Meng-long LU; Lin-bo QIAO; Da-wei FENG; Dong-sheng LI; Xi-cheng LU

doi:10.1631/FITEE.1800596

Your Location：

Home >

Browse articles >

Mini-batch cutting plane method for regularized risk minimization

Regular Papers | Updated：2022-05-19

- Mini-batch cutting plane method for regularized risk minimization
- 正则风险最小化的小批量割平面法
- Frontiers of Information Technology & Electronic Engineering Vol. 20, Issue 11, Pages: 1551-1563(2019)
- Affiliations：
  
  Science and Technology on Parallel and Distributed Laboratory, National University of Defense Technology, Changsha 410073, China
- Author bio：
  
  [ "Meng-long LU, E-mail: lumenglong2018@163.com" ]
  Da-wei FENG, E-mail: davyfeng.c@gmail.com
- Funds：
- DOI：10.1631/FITEE.1800596
  CLC： TP391
- Received：25 September 2018，
  
  Revised：2019-10-10，
  
  Published：2019-11
- Accepted：
Scan QR Code
Meng-long LU, Lin-bo QIAO, Da-wei FENG, et al. Mini-batch cutting plane method for regularized risk minimization[J]. Frontiers of Information Technology & Electronic Engineering, 2019, 20(11): 1551-1563.
DOI：

Meng-long LU, Lin-bo QIAO, Da-wei FENG, et al. Mini-batch cutting plane method for regularized risk minimization[J]. Frontiers of Information Technology & Electronic Engineering, 2019, 20(11): 1551-1563. DOI： 10.1631/FITEE.1800596.

摘要

虽然最近求解非凸问题的研究十分热门，尤其在机器学习需要可解释性模型情况下，凸优化仍然重要。求解凸问题可得到全局最优解，故而最终模型可用数学方法解释。通常为防止过度拟合，凸问题被重新描述为一个正则风险最小化问题。无论目标函数是否可微，割平面法是求解凸问题最佳方法之一。然而，割平面法及其变体无法充分应对大规模密集型数据，因为这些算法每次迭代都需访问整个数据集，大大增加了计算负担和内存成本。为解决这一问题，提出一种新的小批量割平面法。该算法通过对小批量采样数据进行计算，得到估计切割平面用于迭代，使其能处理大规模数据。此外，小批量割平面法使用“sink”算子检测和调整噪声估计以保证收敛性。在大量实际数据集上的数值实验证明了小批量割平面法有效性，收敛速度优于正则风险最小化的bundle法和普遍使用的随机梯度下降法。

Abstract

Although concern has been recently expressed with regard to the solution to the non-convex problem

convex optimization is still important in machine learning

especially when the situation requires an interpretable model. Solution to the convex problem is a global minimum

and the final model can be explained mathematically. Typically

the convex problem is re-casted as a regularized risk minimization problem to prevent overfitting. The cutting plane method (CPM) is one of the best solvers for the convex problem

irrespective of whether the objective function is differentiable or not. However

CPM and its variants fail to adequately address large-scale data-intensive cases because these algorithms access the entire dataset in each iteration

which substantially increases the computational burden and memory cost. To alleviate this problem

we propose a novel algorithm named the mini-batch cutting plane method (MBCPM)

which iterates with estimated cutting planes calculated on a small batch of sampled data and is capable of handling large-scale problems. Furthermore

the proposed MBCPM adopts a "sink" operation that detects and adjusts noisy estimations to guarantee convergence. Numerical experiments on extensive real-world datasets demonstrate the effectiveness of MBCPM

which is superior to the bundle methods for regularized risk minimization as well as popular stochastic gradient descent methods in terms of convergence speed.

关键词

Keywords

references

A Belloni . . Introduction to Bundle Methods . . Lecture Notes for IAP, Operations Research Center, MIT, USA , , 2005 . . .

KP Bennett , , , OL Mangasarian . . Robust linear programming discrimination of two linearly inseparable sets . . Optim Methods Softw , , 1992 . . 1 ( ( 1 ): ): 23 - - 34 . . DOI: 10.1080/10556789208805504 http://doi.org/10.1080/10556789208805504 . .

L Bottou . . Large-scale machine learning with stochastic gradient descent . . Proc 19 th Int Conf on Computational Statistics , , 2010 . . p.177 - - 187 . . DOI: 10.1007/978-3-7908-2604-3_16 http://doi.org/10.1007/978-3-7908-2604-3_16 . .

K Crammer , , , Y Singer . . Ultraconservative online algorithms for multiclass problems . . J Mach Learn Res , , 2003 . . 3 951 - - 991 . . . .

M Duarte , , , YH Hu . . Vehicle classification in distributed sensor networks . . J Parall Distr Comput , , 2004 . . 64 ( ( 7 ): ): 826 - - 838 . . DOI: 10.1016/j.jpdc.2004.03.020 http://doi.org/10.1016/j.jpdc.2004.03.020 . .

J Duchi , , , E Hazan , , , Y Singer . . Adaptive subgradient methods for online learning and stochastic optimization . . J Mach Learn Res , , 2011 . . 12 2121 - - 2159 . . . .

V Franc , , , S Sonnenburg . . Optimized cutting plane algorithm for support vector machines . . Proc 25 th Int Conf on Machine Learning , , 2008 . . p.320 - - 327 . . DOI: 10.1145/1390156.1390197 http://doi.org/10.1145/1390156.1390197 . .

JB Hiriart-Urruty , , , C Lemar chal . . Convex Analysis and Minimization Algorithms I , , : : Berlin, Germany Springer , , 1993 . . DOI: 10.1007/978-3-662-02796-7 http://doi.org/10.1007/978-3-662-02796-7 . .

JEJr Kelley . . The cutting-plane method for solving convex programs . . J Soc Ind Appl Math , , 1960 . . 8 ( ( 4 ): ): 703 - - 712 . . DOI: 10.1137/0108053 http://doi.org/10.1137/0108053 . .

DP Kingma , , , J Ba . . Adam: a method for stochastic optimization , , 2014 . . https://arxiv.org/abs/1412.6980 https://arxiv.org/abs/1412.6980 , , . .

KC Kiwiel . . An aggregate subgradient method for nonsmooth convex minimization . . Math Program , , 1983 . . 27 ( ( 3 ): ): 320 - - 341 . . DOI: 10.1007/BF02591907 http://doi.org/10.1007/BF02591907 . .

KC Kiwiel . . Proximity control in bundle methods for convex nondifferentiable minimization . . Math Program , , 1990 . . 46 ( ( 1 ): ): 105 - - 122 . . DOI: 10.1007/BF01585731 http://doi.org/10.1007/BF01585731 . .

Y LeCun , , , L Bottou , , , Y Bengio , , , 等 . . Gradient-based learning applied to document recognition . . Proc IEEE , , 1998 . . 86 ( ( 11 ): ): 2278 - - 2324 . . DOI: 10.1109/5.726791 http://doi.org/10.1109/5.726791 . .

C Lemar chal , , , A Nemirovskii , , , Y Nesterov . . New variants of bundle methods . . Math Program , , 1995 . . 69 ( ( 1 ): ): 111 - - 147 . . DOI: 10.1007/BF01585555 http://doi.org/10.1007/BF01585555 . .

J Ma , , , LK Saul , , , S Savage , , , 等 . . Identifying suspicious URLs: an application of large-scale online learning . . Proc 26 th Int Conf on Machine Learning , , 2009 . . p.681 - - 688 . . DOI: 10.1145/1553374.1553462 http://doi.org/10.1145/1553374.1553462 . .

A Mokhtari , , , M Eisen , , , A Ribeiro . . IQN: an incremental quasi-Newton method with local superlinear convergence rate . . SIAM J Opt , , 2018 . . 28 ( ( 2 ): ): 1670 - - 1698 . . DOI: 10.1137/17M1122943 http://doi.org/10.1137/17M1122943 . .

LL Mou , , , R Men , , , G Li , , , 等 . . Natural language inference by tree-based convolution and heuristic matching . . Proc 54 th Annual Meeting of the Association for Computational Linguistics , , 2016 . . p.130 - - 136 . . . .

N Qian . . On the momentum term in gradient descent learning algorithms . . Neur Netw , , 1999 . . 12 ( ( 1 ): ): 145 - - 151 . . DOI: 10.1016/S0893-6080(98)00116-6 http://doi.org/10.1016/S0893-6080(98)00116-6 . .

H Schramm , , , J Zowe . . A version of the bundle idea for minimizing a nonsmooth function: conceptual idea, convergence analysis, numerical results . . SIAM J Opt , , 1992 . . 2 ( ( 1 ): ): 121 - - 152 . . DOI: 10.1137/0802008 http://doi.org/10.1137/0802008 . .

S Sonnenburg , , , V Franc . . COFFIN: a computational framework for linear SVMs . . Proc 27 th Int Conf on Machine Learning , , 2010 . . p.999 - - 1006 . . . .

CH Teo , , , SVN Vishwanthan , , , AJ Smola , , , 等 . . Bundle methods for regularized risk minimization . . J Mach Learn Res , , 2010 . . 11 311 - - 365 . . DOI: 10.1145/1756006.1756016 http://doi.org/10.1145/1756006.1756016 . .

I Tsochantaridis , , , T Joachims , , , T Hofmann , , , 等 . . Large margin methods for structured and interdependent output variables . . J Mach Learn Res , , 2005 . . 6 1453 - - 1484 . . . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

Domain adaptation in reinforcement learning: a comprehensive and systematic study

Towards sustainable adversarial training with successive perturbation generation

Advances and challenges in artificial intelligence text generation

A disk failure prediction model for multiple issues

Data-driven soft sensors in blast furnace ironmaking: a survey

Related Author

Mohammad TESHNEHLAB

Arash SHARIFI

Mitra MIRZAREZAEE

Amirfarhad FARHADI

Lichuan LIAO

Wei LIN

Peng YANG

Bing LI

Related Institution

Department of Control Engineering, K.N. Toosi University of Technology

Department of Computer Engineering, Science and Research Branch, Islamic Azad University

Fujian Provincial Key Laboratory of Big Data Mining and Applications, Fujian University of Technology

College of Economics and Management, Xi’an University of Technology

College of Computer Science and Mathematics, Fujian University of Technology

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰