Secant Line Search for Frank-Wolfe Algorithms

We thank the reviewer for their feedback and questions.

The paper lacks a detailed complexity analysis for the proposed methods.

We provide an analysis of the local superlinear convergence rate of the secant method and of its global convergence under suitable assumptions, which is an improvement over what can be stated in the unconstrained case, specifically relying on the setup of Frank-Wolfe algorithms in which the line search happens on a bounded line segment. This superlinear convergence guarantees that in practice, we perform an almost exact line search while remaining highly tractable, as can be noticed from the low number of secant iterations. We must highlight that our results are agnostic to the optimization problem, the precise convergence rate will depend on local properties of the function.

In Lemma 2.1, the convergence guarantees rely on assumptions that seem quite strict, which may limit the broader applicability of the method.

The assumption might not be as strict as they seem; see Theorem 3.1. It suffices that the problem is strictly convex.

The analysis in Section 2.2 raises some concerns, as the symbol "≈" is used frequently. This could suggest a lack of rigor in the analysis.

We use "≈" to ignore lower order terms for the sake of clarity. Specifically the contents of section 2.2 are provided for intuition, since it is folklore and the proof of this specific case is known and can be found, e.g., in Grinshpan (2024).

To sum up, our main contributions are (A) we perform comprehensive experiments on the secant line search in a wide variety of benchmarks and against a wide variety of alternative step-sizes showing its advantages over previous approaches and (B) we observed that the structure of the FW algorithm is such that under mild assumptions it is always guaranteed to converge from any initialization (and the line search always occurs over a compact segment), which justifies that our method works in practice.

We thank the reviewer for their feedback and questions on the paper.

We agree that using root finding methods for line search is not new and in fact many line search methods, such as e.g., bisection line search is of that type. However, (Quasi-)Newton methods, secant methods, etc are traditionally not used as line search methods because in general there is no guarantee that they are globally converging. Put differently, if they converge they are fast but they may not converge at all. This is different here where we actually proved that in the setting of FW methods, where the step size is guaranteed to be confined between 0 and 1 (or 0 and a weight smaller than one for some FW variants), we can guarantee global convergence under mild assumptions that are often satisfied in contexts where FW methods are applied: we only require strict convexity.

In Lemma 2.1, we do not show convergence by just saying that this property holds: $0 < S(x,y) < 1$. As it can be read at the end of our proof, we have instead that by $x_{n+1} = S(x_n, x_{n-1})$ and by that property then $x_n -x_{n+1}$ converges to $0$. And because it is by definition $\phi(x_n) / \Delta(x_n, x_{n-1}) = x_n - x_{n+1} \to 0$ and $\Delta(x_n, x_{n-1})$ is upper bounded by a constant, it can only be that $\phi(x_n) \to 0$ and that can only be if $x_n \to a$, as specified in our proof.

Question 3: We present each problem class in more detail, including the type of constraint set in the appendix due to space constraint. Our benchmark problems contain standard problems from the Frank-Wolfe literature, e.g. similar to some classes studied in Pedregosa et al 2018, Dvurechensky et al 2023, Carderera et al 2021 which all introduce new step-size strategies for FW. We were also careful to include different function classes (self-concordant, quadratics) and conditioning to be able to showcase the performance of SLS in a wide array of applications. Furthermore, our experiments assess multiple criteria for the proposed step size:

1. Is it making FW converge fast, as counted by the number of iterations? This question will typically have the same answer for all line searches given infinite precision (e.g. using arbitrary-size floating point numbers or rational arithmetic). However, when using 64-bit floating points, we showed that great differences can occur in behavior because of floating-point error accumulation, see Figure 5 in the appendix, in which golden ratio, another line search, quickly stalls in terms of FW gap precisely because of numerics. In contrast, we empirically observe the numerical robustness of SLS, even in ill-conditioned problems (when the Lipschitz constant is very high).
2. Is the method also effective in time, meaning that the good performance of the step size is not outweighed by the computational cost of the inner iterations evaluating the gradient at the candidate point?

We answer both questions positively thanks to the computational experiments, evaluating the methods against iterations and time. We also compute the number of inner line search iterations throughout the Frank-Wolfe runs, empirically showing this remains consistently low throughout experiments. This ensures that SLS is also a suitable step size for problems where the gradient is particularly costly to evaluate (relative to the LMO).

