Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets
Authors: Thomas Kerdreux, Lewis Liu, Simon Lacoste-Julien, Damien Scieur
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this work, we introduce new structural assumptions on the problem (such as the directional smoothness) and derive an affine invariant, normindependent analysis of Frank-Wolfe. We show that our rates are better than any other known convergence rates of FW in this setting. ... We conclude in Section 8 with numerical experiments. |
| Researcher Affiliation | Collaboration | 1Zuse Institute, Berlin 2D epartement d informatique et de recherche op erationnelle (DIRO), Universit e de Montr eal 3Mila, Montr eal 4Samsung SAIT AI Lab, Montr eal 5Canada CIFAR AI Chair. |
| Pseudocode | Yes | Algorithm 1 Frank-Wolfe Algorithm Input: x0 C. ... Algorithm 2 Affine invariant backtracking Input: FW vertex vk, point xk, directional smoothness estimate Lk, function f. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code for the described methodology, nor does it provide a link to a code repository. |
| Open Datasets | Yes | Specifically, we compare our affine invariant backtracking method in Algorithm 2 against the naive FW Algorithm 1 with step size 1/L (Demyanov & Rubinov, 1970) and back-tracking FW (Pedregosa et al., 2020) on the Madelon dataset (Guyon et al., 2007). |
| Dataset Splits | No | No specific percentages or counts for training, validation, or test splits were provided. The paper only mentions using the Madelon dataset. |
| Hardware Specification | No | No specific hardware details (e.g., GPU/CPU models, memory amounts, or detailed computer specifications) used for running experiments were provided. |
| Software Dependencies | No | No specific ancillary software details (e.g., library or solver names with version numbers) were provided. |
| Experiment Setup | Yes | Here we adopt the ℓ2-ball, defined as C = {x : x 2 R}, R > 0. Specifically, we compare our affine invariant backtracking method in Algorithm 2 against the naive FW Algorithm 1 with step size 1/L (Demyanov & Rubinov, 1970) and back-tracking FW (Pedregosa et al., 2020) on the Madelon dataset (Guyon et al., 2007). The results are shown in Figure 2. In detail, we set R such that the unconstrained optimum x satisfies x 2 = 1.1R, and the initial iterate x0 = 0. |