REVIEW 3 major objections 4 minor 11 references
Adaptive Conditional Gradient Sliding: Projection-Free and Line-Search-Free Acceleration
T0 review · 3 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read AdCGS, a projection-free and line-search-free algorithm, reaches O(1/k²) accelerated rates for convex objectives and linear convergence for strongly convex objectives, using only a linear minimization oracle.
desk verdict AdCGS is a genuinely useful extension of CGS with adaptive stepsizes, but the main convex-rate corollary's constant is stronger than the proof supports and the nonsmooth experiments are outside the theory. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing mechanism is the pairing of adaptive stepsizes with inner inexactness tolerances. Each outer iteration $k$ runs an LMO-based conditional-gradient loop on the subproblem above until its FW gap is at most $\delta_k$, then forms $y_k=(1-\beta_k)y_{k-1}+\beta_k z_k$ and $x_k=\frac{\tau_k}{1+\tau_k}x_{k-1}+\frac{1}{1+\tau_k}z_k$. The stepsize $\eta_k$ is set from local Lipschitz estimates $L_1=\|\nabla f(x_1)-\nabla f(x_0)\|/\|x_1-x_0\|$ and $L_k=\|\nabla f(x_k)-\nabla f(x_{k-1})\|^2/(2D_f(x_{k-1},x_k))$, where $D_f(x,y)=f(x)-f(y)-\langle\nabla f(y),x-y\rangle$. The proof works because the schedule for $\delta_k$ keeps the accumulated inexactness error $S_k=\sum_i \eta_{i+1}(\delta_{i+1}+\delta_i)$ under control even though larger adaptive steps would otherwise amplify inner errors.
What would settle it
Run AdCGS on the paper's own $\ell_p$ regression experiment with $p=1.5$ over the $\ell_2$-ball and record, at each outer iteration, the running maximum of the local Lipschitz estimates and the primal gap. If that running maximum grows faster than quadratically in the iteration count, or the primal gap does not follow the claimed $O(1/k^2)$ decay, then the acceleration guarantee as stated does not hold in that regime.
Extended reading notes
Core claim
The central claim is that acceleration does not require a projection oracle or a line search when the feasible set is served by a linear minimization oracle. AdCGS maintains an accelerated outer iterate and, at each step, approximately solves the strongly convex subproblem $\min_{z\in P}\{\langle\nabla f(x_{k-1}), z\rangle + \frac{1}{2\eta_k}\|z-y_{k-1}\|^2\}$ by inner conditional-gradient iterations stopped at FW-gap tolerance $\delta_k$. Its stepsizes $\eta_k$ are computed from local Lipschitz estimates, so no global smoothness constant is needed. With the announced schedules, the paper proves $f(x_k)-f(x^*) \le 12\hat L_k R_1/(k(k+1))$, an $O(1/k^2)$ rate when $\hat L_k$ is bounded; and for strongly convex objectives, restarting the method gives $f(w_s)-f(x^*) \le \phi_0/2^s$, linear convergence with no polytope, strongly convex, or uniformly convex assumption on the constraint set.
Load-bearing premise
The central assumption is that the running maximum of the local gradient-smoothness estimates stays bounded or grows slowly along the iterate path; the paper proves this for globally smooth objectives, but gives no proof of it for the non-smooth $\ell_p$ regression experiments with $1<p<2$.
Editorial extensions
If this is right
- For convex $L$-smooth objectives, AdCGS reaches $f(x_k)-f(x^*) \le 12\hat L_k R_1/(k(k+1))$; when $\hat L_k$ is bounded by $L$, this is the projection-free analogue of the standard accelerated $O(1/k^2)$ rate.
- No global smoothness constant or line search is required: stepsizes come from local Lipschitz estimates, leaving only an initial stepsize and the momentum parameter $\beta$ to choose.
- The explicit tolerance schedules, $\delta_k = D_0^2/(k^{1+\theta}(k+1))$ or $\delta_k = D_0^2/(Nk)$ for a fixed horizon, keep the accumulated error from inexact inner solves bounded, so acceleration is not lost to approximation.
- For strongly convex objectives, restarting AdCGS yields $f(w_s)-f(x^*) \le \phi_0/2^s$, a linear rate with no polytope, strongly convex, or uniformly convex assumption on the feasible set; the total LMO count is $O(\mu L D^2/\epsilon)$.
Reading between the lines
- Beyond the paper, the same adaptive-stepsizes-plus-inexactness trade-off could be carried into stochastic or variance-reduced conditional-gradient methods, where inner tolerances are usually fixed; adaptive tolerances there might preserve acceleration without a projection oracle.
- Beyond the paper, tracking the running maximum $\hat L_k$ on the non-smooth $\ell_p$ experiments would decide whether the $O(1/k^2)$ claim holds there: slow growth would suggest a Hölder-smoothness analysis could recover the rate, while fast growth would confine the advertised acceleration to smooth objectives.
- Beyond the paper, the strong-convexity result is best read as linear convergence in gradient calls: the theorem's own LMO bound is $O(\mu L D^2/\epsilon)$, so total oracle work is not logarithmic, and applications dominated by LMO cost would still need geometry-specific analyses for better LMO bounds.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies convex minimization over a compact convex set when projections are expensive but a linear minimization oracle (LMO) is available. It proposes AdCGS, an accelerated conditional-gradient sliding method that combines the accelerated outer scheme of CGS with adaptive stepsizes based on local Lipschitz estimates, following AC-FGM. The inner subproblems are solved inexactly by a Frank-Wolfe-type loop with a prescribed FW-gap tolerance, and the paper analyzes the resulting accumulated error. The theoretical part states a one-step inequality, a general bound in terms of the accumulated error, and corollaries giving O(1/k^2) rates for convex objectives and linear contraction in outer stages for strongly convex objectives, together with oracle-complexity counts. Experiments on least squares, ℓ_p regression, and logistic regression compare AdCGS with CGS, AC-CGM, ACG, and AC-FGM.
Significance. If the quantitative statements are corrected, this is a solid contribution: it extends line-search-free adaptive acceleration to the projection-free LMO model, with explicit control of inexact inner solves and full proofs in the appendices. The main novelty is the combination of known machinery rather than a new conceptual mechanism, and the strongly convex result is weaker than a fully linear LMO complexity; nevertheless, an LMO-only, line-search-free method with O(1/k^2) rates would be of genuine interest to the optimization community. The current manuscript has several errors in the displayed constants, an unsupported nonsmooth claim, and a questionable LMO-complexity statement in Theorem 4.1, so it cannot be accepted in its present form.
major comments (3)
- [Corollary 3.3, Corollary 3.5, Corollary 3.6] The displayed constants in the convex-rate corollaries are not consequences of the stated lower bound on eta_k. Theorem 3.2 gives f(x_k)-f(x*) <= (E+S_k)/((tau_k+1) eta_{k+1}), and the proof of Corollary 3.3 establishes only eta_{k+1} >= (k+1)/(12 hat L_k). With tau_k = k/2 this yields the reciprocal 24 hat L_k / ((k+1)(k+2)), not the claimed 12 hat L_k / (k(k+1)); the claimed constant is smaller by the factor (k+2)/(2k). The same factor-2 discrepancy appears in the second display of Corollary 3.3 and in Corollary 3.5. Corollary 3.6 overstates by a factor 2 as well: eta_{k+1} >= (3+alpha(k-2))/(12 hat L_k) and tau_k+1 >= (alpha k + 4 - 2alpha)/2 support only 24 hat L_k / ((alpha k + 4 - 2alpha)(alpha k + 3 - 2alpha)), not 12 hat L_k over the same product. Since the asymptotic O(1/k^2) rate is unaffected, these are correctable errors, but the proofs as written do not establish the displayed bounds.
- [Section 5.2 and Corollaries 3.3-3.6] The claim that "AdCGS does not rely on local L-smoothness" is unsupported. For the ell_p loss with 1 < p < 2, the gradient is not Lipschitz on any neighborhood, and the quotient in Eq. (4) is not bounded a priori: near a zero residual it can scale like ||x_k - x_{k-1}||^{p-2}, which diverges as the iterates approach each other. The corollaries express all rates through hat L_k, the running maximum of the local Lipschitz estimates, and the paper provides no bound on hat L_k or on its growth for these problems. If hat L_k grows faster than k^2, the displayed O(1/k^2) guarantees do not apply. The authors should either add an analysis for Hölder-smooth objectives with explicit control of hat L_k or remove the unsupported nonsmooth claim.
- [Theorem 4.1 and Appendix A.6] The LMO complexity bound stated in Theorem 4.1 is not supported by the proof and appears to miss a factor of L/mu. From the proof, T_{s,k} <= 36 mu L D^2 2^s N / phi_0, and summing over k and s gives a leading term of order mu L D^2 N^2 2^S / phi_0. Since the chosen N satisfies N^2 ≈ 15 gamma L (1/(beta(1-beta)) + (3/2) eta_1) / mu and 2^S is of order phi_0/epsilon, this leading term is O(gamma L^2 D^2 / epsilon), not O(mu L D^2 / epsilon). More importantly, this confirms that the strong-convexity result is not linear convergence in the LMO oracle model: the total number of LMO calls remains O(1/epsilon). The abstract and the contribution list should be qualified so that "linear convergence" refers to outer stages and gradient evaluations, not to the projection-free oracle complexity.
minor comments (4)
- [Algorithm 1 and Eq. (3)] The initialization is not fully specified: Eq. (3) requires x_1 != x_0, but Algorithm 1 does not state how x_1 is generated before L_1 is computed; please clarify the role of eta_1 and of the auxiliary point z_{-1} in Eq. (11) in the main loop.
- [Corollary 3.5] The proof of Corollary 3.5 uses delta_{N+1} inside S_N, but delta_k is only defined for k <= N; please extend the definition to k = 1, ..., N+1 or otherwise adjust the summation.
- [Algorithm 3] In Algorithm 3, the user-supplied eta_1 is used in the definition of N, but Algorithm 2's line search may return a different eta_1; please explain how the line-searched eta_1 enters the stage length N, or state that N is computed with the line-searched value.
- [Section 5] The experimental labels AdCGS, AdCGS:0.5, AdCGS:0.1, and AdCGS:0.0 refer to alpha values, but Algorithm 1 is stated for generic parameter sequences; please state explicitly that the implementation follows Corollary 3.6 (or Corollary 3.3 with matching tau_k) for each alpha.
Circularity Check
No load-bearing circularity; adaptive rates are proven rather than fitted, with only a background self-citation.
full rationale
AdCGS's central claim—accelerated O(1/k^2) rates with only an LMO and adaptive, line-search-free stepsizes—does not reduce to its inputs. The local Lipschitz estimates L_k are defined in Eqs. (3)-(4) from successive gradients and iterates; they are empirical quantities that enter the stepsize rule, not parameters fitted to the target convergence rate. The one-step inequality (Prop. 3.1) is proved from the FW-gap inexactness and the accelerated recursion; the D_i bounding in Thm. 3.2 and the S_k accumulation bounds in Corollaries 3.3/3.5/3.6 are carried out explicitly in the appendices. The method borrows the CGS and AC-FGM templates from Lan-Zhou (2016) and Li-Lan (2025), but those are external published results with independent proofs; no load-bearing step is justified by the authors' own prior work. The only self-citation (Takahashi et al. 2026) occurs in a related-work sentence about adaptive Bregman step sizes and is not used to establish any theorem. The reviewer-flagged constant discrepancy in Corollary 3.3 is a genuine proof issue—from tau_k=k/2 and eta_{k+1} >= (k+1)/(12 \hat L_k), the reciprocal denominator should be (k+1)(k+2)/(24 \hat L_k), not k(k+1)/(12 \hat L_k)—but this is a correctable numerical slip affecting only the constant, and the O(1/k^2) rate is unaffected; a constant error is not circularity. Similarly, the claim that AdCGS 'does not rely on local L-smoothness' is unsupported for the non-smooth ell-p experiments because \hat L_k could grow, but this is an assumption/verification gap, not a definitional equivalence. Overall the derivation is self-contained and not circular.
Assumptions & free parameters
free parameters (8)
- beta =
1 - sqrt(6)/3 in experiments; allowed in (0, 1 - sqrt(6)/3]
- theta =
1e-3 in experiments; theta > 0 in theory
- alpha =
1.0, 0.5, 0.1, 0.0 in experiments
- eta_1 =
2/(5 L0) in experiments
- L0 =
estimated from a perturbation z_{-1} via Eq. (11)
- D0 or D =
D (diameter of P) used in experiments; D0 unknown in theory
- gamma =
line-search growth factor in Algorithm 2
- mu, L, phi_0 =
assumed known in Algorithm 3
assumptions (6)
- domain assumption P is compact and convex; f is convex and continuously differentiable on R^n
- domain assumption Access to exact first-order oracle and linear minimization oracle; projections may be unavailable
- domain assumption The empirical local Lipschitz estimates L_k are finite and do not grow faster than the iteration index squared; equivalently f is L-smooth on P for uniform rates
- domain assumption For Algorithm 3, f is mu-strongly convex and locally L-smooth, and mu, L, phi_0 are known
- standard math Standard analytic bounds: Young's inequality, Cauchy-Schwarz, integral test, convexity of f
- ad hoc to paper x_1 differs from x_0 so that L_1 in Eq. (3) is well-defined
Cite this review
Pith. "Pith review of Adaptive Conditional Gradient Sliding: Projection-Free and Line-Search-Free Acceleration." pith.science (2026). https://pith.science/paper/SUADJKTM
@misc{pith2026260120443,
author = {Pith},
title = {Pith review of: Adaptive Conditional Gradient Sliding: Projection-Free and Line-Search-Free Acceleration},
year = {2026},
howpublished = {\url{https://pith.science/paper/SUADJKTM}},
note = {Machine review of arXiv:2601.20443}
}
abstract
We study convex optimization problems over a compact convex set where projections are expensive but a linear minimization oracle (LMO) is available. We propose the adaptive conditional gradient sliding method (AdCGS), a projection-free and line-search-free method that retains Nesterov's acceleration with adaptive stepsizes based on local Lipschitz estimates. AdCGS combines an accelerated outer scheme with an LMO-based inner routine. It reuses gradients across multiple LMO calls to reduce gradient evaluations, while controlling the subproblem inexactness via a prescribed accuracy level coupled with adaptive stepsizes. We prove accelerated rates for convex objective functions, matching projection-based methods, without relying on a projection oracle. For locally strongly convex objective functions, we further establish linear convergence without additional geometric assumptions on the constraint set, such as polytopes or strongly convex sets. Experiments on constrained $\ell_p$ regression, logistic regression, and least-squares problems demonstrate that AdCGS improves over projection-free baselines and provides competitive performance when projections are inexpensive.
Figures
Figures from the paper (7 more)
Reference graph
Works this paper leans on
-
[2]
Then, for any j∈{ 1,...,k }, it holds that ζk≤ Λk 0 @ 1−λj Λj ζj−1 + kX i=j νi Λi 1 A
Suppose that Λt > 0 for all t≥ 2 and the sequence {ζt} satisfies, for any t≥ 1 and a sequence {νt}, ζt≤ (1−λt)ζt−1 +νt. Then, for any j∈{ 1,...,k }, it holds that ζk≤ Λk 0 @ 1−λj Λj ζj−1 + kX i=j νi Λi 1 A. (14) The proof follows the same argument as that of ( Lan and Zhou , 2016, Theorem 2.2(c)). We include it here for completeness and to keep the presen...
work page 2016
-
[4]
A. Khademi and A. Silveti-Falls. Adaptive conditional gradient descent. arXiv preprint arXiv:2510.11440,
-
[11]
Furthermore, define xk = Pk−1 i=1 (τi + 1)ηi+1−τi+1ηi+2 xi + (τk + 1)ηk+1xk Pk+1 i=2 ηi
Therefore, f (xk)−f (x∗)≤ 1 (τk + 1)ηk+1 1 2β∥z0−x∗∥2 + 5η2L1 4 − η2 2η1 ∥z1−z0∥2 + kX i=1 ηi+1(δi+1 +δi) ! . Furthermore, define xk = Pk−1 i=1 (τi + 1)ηi+1−τi+1ηi+2 xi + (τk + 1)ηk+1xk Pk+1 i=2 ηi . SincePk−1 i=1 (τi + 1)ηi+1−τi+1ηi+2 + (τk + 1)ηk+1 =Pk+1 i=2 ηi, we obtain f (xk)−f (x∗)≤ 1 Pk+1 i=2 ηi 1 2β∥z0−x∗∥2 + 5η2L1 4 − η2 2η1 ∥z1−z0∥2 + kX i=1 ηi+...
work page 2025
-
[26]
We have the desired result by rearranging it
for i = 3,...,k + 1, and using τ1 = 0 and βi =β for i≥ 2, we obtain kX i=1 ηi+1 τif (xi) +⟨∇f (xi), xi−z⟩− τif (xi−1)− (δi+1 +δi) + η2 2η1 ∥z1−y1∥2 +∥z2−z1∥2 ≤ 1 2β∥y1−z∥2− 1 2β∥yk+1−z∥2 + k+1X i=2 Di, where, for any i≥ 2, Di :=ηi⟨∇f (xi−1)−∇f (xi−2),z i−1−zi⟩− ηiτi−1 2Li−1 ∥∇f (xi−1)−∇f (xi−2)∥2− 1 2∥zi−yi−1∥2. We have the desired result by rearranging i...
work page 2025
-
[1956]
D. Garber. Accelerated Frank-Wolfe algorithms: Complementarity conditions and sparsity. arXiv preprint arXiv:2511.02821 ,
-
[2008]
S. Yagishita and M. Ito. Simple linesearch-free first-order methods for nonconvex optimization. arXiv preprint arXiv:2509.14670 ,
-
[2015]
G. Lan. The complexity of large-scale convex programming under a linear optimization oracle. arXiv preprint arXiv:1309.5550 ,
-
[2019]
PMLR. T. Kerdreux, A. d’Aspremont, and S. Pokutta. Local and global uniform convexity conditions. arXiv preprint arXiv:2102.05134 , 2021a. T. Kerdreux, A. d’Aspremont, and S. Pokutta. Projection-free optimization on uniformly convex sets. In A. Banerjee and K. Fukumizu, editors, Proc. 24th Int. Conf. Artif. Intell. Stat. , volume 130 of PMLR, pages 19–27,...
Show all 11 references
-
[2022]
Borodich and D
12 E. Borodich and D. Kovalev. Nesterov finds GRAAL: Optimal and adaptive gradient method for convex optimization. arXiv preprint arXiv:2507.09823 ,
-
[2024]
J. J. Suh and S. Ma. An adaptive and parameter-free Nesterov’s accelerated gradient method for convex optimization. arXiv preprint arXiv:2505.11670 ,
-
[2025]
Lemma A.1 ((Lan and Zhou , 2016, Lemma 2.1))
14 A Proofs of Theoretical Results A.1 Proof of Theorem 2.1 The following lemma will be useful in the analysis. Lemma A.1 ((Lan and Zhou , 2016, Lemma 2.1)) . Letλt∈ (0, 1], t = 1, 2,... and let Λt = ( 1, if t = 1, (1−λt)Λt−1, if t≥
2016
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.