Incremental quasi-Newton algorithms for solving a nonconvex, nonsmooth, finite-sum optimization problem

References

• M.M. Ali, C. Khompatraporn, and Z.B. Zabinsky, A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems, J. Glob. Optim. 31 (2005), pp. 635–672.
   Web of Science ®Google Scholar
• A. Astorino and A. Fuduli, Nonsmooth optimization techniques for semisupervised classification, IEEE Trans. Pattern Anal. Mach. Intell. 29 (2007), pp. 2135–2142.
   PubMed Web of Science ®Google Scholar
• A. Astorino and A. Fuduli, Support vector machine polyhedral separability in semisupervised learning, J. Optim. Theory Appl. 164 (2015), pp. 1039–1050.
   Web of Science ®Google Scholar
• V. Beiranvand, W. Hare, and Y. Lucet, Best practices for comparing optimization algorithms, Optim. Eng. 18 (2017), pp. 815–848.
   Web of Science ®Google Scholar
• M. Belkin, P. Niyogi, and V. Sindhwani, Manifold regularization: A geometric framework for learning from labeled and unlabeled examples., J. Mach. Learn. Res. 7 (2006), pp. 2399–2434.
   Web of Science ®Google Scholar
• K. Bennett and A. Demiriz, Semi-supervised support vector machines, Adv. Neural Inf. Process. Syst. 11 (1998), pp. 368–374.
   Google Scholar
• D.P. Bertsekas, Incremental gradient, subgradient, and proximal methods for convex optimization: A survey, Optim. Mach. Learn. 2010 (2011), pp. 3.
   Google Scholar
• D. Blatt, A.O. Hero, and H. Gauchman, A convergent incremental gradient method with a constant step size, SIAM J. Optim. 18 (2007), pp. 29–51.
   Web of Science ®Google Scholar
• C.G. Broyden, The convergence of a class of double-rank minimization algorithms 1. general considerations, IMA J. Appl. Math. 6 (1970), pp. 76–90.
   Google Scholar
• C.G. Broyden, J.E. Dennis, and Jr. J.J. Moré, On the local and superlinear convergence of quasi-newton methods, J. Inst. Math. Appl. 12 (1973), pp. 223–245.
   Google Scholar
• R.H. Byrd, J. Nocedal, and Y.X. Yuan, Global convergence of a cass of quasi-newton methods on convex problems, SIAM J. Numer. Anal. 24 (1987), pp. 1171–1190.
   Web of Science ®Google Scholar
• R.H. Byrd, G.M. Chin, W. Neveitt, and J. Nocedal, On the use of stochastic hessian information in optimization methods for machine learning, SIAM J. Optim. 21 (2011), pp. 977–995.
   Web of Science ®Google Scholar
• R.H. Byrd, S.L. Hansen, J. Nocedal, and Y. Singer, A stochastic quasi-newton method for large-scale optimization, SIAM J. Optim. 26 (2016), pp. 1008–1031.
   Web of Science ®Google Scholar
• C.C. Chang and C.J. Lin, Libsvm: A library for support vector machines, ACM Trans. Intell. Syst. Technol. 2 (2011), pp. 1–27.
   Web of Science ®Google Scholar
• O. Chapelle and A. Zien, Semi-supervised classification by low density separation, in International Workshop on Artificial Intelligence and Statistics, PMLR, 2005, pp. 57–64.
   Google Scholar
• O. Chapelle, V. Sindhwani, and S.S. Keerthi, Optimization techniques for semi-supervised support vector machines., J. Mach. Learn. Res. 9 (2008), pp. 203–233.
   Web of Science ®Google Scholar
• X. Chen, Smoothing methods for nonsmooth, nonconvex minimization, Math. Program. 134 (2012), pp. 71–99.
   Web of Science ®Google Scholar
• X. Chen, L. Niu, and Y. Yuan, Optimality conditions and a smoothing trust region Newton method for nonLipschitz optimization, SIAM J. Optim. 23 (2013), pp. 1528–1552.
   Web of Science ®Google Scholar
