IEEE Transactions on Neural Networks and Learning Systems · 2021 · 22 citations · 18 references
ComputingComputer ScienceAlgorithmsOptimizationScientific ComputingLarge-scale OptimizationNumerical AlgorithmsNumerical AnalysisNumerical Linear AlgebraConvergenceGradient DescentLocal Convergence AnalysisNewton ConvergenceNewton's Method As A Fixed Point Process
Truncated Newton (TN) methods have been a useful technique for large-scale optimization. Instead of obtaining the full Newton direction, a truncated method approximately solves the Newton equation with an inner conjugate gradient (CG) procedure (TNCG for the whole method). These methods have been employed to efficiently solve linear classification problems. However, even in this deeply studied field, various theoretical and numerical aspects were not completely explored. The first contribution of this work is to comprehensively study the global and local convergence when TNCG is applied to linear classification. Because of the lack of twice differentiability under some losses, many past works cannot be applied here. We prove various missing pieces of theory from scratch and clarify many proper references. The second contribution is to study the termination of the CG method. For the first time when TNCG is applied to linear classification, we show that the inner stopping condition strongly affects the convergence speed. We propose using a quadratic stopping criterion to achieve both robustness and efficiency. The third contribution is that of combining the study on inner stopping criteria with that of preconditioning. We discuss how convergence theory is affected by preconditioning and finally propose an effective preconditioned TNCG.
18
Scikit-learn: Machine Learning in Python
Fabián Pedregosa, Gaël Varoquaux, Alexandre Gramfort et al. · arXiv (Cornell University) · 2012 · 63.7K citations · Full text
LIBLINEAR: A Library for Large Linear Classification
Rong-En Fan, Kai‐Wei Chang, Cho‐Jui Hsieh et al. · 2008 · 6.6K citations
Ron S. Dembo, Stanley C. Eisenstat, Trond Steihaug · SIAM Journal on Numerical Analysis · 1982 · 1.6K citations
A nonsmooth version of Newton's method
Liqun Qi, Jie Sun · Mathematical Programming · 1993 · 1.5K citations