Frank-Wolfe-Algorithmen: Modernste Konvergenzraten mit biomedizinischen Anwendungen

• Antragsteller: Elias Wirth
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung seit 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 547711623

Eine zentrale Herausforderung in Datenwissenschaft liegt in der Lösung von beschränkten konvexen Optimierungsproblemen, einem Bereich, in dem sich der projektionsfreie Frank-Wolfe Algorithmus (FW) (Frank und Wolfe, 1956) hervorhebt. Dieser Vorschlag zielt darauf ab, a) neue Einsichten in der konvexen Geometrie zu entwickeln, b) modernste Konvergenzraten für FW Varianten in hochdimensionalen Umgebungen zu beweisen und c) die breitere Gesellschaft positiv zu beeinflussen, indem maschinelle Lernpipelines in der Biomedizin beschleunigt werden. Im FW bestimmt die Schrittgröße, wie stark das aktuelle Iterat aktualisiert wird. Forschung über FW mit open-loop Schrittgrößen (OLSS) (Li et al., 2021; Bach, 2021) verwendet typischerweise ηt = ℓ/(t+ℓ) mit ℓ=2, trotz des Potenzials für schnellere Konvergenz mit größerem ℓ (Wirth et al., 2023a). Das erste Projekt führt eine neue 'standard'-OLSS ein, die schnellere Konvergenzraten erreicht als aktuelle Schrittgrößen. Dadurch wird Kernel-Herding in der biomedizinischen Forschung (Bach et al., 2012; Baskaran et al., 2022) verbessert, die Entscheidungsfindung in der Wirtschaft durch schnellere Nash-Gleichgewichtsberechnungen (Barman, 2018; Combettes und Pokutta, 2023) verbessert und die Effizienz in Physiksimulationen (Clarkson, 2010; Ravi et al., 2019; Hubbard, 1996; Montaut et al., 2022) erhöht, durch Kollisionserkennung in Computergrafik und Robotik (Schulman et al., 2014; Mirabel et al., 2016; Toussaint et al., 2018). Das zweite Projekt, basierend auf Beobachtungen von Wirth et al. (2023b), etabliert modernste Raten der Ordnung O(t^−2) für FW mit OLSS für kollaboratives Filtern. Diese massive Verbesserung gegenüber den O(t^−1) Raten (Jaggi, 2013) beschleunigt das Training von Empfehlungssystemen, was die genomische Forschung, das Gesundheitswesen und Streaming-Dienste (Troyanskaya et al., 2001; Tran et al., 2021; Koren, 2009) beeinflussen wird. Die Entwicklung des Ergebnisses erfordert ein tieferes Verständnis von FW in Regionen jenseits typischer Polytope oder gleichmäßig konvexen Mengen, ein vielversprechender intellektueller Beitrag zur konvexen Geometrie. Das dritte Projekt etabliert dimensionsunabhängige Konvergenzraten für den away-step Frank-Wolfe Algorithmus (AFW) und Varianten in Lacoste-Julien und Jaggi (2015); Tsuji et al. (2022), ohne die starken Zusatzannahmen früherer Arbeiten (Garber und Meshi, 2016; Bashiri und Zhang, 2017; Garber, 2020). Das Projekt korrigiert auch einen Fehler in Garber und Meshi (2016, Lemma 2), wodurch Missverständnisse in der bestehenden Literatur geklärt werden. Das Projekt beschleunigt komprimiertes Sensing (Jarret et al., 2022), was für die medizinische Bildgebung, Astronomie und drahtlose Kommunikation (Graff und Sidky, 2015; Bobin et al., 2008; Gao et al., 2018) entscheidend ist. Integration der Ergebnisse in das von meiner Gruppe entwickelte Softwarepaket FrankWolfe.jl (Besançon et al., 2022) garantiert breiten Zugang sowohl in der Akademie als auch in der Praxis.

• DFG-Verfahren: WBP Stipendium
• Internationaler Bezug: USA
• Gastgeber: Professor Dr. Javier Peña, Ph.D.