• F.H. Clarke, Optimization and Nonsmooth Analysis, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, New York, NY, USA, 1983.
   Google Scholar
• R. Collobert, F. Sinz, J. Weston, L. Bottou, and T. Joachims, Large scale transductive svms., J. Mach. Learn. Res. 7 (2006), pp. 1687–1712.
   Web of Science ®Google Scholar
• Y. Cui and J.S. Pang, Modern Nonconvex Nondifferentiable Optimization, SIAM, 2021.
   Google Scholar
• F.E. Curtis and X. Que, A quasi-newton algorithm for nonconvex, nonsmooth optimization with global convergence guarantees, Math. Program. Comput. 7 (2015), pp. 399–428.
   Web of Science ®Google Scholar
• F.E. Curtis, D.P. Robinson, and B. Zhou, A self-correcting variable-metric algorithm framework for nonsmooth optimization, IMA J. Numer. Anal. 40 (2020), pp. 1154–1187.
   Web of Science ®Google Scholar
• D. Davis, D. Drusvyatskiy, K.J. MacPhee, and C. Paquette, Subgradient methods for sharp weakly convex functions, J. Optim. Theory Appl. 179 (2018), pp. 962–982.
   Web of Science ®Google Scholar
• J.E. Dennis and J.J. Moré, A characterization of superlinear convergence and its application to quasi-newton methods, Math. Comput. 28 (1974), pp. 549–560.
   Web of Science ®Google Scholar
• E.D. Dolan and J.J. Moré, Benchmarking optimization software with performance profiles, Math. Program. 91 (2002), pp. 201–213.
   Web of Science ®Google Scholar
• R. Fletcher, A new approach to variable metric algorithms, Comput. J. 13 (1970), pp. 317–322.
   Web of Science ®Google Scholar
• A. Fuduli, M. Gaudioso, and G. Giallombardo, Minimizing nonconvex nonsmooth functions via cutting planes and proximity control, SIAM J. Optim. 14 (2004), pp. 743–756.
   Web of Science ®Google Scholar
• D. Goldfarb, A family of variable-metric methods derived by variational means, Math. Comput. 24 (1970), pp. 23–26.
   Web of Science ®Google Scholar
• M. Gürbüzbalaban, A. Ozdaglar, and P. Parrilo, A globally convergent incremental newton method, Math. Program. 151 (2015), pp. 283–313.
   Web of Science ®Google Scholar
• M. Gurbuzbalaban, A. Ozdaglar, and P.A. Parrilo, On the convergence rate of incremental aggregated gradient algorithms, SIAM J. Optim. 27 (2017), pp. 1035–1048.
   Web of Science ®Google Scholar
• M. Gurbuzbalaban, A. Ozdaglar, and P.A. Parrilo, Convergence rate of incremental gradient and incremental newton methods, SIAM J. Optim. 29 (2019), pp. 2542–2565.
   Web of Science ®Google Scholar
• Gurobi Optimization, LLC, Gurobi Optimizer Reference Manual, (2022). Available at https://www.gurobi.com.
   Google Scholar
• R. Horst and N.V. Thoai, Dc programming: Overview, J. Optim. Theory Appl. 103 (1999), pp. 1–43.
   Web of Science ®Google Scholar
• Y. Hu, C.K.W. Yu, and X. Yang, Incremental quasi-subgradient methods for minimizing the sum of quasi-convex functions, J. Glob. Optim. 75 (2019), pp. 1003–1028.
   Web of Science ®Google Scholar
• H. Iiduka, Incremental subgradient method for nonsmooth convex optimization with fixed point constraints, Optim. Methods Softw. 31 (2016), pp. 931–951.
   Web of Science ®Google Scholar
• T. Joachims, Transductive inference for text classification using support vector machines, in ICML, Vol. 99. 1999, pp. 200–209.
   Google Scholar
