- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper proposes damped Newton Frank–Wolfe methods for minimizing twice differentiable convex functions with positive definite Hessians over general compact convex sets, accessed only through a linear minimization oracle. The methods approximately solve damped constrained Newton subproblems via FW or away-step FW inner loops, using a residual backtracking scheme with a root Newton stepsize as a safe reference and a switching rule that eventually takes full steps. Under Hölder continuity of the th derivative, the authors prove global linear convergence and local convergence with Q-order at least () or quadratic (), removing the polytope, strict complementarity, and primal-gap-bound requirements of SOCGS. Experiments on matrix sensing and ridge-regularized logistic regression show robust and often best-in-class performance.
Critical strengths
- Highly motivated problem. The paper clearly identifies the gap in existing second-order FW methods: NFW only guarantees a local linear rate, while SOCGS requires polyhedrality, strict complementarity, and a lower bound on the primal gap to set inner accuracy. The central question—whether a projection-free Newton method can combine global linear and local quadratic convergence over general compact convex sets—is natural and well posed, and the paper answers it affirmatively.
- Clear results and presentation. The contributions are precisely stated, and Tables 1 and 2 give a transparent comparison of outer-iteration and total LMO complexities against FW, CGS, NFW, and SOCGS. The convergence guarantees (Theorems 3.6, 3.8, 3.9) are explicit, with constants and switching criteria written out, and the experiments consistently support the theory across both polytope and non-polytope constraint sets.
Critical weaknesses
- The local total LMO complexity of Algorithm 1 over general convex sets, or , is substantially worse than the polytope case and appears conservative; a brief discussion of whether this is tight or an artifact of the analysis would help.
Questions for authors
- Are the established convergence rates tight? Specifically: (a) for the global R-linear rate in Theorem 3.6, is there a matching lower bound (e.g., a worst-case instance over a compact convex set) showing that the contraction factor's dependence on , , and cannot be improved, or might a sharper potential function yield a faster rate? (b) For the local rates, the Q-order for matches what one expects from the Hölder continuity of the Hessian in the unconstrained setting (Hanzely et al., 2026), but is it known to be optimal in the constrained LMO-based setting, where the inner stopping rule (3.10) introduces an additional error of order ? Could a lower bound or an example demonstrate that the exponents in (3.14) and (3.18) are not improvable?
3 comments
Dear Reviewer ngra,
Thank you again for your time and valuable comments. Your feedback has been very helpful in improving our manuscript.
We have carefully considered your feedback and revised the manuscript to address your concerns, as detailed in our responses. In particular, we have added an example showing the sharpness of the local convergence orders under our stopping rule and clarified the limitations of the total LMO bounds.
Would you mind reviewing our responses and revised manuscript and letting us know if you have any remaining questions or concerns? We would be happy to provide further clarification.
Best regards,
The Authors
I appreciate and am satisfied with the rebuttal. I will keep my positive score!
Thank you for these helpful comments.
(W1) The local total LMO complexity of Algorithm 1 over general convex sets, O(ϵ−2(1+ν)) or O(ϵ−4), is substantially worse than the polytope case and appears conservative; a brief discussion of whether this is tight or an artifact of the analysis would help.
When the global stepsize and inner accuracy rules are used throughout, our total LMO bound is O(ϵ−1logϵ−1), differing from the O(ϵ−1) bound for standard FW only by a logarithmic factor. After switching to the local rules, sufficient inner accuracy for fast local convergence yields total LMO bounds of O(ϵ−2(1+ν)) for p=2 and O(ϵ−4) for p=3. These are conservative bounds and are not optimal for the problem class in terms of total LMO calls (Section D.4, Table 2). Whether these local bounds are tight for Algorithm 1 with the current inner stopping rule remains open, and we have listed this as future work in Section 5.
(Q1) Are the established convergence rates tight? Specifically: (a) for the global R-linear rate in Theorem 3.6, is there a matching lower bound (e.g., a worst-case instance over a compact convex set) showing that the contraction factor's dependence on μ/L, ρ, and Bq cannot be improved, or might a sharper potential function yield a faster rate? (b) For the local rates, the Q-order 1+ν for p=2 matches what one expects from the Hölder continuity of the Hessian in the unconstrained setting (Hanzely et al., 2026), but is it known to be optimal in the constrained LMO-based setting, where the inner stopping rule (3.10) introduces an additional error of order $ |\widehat{x}_{k+1}-x_k|^{a/2} $? Could a lower bound or an example demonstrate that the exponents in (3.14) and (3.18) are not improvable?
(a) Global linear convergence. The contraction factor's dependence on μ/L, ρ, and Bq may be improved through a sharper potential function or analysis. Section 5 now identifies matching lower bounds and sharper convergence guarantees as directions for future work.
(b) Local convergence orders. We have added a quadratic example over a half-disk that addresses both the local orders and the inner-error exponent (Section D.4, Proposition D.2). In this example, FW stops with a nonzero inner error, and matching upper and lower bounds hold with exponent a/2 for the inner error, iterate error, and primal gap. Setting a=2(1+ν) or a=4 shows that the local exponents 1+ν or 2 and the inner-error exponent a/2 are simultaneously tight in the worst case. The constants C2 and C3 in the bounds may be improved by a sharper analysis.