{"id":"5ce3259a-726a-4da7-896a-b88a5066a797","arxiv_id":"2601.20443","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":8,"one_line_summary":"AdCGS combines conditional gradient sliding with adaptive local-Lipschitz stepsizes to achieve accelerated projection-free, line-search-free convergence for convex and strongly convex objectives.","lead":"This paper introduces AdCGS, an optimization algorithm that accelerates conditional gradient methods without needing projections, line searches, or a known global smoothness constant. It reports O(1/k^2) convergence for convex problems and linear convergence for strongly convex problems, backed by experiments on regression tasks.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 3.3's O(1/k^2) bound is stronger than the stated eta_k lower bound supports; the displayed constant needs correction, although the asymptotic rate survives.","rationale":"The reader's weakest_assumption concerns growth of \\hat L_k for non-smooth ell_p objectives; that is a scope issue for the experimental claim, but the core O(1/k^2) theorem for smooth f is not endangered by it. The genuinely load-bearing issue I find is internal: the displayed constants in Corollary 3.3 do not follow from the paper's own lower bound on eta_k. The algebra is straightforward: with tau_k = k/2, the denominator in Theorem 3.2 is at least (k+1)(k+2)/(24 \\hat L_k), giving a reciprocal of 24 \\hat L_k / ((k+1)(k+2)); the corollary claims 12 \\hat L_k / (k(k+1)), which is smaller for all k > 2. The lower bound on eta_k is tight, achieved when all L_i are equal, so the failure is not an artifact of a loose intermediate step. The same factor issue affects the averaged-iterate bound. The asymptotic rate O(1/k^2) survives, so this does not overturn the main contribution, but it means the proof as written is not correct and the constants must be revised. I therefore keep the reader's CONDITIONAL verdict.","tokens_in":20093,"tokens_out":30042,"duration_ms":256166,"concrete_test":"Re-derive Eq. (9) of Corollary 3.3 from Theorem 3.2 by substituting tau_k = k/2 and the lower bound eta_{k+1} >= (k+1)/(12 \\hat L_k); check whether 1/((tau_k+1)eta_{k+1}) <= 12 \\hat L_k / (k(k+1)) can hold for all k>=2. Then instantiate the extreme case L_i = 1, choose eta_1 so that eta_2 = 1/4, run the Corollary 3.3 recurrence for k = 2 through 100, and compare the computed 1/((k/2+1)eta_{k+1}) with 12/(k(k+1)). If the former exceeds the latter for k > 2, the displayed bound is false as stated and the proof must be corrected.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The main convex-rate corollary is not a consequence of the stated lemmas. Theorem 3.2 bounds f(x_k)-f(x*) by (E+S_k)/((tau_k+1)eta_{k+1}). Corollary 3.3 sets tau_k = k/2 for k>=2 and proves, in Appendix A.4, that eta_{k+1} >= (k+1)/(12 \\hat L_k). Therefore (tau_k+1)eta_{k+1} >= (k/2+1)(k+1)/(12 \\hat L_k) = (k+1)(k+2)/(24 \\hat L_k), so the tightest reciprocal available from the stated lower bound is 24 \\hat L_k / ((k+1)(k+2)), not the claimed 12 \\hat L_k / (k(k+1)). The claimed constant is smaller by a factor (k+2)/(2k) > 1 for every k > 2. The lower bound is tight: with L_i identical to L, the recurrence gives eta_{k+1} = (k+1)/(12L) exactly for k>=4, so the corollary's first display fails numerically in this extreme case. The averaged-iterate bound in (10) has a similar factor issue. Since the rate remains O(1/k^2), this is a correctable error rather than a refutation, but the proof as written does not establish the displayed constant.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":20355,"tokens_out":19264,"duration_ms":154249,"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":[{"comment":"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":"Corollary 3.3, Corollary 3.5, Corollary 3.6"},{"comment":"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.","section":"Section 5.2 and Corollaries 3.3-3.6"},{"comment":"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.","section":"Theorem 4.1 and Appendix A.6"}],"minor_comments":[{"comment":"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.","section":"Algorithm 1 and Eq. (3)"},{"comment":"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.","section":"Corollary 3.5"},{"comment":"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":"Algorithm 3"},{"comment":"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.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"The paper's core idea is a combination of the CGS framework of Lan-Zhou and the adaptive stepsizes of Li-Lan; the novelty is incremental but reasonable for a journal paper. The main barriers are the incorrect constants in the main corollaries, the unsupported nonsmooth claim in Section 5.2, and the LMO-complexity statement in Theorem 4.1. These are fixable corrections rather than a refutation of the central asymptotic rates, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a genuine and useful combination—conditional gradient sliding with AC-FGM's adaptive stepsize rule, plus an analysis of how the inexact inner solves interact with the adaptive schedule. The advertised rates are real: O(1/k^2) for smooth convex and linear convergence for strongly convex in terms of outer iterations. The paper deserves a serious referee. But the main convex-rate corollary has a constant that does not follow from the proof as written, and the experiments on nonsmooth ℓ_p objectives are outside the stated theory.\n\nWhat is new: Lan and Zhou's CGS gives acceleration with an LMO but needs the global smoothness constant. Li and Lan's AC-FGM removes that for the projected case. This paper closes the combination gap: an LMO-based method with local Lipschitz stepsizes and no line search. The proof machinery is mostly lifted from the two source papers, but the coupling between adaptive stepsizes and inner FW-gap tolerances is not trivial, and the termination schedule for δ_k is worked out carefully. The numerical results on least squares and logistic regression look reasonable.\n\nSoft spots, in order of severity:\n\n1. Corollary 3.3's constant is off. Theorem 3.2 gives f(x_k)−f(x*) ≤ (E+S_k)/((τ_k+1)η_{k+1}). With τ_k = k/2 and the proven η_{k+1} ≥ (k+1)/(12 L̂_k), the denominator is at least (k+1)(k+2)/(24 L̂_k), so the tightest reciprocal is 24 L̂_k/((k+1)(k+2)), not 12 L̂_k/(k(k+1)). The displayed constant is smaller by a factor (k+2)/(2k) > 1 for all k > 2. The lower bound is tight when the L_k are equal, so this is a real arithmetic error in the statement, not just loose analysis. The asymptotic rate survives, but the exact constant needs correction.\n\n2. The \"linear convergence\" headline is generous. The method is linearly convergent in outer stages, yes, but the total LMO calls are O(µLD²/ε), not O(log(1/ε)). The paper does state this in Theorem 4.1, but the abstract and conclusion overstate.\n\n3. The ℓ_p experiments with 1 < p < 2 run the method on a problem where the gradient is not Lipschitz. The paper claims AdCGS does not rely on local L-smoothness, but the corollaries produce rates depending on L̂_k, and nothing bounds L̂_k for such objectives. The experiments are fine as empirical demonstrations, but the claim needs qualification or a separate analysis.\n\nMinor: the initialization x1 ≠ x0 has an unhandled edge case if x1 = x0; the paper does not ship code.\n\nBottom line: this is a sound extension with a buggy constant and an overclaimed nonsmooth applicability. A focused revision can fix both. I would send it to review—major revision—and cite it once the constant is fixed.","headline":"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.","tokens_in":20917,"tokens_out":4554,"would_cite":true,"duration_ms":36852,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C06"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["conditional gradient","Frank–Wolfe","projection-free optimization","adaptive stepsizes","local Lipschitz estimates","accelerated gradient methods","linear minimization oracle","convex optimization"],"falsifier":"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.","tokens_in":19807,"feed_emoji":"⚡","tokens_out":18382,"duration_ms":138988,"temperature":0.7,"pith_summary":"This paper asks whether accelerated convergence can coexist with projection-free, line-search-free updates. It answers yes with AdCGS, an adaptive conditional gradient sliding method that couples an accelerated outer scheme with inner linear-minimization loops. The paper proves $O(1/k^2)$ convergence for convex objectives, matching projection-based accelerated methods, and linear convergence for strongly convex objectives without geometric assumptions on the feasible set. This matters in large-scale optimization when projections are expensive but linear minimization is cheap, and when a global smoothness constant is unavailable or hard to estimate.","feed_headline":"Projection-free method reaches O(1/k²) with no line search","feed_subtitle":"Adaptive local-Lipschitz stepsizes preserve the accelerated convex rate and give strong-convex linear rates.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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)$."],"supporting_citations":[{"why":"Supplies the conditional gradient sliding framework—an accelerated outer loop over inner CG loops—and the inner-loop iteration-count lemma used in Theorem 2.1.","marker":"(Lan and Zhou, 2016)"},{"why":"Supplies AC-FGM's adaptive local-Lipschitz stepsize rule and the one-step inequality whose telescoping is the backbone of the convergence proofs.","marker":"(Li and Lan, 2025)"},{"why":"Provides the accelerated gradient framework and the $O(1/k^2)$ rate that AdCGS aims to match without projections.","marker":"(Nesterov, 1983; 2018)"},{"why":"Introduces the conditional-gradient iteration and LMO that AdCGS is built on and accelerates.","marker":"(Frank and Wolfe, 1956)"},{"why":"Shows global linear convergence of FW variants over polytopes, the geometric assumption the strong-convexity result removes.","marker":"(Lacoste-Julien and Jaggi, 2015)"},{"why":"Proves faster FW rates over strongly convex sets, another geometric assumption the paper's linear-convergence theorem bypasses.","marker":"(Garber and Hazan, 2015)"},{"why":"Extends linear convergence to uniformly convex sets, used as a contrast point for the geometry-free strong-convexity claim.","marker":"(Kerdreux et al., 2021b)"}],"fun_headline_variants":["Projection-free and line-search-free acceleration with adaptive steps","AdCGS: no projection, no line search, still O(1/k²)","Linear convergence for strongly convex without geometric assumptions","Adaptive steps replace line search in projection-free sliding method","Gradient sliding achieves accelerated rates with only LMO"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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