Pith. sign in

REVIEW 4 major objections 6 minor 69 references

Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms

T0 review · 4 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper claims that a warm-started BPCG with an adaptive error bound solves constrained difference-of-convex problems far more efficiently than standard Frank-Wolfe DCA, with speedups often exceeding 100-fold.

desk verdict Solid computational study showing large speedups from warm-started BPCG with adaptive early stopping for FW-based DCA; the theory is borrowed, the empirical case is strong but needs sensitivity analysis and code. read the letter →

arxiv 2507.17545 v2 pith:2FAL7C5P submitted 2025-07-23 math.OC cs.LG

Sebastian Pokutta This is my paper · ORCID
classification math.OCcs.LG MSC 90C2690C25
keywords difference-of-convexoptimizationFrank-WolfealgorithmBlendedPairwiseConditionalGradientsadaptiveerrorboundwarm-startinglinearminimizationoracleQuadraticAssignmentProblemDCA
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies the constrained difference-of-convex (DC) problem $\min_{x\in P} f(x)-g(x)$ with $f,g$ convex and $P$ a compact convex set that may be complicated. It claims that the standard Difference-of-Convex Algorithm becomes substantially cheaper when each convex subproblem is solved by the Blended Pairwise Conditional Gradients (BPCG) algorithm, warm-started from the previous iterate, and stopped early according to the adaptive error bound from Maskan et al. [2025]. Empirically, on differences of convex quadratics, a hard mixed nonlinear example, and Quadratic Assignment Problems over the Birkhoff polytope, this combination uses orders of magnitude fewer linear minimization oracle (LMO) calls and is often more than 100 times faster in wall-clock time than baseline Frank-Wolfe-based DCA variants. If correct, this makes projection-free DC optimization tractable at large scales that were previously out of reach.

What carries the argument

The load-bearing mechanism is the adaptive error bound (3.3): solve the inner convex subproblem $\min_{x\in P}\hat\Phi_t(x)$ only until its Frank-Wolfe gap at the candidate iterate $y$ is at most $\Phi(x_t)-\hat\Phi_t(y)$. By an arithmetic-geometric crossover, this inexactness preserves a multiplicative factor $1/2$ of the DC gap as guaranteed progress, replacing the additive $\varepsilon$ error of Theorem 3.1 and removing the need to preselect $\varepsilon$. The second piece is BPCG, an active-set Frank-Wolfe variant that supports warm-starting by reusing the active set from the previous DCA subproblem, which is nearly identical near convergence.

What would settle it

Run the DCA-BPCG-WS-ES variant against the fixed-tolerance DCA-FW baseline on the same DC quadratic instances but with the baseline's inner tolerance relaxed to, say, $10^{-3}$; if the LMO-call and wall-clock advantages shrink to a small constant, the reported order-of-magnitude gains depend on the baseline's accuracy setting.

Watch

Extended reading notes

Core claim

The central claim is that the adaptive error bound criterion (3.3), which stops the inner Frank-Wolfe solver as soon as the subproblem's Frank-Wolfe gap falls below $\Phi(x_t)-\hat\Phi_t(y)$, removes the need to choose a subproblem tolerance $\varepsilon$ while keeping an $O(1/T)$ convergence rate in the DC gap (Theorem 3.2, reproduced from Maskan et al. [2025]). When this criterion is paired with BPCG and warm-starting, reusing the previous iterate and its active set, each DCA iteration becomes very cheap and the number of LMO calls collapses. Across all tested instances excluding QAP, the combined DCA-BPCG-WS-ES variant attains a DC gap below $10^{-6}$ with geometric-mean speedups over DCA-FW exceeding factors of 100 in time and often several orders of magnitude in LMO calls.

Load-bearing premise

The comparison assumes the fixed inner tolerance $10^{-6}/2$ used for the non-early-stopping baselines is representative of typical prior practice; if typical users use a coarser inner tolerance, the adaptive early-stopping advantage would shrink.

Editorial extensions