Q1: SLS shows superior performance on all problems with a quadratic objective function. It, in particular, shows stable performance even for ill-conditioned problems. Additionally, we also see a good performance on generalized self concordant objectives like the A-Optimal and D-Optimal Design problems and the Portfolio problem with log revenue.

Q2: Frank-Wolfe is stopped if we reach either the dual gap of 1e-7 or a time of 1 hour (we will state this explicitly in the paper). The different strategies lead to different trajectories of Frank-Wolfe hence the different end points. Since there is a time limit, the dual gap value is of interest for the unsolved instances as we can compare how much progress each method obtained within the time. In the table, the geometric mean of the dual gap is only computed for the unsolved instances.

The tolerance in the line search corresponds to one on the univariate derivative, which directly leads to a bounded function error ($\gamma \in [0,1]$). Others, e.g. Pedregosa et al 2020, Bomze et al 2019 have studied approximate LS for FW. We will highlight these references in the revised version.

To sum up, our main contributions are (A) we perform comprehensive experiments on the secant line search in a wide variety of benchmarks and against a wide variety of alternative step-sizes showing its advantages over previous approaches and (B) we observed that the structure of the FW algorithm is such that under mild assumptions it is always guaranteed to converge from any initialization (and the line search always occurs over a compact segment), which justifies that our method works in practice.

We thank the reviewer for their feedback and questions.

Limited theoretical novelty. The convergence guarantee is derived by directly combining the existing convergence results of the Frank-Wolfe method and the secant method.

The theoretical novelty is indeed not the central element here, however in contrast to gradient descent methods where there it is hard (if not next to impossible) to make the secant method work consistently as a line search, in the context of Frank-Wolfe the Secant Line Search actually becomes a valid line search method. So the contribution here is really showing that in the settings were FW methods are usually applied we have a global theoretical guarantee that the secant method works.

Evidence of claims (more convincing if references about the convergence of the Frank-Wolfe method were added in Theorem 3.1). (the linear convergence mentioned in lines 287–288 and the superlinear convergence in Remark 3.2 are not supported by proofs or references)

We did not include an in-depth discussion about the local convergence of the secant method because it is not the main focus of the paper and has been established elsewhere. In fact, we cited Díez 2003 who provided an in-depth analysis and provided the convergence rate inducing equation $\lambda^m + \lambda^{m-1} = 1$, where m is the multiplicity of the root; $\lambda$ is then the rate we can expect. What we did provide though is a proof for the global convergence in common FW settings, which is the key crux for the secant method as it is not a globally convergent method in general. This way we can ensure that the secant method can be used as line search method. We will restate the Theorem etc to make this more clear.

Self concordance

The self-concordant property is defined in (3.5), we will rephrase to make this more clear and will reference this in the introduction.

To sum up, our main contributions are (A) we perform comprehensive experiments on the secant line search in a wide variety of benchmarks and against a wide variety of alternative step-sizes showing its advantages over previous approaches and (B) we observed that the structure of the FW algorithm is such that under mild assumptions it is always guaranteed to converge from any initialization (and the line search always occurs over a compact segment), which justifies that our method works in practice.

Line 159, left column: $S(x,y) = S(y,x)$ is not true.

$S(x, y) = S(y, x)$ holds. Writing the definition and multiplying by $\Delta(x, y) = \Delta(y, x)$ and reorganizing, we obtain that the expression is equivalent to $(x-y)\Delta(x,y) = \phi(x) - \phi(y)$, which clearly holds true by definition of $\Delta(x, y)$

Proof of lemma 2.1 is dubious: by what monotonicity can one claim that $\frac{\Delta(x,a)}{\Delta(x,y)} > 0$? Also, the argument for $<1$ part is also shaky.

The monotonicity of $\phi$, as assumed in the statement, trivially implies that $\Delta(z, w) > 0$, for all $z, w \in \mathcal{U}$ as by definition monotonicity means $\phi(z) - \phi(w) > 0$ if $z - w > 0$. Our proof is correct, see also the response to Reviewer bzSe.