Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

logo del sistema bibliotecario dell'ateneo di padova

Zeffiro, Damiano (2019) Convergence analysis and active set complexity for some FW variants. [Magistrali biennali]

Full text disponibile come:

[img]
Preview
PDF
1429Kb

Abstract

*The FW method, first introduced in 1956 by Marguerite Frank and Philip Wolfe, has recently been the subject of renewed interest thanks to its many applications in machine learning. In this thesis we prove convergence and active set identification properties for some popular variations of this method. While the classic FW method has a slow O(1/t)** convergence rate even for strongly convex objectives, i* *t has recently been proved that some FW variants on polytopes have faster convergence rates assuming an Holderian error bound condition which generalizes strong convexity. In this thesis we prove that for one of these variants this acceleration of the convergence rate can be extended also to a class of non polyhedral sets, including strictly convex smooth convex sets whose boundary satisfies some positive curvature property. We also prove that under suitable assumptions some FW variants on polytopes identify the active set in finite time. This result extends an analogous well known result proved for projected gradient methods. To prove our result however we use a fundamentally different technique, relating the identification property to active set identification strategies with Lagrange multipliers. Other minor results of the thesis include a proof of finite time active set identification for the pairwise step FW variant, a new proof for the projected gradient finite time active set identification property with explicit estimates, and a generalization of some of the convergence rate results to reflexive Banach spaces. *

Item Type:Magistrali biennali
Uncontrolled Keywords:first order methods, FW variants, active set identitification
Subjects:Area 01 - Scienze matematiche e informatiche > MAT/09 Ricerca operativa
Codice ID:62635
Relatore:Rinaldi, Francesco
Data della tesi:05 July 2019
Biblioteca:Polo di Scienze > Biblioteca di Matematica
Tipo di fruizione per il documento:on-line per i full-text
Tesi sperimentale (Si) o compilativa (No)?:Yes

Solo per lo Staff dell Archivio: Modifica questo record