If this is right

  • The adaptive criterion (3.3) removes the need to preset a subproblem tolerance $\varepsilon$, so users no longer trade outer accuracy against inner cost by hand.
  • Because warm-starting reuses the previous active set, the method is cheapest exactly where it matters most: the final DCA iterations, when consecutive subproblems are nearly identical.
  • The $O(1/T)$ worst-case rate in the DC gap survives the early stopping, with only a factor-2 slowdown in outer iterations that is outweighed by much cheaper inner solves.
  • On Quadratic Assignment instances over the Birkhoff polytope, the combined variant reaches the DCA iteration limit with far fewer Hungarian-method LMO calls than the baselines.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same adaptive early-stopping criterion should transfer to stochastic or block-coordinate Frank-Wolfe subsolvers, since it only requires a Frank-Wolfe gap estimate at each inner iterate.
  • Adding lazification to BPCG, which the paper deliberately skipped to keep tight gap control, could reduce LMO calls further when the linear oracle is expensive, such as the Hungarian method in QAP.
  • The QAP experiments suggest the relaxed Birkhoff solution might be rounded to feasible assignments, but the paper does not evaluate rounding quality or the gap to the integer optimum.
  • The boosted-DCA line search showed no extra gain here, but a line search on the DC gap itself, rather than on the inner convex surrogate, could still cut outer iterations without extra LMO calls.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

Summary. The paper proposes a practical framework for constrained difference-of-convex (DC) minimization, combining the DCA outer loop with advanced Frank-Wolfe subsolvers, specifically Blended Pairwise Conditional Gradients (BPCG), warm-starting, and an adaptive subproblem stopping criterion attributed to Maskan et al. (2025). It reproduces the adaptive error-bound theorem (Theorem 3.2), presents a modular algorithmic template (Algorithm 2), and reports an extensive computational study on DC quadratics, hard exponential/logistic DC instances, and QAPLIB instances. The central empirical claim is that the DCA-BPCG-WS-ES variant reduces LMO calls by orders of magnitude and runtime by factors exceeding 100 relative to previous Frank-Wolfe-based DCA variants.

Significance. If the reported gains are robust, the paper delivers a practically valuable recipe: a parameter-free adaptive subproblem tolerance, built on the open-source FrankWolfe.jl toolbox, that scales to Birkhoff-polytope problems with n up to 256. The experimental scope is broad and the results are internally consistent across problem classes, and the theoretical backbone (adaptive inexact DCA) is correctly attributed to and reproduced from Maskan et al. (2025). The main open question is whether the headline speedups are an artifact of the asymmetric subproblem tolerances used for the fixed-tolerance baselines; this is a testable empirical issue rather than an internal inconsistency.

major comments (4)
  1. [Section 5.1 and Tables 1, 3, 4, 5; Figure 1] The comparison between ES and non-ES variants is asymmetric. The non-ES baselines are stopped only when the inner Frank-Wolfe gap is below 10^{-6}/2, while the ES variants stop as soon as condition (3.3) holds, i.e., when the inner FW gap is at most the realized DCA progress Phi(x_t) - hatPhi_t(x_{t+1}), which is at least the DC gap Delta_t and can be orders of magnitude larger than 10^{-6}/2 in early outer iterations. Since FW-type methods require on the order of 1/gap iterations to reach a given gap, the fixed-tolerance baselines are forced to spend many LMO calls on early subproblems that the adaptive rule correctly identifies as needing little accuracy. The reported LMO reductions and runtime speedups may therefore largely reflect the choice of 10^{-6}/2 rather than an intrinsic advantage of the adaptive rule. Please add a sensitivity study in which DCA-BPCG-WS and DCA-FW are run with fixed subproblem tolerances of, e.g., 10^{-3}, 10^{-4}, and 10^{-5}, and report whether the qualitative conclusions of Table 1 and Figure 1 survive.
  2. [Section 5.5 and Appendix A] The QAP experiment is based on only 97 of the 136 QAPLIB instances; the 39 excluded instances are not a random subsample. The list in Appendix A includes all sko100a-f, sko42-90, several lipa instances, nug30, and ste36a-c, i.e., many of the largest and structurally distinct instances. This selection can bias the performance profiles in Figures 5 and 6 and the corresponding rows of Table 5. Please report the size and family distribution of the excluded instances, and either repair the parser or demonstrate that the parsing failures are independent of instance size and family; ideally rerun the affected families.
  3. [Section 1 and Section 5] The paper frames the contribution as projection-free scalability and states that traditional projection-based methods are computationally prohibitive, but no projection-based DCA baseline is included in the experiments. On the Birkhoff polytope, projections are expensive but feasible at the tested dimensions (n <= 256), so a comparison against DCA with projected gradient or accelerated projected gradient on the convex subproblems would directly substantiate the scalability claim. Without such a comparison, the 'previously out of reach' claim relative to standard DCA practice is not fully supported by the data.
  4. [Section 5] The code for the experiments is not released; the paper states that it 'will be made separately available on GitHub.' Since the central contribution is an empirical claim about large speedups, the absence of runnable scripts, exact random seeds (only hashes are shown), and version-pinned dependencies makes the specific numbers in Tables 1-5 difficult to verify. For a computational study, releasing the experiment harness is a necessary condition for the reproducibility of the headline claims.
