acceptodds
Under review as a conference paper at ICLR 2027

Beyond Polytopes: Damped Newton Frank–Wolfe Methods over Compact Convex Sets

Abstract

We study convex optimization over compact convex sets for twice differentiable objective functions with positive definite Hessians, assuming access to the feasible set through a linear minimization oracle. Existing second-order Frank–Wolfe methods either provide only a local linear rate over general convex sets or achieve global linear and local quadratic convergence only over polytopes. We propose *damped Newton Frank–Wolfe methods* that approximately solve constrained damped Newton subproblems using Frank–Wolfe or away-step Frank–Wolfe inner iterations. We develop residual backtracking, using a root Newton stepsize as a safe reference, together with a switching rule that eventually takes full steps. Under H\"older smoothness assumptions for th derivatives, we establish global linear convergence and local convergence with Q-order at least () and local quadratic convergence (). Experiments on matrix sensing and ridge-regularized logistic regression show that the residual-backtracking variant is consistently robust and often achieves the best performance among the tested first- and second-order baselines.

Primary area:
optimization
Keywords:
Constrained optimization, Second-order method, Projection-free method

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_ngraOpenReview ↗
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 ppth derivative, the authors prove global linear convergence and local convergence with Q-order at least 1+ν1+\nu (p=2p=2) or quadratic (p=3p=3), 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, O(ϵ−2(1+ν))O(\epsilon^{-2(1+\nu)}) or O(ϵ−4)O(\epsilon^{-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.
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 μ/L\mu/L, ρ\rho, and BqB_q cannot be improved, or might a sharper potential function yield a faster rate? (b) For the local rates, the Q-order 1+ν1+\nu for p=2p=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 ∥x^k+1−xk∥a/2\|\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?
3 comments

Thank you for these helpful comments.

(W1) The local total LMO complexity of Algorithm 1 over general convex sets, O(ϵ−2(1+ν))O(\epsilon^{-2(1+\nu)}) or O(ϵ−4)O(\epsilon^{-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)O(\epsilon^{-1}\log\epsilon^{-1}), differing from the O(ϵ−1)O(\epsilon^{-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+ν))O(\epsilon^{-2(1+\nu)}) for p=2p=2 and O(ϵ−4)O(\epsilon^{-4}) for p=3p=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\mu/L, ρ\rho, and BqB_q cannot be improved, or might a sharper potential function yield a faster rate? (b) For the local rates, the Q-order 1+ν1+\nu for p=2p=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\mu/L, ρ\rho, and BqB_q 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/2a/2 for the inner error, iterate error, and primal gap. Setting a=2(1+ν)a=2(1+\nu) or a=4a=4 shows that the local exponents 1+ν1+\nu or 22 and the inner-error exponent a/2a/2 are simultaneously tight in the worst case. The constants C2C_2 and C3C_3 in the bounds may be improved by a sharper analysis.

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!

Reviewer_VazqOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies constrained convex optimization using Newton steps whose quadratic subproblems are solved approximately by Frank–Wolfe. The authors introduce a damping strategy, a backtracking procedure, and stopping rules for the inner iterations. Near the solution, the method switches to full Newton steps.

Under the stated smoothness and positive-definiteness assumptions, the authors prove global linear convergence of the objective gap and local superlinear or quadratic convergence of the iterates and objective gap over general compact convex sets. They evaluate the methods on synthetic matrix sensing and constrained ridge-regularized logistic regression, comparing them with several first- and second-order methods.

Critical strengths
  • Broader convergence guarantees.
    The paper combines global linear and local superlinear or quadratic convergence over general compact convex sets, without requiring polytope geometry or strict complementarity.

  • Explicit algorithmic rules.
    The authors provide computable criteria for choosing the damping, controlling the accuracy of the inner solves, and switching to full Newton steps.

  • Source code.
    Source code is provided.

Critical weaknesses
  • Limited novelty.
    The outer Newton / inner Frank–Wolfe architecture is established, and NFW already uses damping and a switch to full steps. SOCGS already combines global linear and local quadratic convergence on polytopes [1, 2]. The contribution is a particular backtracking and stopping framework with broader guarantees, rather than a new algorithmic principle.

  • Outer rates do not establish computational gains.
    The fast convergence rates count outer iterations, each requiring an increasingly accurate inner solve. For general compact sets, the paper’s conservative local LMO bound is O(ε−4)O(\varepsilon^{-4}) in the quadratic-rate cases. The headline rate therefore does not establish better total oracle complexity or running time.
    Thus, the theoretical results do not establish improved total LMO complexity in this setting, and the practical benefit requires convincing experimental evidence.

  • Matrix sensing: exceptionally narrow evaluation and missing established alternatives.
    The experiments consist of three controlled, noiseless instances at a fixed matrix size of 750×750750 \times 750, planted rank one, condition number 10001000, and seed. The construction also gives a specially structured Hessian consisting of the identity plus a rank-16 operator correction. There is no evaluation across sizes, ranks, conditioning levels, or independent realizations. Earlier work on related low-rank matrix recovery already provided substantially broader computational evidence: Jaggi and Sulovský evaluated a Frank–Wolfe-based method on MovieLens10M and Netflix, reporting numerical runtimes and comparisons with competing solvers; Mishra et al. evaluated rank-adaptive factorized second-order methods on 50,000×50,00050{,}000 \times 50{,}000 matrix-completion problems [5, 6]. These formulations differ from the present sensing problem, but establish relevant computational alternatives and a longstanding precedent for scalability studies. The current evaluation neither demonstrates scalability nor establishes an advantage over established low-rank factorized methods.

  • Logistic regression: limited scale relative to established practice.
    The five datasets yield optimization problems with only 54–300 variables, and the proposed methods generally finish on a subsecond scale. Although some datasets contain many observations, this provides very limited evidence of scalability and efficiency. Substantially higher-dimensional logistic problems were already solved efficiently fifteen years ago: Yu et al. used the larger RCV1 test split as training data, with 677,399 examples and 47,236 features, reporting 3.56 seconds to reach 1% relative objective error on a 2.0 GHz Xeon [3]. The present paper does not compare against suitable constraint-compatible Newton or quasi-Newton alternatives, including established projected quasi-Newton methods [4]. Its restricted benchmarks and missing comparisons leave the claimed practical advance insufficiently supported.

  • Unclear application motivation for combining an ℓ2\ell_2 constraint with ridge regularization.
    The logistic regression examples over the ℓ2\ell_2 ball also include an ℓ2\ell_2 penalty. At the optimum, the constraint multiplier can be absorbed into an appropriately adjusted ridge coefficient. This does not permit dropping the constraint while keeping the coefficient fixed, but it raises a legitimate question about the application need for this formulation. The paper does not explain why imposing both is a compelling benchmark beyond providing a strongly convex objective over a compact nonpolyhedral set.

  • Insufficient numerical reporting.
    Runtime curves are provided, but they are difficult to read precisely, and no tables report runtime and oracle work at matched accuracies. The full damping sequences, backtracking counts, and exact outer-iteration totals are also missing. Table 3 counts outer iterations affected by the inner cap; it does not provide these measurements. (Yes, the appendix acknowledges that accepting capped solves falls outside the convergence analysis.)

  • Weak demonstration of the Newton machinery.
    For the quadratic matrix objective, the undamped Newton model equals the original objective. Section 4.1 states that RBNFW (local2) and RBNFW (local3) switch to full steps, αk=1\alpha_k=1, by k=2k=2 in the alignment-0.80.8 case. Subsequent inner iterations therefore perform ordinary Frank–Wolfe on the original objective, grouped into outer iterations with additional stopping checks. The initial damped phase can affect the trajectory, but the experiments do not separate its benefit from the subsequent FW work. This limits what the matrix experiment demonstrates about Newton model updates and damping.

References

[1] Deyi Liu, Volkan Cevher, and Quoc Tran-Dinh. “A Newton Frank–Wolfe Method for Constrained Self-Concordant Minimization.” Journal of Global Optimization, 83:273–299, 2022.

[2] Alejandro Carderera and Sebastian Pokutta. “Second-Order Conditional Gradient Sliding.” arXiv preprint arXiv:2002.08907, 2020, revised 2025.

[3] Hsiang-Fu Yu, Fang-Lan Huang, and Chih-Jen Lin. “Dual Coordinate Descent Methods for Logistic Regression and Maximum Entropy Models.” Machine Learning, 85:41–75, 2011.

[4] Mark Schmidt, Ewout van den Berg, Michael P. Friedlander, and Kevin Murphy. “Optimizing Costly Functions with Simple Constraints: A Limited-Memory Projected Quasi-Newton Algorithm.” Proceedings of AISTATS, PMLR 5:456–463, 2009.

[5] Martin Jaggi and Marek Sulovský. “A Simple Algorithm for Nuclear Norm Regularized Problems.” Proceedings of ICML, pp. 471–478, 2010.

[6] Bamdev Mishra, Gilles Meyer, Francis Bach, and Rodolphe Sepulchre. “Low-Rank Optimization with Trace Norm Penalty.” SIAM Journal on Optimization, 23(4):2124–2149, 2013.

Questions for authors

I have no additional questions beyond the weaknesses discussed above. The authors are welcome to comment on these concerns or correct any factual misunderstandings. My recommendation rests mainly on the substantial shortcomings of the experimental evaluation that is clearly below the ICLR bar. Addressing these concerns would require a substantially broader and stronger experimental study.

4 comments

Thank you for your careful review.

(W1) Limited novelty...

Newton--FW frameworks and switching to full steps appear in prior work. We clarified our contribution in the Introduction: local quadratic convergence over general compact convex sets without polytope geometry or strict complementarity, using a damped Newton model, residual backtracking, inner stopping criteria, and a switch to full steps. Our subproblems can use FW or AFW, while SOCGS is restricted to AFW.

(W2) Outer rates do not establish computational gains...

Fast outer convergence does not imply improved total LMO complexity or runtime. With the global rules, our bound is O(ϵ−1log⁡ϵ−1)O(\epsilon^{-1}\log\epsilon^{-1}), only a logarithmic factor above standard FW. See our response to Reviewer ngra (W1) for the local bounds and the discussion of their conservativeness and tightness under the current inner stopping rule (Section D.4 and Future Work). Table 7 reports matched-accuracy costs on NEWS20 (see W6 below).

(W3) Matrix sensing: exceptionally narrow evaluation and missing established alternatives...

Tables 3--6 add all eight settings n∈{750,1500}n\in\{750,1500\}, rank X⋆∈{1,5}X_\star\in\{1,5\}, Λ∈{103,104}\Lambda\in\{10^3,10^4\}, with five instances each. We report means and sample standard deviations of outer iterations, LMO calls, and final primal gaps within 10 seconds. RBNFW (global) has the smallest mean gap throughout, including ties. Figures 1, 6, 7 now include SOCGS and PQN. We added MovieLens 100K (n=1650n=1650) and random (n=1000n=1000) log-determinant problems (Figures 2, 19; Section E.3).

On MovieLens, a rank-adaptive Riemannian trust-region method (RA-Q-RTR) adapts the fixed-rank optimization and rank-one updates of Mishra et al. (2013) to the PSD trace constraint (Figure 2, Section E.3). Costs at the first accepted iterate whose objective value was within 10−710^{-7} of the numerical reference are:

MethodTime (s)Updates
RBNFW(global)8.9194
RBNFW(local2)8.8324
RBNFW(local3)5.9783
RA-Q-RTR12.2088

(W4) Logistic regression: limited scale... missing comparisons...

Beyond covtype.binary (581,012 samples), we added ellipsoid-constrained NEWS20 logistic regression (2048 samples, 1,355,191 variables) and PQN. Figure 3 and Figures 11--15 cover three subsamples. Mean times to reach primal gap 10−910^{-9} are 0.550 seconds for RBNFW (global), 0.864 for NFW, 0.996 for SOCGS, and 10.812 for PQN (Table 7).

(W5) Unclear application motivation for combining an ℓ2\ell_2 constraint with ridge regularization...

The ball multiplier can be absorbed into an effective ridge coefficient at the optimum. Here the ridge term ensures strong convexity, while the ball constraint explicitly bounds the solution norm. This combination is also used in differentially private learning: Su et al. (2024, Section 6, Eq. (6)) minimize ridge-regularized logistic loss over a ball and test on real data, including a9a and w7a. We added this reference in Section 4.2.

(W6) Insufficient numerical reporting... runtime and oracle work at matched accuracies...

Table 7 reports means and sample standard deviations of time, outer iterations, LMO calls, gradient/Hessian evaluations, and RBT trials needed to reach primal gap 10−910^{-9} on NEWS20, excluding common diagnostic LMO calls. Section E.2 gives the full damping sequences: αk=(1+8−k/32)−1\alpha_k=(1+8^{-k}/32)^{-1} for global and local3; (α0,α1,α2)=(4/5,32/33,256/257)(\alpha_0,\alpha_1,\alpha_2)=(4/5,32/33,256/257) for local2.

(W7) Weak demonstration of the Newton machinery...

The existing logistic regression and added log-determinant experiments have nonquadratic objectives, so their undamped Newton models differ from the objectives (Sections 4.1, E.3).

For the quadratic problem, inner iterations after switching coincide with standard FW, as clarified in Section 4.1.

On the Figure 1 problem with the same initial point, we compared local3 with a variant using αk=1\alpha_k=1 and the local inner stopping rule from the first iteration. Both reached comparable gaps after two updates; LMO calls below are cumulative through the second update.

MethodGap after 1 updateGap after 2 updatesLMO calls
RBNFW(local3)1.83e-31.89e-101,010
Full step (local3, K=0)8.05e-44.46e-101,011

(Q1) ... a substantially broader and stronger experimental study.

We addressed each point and substantially expanded the study by varying settings, reporting variability, adding high-dimensional data and PQN (Tables 3--7 and NEWS20 figures), and adding MovieLens/random nonquadratic problems and RA-Q-RTR (W3 above); matched-accuracy costs appear in W6. We hope these additions resolve your concerns and that you will reconsider your assessment and recommendation in light of the revised manuscript.

Dear Reviewer Vazq,

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 expanded the experimental study, added further baselines, and reported runtime and oracle costs at matched accuracy.

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

Recommendation: Clear reject (unchanged). I thank the authors for includeing more experiments into their revision. However, my major concern has still not been addressed: it does not establish scalability or an advantage over the most relevant solvers. In short: the number of optimization variables is still at most 2,048. This is still very small for standard ML problems. (It seems the authors try to avoid any larger instances, even when suggested to run reasonably-sizeed instances.) Here are the details.

  • Quadratic matrix sensing. The expanded sweep still uses fully observed, noiseless instances. The unconstrained least-squares solution already satisfies the PSD and trace constraints, and the identity-plus-rank-16 Hessian permits a direct solve in one structured Newton step. The paper does not time that solve.
  • Log-determinant minimization. MovieLens supplies a Gram matrix for a constructed objective; the experiment does not fit or predict ratings. The MovieLens and Gaussian instances reduce exactly to 1,650 and 1,000 scalar variables, respectively. The authors use the eigenbasis reduction to compute reference values but do not report its runtime as a baseline, including the eigendecomposition.
  • Logistic regression. Five datasets have 54–300 variables. The only larger case, the newly added NEWS20, uses 2,048 of 19,996 examples per run, reducing the effective dimension from 1,355,191 coordinates to at most 2,048. The subsample size is unexplained (why didn't the authors use the whole dataset which is still small?), and projected quasi-Newton is tested only on those subsamples. The revision does not include the larger RCV1 test split cited in my original review (with 677,399 examples and 47,236 features, reporting 3.56 seconds to reach 1% relative objective error on a 2.0 GHz Xeon [3]) or a comparison there against established logistic-regression solvers.

Given the narrow theoretical advance, the missing direct-solver comparisons and the lack of evidence at larger effective dimensions leave my recommendation unchanged.

Thank you for your insightful comments.

  • Large-scale logistic regression. We added experiments on the full NEWS20 dataset (19,996 examples, 1,355,191 features) and the RCV1 test split you requested (677,399 examples, 47,236 features). Their design matrices have rank at least 18,648 and 20,086, respectively. In each dataset, that many rows introduce a feature absent from all preceding rows.

    Figures 3 and 4 include projected quasi-Newton (PQN) and the dual coordinate descent method (DCD) of Yu et al. [3]. The DCD convergence rate for unconstrained logistic regression does not cover the multiplier search we added for the ellipsoid. On full NEWS20 at the reported radius, RBNFW reached a primal gap of 10−910^{-9} faster than every tested baseline. On RCV1, RBNFW was competitive with DCD at 1% relative objective error. At a primal gap of 10−1010^{-10}, it was comparable to FW and faster than DCD and the projection-based methods.

  • Matrix sensing. You are right that one Newton step solves the original noiseless matrix-sensing problem. Figures 1, 6, and 7 now use 1% Gaussian measurement noise. The unconstrained solution violates the PSD and trace constraints. We added a structured Newton solver (SN) for quadratic matrix sensing. At all three alignments, RBNFW (global) was fastest to a primal gap of 10−410^{-4}. RBNFW (global) and SN both reached 10−710^{-7} in a few seconds. Tables 3–6 now also use 1% Gaussian measurement noise.

  • MovieLens matrix completion. As you suggested, we agree that direct solvers are appropriate for special problems that admit such solutions. We therefore removed the log-determinant experiment and replaced it with a MovieLens matrix completion problem using pseudo-Huber loss on 80,000 observed ratings. RBNFW (global) reached a primal gap of 10−510^{-5} before FW (Figure 2). At a common FW-gap tolerance of 10−510^{-5}, RBNFW with away-step inner solves returned about half the primal gap of NFW and the rank-adaptive Riemannian trust-region solver. Both baselines met this stopping criterion sooner.

  • Theoretical contribution. SOCGS requires a polytope and strict complementarity for its local quadratic rate. For strongly convex objectives with Lipschitz Hessians, our method achieves this rate on any compact convex set without strict complementarity (Theorem 3.7). This covers the ellipsoids and nuclear-norm ball in the new experiments.

We believe these results address your concerns and hope you will reconsider your recommendation.

Reviewer_ht2xOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3(+1)
Soundness
3
Read review
Paper summary

A new damped Newton Frank-Wolfe method is proposed for the minimization of twice differentiable convex objective functions over general compact set in finite dimension. This method is structured into outer steps and FW inner steps. At each outer step kk, two estimations are performed: an estimation of a damping parameter αk\alpha_k and an estimation of an inner accuracy threshold ηk\eta_k. The damping parameter αk\alpha_k is used to build a quadratic approximation of the objective function. This quadratic approximation is then passed to a FW subroutine which performs FW inner steps until its dual gap reaches the inner accuracy threshold ηk\eta_k.

Two additional variants of the method are provided where the damping parameter estimation is always 11 after a certain number of outer steps defined by two different switching strategies.

The inner accuracy formula is given in Equation (3.2) while the backtracking strategy for the damped parameter estimation is given in Algorithm 4. The switching strategy is described in Equation (3.13), for the second order case, and in Equation (3.17), for the third order case.

In Theorem 3.6, a global R-linear convergence rate is provided. In Theorem 3.8, a local Q-order convergence rate is provided with a second order Hölder inequality assumption on the objective function. In Theorem 3.9, a quadratic convergence rate is provided with a third order Hölder inequality assumption on the objective function (when the latter is thrice differentiable).

Numerical experiments have been conducted on four minimization problems: a matrix sensing problem with a quadratic loss over trace constrained definite positive matrices; a ridge-regularized logistic regression on the covtype.binary dataset with ℓ2\ell_2-ball constraint; the same with a sparse polytope constraint; the same on the a9a dataset with a sparse polytope constraint. Each variant of the method is compared to first orders methods: Conditional Gradient Sliding, Projected Gradient, Accelerated Projected Gradient and Frank-Wolfe. Each variant of the method is also compared to second order method: Newton Frank-Wolfe and Second Order Conditional Gradient Sliding.

Critical strengths

This paper contributes to the understanding of global and local convergence rates for second order constrained methods. Global linear convergence rate and local Q-order convergence rate do not require additional assumptions on the compact constraint set: an additional assumption on the second or third differential of the objective function is enough.

From an experimental standpoint, it has been demonstrated that the damped Newton FW method performs better than the NFW method on compact sets that are not polytopes and on compact sets that are polytopes. It has also been demonstrated that the method competes with SOCGS over polytopes.

Not having to estimate the primal gap through the outer steps is a conceptual advantage that the damped Newton FW method has over SOCGS. Indeed, this estimation is one of the main obstacles for reliable implementation of SOCGS.

Critical weaknesses

This paper mainly suffers from a lack of clarity in explaining the computation of the damping parameters αk\alpha_k and the switching strategies. This is especially noticeable in Section 3 where the algorithmic definition of residual backtracking is presented alongside the global convergence result which makes it hard to follow.

On the experimental side, the paper lacks comparisons between the damped Newton FW method and SOCGS on nonpolytope compact constraint sets, where the new method is expected to perform better according to theoretical guarantees.

Questions for authors

Needed changes and additions.

  • The output of Algorithm 4 should be made explicit. Are we only interested in the value of αk\alpha_k?

  • In Algorithms 1 and 3, αk\alpha_k should not appear in the input but in an additional subroutine step. This would clarify where Algorithm 4 fits.

  • The general idea of switching should be introduced as an alternative subroutine to Algorithm 4 to compute αk\alpha_k in Algorithms 1 and 3. Again, this would clarify where the switching plays a role in the method.

  • Describing Algorithm 4 and switching strategies should appear in Section 2 as integral parts of the proposed method. Section 3 would then only deal with the conditions for global and local convergence rates (which are independent of the definition of Algorithm 4 and switching methods).

Questions.

  • In your implementation of SOCGS how do you estimate the primal gap for the termination of the inner steps? Have you tried to compare your method to different implementation of SOCGS with different primal gap estimations?

  • What is the motivation behind testing first order methods against your second order method?

  • In Figure 1, how do you interpret the lower primal gap achieved by APG compared to your method?

  • Have you conducted other experiments over compact sets that are not polytopes (like ellipses)?

  • Have you been able to find instances where the variants local2 and local3 lead to other primal gap trajectories than with global? Under which conditions should we expect the local variants to perform better than the global one?

Minor suggestions.

  • In line 104, DD should be called the diameter of X\mathcal{X}.
  • The name of Algorithm 2 and Algorithm 4 should include the word "subroutine'' so we do not confuse them for variants of the method.
  • In line 130, replacing "We define the damped quadratic model of ff'' by "For α∈(0,1)\alpha \in (0,1), we define the (α\alpha-)damped quadratic model of ff'' could make the central role of α\alpha clearer.
3 comments

Thank you for your careful review.

(W1, Q2--Q4) Clarify the computation of αk\alpha_k and switching, and present them as subroutines in Section 2. Compute αk\alpha_k rather than supply it as input.

We moved residual backtracking and switching to Section 2. In Algorithm 1, Subroutine RBT computes αk\alpha_k rather than taking it as an input and accepts a candidate satisfying the residual condition. The ``Switching Strategy'' paragraph specifies the FW-gap criterion and the switch to αk=1\alpha_k=1 and the local inner stopping rule. Section 3 analyzes global and local convergence under these rules.

(Q1) The output of Algorithm 4 should be made explicit.

Algorithm 1 now lists RBT's return values (xk+1,αk,sk,θˉk+1)(x_{k+1},\alpha_k,s_k,\bar\theta_{k+1}). Section 2's ``Away-Step FW Inner Loop'' and Subroutine AFW specify the active set and weight inputs and outputs. Those of the accepted inner solution are carried to the next outer iteration.

(Q11) Label Algorithms 2 and 4 as subroutines.

RBT is now a subroutine within Algorithm 1; FW and AFW are also labeled Subroutines to distinguish them from the overall algorithm.

(W2, Q8) Add comparisons with SOCGS over compact sets that are not polytopes, such as ellipses.

We added SOCGS comparisons to trace-constrained matrix sensing (Figures 1, 6, 7; Tables 3--6), ℓ2\ell_2-ball logistic regression on covtype.binary, a9a, and mushrooms (Figures 8--10), and the new trace-constrained MovieLens log-determinant and ellipsoid-constrained NEWS20 problems (Figures 2, 3; Table 7). These are empirical comparisons beyond SOCGS's existing guarantees. See also our responses to Reviewer Vazq's W3 and W4.

(Q5) How do you estimate the primal gap for SOCGS's inner stopping rule? Have you compared different estimates?

SOCGS sets its inner accuracy from the current objective value minus a known or estimated optimum (Section 4). We use the known optimum for quadratic matrix sensing, the smallest value from extended runs of other methods for other problems, and a numerical reference from the KKT conditions in the eigenbasis for log-determinant minimization.

On Figure 1's problem, we compared the known optimum, an independent numerical reference, and an estimate from up to five FW updates from the current point (FW5). All accepted five outer updates within 100 seconds. The first two agreed; FW5's relative primal-gap difference was at most about 4.50% and about 1.26% at the final point.

SOCGS primal gaps f(xk)−f(x⋆)f(x_k)-f(x^\star); k=0k=0 is the initial point and k=1,…,5k=1,\ldots,5 are all accepted outer updates.

kKnown optimumNumerical referenceFW5
07.123619e+017.123619e+017.123619e+01
11.445613e-031.445613e-031.445613e-03
27.758984e-087.758984e-087.410177e-08
31.395289e-081.395289e-081.358943e-08
46.615586e-096.615586e-096.436390e-09
54.137370e-094.137370e-094.189538e-09

All used (31,1000,1000,1000,1000)(31,1000,1000,1000,1000) inner iterations. The cap of 1000 follows Carderera & Pokutta (2026). Only the first solve met the stopping criterion; in the other four, we accepted the last inner iterate at the cap.

(Q6) What is the motivation behind testing first order methods against your second order method?

NFW and SOCGS are the two main existing second-order LMO-based methods. We also compare with FW and CGS to assess whether the benefits of second-order information offset its computational cost, and with PG and APG to evaluate performance when projections are available. Following Reviewer Vazq's comments, we added projected quasi-Newton and rank-adaptive Riemannian trust-region methods. Section 4 now states this motivation.

(Q7) In Figure 1, how do you interpret the lower primal gap achieved by APG compared to your method?

APG attained smaller gaps using accurate projections with full eigenvalue decompositions, which required more time (Section 4.1). The common termination criterion uses the FW gap, so final primal gaps need not coincide.

(Q9) Do local2 and local3 give different primal gap curves from global, and when should they perform better?

In Figure 1, local2 and local3 switch by k=2k=2 and yield convergence curves different from those of global. They attained smaller final gaps in Figures 6 and 7, but global reached 10−810^{-8} fastest (Section E.1). Under Section 3.2's conditions, fewer outer iterations can improve runtime when the local inner stopping rule is met at low cost.

(Q10) In line 104, DD should be called the diameter of XX.

We changed this to "the diameter of XX" in the Introduction's "Notation" paragraph.

(Q12) Introduce the model as the (α\alpha-)damped quadratic model for α∈(0,1)\alpha\in(0,1) to clarify the role of α\alpha.

Section 2 now reads: "For α∈(0,1)\alpha\in(0,1), we define the (α\alpha-)damped quadratic model of ff at xkx_k as".

Dear Reviewer ht2x,

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 clarified the damping and switching rules and added comparisons with SOCGS on nonpolyhedral sets.

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 thank the authors for their thorough answers to my questions and suggestions. Now that the algorithms statements and the convergence results are separated, the paper is easier to read and the contributions appear more clearly.

I keep my current rating of 3: Weak acceptance.

I raise the presentation to 3: Clear and easy to follow.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.