Scalable Frank-Wolfe on Generalized Self-concordant Functions via Simple Steps

2021/05/28 by Alejandro Carderera, Carderera, Alejandro, Mathieu Besançon +3 · 1 citation
Computer Science · Engineering · #Advancements in Photolithography Techniques #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2105.13913

openalex publication_date 2021/05/28 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28

Abstract

Generalized self-concordance is a key property present in the objective function of many important learning problems. We establish the convergence rate of a simple Frank-Wolfe variant that uses the open-loop step size strategy γ_t = 2/(t+2), obtaining a O(1/t) convergence rate for this class of functions in terms of primal gap and Frank-Wolfe gap, where t is the iteration count. This avoids the use of second-order information or the need to estimate local smoothness parameters of previous work. We also show improved convergence rates for various common cases, e.g., when the feasible region under consideration is uniformly convex or polyhedral.

Cited by

• Efficient Network Reconfiguration by Randomized Switching

Related

• Generalized Self-Concordant Analysis of Frank-Wolfe algorithms
• Self-Concordant Analysis of Frank-Wolfe Algorithms
• Beyond Short Steps in Frank-Wolfe Algorithms
• Fast convergence of Frank-Wolfe algorithms on polytopes
• Convergence rates of Newton's method for strongly self-concordant minimization