minor comments (6)
  1. [Section 3] There is a typo: 'One the one hand' should be 'On the one hand'.
  2. [Section 5.1] The stopping-rule description is ambiguous: 'we stop with a Frank-Wolfe gap less than 10^{-6}/2 or when the adaptive error bound is satisfied, for those variants using it' could be read as the ES variants also requiring the 10^{-6}/2 gap. Please clarify that the ES variants stop purely on condition (3.3).
  3. [Section 5.5] There are typos: 'signficantly' should be 'significantly', and 'see Table 2 and Figure 2 and Figure 3' repeats 'Figure 3' in Section 5.3.
  4. [Table 5] Several rows of Table 5 are misaligned in the text (e.g., n=26, n=50, n=64, n=100, n=128), with apparent duplicate or missing column entries. Please reformat the table.
  5. [Section 5.2 and Abstract] The claim of 'runtime speedups exceeding factors of 100' is an overgeneralization: in Table 5, several size brackets (e.g., n=128, n=150, n=256) show comparable or worse times for DCA-BPCG-WS-ES relative to the baselines. Suggest adding qualifiers that reflect instance-to-instance variability.
  6. [Table 1 vs Tables 3 and 4] The composition of the 'all instances (excluding QAP)' set should be described more precisely; for sizes n=600-1000, Table 1 appears to contain only the large-quadratic instances from Table 3, while smaller sizes combine multiple suites. Stating this explicitly would help interpretation.

Circularity Check

0 steps flagged · score 2.0 of 10

No load-bearing circularity: Theorem 3.2 is proved from its stated assumption, and the headline speedups are measured against external benchmarks; the fixed 1e-6/2 baseline is a comparison-protocol concern, not a fitted input.

full rationale

The paper's convergence claim (Theorem 3.2) is not circular: it takes the adaptive stopping condition (3.3) as an explicit assumption, proves by a short algebraic argument that this assumption implies the rate O(1/T), and reproduces the proof in full. This is a standard conditional guarantee, not an import of the conclusion via citation. The theorem is attributed to Maskan et al. [2025], which has no author overlap with the present paper, so the citation is independent evidence. The central empirical claim—that DCA-BPCG-WS-ES reduces LMO calls and runtime—is a measured comparison on random instances and the external QAPLIB benchmark, not a quantity derived from the paper's own assumptions. The many self-citations (BPCG, FrankWolfe.jl, secant line search) justify the choice of algorithmic components and software, but the speedups are observed, not inferred from those references. The skeptic's concern about the fixed Frank-Wolfe subproblem tolerance of 1e-6/2 for non-ES baselines (Section 5.1) is a legitimate question of experimental fairness: a coarser baseline tolerance might reduce the reported speedup magnitudes. However, that is a comparison-protocol issue, not circularity. No equation reduces to its own input by construction, and no fitted parameter is renamed as a prediction. The paper is self-contained against external benchmarks, so it scores in the 0-2 range.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard convex-analysis assumptions and on the correctness of the adaptive error bound from Maskan et al. [2025], which is reproduced but not novel. The experimental parameters (stopping tolerances, iteration limits) are hand-chosen and affect the quantitative claims.

free parameters (3)
  • Fixed subproblem Frank-Wolfe gap tolerance (non-ES baselines) = 10^{-6}/2
    Set in Section 5.1; tight tolerance for baselines may amplify the apparent gain of adaptive early stopping.
  • DCA gap target = 10^{-6}
    Instances are considered solved when DCA gap < 10^{-6}; affects performance profiles.
  • Inner iteration limits = 10000 to 50000 depending on experiment
    Cap on subproblem iterations; interacts with the stopping criteria.
assumptions (4)
  • domain assumption Existence of an exact linear minimization oracle over P
    Section 2.2; the algorithm and theory depend on exact LMO, available for the tested sets.
  • domain assumption f is L_f-smooth convex and g is L_g-Lipschitz convex
    Equation (1.1) and Section 2.1; defines the problem class.
  • standard math Adaptive error bound theorem (Theorem 3.2) of Maskan et al. [2025]
    Reproduced in Section 3; the computational study's stopping rule relies on its validity.
  • standard math BPCG convergence properties from Tsuji et al. [2022] and Braun et al. [2025]
    Section 4.1; assumes BPCG solves smooth convex subproblems efficiently and warm-starting preserves convergence.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms." pith.science (2026). https://pith.science/paper/2FAL7C5P

