{"id":"f106a2d0-9091-4e26-8775-409959555bfc","arxiv_id":"2505.09886","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Frank-Wolfe with the log-adaptive step-size η_t=(2+log(t+1))/(t+2+log(t+1)) provably matches or beats fixed-ℓ open-loop step-sizes in several convergence regimes.","lead":"The paper proves that the Frank-Wolfe optimization algorithm with a simple log-adaptive step-size converges at least as fast as any fixed-parameter step-size, up to log factors, under standard growth conditions. The result offers practitioners a parameter-free default step-size for projection-free constrained convex optimization.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Step 2b of Theorem 3.2 contains an invalid maximization for the subcase g(S)-epsilon < 1/(1-r), leaving the general theorem unproven as printed; the log-adaptive headline avoids this branch but the proof needs repair.","rationale":"The paper's main contribution is a parameter-free log-adaptive open-loop step-size whose proven rates match or beat all fixed-ell rules under the stated growth assumptions. The proof strategy is coherent, and the specific log-adaptive instantiation in Theorem 3.2 is designed so that g(S)-epsilon >= 1/(1-r), which sidesteps the broken subcase in Step 2b. Thus the headline rate O~(t^{-1/(1-r)}) appears sound, and the reported numerical behavior is consistent with the theory. The most load-bearing concern is that Theorem 3.2 as stated is not fully proven as printed: the maximization in Case 2b is invalid for the subcase g(S)-epsilon < 1/(1-r), and a reader cannot verify the general theorem or the fixed-ell comparison from the new blueprint without repairing that step. The repair is a short analytic argument, so this is a proof gap rather than a false conclusion. The secondary endpoint issue, strong (M,1), is also real but separate: the theorem explicitly excludes r = 1 while Table 1 and the abstract claim rates for that endpoint. Both issues are fixable and do not overturn the central claim, so the conditional verdict stands unchanged.","tokens_in":14946,"tokens_out":16794,"duration_ms":153628,"concrete_test":"Re-derive the maximization in Step 2b of Theorem 3.2: for a = g(S)-epsilon, b = 1/(1-r), and q = g(R)-epsilon, verify that max_{R in {S,...,t}} eta_t^q / eta_{R-1}^{q-b} <= eta_t^{min{a,b}} by splitting into the cases q < b and q >= b. If this inequality holds, replace the displayed branch in the proof and check the rest of the induction; if it fails, Theorem 3.2's general statement is false. Separately, attempt the same induction for r = 1; if no proof is supplied, amend Table 1 and the abstract to restrict the 'arbitrarily fast' claim to r < 1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central technical assertion is Theorem 3.2. In Case 2b, after applying the cumulative-product bound, the proof must control max_{R in {S,...,t}} (M g(R-1)/(2 epsilon))^{1/(1-r)} eta_t^{g(R)-epsilon} / eta_{R-1}^{g(R)-epsilon - 1/(1-r)}. Let a = g(S)-epsilon and b = 1/(1-r). For each R, q = g(R)-epsilon >= a. If q >= b, then eta_t^q / eta_{R-1}^{q-b} <= eta_t^b. If q < b, the exponent q-b is negative, so eta_t^q / eta_{R-1}^{q-b} = eta_t^q * eta_{R-1}^{b-q} <= eta_t^q <= eta_t^a. Thus the correct bound is eta_t^{min{a,b}}. However, the proof as printed states that in the subcase a < b the maximum equals eta_t^a / eta_{S-1}^{a-b}, which is >= eta_t^a because a-b < 0 and eta_{S-1} <= 1; this cannot imply the claimed upper bound. Consequently the general statement of Theorem 3.2 is not established by the printed proof in that subcase. The advertised log-adaptive rate O~(t^{-1/(1-r)}) is not directly affected, because the chosen S = ceil(exp(1/(1-r))) with epsilon = 1 forces g(S)-epsilon >= 1/(1-r)+1, so only the q >= b branch is used; but a reader relying on the full theorem cannot verify it without the corrected maximization. A separate gap is that Table 1 and the abstract claim strong (M,1) rates O~(t^{-k}) although Theorem 3.2 is stated only for r in [0,1); either the endpoint needs its own proof or the claim must be qualified.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Frank-Wolfe algorithm with open-loop step-sizes of the form η_t = g(t)/(t+g(t)) for a non-decreasing function g satisfying two structural assumptions (A1 and A2). Its main results are Theorem 3.2, an affine-invariant bound on the primal-dual gap under the strong (M,r)-growth property, and Theorem 4.1, an analogous bound on the suboptimality gap under the weak (M,r)-growth property together with strong (M,0)-growth. The authors propose the log-adaptive rule g(t)=2+log(t+1) and show that it achieves O~(t^{-1/(1-r)}) in the strong case and O~(t^{-1/(1-r)}+t^{-2}) in the weak case, matching or exceeding every fixed-ℓ rule η_t=ℓ/(t+ℓ) up to polylogarithmic factors. Numerical experiments on constrained regression and collaborative filtering, together with an implementation in FrankWolfe.jl, illustrate the proposed rule.","tokens_in":15303,"tokens_out":29219,"duration_ms":251523,"significance":"The central contribution is a clean extension of the cumulative-product technique of Wirth, Pena, and Pokutta to time-varying g, with Lemma 3.1 as a self-contained strengthening that appears to be new. If the (M,1) endpoint is resolved, the log-adaptive step-size is a genuinely attractive default: it requires no tuning of ℓ, is affine-covariant, and its analysis covers all r∈[0,1) and the weak-growth case up to the natural O(t^{-2}) cap. The paper is also commendable for shipping reproducible code and integrating the rule into FrankWolfe.jl, which lowers the barrier to adoption. The main caveat is that the advertised arbitrarily-fast rates in the strong (M,1) case are not covered by Theorem 3.2 as stated.","major_comments":[{"comment":"Table 1, the introduction, and the abstract's 'at least as fast as every fixed-ℓ rule' claim cover the strong (M,1)-growth endpoint, where the table reports O~(t^{-k}) for every k∈N and attributes this to Theorem 3.2. However, Theorem 3.2 is stated for r∈[0,1[ and its proof uses the exponent 1/(1-r), which is undefined at r=1; no separate endpoint argument is given. This is load-bearing because the arbitrarily-fast-sublinear statement for (M,1) is part of the headline comparison with fixed-ℓ rules. Please either prove the endpoint (for instance by a dedicated induction replacing 1/(1-r) with an arbitrary k) or explicitly restrict the claims and Table 1 to r∈[0,1).","section":"Table 1 and Theorem 3.2"}],"minor_comments":[{"comment":"In the subcase g(S)-ε ≥ 1/(1-r), the displayed equality for the maximum over R is not correct as an equality; the maximum is attained at R=t and equals η_t^{g(S)-ε}/η_{t-1}^{g(S)-ε-1/(1-r)}, which is at most η_t^{1/(1-r)}. Replacing the '=' by '≤' (or bounding the maximum directly) fixes the display, and the final bound is unaffected.","section":"§3, proof of Theorem 3.2, Case 2b"},{"comment":"The displayed 'New cumulative product bound' in Section 2.2 uses ε/g(t) inside the product, while Lemma 3.1 and the subsequent proofs use ε/g(i); these should be made consistent.","section":"§2.2, blueprint product bound"},{"comment":"The statement says g:R_{\\ge0}→R_{\\ge0}, but Assumptions A1/A2 and the arguments of g are on N and require g(i)≥2; also, the 'In particular' case uses g(t)=2+log(t), while the log-adaptive rule elsewhere is g(t)=2+log(t+1). Align these notations.","section":"Theorem 4.1 statement"},{"comment":"The figures show single runs without error bars or multiple restarts, so the visual 'at least as fast' comparisons should be read as illustrative; adding a brief note on this would strengthen reproducibility.","section":"§5, numerical experiments"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a direct continuation of the authors' own [50,51], and the log-adaptive rule itself is already mentioned in [44]; the novelty is primarily analytical. I would not treat this as a reason to reject; the strengthened product bound and the general-g analysis are worth publishing once the endpoint-claim gap is fixed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know this paper gives the Frank-Wolfe community a genuinely useful new default: the log-adaptive step-size η_t = (2+log(t+1))/(t+2+log(t+1)). It provably matches, up to polylog factors, every fixed-ℓ open-loop rule in the strong and weak growth settings, and it removes the need to pick ℓ. That is a real contribution, and the extension to general g(t)/(t+g(t)) step-sizes under Assumptions A1–A2 is the right way to organize the analysis. The proofs are mostly self-contained, Lemma 3.1 is correct, and the numerical experiments are consistent with the theory. The software integration in FrankWolfe.jl is a nice touch.\n\nThe soft spots are real but fixable. The proof of Theorem 3.2, Case 2b, has an exponent bug: the displayed maximum uses g(S)−ε where it should use g(R)−ε. With that typo, the subcase g(S)−ε < 1/(1−r) is not actually bounded by η_t^{min{·,·}}. The stress-test note is right that the correct case analysis gives η_t^{min{a,b}}, so the theorem is repairable, but the printed proof does not establish it as written. Importantly, the advertised log-adaptive rate O~(t^{−1/(1−r)}) sidesteps this branch by choosing S and ε so that g(S)−ε ≥ 1/(1−r), so the main headline survives. A second gap: Table 1 and the abstract claim strong (M,1) rates O~(t^{−k}) for every k, but Theorem 3.2 is stated for r ∈ [0,1). The endpoint r=1 needs its own argument or a clear qualifier. The collaborative filtering experiments are explicitly labeled in Remark 5.1 as not known to satisfy the growth assumptions; treat those as suggestive, not evidence.\n\nOverall: the central idea is sound, the contribution is new (the step-size itself was mentioned in [44], but without rates), and the flaws are a typo and a missing endpoint case. This paper deserves a serious referee; with those two fixes it should be accepted. I would cite it if I work on FW step-size rules, and I'd bring it to a reading group as a good example of a practical theory paper.","headline":"A useful new default step-size for Frank-Wolfe, with a fixable proof bug in the general theorem and an unproven endpoint claim.","tokens_in":15916,"tokens_out":3420,"would_cite":true,"duration_ms":32685,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C30","65K05","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"The log-adaptive Frank-Wolfe step-size dominates every fixed parameter rule.","keywords":["Frank-Wolfe algorithm","open-loop step-sizes","log-adaptive step-size","growth property","accelerated convergence rates","primal-dual gap","conditional gradients","constrained convex optimization"],"falsifier":"Run FW with the log-adaptive step-size on constrained least squares over an $\\ell_2$-ball with the unconstrained optimum outside the ball, which is a strong $(M,1)$-growth instance; Theorem 3.2 predicts that primaldualt decays faster than any fixed polynomial. If the observed curve instead levels off at the $O(t^{-2})$ or $O(t^{-1})$ slope exhibited by fixed-$\\ell$ rules, the central claim is wrong. A more direct check is to compute the tail product in Lemma 3.1 numerically for $g(t)=2+\\log(t+1)$ and verify the stated inequality for large $t$; any violation would pinpoint the proof step.","tokens_in":14664,"feed_emoji":"📉","tokens_out":7152,"duration_ms":65943,"temperature":0.7,"pith_summary":"This paper tries to answer a practical question: which open-loop step-size should a Frank-Wolfe user pick when solving constrained convex problems? It argues that the log-adaptive rule $\\eta_t=\\frac{2+\\log(t+1)}{t+2+\\log(t+1)}$ converges at least as fast as any fixed-parameter rule $\\eta_t=\\frac{\\ell}{t+\\ell}$ with $\\ell\\ge 2$, up to polylogarithmic factors, and strictly faster in strong growth settings. To prove this, the paper generalizes earlier accelerated-rate results from fixed $\\ell$ to step-sizes $\\eta_t=\\frac{g(t)}{t+g(t)}$ for non-decreasing $g$ with non-increasing $\\eta_t$, yielding the main rates in Theorem 3.2 and Theorem 4.1. If correct, this gives a parameter-free default step-size that needs no tuning and is already implemented in a public Frank-Wolfe software package.","feed_headline":"Log-adaptive step sizes beat every fixed Frank-Wolfe rule","feed_subtitle":"A parameter-free Frank-Wolfe schedule matches or beats all fixed rules up to polylog factors.","key_machinery":"The load-bearing object is the strengthened cumulative-product bound (Lemma 3.1): for $\\eta_t=\\frac{g(t)}{t+g(t)}$ with $g$ non-decreasing, and any $S\\le t$, $\\epsilon\\in(0,g(S))$, the tail product $\\prod_{i=S}^{t}\\big(1-(1-\\frac{\\epsilon}{g(i)})\\eta_i\\big)\\le\\big(\\frac{\\eta_t}{\\eta_{S-1}}\\big)^{g(S)-\\epsilon}$. This bound replaces the fixed-$\\ell$ product bound used in earlier work and makes the decay exponent grow with $g(S)$. It is combined with the objective reduction identity $f(x+\\eta(v-x))=f(x)-\\eta\\,\\mathrm{gap}(x)+D_f(x+\\eta(v-x),x)$ and with strong or weak growth properties that control the Bregman remainder. The assumptions that $g$ is non-decreasing and that $\\eta_t$ is non-increasing are exactly what the product bound needs.","core_discovery":"The central claim is that Frank-Wolfe with the log-adaptive step-size $\\eta_t=\\frac{2+\\log(t+1)}{t+2+\\log(t+1)}$ converges at least as fast as FW with $\\eta_t=\\frac{\\ell}{t+\\ell}$ for every integer $\\ell\\ge 2$, up to polylogarithmic factors, and strictly faster in strong $(M,r)$-growth settings. Concretely, Theorem 3.2 bounds the primal-dual suboptimality gap by $O\\big(g(t-1)^{\\frac{1}{1-r}}\\eta_{t-1}^{\\min\\{g(S)-\\epsilon,\\frac{1}{1-r}\\}}\\big)$ for any admissible $g$; with $g(t)=2+\\log(t+1)$, $\\epsilon=1$, and $S=\\lceil\\exp(\\frac{1}{1-r})\\rceil$, this is $\\tilde{O}(t^{-\\frac{1}{1-r}})$, and in the strong $(M,1)$ endpoint it becomes $\\tilde{O}(t^{-k})$ for any $k$. In the weak growth setting, Theorem 4.1 gives $\\tilde{O}(t^{-\\frac{1}{1-r}}+t^{-2})$. The proof works for arbitrary non-decreasing $g$ satisfying the paper's assumptions A1 and A2, so the log-adaptive rule is one instantiation of a general family that inherits the acceleration.","pith_inferences":["Because the proof only requires $g$ non-decreasing with $\\eta_t$ non-increasing, other slowly growing choices such as $g(t)=2+\\log\\log(t+2)$ should also be covered; they would trade asymptotic rate for an even slower step-size progression, which could help when the growth constant $M$ is unknown or large.","The log-adaptive rule behaves like an open-loop proxy for closed-loop heuristics that enlarge the step size as the objective flattens; if growth constants are unknown, it may capture some of that acceleration without estimating $M$.","A natural testable extension is to combine the rule with stochastic or block-coordinate FW variants, where the Bregman term carries extra variance; the cumulative-product mechanism could still yield rate statements under an expected growth condition.","The authors flag that collaborative filtering is not yet known to satisfy the growth assumptions, so the fast rates observed in those experiments are not covered by the theorems; closing that gap would substantially widen the practical reach of the rule."],"forward_implications":["No fixed parameter $\\ell\\in\\mathbb{N}_{\\ge 2}$ can be considered optimal anymore: the log-adaptive rule matches every fixed-$\\ell$ rate up to polylogarithmic factors and beats it in strong growth settings.","In strong $(M,r)$-growth problems, the log-adaptive rule reaches $\\tilde{O}(t^{-\\frac{1}{1-r}})$, which is arbitrarily fast sublinear as $r$ approaches $1$; fixed-$\\ell$ rules only deliver $O(t^{-\\ell})$.","In weak growth settings, the log-adaptive rule achieves $\\tilde{O}(t^{-\\frac{1}{1-r}}+t^{-2})$, matching the best fixed-$\\ell$ rules up to polylogarithmic factors.","The rule needs no problem-dependent parameters, no line search, and no extra per-iteration cost, so it can serve as a drop-in default open-loop step-size.","The rate statements are affine-invariant and apply to the primal-dual gap in the strong growth setting and to the suboptimality gap in the weak growth setting."],"supporting_citations":[{"why":"Establishes the fixed-parameter open-loop step-size family that the paper uses as its baseline for comparison.","marker":"[14]"},{"why":"Introduces the strong and weak $(M,r)$-growth properties that are the assumptions under which the accelerated rates are proved.","marker":"[42]"},{"why":"Contains the remark first mentioning the log-adaptive step-size, which this paper turns into a theorem.","marker":"[44]"},{"why":"Earlier acceleration results for FW with open-loop step-sizes under growth settings that motivate seeking a universal schedule.","marker":"[50]"},{"why":"The preceding affine-invariant accelerated convergence analysis for fixed-$\\ell$ step-sizes whose technique and rates this paper extends to general $g$.","marker":"[51]"},{"why":"The software package in which the paper integrates adaptive open-loop step-sizes for practical adoption.","marker":"[6]"}],"fun_headline_variants":["Log-adaptive step sizes outrun every fixed Frank-Wolfe rule","One step-size for all: log-adaptive Frank-Wolfe accelerates without tuning","No tuning, no loss: log-adaptive Frank-Wolfe matches any fixed-parameter rate","Parameter-free Frank-Wolfe: log-adaptive step sizes dominate fixed choices","Log-adaptive steps beat all constants in Frank-Wolfe convergence"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire acceleration rests on the instance satisfying a strong or weak growth property: if the objective and feasible region do not obey one of these inequalities, only the classical $O(t^{-1})$ rate is guaranteed, and the paper's own collaborative-filtering experiments are not yet known to satisfy the assumption.","fun_headline_variants_meta":{"raw":{"variants":["Log-adaptive step sizes outrun every fixed Frank-Wolfe rule","One step-size for all: log-adaptive Frank-Wolfe accelerates without tuning","No tuning, no loss: log-adaptive Frank-Wolfe matches any fixed-parameter rate","Parameter-free Frank-Wolfe: log-adaptive step sizes dominate fixed choices","Log-adaptive steps beat all constants in Frank-Wolfe convergence"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001083,"raw_usage":{"total_tokens":4655,"prompt_tokens":1200,"completion_tokens":3455,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":816,"completion_tokens_details":{"reasoning_tokens":3352}},"tokens_in":816,"tokens_out":3455,"duration_ms":25291,"temperature":1.0,"reasoning_tokens":3352,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:22:47.916900+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run FW with the log-adaptive step-size on constrained least squares over an $\\ell_2$-ball with the unconstrained optimum outside the ball, which is a strong $(M,1)$-growth instance; Theorem 3.2 predicts that primaldualt decays faster than any fixed polynomial. If the observed curve instead levels off at the $O(t^{-2})$ or $O(t^{-1})$ slope exhibited by fixed-$\\ell$ rules, the central claim is wrong. A more direct check is to compute the tail product in Lemma 3.1 numerically for $g(t)=2+\\log(t+1)$ and verify the stated inequality for large $t$; any violation would pinpoint the proof step.","supporting_citations":[{"cited_title":"Affine invariant convergence rates of the conditional gradient method","cited_arxiv_id":null,"evidence_quote":"Introduces the strong and weak $(M,r)$-growth properties that are the assumptions under which the accelerated rates are proved."},{"cited_title":"The Frank-Wolfe algorithm: a short introduction","cited_arxiv_id":null,"evidence_quote":"Contains the remark first mentioning the log-adaptive step-size, which this paper turns into a theorem."},{"cited_title":"Acceleration of Frank- Wolfe algorithms with open-loop step-sizes","cited_arxiv_id":null,"evidence_quote":"Earlier acceleration results for FW with open-loop step-sizes under growth settings that motivate seeking a universal schedule."},{"cited_title":"Accelerated affine-invariant convergence rates of the Frank-Wolfe algorithm with open-loop step-sizes","cited_arxiv_id":null,"evidence_quote":"The preceding affine-invariant accelerated convergence analysis for fixed-$\\ell$ step-sizes whose technique and rates this paper extends to general $g$."},{"cited_title":"Frankwolfe","cited_arxiv_id":null,"evidence_quote":"The software package in which the paper integrates adaptive open-loop step-sizes for practical adoption."}],"review_version":1}