• K.C. Kiwiel, Convergence of approximate and incremental subgradient methods for convex optimization, SIAM J. Optim. 14 (2004), pp. 807–840.
   Web of Science ®Google Scholar
• A.S. Lewis and M.L. Overton, Nonsmooth optimization via quasi-newton methods, Math. Program.141 (2013), pp. 135–163.
   Web of Science ®Google Scholar
• D.H. Li and M. Fukushima, A modified bfgs method and its global convergence in nonconvex minimization, J. Comput. Appl. Math. 129 (2001), pp. 15–35.
   Web of Science ®Google Scholar
• D.H. Li and M. Fukushima, On the global convergence of the bfgs method for nonconvex unconstrained optimization problems, SIAM J. Optim. 11 (2001), pp. 1054–1064.
   Web of Science ®Google Scholar
• A. Mokhtari, M. Eisen, and A. Ribeiro, Iqn: An incremental quasi-newton method with local superlinear convergence rate, SIAM J. Optim. 28 (2018), pp. 1670–1698.
   Web of Science ®Google Scholar
• P.M. Murphy, Uci repository of machine learning databases, (1994), Available at ftp:/pub/machine-learning-databaseonics.uci.edu.
   Google Scholar
• A. Nedic and D.P. Bertsekas, Incremental subgradient methods for nondifferentiable optimization, SIAM J. Optim. 12 (2001), pp. 109–138.
   Web of Science ®Google Scholar
• J. Nocedal and S. Wright, Numerical Optimization, Springer Science & Business Media, 2006.
   Google Scholar
• P. Qi, W. Zhou, and J. Han, A method for stochastic L-BFGS optimization, in 2017 IEEE 2nd International Conference on Cloud Computing and Big Data Analysis (ICCCBDA), IEEE, 2017, pp. 156–160.
   Google Scholar
• S.S. Ram, A. Nedić, and V.V. Veeravalli, Incremental stochastic subgradient algorithms for convex optimization, SIAM J. Optim. 20 (2009), pp. 691–717.
   Web of Science ®Google Scholar
• D.F. Shanno, Conditioning of quasi-newton methods for function minimization, Math. Comput. 24 (1970), pp. 647–656.
   Web of Science ®Google Scholar
• V. Sindhwani and S.S. Keerthi, Large scale semi-supervised linear SVMs, in Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Seattle, WA, 2006, pp. 477–484.
   Google Scholar
• M.V. Solodov, Incremental gradient algorithms with stepsizes bounded away from zero, Comput. Optim. Appl. 11 (1998), pp. 23–35.
   Web of Science ®Google Scholar
• J.E. Van Engelen and H.H. Hoos, A survey on semi-supervised learning, Mach. Learn. 109 (2020), pp. 373–440.
   Web of Science ®Google Scholar
• A.I.F. Vaz and L.N. Vicente, A particle swarm pattern search method for bound constrained global optimization, J. Glob. Optim. 39 (2007), pp. 197–219.
   Web of Science ®Google Scholar
• J.P. Vial, Strong and weak convexity of sets and functions, Math. Oper. Res. 8 (1983), pp. 231–259.
   Web of Science ®Google Scholar
• H.T. Wai, W. Shi, C.A. Uribe, A. Nedić, and A. Scaglione, Accelerating incremental gradient optimization with curvature information, Comput. Optim. Appl. 76 (2020), pp. 347–380.
   Web of Science ®Google Scholar
• R. Zhao, W.B. Haskell, and V.Y. Tan, Stochastic l-bfgs: Improved convergence rates and practical acceleration strategies, IEEE Trans. Signal. Process. 66 (2017), pp. 1155–1169.
   Web of Science ®Google Scholar
• X. Zhou and M. Belkin, Semi-supervised learning, in Academic Press Library in Signal Processing Vol.1, P.S.R. Diniz, J.A.K. Suykens, R. Chellappa, and S. Theodoridis eds., 2014, pp. 1239–1269.
   Google Scholar