@misc{pith2026250717545,
  author       = {Pith},
  title        = {Pith review of: Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2FAL7C5P}},
  note         = {Machine review of arXiv:2507.17545}
}
abstract

We consider the problem of minimizing a difference of (smooth) convex functions over a compact convex feasible region $P$, i.e., $\min_{x \in P} f(x) - g(x)$, with smooth $f$ and Lipschitz continuous $g$. This computational study builds upon and complements the framework of Maskan et al. [2025] by integrating advanced Frank-Wolfe variants to reduce computational overhead. We empirically show that constrained DC problems can be efficiently solved using a combination of the Blended Pairwise Conditional Gradients (BPCG) algorithm [Tsuji et al., 2022] with warm-starting and the adaptive error bound from Maskan et al. [2025]. The result is a highly efficient and scalable projection-free algorithm for constrained DC optimization.

Figures

Figures reproduced from arXiv: 2507.17545 by the authors.

Figure 1
Figure 1. Performance profile over all tested instances (excluding QAP) as described in [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Performance profile over small to medium-sized instances of differences of convex quadratics [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Performance profile over medium to large-sized instances of differences of convex quadratics [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figures from the paper (16 more)
Figure 4
Figure 4. Figure 4: Performance profile over hard DC instances from [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]
Figure 5
Figure 5. Figure 5: Performance profile over Quadratic Assignment Problem instances from [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]
Figure 6
Figure 6. Figure 6: Modified performance profile over Quadratic Assignment Problem instances from [PITH_FULL_IMAGE:figures/full_fig_p015_6.png]
Figure 7
Figure 7. Figure 7: Performance profile over difference of convex quadratic functions as initial test of the effect [PITH_FULL_IMAGE:figures/full_fig_p022_7.png]
Figure 8
Figure 8. Figure 8: Run of the different variants on a Difference of Convex Quadratics example with seed [PITH_FULL_IMAGE:figures/full_fig_p023_8.png]
Figure 9
Figure 9. Figure 9: Run of the different variants on a Difference of Convex Quadratics example with seed [PITH_FULL_IMAGE:figures/full_fig_p023_9.png]
Figure 10
Figure 10. Figure 10: Run of the different variants on a Difference of Convex Quadratics example with seed [PITH_FULL_IMAGE:figures/full_fig_p024_10.png]
Figure 11
Figure 11. Figure 11: Run of the different variants on a Difference of Convex Quadratics example with seed [PITH_FULL_IMAGE:figures/full_fig_p024_11.png]
Figure 12
Figure 12. Figure 12: Run of the different variants on the hard DC function example with size [PITH_FULL_IMAGE:figures/full_fig_p025_12.png]
Figure 13
Figure 13. Figure 13: Run of the different variants on the hard DC function example with size [PITH_FULL_IMAGE:figures/full_fig_p025_13.png]
Figure 14
Figure 14. Figure 14: Run of the different variants on the hard DC function example with size [PITH_FULL_IMAGE:figures/full_fig_p026_14.png]
Figure 15
Figure 15. Figure 15: Run of the different variants on the hard DC function example with size [PITH_FULL_IMAGE:figures/full_fig_p026_15.png]
Figure 16
Figure 16. Figure 16: Run of the different variants on the small-sized [PITH_FULL_IMAGE:figures/full_fig_p027_16.png]
Figure 17
Figure 17. Figure 17: Run of the different variants on the medium-sized [PITH_FULL_IMAGE:figures/full_fig_p027_17.png]
Figure 18
Figure 18. Figure 18: Run of the different variants on the medium-sized [PITH_FULL_IMAGE:figures/full_fig_p028_18.png]
Figure 19
Figure 19. Figure 19: Run of the different variants on the large-sized [PITH_FULL_IMAGE:figures/full_fig_p028_19.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

69 extracted references · 61 canonical work pages

  1. [1]

    On the rate of convergence of the difference-of-convex algorithm ( DCA )

    Abbaszadehpeivasti, H., de Klerk, E., and Zamani, M. On the rate of convergence of the difference-of-convex algorithm ( DCA ). Journal of Optimization Theory and Applications, pp.\ 1--22, 2023

    work page 2023

  2. [2]

    An, L. T. H. and Tao, P. D. Solving a class of linearly constrained indefinite quadratic problems by DC algorithms. Journal of global optimization, 11: 0 253--285, 1997

    work page 1997

  3. [3]

    An, L. T. H. and Tao, P. D. A branch and bound method via DC optimization algorithms and ellipsoidal technique for box constrained nonconvex quadratic problems. Journal of Global Optimization, 13 0 (2): 0 171--206, 1998

    work page 1998

  4. [4]

    Arag \'o n Artacho, F. J. and Vuong, P. T. The boosted dc algorithm for nonsmooth functions. arXiv e-prints, pp.\ arXiv--1812, 2018

    work page 2018

  5. [5]

    J., Fleming, R

    Arag \'o n Artacho, F. J., Fleming, R. M. T., and Vuong, P. T. Accelerating the DC algorithm for smooth functions. Mathematical Programming, 169 0 (1): 0 95--118, May 2018. ISSN 0025-5610, 1436-4646. doi:10.1007/s10107-017-1180-1

    doi:10.1007/s10107-017-1180-1 2018

  6. [6]

    J., Campoy, R., and Vuong, P

    Arag \'o n Artacho , F. J., Campoy, R., and Vuong, P. T. The Boosted DC Algorithm for Linearly Constrained DC Programming . Set-Valued and Variational Analysis, 30 0 (4): 0 1265--1289, December 2022. ISSN 1877-0533, 1877-0541. doi:10.1007/s11228-022-00656-x

    doi:10.1007/s11228-022-00656-x 2022

  7. [7]

    A., and Pontil, M

    Argyriou, A., Hauser, R., Micchelli, C. A., and Pontil, M. A DC -programming algorithm for kernel selection. In Proceedings of the 23rd international conference on Machine learning, pp.\ 41--48, 2006

    work page 2006

  8. [8]

    Best-effort adaptation

    Awasthi, P., Cortes, C., and Mohri, M. Best-effort adaptation. Annals of Mathematics and Artificial Intelligence, pp.\ 1--46, 2024 a

    work page 2024

Show all 69 references
  1. [9]

    DC -programming for neural network optimizations

    Awasthi, P., Mao, A., Mohri, M., and Zhong, Y. DC -programming for neural network optimizations. Journal of Global Optimization, pp.\ 1--17, 2024 b

    2024

  2. [10]

    Bashiri, M. A. and Zhang, X. Decomposition-invariant conditional gradient for general polytopes with line search. Advances in neural information processing systems, 30, 2017

    2017

  3. [11]

    Addressing misspecification in contextual optimization

    Bennouna, O., Zhang, J., Amin, S., and Ozdaglar, A. Addressing misspecification in contextual optimization. arXiv preprint arXiv:2409.10479, 2024

    2024 arXiv

  4. [12]

    FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and Conditional Gradients

    Besan c on, M., Carderera, A., and Pokutta, S. FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and Conditional Gradients . INFORMS Journal on Computing, 2 2022

    2022

  5. [13]

    Improved algorithms and novel applications of the FrankWolfe.jl library

    Besan c on, M., Designolle, S., Halbey, J., Hendrych, D., Kuzinowicz, D., Pokutta, S., Troppens, H., Viladrich Herrmannsdoerfer, D., and Wirth, E. Improved algorithms and novel applications of the FrankWolfe.jl library . preprint, 1 2025

    2025

  6. [14]

    Lazifying Conditional Gradient Algorithms

    Braun, G., Pokutta, S., and Zink, D. Lazifying Conditional Gradient Algorithms . Proceedings of the International Conference on Machine Learning (ICML) , 2017

    2017

  7. [15]

    Blended Conditional Gradients: the unconditioning of conditional gradients

    Braun, G., Pokutta, S., Tu, D., and Wright, S. Blended Conditional Gradients: the unconditioning of conditional gradients . Proceedings of ICML , 2019 a

    2019

  8. [16]

    Blended conditional gradients: the unconditioning of conditional gradients

    Braun, G., Pokutta, S., Tu, D., and Wright, S. Blended conditional gradients: the unconditioning of conditional gradients. In Proceedings of the 36th International Conference on Machine Learning, 2019 b

    2019

  9. [17]

    Lazifying Conditional Gradient Algorithms

    Braun, G., Pokutta, S., and Zink, D. Lazifying Conditional Gradient Algorithms . Journal of Machine Learning Research (JMLR) , 20 0 (71): 0 1--42, 2019 c

    2019

  10. [18]

    W., Hassani, H., Karbasi, A., Mokthari, A., and Pokutta, S

    Braun, G., Carderera, A., Combettes, C. W., Hassani, H., Karbasi, A., Mokthari, A., and Pokutta, S. Conditional Gradient Methods. to appear in MOS-SIAM Series on Optimization, 1 2025

    2025

  11. [19]

    E., Karisch, S

    Burkard, R. E., Karisch, S. E., and Rendl, F. Qaplib--a quadratic assignment problem library. Journal of Global Optimization, 10 0 (4): 0 391--403, 1997

    1997

  12. [20]

    Y., and Pokutta, S

    Carderera, A., Diakonikolas, J., Lin, C. Y., and Pokutta, S. Parameter-free Locally Accelerated Conditional Gradients . Proceedings of ICML, 2 2021

    2021

  13. [21]

    Combettes, C. W. and Pokutta, S. Blended Matching Pursuit . Proceedings of NeurIPS , 2019

    2019

  14. [22]

    Combettes, C. W. and Pokutta, S. Boosting Frank-Wolfe by Chasing Gradients . Proceedings of ICML , 3 2020

    2020

  15. [23]

    Combettes, C. W. and Pokutta, S. Complexity of Linear Minimization and Projection on Some Sets . Operations Research Letters, 49, 7 2021

    2021

  16. [24]

    T., Padmanabhan, S., and Ye, G

    Davis, D., Drusvyatskiy, D., Lee, Y. T., Padmanabhan, S., and Ye, G. A gradient sampling method with complexity guarantees for L ipschitz functions in high and low dimensions. Advances in neural information processing systems, 35: 0 6692--6703, 2022

    2022

  17. [25]

    Dem'yanov, V. F. and Rubinov, A. M. Approximate methods in optimization problems. (No Title), 1970

    1970

  18. [26]

    Locally Accelerated Conditional Gradients

    Diakonikolas, J., Carderera, A., and Pokutta, S. Locally Accelerated Conditional Gradients . Proceedings of AISTATS , 2020

    2020

  19. [27]

    P., Santos, E

    Ferreira, O. P., Santos, E. M., and Souza, J. C. O. A boosted DC algorithm for non-differentiable DC components with non-monotone line search, June 2022

    2022

  20. [28]

    and Wolfe, P

    Frank, M. and Wolfe, P. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3 0 (1--2): 0 95--110, June 1956. doi:10.1002/nav.3800030109

    1956 doi

  21. [29]

    M., Grigas, P., and Mazumder, R

    Freund, R. M., Grigas, P., and Mazumder, R. An extended frank--wolfe method with “in-face” directions, and its application to low-rank matrix completion. SIAM Journal on optimization, 27 0 (1): 0 319--346, 2017

    2017

  22. [30]

    and Hazan, E

    Garber, D. and Hazan, E. Faster rates for the frank-wolfe method over strongly-convex sets. In International Conference on Machine Learning, pp.\ 541--549. PMLR, 2015

    2015

  23. [31]

    and Meshi, O

    Garber, D. and Meshi, O. Linear-memory and decomposition-invariant linearly convergent conditional gradient algorithm for structured polytopes. Advances in neural information processing systems, 29, 2016

    2016

  24. [32]

    and Marcotte, P

    Gu \'e lat, J. and Marcotte, P. Some comments on W olfe's `away step'. Mathematical Programming, 35 0 (1): 0 110--119, 1986

    1986

  25. [33]

    Efficient Quadratic Corrections for Frank-Wolfe Algorithms

    Halbey, J., Rakotomandimby, S., Besan c on, M., Designolle, S., and Pokutta, S. Efficient Quadratic Corrections for Frank-Wolfe Algorithms . preprint , 6 2025

    2025

  26. [34]

    Secant Line Search for Frank-Wolfe Algorithms

    Hendrych, D., Besan c on, M., Mart \'i nez-Rubio, D., and Pokutta, S. Secant Line Search for Frank-Wolfe Algorithms . to appear in Proceedings of ICML, 5 2025 a

    2025

  27. [35]

    Convex mixed-integer optimization with frank-wolfe methods

    Hendrych, D., Troppens, H., Besan c on, M., and Pokutta, S. Convex mixed-integer optimization with frank-wolfe methods. Mathematical Programming Computation , 4 2025 b

    2025

  28. [36]

    T., Tao, P

    Hoai An, L. T., Tao, P. D., Nguyen Canh, N., and Van Thoai, N. DC programming techniques for solving a class of nonlinear bilevel programs. Journal of Global Optimization, 44: 0 313--337, 2009

    2009

  29. [37]

    Holloway, C. A. An extension of the frank and wolfe method of feasible directions. Mathematical Programming, 6 0 (1): 0 14--27, 1974

    1974

  30. [38]

    T., Huyen, D

    Huong, V. T., Huyen, D. T. K., and Yen, N. D. Generalized polyhedral dc optimization problems. arXiv preprint arXiv:2411.19272, 2024

    2024 arXiv

  31. [39]

    Revisiting Frank -- Wolfe : Projection -free sparse convex optimization

    Jaggi, M. Revisiting Frank -- Wolfe : Projection -free sparse convex optimization. In Dasgupta, S. and McAllester, D. (eds.), Proceedings of the 30th International Conference on Machine Learning, volume 28 of ICML'13, pp.\ 427--435, Atlanta, Georgia, USA, June 2013. PMLR. URL ...

    2013

  32. [40]

    Restarting Frank-Wolfe

    Kerdreux, T., d'Aspremont, A., and Pokutta, S. Restarting Frank-Wolfe . In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pp.\ 1275--1283. PMLR, 2019

    2019

  33. [41]

    Projection-free optimization on uniformly convex sets

    Kerdreux, T., d'Aspremont, A., and Pokutta, S. Projection-free optimization on uniformly convex sets. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, pp.\ 19--27. PMLR, 2021

    2021

  34. [42]

    Restarting Frank-Wolfe: Faster Rates under H \"o lderian Error Bounds

    Kerdreux, T., d'Aspremont, A., and Pokutta, S. Restarting Frank-Wolfe: Faster Rates under H \"o lderian Error Bounds . Journal of Optimization Theory and Applications , 192: 0 799--829, 2022

    2022

  35. [43]

    Local and Global Uniform Convexity Conditions

    Kerdreux, T., d'Aspremont, A., and Pokutta, S. Local and Global Uniform Convexity Conditions . to appear in Special Issue of Fields Institute Communications , 1 2025

    2025

  36. [44]

    and Wainwright, M

    Khamaru, K. and Wainwright, M. J. Convergence guarantees for a class of non-convex and non-smooth optimization problems. Journal of Machine Learning Research, 20: 0 1--52, 2019. URL https://jmlr.org/papers/v20/18-762.html

    2019

  37. [45]

    and Lewis, A

    Kong, S. and Lewis, A. The cost of nonconvexity in deterministic nonsmooth optimization. Mathematics of Operations Research, 2023

    2023

  38. [46]

    Convergence rate of F rank- W olfe for non-convex objectives

    Lacoste-Julien, S. Convergence rate of F rank- W olfe for non-convex objectives. arXiv preprint arXiv:1607.00345, 2016

    2016 arXiv

  39. [47]

    and Jaggi, M

    Lacoste-Julien, S. and Jaggi, M. On the global linear convergence of F rank- W olfe optimization variants. In Proceedings of the 29th Conference on Neural Information Processing Systems, pp.\ 566--575. PMLR, 2015

    2015

  40. [48]

    and Zhou, Y

    Lan, G. and Zhou, Y. Conditional gradient sliding for convex optimization. volume 26, pp.\ 1379--1409, 2016

    2016

  41. [49]

    Conditional Accelerated Lazy Stochastic Gradient Descent

    Lan, G., Pokutta, S., Zhou, Y., and Zink, D. Conditional Accelerated Lazy Stochastic Gradient Descent . Proceedings of the International Conference on Machine Learning (ICML) , 2017

    2017

  42. [50]

    and Sriperumbudur, B

    Lanckriet, G. and Sriperumbudur, B. K. On the convergence of the concave-convex procedure. Advances in Neural Information Processing Systems, 22, 2009

    2009

  43. [51]

    Le Thi, H. A. and Pham Dinh, T. DC programming and DCA : T hirty years of developments. Mathematical Programming, 169 0 (1): 0 5--68, 2018

    2018

  44. [52]

    Levitin, E. S. and Polyak, B. T. Constrained minimization methods. USSR Computational Mathematics and Mathematical Physics, 6 0 (5): 0 1--50, 1966

    1966

  45. [53]

    and Sra, S

    Mariet, Z. and Sra, S. Fixed-point algorithms for learning determinantal point processes. In International Conference on Machine Learning, pp.\ 2389--2397. PMLR, 2015

    2015

  46. [54]

    Revisiting Frank-Wolfe for Structured Nonconvex Optimization , March 2025

    Maskan, H., Hou, Y., Sra, S., and Yurtsever, A. Revisiting Frank-Wolfe for Structured Nonconvex Optimization , March 2025. URL https://arxiv.org/abs/2503.08921

    2025

  47. [55]

    D., Ferreira, O., and Ugon, J

    Mill \'a n, R. D., Ferreira, O., and Ugon, J. Frank- W olfe algorithm for DC optimization problem. arXiv preprint arXiv:2308.16444, 2023

    2023

  48. [56]

    Minding the gaps for block frank-wolfe optimization of structured svms

    Osokin, A., Alayrac, J.-B., Lukasewitz, I., Dokania, P., and Lacoste-Julien, S. Minding the gaps for block frank-wolfe optimization of structured svms. In international conference on machine learning, pp.\ 593--602. PMLR, 2016

    2016

  49. [57]

    Linearly convergent F rank-- W olfe with backtracking line-search

    Pedregosa, F., Negiar, G., Askari, A., and Jaggi, M. Linearly convergent F rank-- W olfe with backtracking line-search. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics. PMLR, 2020

    2020

  50. [58]

    The Frank-Wolfe algorithm: a short introduction

    Pokutta, S. The Frank-Wolfe algorithm: a short introduction . Jahresbericht der Deutschen Mathematiker-Vereinigung , 126: 0 3--35, 1 2024

    2024

  51. [59]

    Non-convex conditional gradient sliding

    Qu, C., Li, Y., and Xu, H. Non-convex conditional gradient sliding. pp.\ 4208--4217, 2018

    2018

  52. [60]

    Tight analysis of difference-of-convex algorithm (dca) improves convergence rates for proximal gradient descent, 2025

    Rotaru, T., Patrinos, P., and Glineur, F. Tight analysis of difference-of-convex algorithm (dca) improves convergence rates for proximal gradient descent, 2025. URL https://arxiv.org/abs/2503.04486

    2025

  53. [61]

    Disciplined convex-concave programming

    Shen, X., Diamond, S., Gu, Y., and Boyd, S. Disciplined convex-concave programming. In 2016 IEEE 55th conference on decision and control (CDC), pp.\ 1009--1014. IEEE, 2016

    2016

  54. [62]

    Tao, P. D. Convex analysis approach to DC programming: theory, algorithms and applications. Acta mathematica vietnamica, 22 0 (1): 0 289--355, 1997

    1997

  55. [63]

    Tao, P. D. et al. Algorithms for solving a class of nonconvex optimization problems. methods of subgradients. In North-Holland Mathematics Studies, volume 129, pp.\ 249--271. Elsevier, 1986

    1986

  56. [64]

    Learning Cuts via Enumeration Oracles

    Thuerck, D., Sofranac, B., Pfetsch, M., and Pokutta, S. Learning Cuts via Enumeration Oracles . Proceedings of NeurIPS , 9 2023

    2023

  57. [65]

    Pairwise Conditional Gradients without Swap Steps and Sparser Kernel Herding

    Tsuji, K., Tanaka, K., and Pokutta, S. Pairwise Conditional Gradients without Swap Steps and Sparser Kernel Herding . Proceedings of ICML , 5 2022

    2022

  58. [66]

    T., Conroy, J

    Vogelstein, J. T., Conroy, J. M., Lyzinski, V., Podrazik, L. J., Kratzer, S. G., Harley, E. T., Fishkind, D. E., Vogelstein, R. J., and Priebe, C. E. Fast approximate quadratic programming for graph matching. PLOS one, 10 0 (4): 0 e0121002, 2015

    2015

  59. [67]

    Yuille, A. L. and Rangarajan, A. The concave-convex procedure. Neural computation, 15 0 (4): 0 915--936, 2003

    2003

  60. [68]

    and Sra, S

    Yurtsever, A. and Sra, S. CCCP is Frank-Wolfe in disguise . Advances in Neural Information Processing Systems, 35: 0 35352--35364, 2022

    2022

  61. [69]

    Complexity of finding stationary points of nonconvex nonsmooth functions

    Zhang, J., Lin, H., Jegelka, S., Sra, S., and Jadbabaie, A. Complexity of finding stationary points of nonconvex nonsmooth functions. pp.\ 11173--11182, 2020

    2020

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.