Project Details
Projekt
Frank-Wolfe Algorithms: State-Of-The-Art Convergence Rates with Biomedical Prospects
Applicant
Elias Wirth
Subject Area
Mathematics
Term
since 2024
Project identifier
Deutsche Forschungsgemeinschaft (DFG) - Project number 547711623
A central challenge in data science lies in solving constrained convex optimization problems, an area where the projection-free Frank-Wolfe algorithm (FW) (Frank and Wolfe, 1956) stands out. This proposal outlines projects designed to: a) develop new insights in convex geometry, b) derive state-of-the-art convergence rates for FW variants in large-scale environments, and c) impact the broader society by speeding up machine learning pipelines in biomedicine. In FW, the step-size determines how much the current iterate gets updated in each iteration. FW with open-loop step-sizes (OLSS) research (Li et al., 2021; Bach, 2021) typically employs ηt = ℓ/(t+ℓ) with ℓ = 2, despite the potential for faster convergence with larger ℓ (Wirth et al., 2023a). The first project introduces a new 'default' OLSS that outperforms the current standard in convergence rates. This innovation is poised to improve applications like kernel herding in biomedical research (Bach et al., 2012; Baskaran et al., 2022), enhance decision-making in economics through faster Nash equilibria computation (Barman, 2018; Combettes and Pokutta, 2023), and improve efficiency in physics simulations (Clarkson, 2010; Ravi et al., 2019; Hubbard, 1996; Montaut et al., 2022), such as collision detection in computer graphics and robotics (Schulman et al., 2014; Mirabel et al., 2016; Toussaint et al., 2018). The second project, building on numerical observations from Wirth et al. (2023b), establishes state-of-the-art rates of order O(t^−2) for FW with OLSS for the collaborative filtering problem. This massive improvement over the standard rates of order O(t^−1) (Jaggi, 2013) speeds up recommender system training, which will impact genomic research, healthcare, and streaming services (Troyanskaya et al., 2001; Tran et al., 2021; Koren, 2009). Developing the result requires a deeper understanding of FW in more complex feasible regions beyond typical polytopes or uniformly convex sets, a promising intellectual contribution to convex geometry. In large-scale settings, the ambient dimension is usually large. The third project uniquely establishes dimension-independent convergence rates for the away-step Frank-Wolfe algorithm (AFW) and related variants in Lacoste-Julien and Jaggi (2015); Tsuji et al. (2022), without the strong additional assumptions of prior work (Garber and Meshi, 2016; Bashiri and Zhang, 2017; Garber, 2020). The project also rectifies a key error in Garber and Meshi (2016, Lemma 2), clarifying misconceptions in the existing literature. Its broader impact includes speeding up compressed sensing (Jarret et al., 2022), crucial for medical imaging, astronomy, and wireless communication (Graff and Sidky, 2015; Bobin et al., 2008; Gao et al., 2018). Integration of the results into the FrankWolfe.jl software package developed by my group (Besançon et al., 2022) guarantees wide accessibility and impact on both academia and practice.
DFG Programme
WBP Fellowship
International Connection
USA
