FLORE (FLOrence REsearch) è il repository istituzionale ad accesso pieno e aperto dell'Università degli Studi di Firenze.
Raccoglie, documenta e conserva le informazioni sulla produzione scientifica dell'Università e costituisce l'Anagrafe della ricerca dell'Ateneo.
EnglishTruncated 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.
| Titolo: | A Study on Truncated Newton Methods for Linear Classification |
| Autori di Ateneo: | |
| Autori: | leonardo galli; chih-jen lin |
| Anno di registrazione: | 2021 |
| Rivista: | |
| Volume: | - |
| Pagina iniziale: | 1 |
| Pagina finale: | 14 |
| Abstract: | 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. |
| Handle: | http://hdl.handle.net/2158/1221395 |
| Codice ONU Sustainable Development Goals (SDG): | Goal 9: Industry, Innovation, and Infrastructure |
| Appare nelle tipologie: | 1a - Articolo su rivista |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| galli21a.pdf | Articolo principale | Versione finale referata | DRM non definito | Administrator Richiedi una copia |
| tncg_supplement.pdf | Supplementary Materials | Altro | Open Access | Accesso pubblicoVisualizza/Apri |
Copyright © 2021