{"id":"890ac479-53e6-41eb-af11-9fb8eb1cdc15","arxiv_id":"2411.19848","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A smoothed Frank-Wolfe algorithm solves oracle-based robust optimization with 4 D^2 M^2 / eps^2 oracle calls and gives the first explicit oracle-call bound for min-max-min robust optimization.","lead":"This paper presents a Frank-Wolfe algorithm for robust optimization when the feasible region is known only through a linear optimization oracle. The method matches the best known oracle-call complexity and runs faster than constraint generation on large instances with large uncertainty sets.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 4's adaptive-smoothing bound is false: on a 1D instance with D=Mmax=1 and T=4, Algorithm 2 reaches primal gap 0.6, exceeding the claimed 0.25.","rationale":"The reader identified the projection-oracle assumption as the weakest point and accepted the paper, but I found a stronger, internal problem: Proposition 4 is false as stated. A direct 1D counterexample shows the adaptive smoothing schedule and step sizes do not deliver the claimed O(1/sqrt(T)) bound. This does not invalidate Theorem 1, whose proof and inequality chain are correct for fixed smoothing, and the oracle-model caveat raised by the reader is a legitimate limitation. However, the paper presents Proposition 4 as the theoretical basis for Algorithm 2, which is used in the experiments and described as a natural improvement. Since the proposition is demonstrably incorrect, the manuscript cannot be accepted in its current form; it needs either a corrected adaptive-smoothing analysis, a repaired schedule, or removal of the unsupported adaptive convergence claim and a corresponding adjustment of the experimental narrative. The concrete computational test above settles the matter immediately.","tokens_in":10249,"tokens_out":28831,"duration_ms":251513,"concrete_test":"Run Algorithm 2 on X=[0,1], U=[-1,1], c0=-1, D=Mmax=1, with mu_t=2/sqrt(t+1), gamma_t=2/(t+1), x0=0, T=4, and record f(x_t)=x_t. Using the natural indexing (current iterate before the update), the iterates are x1=1, x2=1, x3=1 (with the degenerate LMO tie-break v=1), x4=0.6, so the primal gap is 0.6 versus the claimed bound 0.25. If a different tie-breaking rule is used, the test should still show a violation at T=4, as the favorable v=0 at t=3 gives x4=0.7 instead.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The main fixed-smoothing Theorem 1 is sound, but Proposition 4, which underpins Algorithm 2 and the A-FW experiments, is not. Take X=[0,1], U=[-1,1], c0=-1, so D=1, Mmax=1, f(x)=max_{c in U} c x = x, and f*=0 at x=0. Run Algorithm 2 with the stated schedule mu_t=2/sqrt(t+1) and gamma_t=2/(t+1), starting at x0=0. At t=1, mu=sqrt(2), gradient at x0 is argmax -mu/2(c+1)^2 = -1, so the LMO returns v=1 and gamma=1, giving x1=1. At t=2, mu=2/sqrt(3), the gradient at x=1 is negative but still tiny, and the LMO returns v=1, so x2=1. At t=3, mu=1, the gradient at x=1 is zero; a valid LMO tie-break is v=1, giving x3=1. At t=4, mu=2/sqrt(5), the gradient at x=1 is c solving 1-mu(c+1)=0, i.e. c about 0.118, so the LMO returns v=0 and gamma=0.4, giving x4=0.6. Thus f(x4)-f*=0.6, but Proposition 4 asserts f(x_T)-f* <= D Mmax/(2 sqrt(T)) = 1/(2*2)=0.25. Even with the favorable tie-break v=0 at t=3, the t=4 iterate is 0.7, still above 0.25. This is not an oracle-model caveat; it is an incorrect convergence theorem for the adaptive smoothing algorithm, and the experimental section relies on that algorithm.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the oracle model for robust optimization problems of the form min_{x in X} max_{c in U} c^T x, where X is accessed only through a linear minimization oracle and U through a projection oracle. It introduces a smoothed Frank-Wolfe method (Algorithm 1) with fixed smoothing parameter mu=epsilon/M^2 and proves in Theorem 1 an O(D^2 M^2 / epsilon^2) iteration bound; Corollaries 2 and 3 translate this into oracle-complexity bounds, including the first explicit bound for min-max-min robust combinatorial optimization. The paper also presents an adaptive-smoothing variant (Algorithm 2), claims an O(1/sqrt(T)) convergence in Proposition 4, and reports experiments on robust spanning tree and TSP instances comparing constraint generation, fixed smoothing, adaptive smoothing, and a convex-hull-accelerated variant.","tokens_in":10642,"tokens_out":17267,"duration_ms":146234,"significance":"The fixed-smoothing part of the paper is clean and mostly self-contained: the proof of Theorem 1 balances the smoothing bias mu M^2 / 2 against the Frank-Wolfe gap 2 D^2 / (mu t), the constants are specified, and no fitted parameters enter. This gives a parameter-free oracle-complexity bound that matches the best known order and provides the first explicit oracle-call count for min-max-min problems. The paper also makes its code publicly available. The main weakness is that the adaptive-smoothing Proposition 4, on which Algorithm 2 and the A-FW experiments rest, is false as stated; a one-dimensional example violates its bound. The contribution is therefore currently conditional on the fixed-smoothing theorems, and the adaptive claims need repair before the paper can be accepted.","major_comments":[{"comment":"Proposition 4 is false as stated. Consider X=[0,1], U=[-1,1], c0=-1, so D=1, Mmax=1, f(x)=x, and f*=0. Running Algorithm 2 with mu_t=2/sqrt(t+1), gamma_t=2/(t+1), and x0=0 gives: x1=1 at t=1; x2=1 at t=2 (gradient c=-1+1/mu2 approximately -0.134); at t=3 the gradient at x=1 is zero and the LMO tie-break v=1 gives x3=1 (the alternative v=0 leads to an even worse final value); at t=4 the gradient is c=-1+1/mu4 approximately 0.118, so the LMO returns v=0 and x4=0.6. Thus f(x4)-f*=0.6, while the proposition promises D Mmax / (2 sqrt(T)) = 0.25. This is not an oracle-model caveat or a tie-break artifact; it is a violation of the stated bound by the algorithm's own update rule. The proof by direct reference to Yurtsever et al. [2018, Theorem 3.2] is therefore not valid for Algorithm 2 as written, since the hypotheses and step-size/smoothing conditions of that theorem are not verified. Because Proposition 4 is the only theoretical support for Algorithm 2 and for the A-FW experiments, the adaptive-smoothing convergence claim needs to be corrected or removed.","section":"2.2, Proposition 4"},{"comment":"Algorithm 2 is underspecified in a way that is directly relevant to Proposition 4: the Data line lists D and L_U, but L_U is never defined, while Proposition 4 defines the schedule with Mmax (max_{c in U} ||c||). If L_U is intended to be Mmax, this should be stated; otherwise the schedule in the algorithm box is not the schedule analyzed in the proposition. The notation M, Mmax, D, and Dmax should also be kept distinct, since D is the diameter of X, Dmax is the maximum norm of a point in X, M is the diameter of U, and Mmax is the maximum norm of a point in U.","section":"2.2, Algorithm 2"},{"comment":"The experimental section presents A-FW as an implementation of Algorithm 2 and uses it to draw conclusions about adaptive smoothing (e.g., better performance on TSP and larger uncertainty sets). Since Proposition 4 is false, A-FW has no proven convergence guarantee in the current manuscript; the empirical observations may still be valid as heuristics, but the claims that adaptive smoothing is a theoretically supported instance of the proposed framework should be revised. The fixed-smoothing FW and FW-convhull results remain informative, but the paper should make clear which experimental conclusions depend only on Theorem 1 and which depend on the unproven adaptive variant.","section":"3, Experiments"}],"minor_comments":[{"comment":"The Frank-Wolfe bound should be stated with the iteration index matching the step-size rule gamma_t=2/(t+1) in Algorithm 1; as written the denominator t+3 and the later replacement by t are safe, but the indexing should be made explicit.","section":"2.2, Eq. (9)"},{"comment":"'Oracle calls' is used for a bound that counts each iteration, although Algorithm 1 makes one LMO call and one projection call per iteration; please state the convention (LMO calls only, or both oracles with the factor 2).","section":"Table 1 and Corollary 2"},{"comment":"The 'best known oracle complexity' claim should be qualified: Ben-Tal et al. [2015] already gives a bound of order D_max^2 M^2 / epsilon^2 in the same oracle model, and since D^2 can be up to 4 D_max^2, the present constant is not uniformly better.","section":"Abstract"},{"comment":"Corollary 3 should state explicitly that D^2 is at most n when X=conv(Z) and Z is a subset of {0,1}^n; otherwise the appearance of 4 n M^2 / epsilon^2 needs a derivation.","section":"Corollary 3"},{"comment":"The experiments use the BPCG variant with lazification, but the theoretical analysis is for plain Frank-Wolfe with the step-size rule in Algorithm 1; the text should explain how the convergence guarantee transfers to the implemented variant, or label the variant as a heuristic.","section":"3, Experiments"},{"comment":"There is a typo: 'sknapsack constraints' should be 'knapsack constraints'.","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":"I believe the paper is recoverable. The fixed-smoothing Theorem 1 and Corollaries are sound and within scope, and the reproducible code is a plus. The false Proposition 4 and the resulting claims around Algorithm 2 and A-FW are the main obstacle; a revision that removes or corrects the adaptive guarantee, re-labels the adaptive experiments, and fixes the notation would make the paper acceptable. I recommend major revision rather than rejection because the core fixed-smoothing contribution does not depend on Proposition 4."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read the paper. The central fixed-smoothing result is solid, but the adaptive-smoothing Proposition 4 is wrong, and that needs to be fixed before this is publishable in anything close to its current form.\n\nThe genuinely good part is Theorem 1. Combining Nesterov smoothing with Frank-Wolfe, balancing the smoothing bias against the FW gap, gives a clean proof of an oracle-call bound of 4 D^2 M^2 / eps^2 for (RO). This matches the best known bound from Ben-Tal et al. and the proof is transparent. Corollary 3, giving the first explicit oracle bound for min-max-min problems, is a real bonus. The experiments on spanning tree and TSP instances, with public code, show that the fixed-smoothing and convex-hull variants are practical and beat constraint generation on large uncertainty budgets. Credit where earned: this is a useful algorithmic contribution.\n\nThe problem is Proposition 4. The claimed bound f(x_T) - f* <= D Mmax / (2 sqrt(T)) under the schedule mu_t = 2D/(Mmax sqrt(t+1)) is false. Take X=[0,1], U=[-1,1], c0=-1. Then f(x)=x, D=Mmax=1. Run Algorithm 2 from x0=0. At t=4 the iterate is 0.6 with a natural tie-break, giving gap 0.6 > 0.25. Even with the most favorable tie-break at t=3, you get 0.7. The proof is just an appeal to Yurtsever et al. Theorem 3.2, and that theorem doesn't cover this setting in the way claimed. This is not a constant-factor nitpick; the schedule or the rate, or both, are wrong. Since A-FW is used in the experiments, the experimental claims about adaptive smoothing currently rest on an algorithm with no valid convergence guarantee.\n\nThe oracle model assumption (constant-time projection) is a caveat, but it's standard in this literature and not a deal-breaker. The main theorem holds under that model.\n\nBottom line: the fixed-smoothing half of the paper is good and likely correct; the adaptive half is not. This deserves a serious referee, but only with a request for major revision. I would not cite it until Proposition 4 is corrected or removed, and the experiments updated accordingly.","headline":"The fixed-smoothing Frank-Wolfe theorem is sound and the paper's core idea has value, but the adaptive-smoothing Proposition 4 is false, which undercuts a chunk of the experiments.","tokens_in":11181,"tokens_out":5256,"would_cite":false,"duration_ms":43203,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C47"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that a smoothed Frank-Wolfe method solves oracle-based robust optimization in O(1/epsilon^2) oracle calls, matching the best known bound and giving the first explicit oracle count for min-max-min problems.","keywords":["robust optimization","oracle-based algorithm","Frank-Wolfe","smoothing","min-max-min robust optimization","oracle complexity","linear minimization oracle","projection oracle"],"falsifier":"Run Algorithm 1 on a small instance such as $X=[0,1]$ and $U=[-1,1]$, compute the exact optimum of (RO), and check at $t=\\lceil 4D^2M^2/\\varepsilon^2\\rceil$ iterations for a range of $\\varepsilon$ values whether $f(x_t)-f(x^*) \\le \\varepsilon$; a single violation would disprove Theorem 1.","tokens_in":10046,"feed_emoji":"🎯","tokens_out":15545,"duration_ms":113172,"temperature":0.7,"pith_summary":"This paper tries to establish that robust min-max problems of the form $\\min_{x \\in X} \\max_{c \\in U} c^{\\top} x$, where the feasible set $X$ is available only through a linear minimization oracle, can be solved by Frank-Wolfe on a smoothed version of the objective. The smoothing adds a quadratic penalty $-\\frac{\\mu}{2}\\|c-c_0\\|^2$ to the inner maximization, making the piecewise-linear function differentiable, with a gradient that costs one Euclidean projection onto the uncertainty set $U$. The main theorem says that with $\\mu = \\varepsilon/M^2$, after $t \\ge 4D^2M^2/\\varepsilon^2$ Frank-Wolfe iterations the primal gap is at most $\\varepsilon$, giving an oracle-polynomial algorithm (polynomial in the problem data when each oracle call is cheap) and the first explicit oracle-call bound for min-max-min robust optimization. A sympathetic reader would care because the result matches the best known complexity while working in the high-dimensional, large-uncertainty regime where earlier constraint-generation methods stall.","feed_headline":"Smoothed Frank-Wolfe solves robust min-max in O(1/eps^2) oracle calls","feed_subtitle":"The method needs no constraint list for X, only a linear-optimization oracle plus a projection onto the uncertainty set.","key_machinery":"The load-bearing object is the smoothed robust objective $f_\\mu(x) = \\max_{c\\in U}\\{c^{\\top} x - \\frac{\\mu}{2}\\|c-c_0\\|^2\\}$ with $\\mu=\\varepsilon/M^2$. The quadratic penalty is strongly concave in $c$, which makes $f_\\mu$ differentiable and its gradient $1/\\mu$-Lipschitz; evaluating the gradient is equivalent to projecting $c_0 + x/\\mu$ onto $U$. Each Frank-Wolfe iteration therefore alternates a projection oracle on $U$ and a linear minimization oracle on $X$. The proof of Theorem 1 splits the true gap as $f(x_t)-f(x^*) \\le [f(x_t)-f_\\mu(x_t)] + [f_\\mu(x_t)-f_\\mu(x^*_\\mu)]$, bounding the first term by $\\varepsilon/2$ through the choice of $\\mu$ and the second by the classical Frank-Wolfe convergence rate $2D^2/(\\mu t)$; the schedule $\\mu = \\varepsilon/M^2$ and $t \\ge 4D^2M^2/\\varepsilon^2$ then force each term below $\\varepsilon/2$.","core_discovery":"The central claim is that the nonsmooth problem (RO) can be approximated to accuracy $\\varepsilon$ by a single smoothing parameter $\\mu = \\varepsilon/M^2$: the smoothed objective $f_\\mu(x)=\\max_{c\\in U}\\{c^{\\top} x - \\frac{\\mu}{2}\\|c-c_0\\|^2\\}$ differs from $f(x)=\\max_{c\\in U} c^{\\top} x$ by at most $\\varepsilon/2$ at every $x$, while the Frank-Wolfe gap on $f_\\mu$ after $t$ steps is at most $2D^2/(\\mu t)$. Balancing the two $\\varepsilon/2$ terms gives the oracle bound $4D^2M^2/\\varepsilon^2$. The proof works for any Frank-Wolfe variant, so the authors run a lazified blended pairwise conditional gradient in practice; it also extends, through a standard composite convex minimization argument, to an adaptive schedule $\\mu_t = 2D/(M_{\\max}\\sqrt{t+1})$ with $O(1/\\sqrt{T})$ convergence. A direct corollary is the first explicit oracle-call bound $4nM^2/\\varepsilon^2$ for min-max-min robust combinatorial optimization when $U$ is the convex hull of scenarios.","pith_inferences":["The paper leaves implicit that the same $\\varepsilon/2$ splitting should transfer to other projection-free variants such as away-step, pairwise, or fully-corrective Frank-Wolfe, potentially improving the constant $4$ in the oracle bound.","A testable extension is to replace the exact projection oracle with an approximate projection: if the approximation error propagates linearly through the bound, the $O(1/\\varepsilon^2)$ rate should survive with a slightly larger constant, broadening the class of uncertainty sets.","The explicit $4nM^2/\\varepsilon^2$ bound for min-max-min problems suggests that branch-and-bound solvers for two-stage robust optimization could certify node lower bounds with a predictable oracle budget, a connection the paper mentions only as future work."],"forward_implications":["Whenever the linear minimization oracle over $X$ and the projection oracle over $U$ are both polynomial-time subroutines, problem (RO) is solvable to accuracy $\\varepsilon$ in at most $4D^2M^2/\\varepsilon^2$ oracle calls, matching the previous best bound in the same model.","For min-max-min robust combinatorial optimization with $k \\ge n+1$ solutions, the same result supplies the first explicit oracle-call bound, $4nM^2/\\varepsilon^2$.","Because the convergence proof does not depend on the specific Frank-Wolfe variant, modern implementations such as lazified blended pairwise conditional gradient can be used without losing the theoretical guarantee, which is what makes the method competitive in the experiments.","The adaptive smoothing schedule $\\mu_t = 2D/(M_{\\max}\\sqrt{t+1})$ gives an $O(1/\\sqrt{T})$ primal-gap bound without knowing $\\varepsilon$ in advance, and the analysis tolerates inexact linear minimization oracles with additive or multiplicative error."],"supporting_citations":[{"why":"Establishes the smoothing construction: a strongly concave penalty makes the max function differentiable with $1/\\mu$-Lipschitz gradient and gives the approximation error used to fix $\\mu = \\varepsilon/M^2$.","marker":"[Nesterov, 2005]"},{"why":"Supplies the classical Frank-Wolfe primal-gap bound $2LD^2/(t+2)$ used as the second $\\varepsilon/2$ term in the proof of Theorem 1.","marker":"[Braun et al., 2022]"},{"why":"Provides the canonical Frank-Wolfe analysis and the inexact-oracle variants that let the smoothing argument extend to approximate linear minimization.","marker":"[Jaggi, 2013]"},{"why":"Gives the composite conditional-gradient bound (Theorem 3.2) from which the adaptive smoothing schedule's $O(1/\\sqrt{T})$ convergence is derived.","marker":"[Yurtsever et al., 2018]"},{"why":"Prior oracle-based algorithm (projected subgradient on the dual) with a $D^2M^2/\\varepsilon^2$ iteration bound; the new method matches this complexity and inherits the projection-oracle model.","marker":"[Ben-Tal et al., 2015]"},{"why":"Defines the min-max-min robust optimization model and the constraint-generation baseline whose lack of an explicit oracle bound is addressed by Corollary 3.","marker":"[Buchheim and Kurtz, 2017]"},{"why":"Introduces the simplicial-decomposition algorithm and the convex-hull subproblem used in Section 2.4 to produce improved primal solutions and subgradient gaps.","marker":"[Bettiol et al., 2023]"}],"fun_headline_variants":["Smoothed Frank-Wolfe attains optimal oracle complexity for robust problems","Frank-Wolfe smoothing gives O(1/eps^2) oracle calls for robust min-max","First explicit oracle bound for robust combinatorial min-max-min","Oracle-based robust optimization solved in O(1/eps^2) calls","Smoothed FW reaches optimal oracle complexity in robust settings"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire complexity promise rests on the assumption that each linear minimization oracle call over $X$ and each Euclidean projection oracle call over $U$ takes constant time, so the bound is useful only when projection onto the uncertainty set is itself a cheap subroutine.","fun_headline_variants_meta":{"raw":{"variants":["Smoothed Frank-Wolfe attains optimal oracle complexity for robust problems","Frank-Wolfe smoothing gives O(1/eps^2) oracle calls for robust min-max","First explicit oracle bound for robust combinatorial min-max-min","Oracle-based robust optimization solved in O(1/eps^2) calls","Smoothed FW reaches optimal oracle complexity in robust settings"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000674,"raw_usage":{"total_tokens":3053,"prompt_tokens":915,"completion_tokens":2138,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":531,"completion_tokens_details":{"reasoning_tokens":2041}},"tokens_in":531,"tokens_out":2138,"duration_ms":13892,"temperature":1.0,"reasoning_tokens":2041,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:45:51.076451+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on a small instance such as $X=[0,1]$ and $U=[-1,1]$, compute the exact optimum of (RO), and check at $t=\\lceil 4D^2M^2/\\varepsilon^2\\rceil$ iterations for a range of $\\varepsilon$ values whether $f(x_t)-f(x^*) \\le \\varepsilon$; a single violation would disprove Theorem 1.","supporting_citations":[{"cited_title":"Smooth minimization of non-smooth functions","cited_arxiv_id":null,"evidence_quote":"Establishes the smoothing construction: a strongly concave penalty makes the max function differentiable with $1/\\mu$-Lipschitz gradient and gives the approximation error used to fix $\\mu = \\varepsilon/M^2$."},{"cited_title":"Revisiting frank-wolfe: Projection-free sparse convex optimization","cited_arxiv_id":null,"evidence_quote":"Provides the canonical Frank-Wolfe analysis and the inexact-oracle variants that let the smoothing argument extend to approximate linear minimization."},{"cited_title":"A conditional gradient framework for composite convex minimization with applications to semidefinite programming","cited_arxiv_id":null,"evidence_quote":"Gives the composite conditional-gradient bound (Theorem 3.2) from which the adaptive smoothing schedule's $O(1/\\sqrt{T})$ convergence is derived."},{"cited_title":"Oracle-based robust optimization via online learning","cited_arxiv_id":null,"evidence_quote":"Prior oracle-based algorithm (projected subgradient on the dual) with a $D^2M^2/\\varepsilon^2$ iteration bound; the new method matches this complexity and inherits the projection-oracle model."},{"cited_title":"Min--max--min robust combinatorial optimization","cited_arxiv_id":null,"evidence_quote":"Defines the min-max-min robust optimization model and the constraint-generation baseline whose lack of an explicit oracle bound is addressed by Corollary 3."},{"cited_title":"An oracle-based framework for robust combinatorial optimization","cited_arxiv_id":null,"evidence_quote":"Introduces the simplicial-decomposition algorithm and the convex-hull subproblem used in Section 2.4 to produce improved primal solutions and subgradient gaps."}],"review_version":1}