{"id":"9e73273b-49f5-40dc-a19a-8354351f329d","arxiv_id":"2412.21068","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"A finite-horizon stepsize rule for the primal-dual method on LP, found via a 4x4 SDP, is claimed to accelerate convergence at the T-th iteration and to give about 3.9x speedup on Netlib instances.","lead":"This paper proposes optimizing the stepsize of a primal-dual method for linear programming to perform well within a fixed, finite number of iterations, rather than in the limit of many iterations. The authors derive a convex SDP to find these stepsizes and report about 3.9x speedup over a constant stepsize on Netlib LP instances.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's rate is internally inconsistent: the Chebyshev bound drops a factor of 2, so the stated guarantee can contradict the true minimax lower bound; the SDP discretization/projection gaps further separate the proof from the proposed algorithm.","rationale":"The reader's verdict is REJECT, and the concern I identify supports that verdict, so no adjustment is needed. The reader's weakest assumption was the exactness of the discretized SDP and the projection gap; I agree those are real gaps. However, the more decisive issue is that even granting the exact SDP and the unprojected setting, the proof of Theorem 1 contains a concrete algebraic error: the standard Chebyshev lower bound gives a factor 2 in the denominator, and the displayed chain drops that factor. This makes the stated rate (38) stronger than the true minimax lower bound in explicit numerical settings. That is not a matter of asymptotic consensus or a missing reference; it is an internal inconsistency in the theorem as stated. The central O(sqrt(kappa) log(1/epsilon)) complexity claim would survive if the factor 2 were restored, so the paper's high-level idea is not necessarily dead, but the theorem needs correction. The SDP discretization issue compounds the problem: Algorithm 1 solves a finite grid SDP with a fixed solver iteration count, and no argument shows that the returned coefficients satisfy the continuum constraint or that the factorized roots are real. The projection gap is also real: the theory is for (32), the experiments are for (10), and Figure 6 only provides empirical projection ratios on one instance. The empirical 3.9x speedup may be genuine, but the theoretical guarantee claimed in the abstract and Theorem 1 is not established as written.","tokens_in":38542,"tokens_out":19310,"duration_ms":188455,"concrete_test":"Compute, for kappa=100 with beta=4/mu, the scalar minimax value s* = 1/C_10((kappa+1)/(kappa-1)) = 1/C_10(101/99) and compare it with sqrt(2+4*gamma)*((sqrt(kappa)-1)/(sqrt(kappa)+1))^10. If s* is larger, Theorem 1's inequality is impossible for any valid real stepsize sequence. To test the algorithm-side gap, take Algorithm 1's output for this kappa and T, form the polynomial p(x)=1+a_1 x + ... + a_T x^T, check that all roots are real (otherwise the returned coefficients do not correspond to a valid stepsize rule), and evaluate max_{sigma in [1,2.588]} ||I + p(B(sigma))||_op on a dense grid; if this exceeds the theorem's RHS, the discretized SDP solution does not certify the claimed rate.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.2 Step 4 contains a concrete algebraic error. The proof invokes the standard bound C_T(x) >= (x + sqrt(x^2-1))^T / 2, which gives 1/C_T <= 2((sqrt(kappa)-1)/(sqrt(kappa)+1))^T. In the chain from equation (47) to (48), the factor 2 is silently removed. This cannot be justified: for kappa=100, T=10, gamma=1/3 (the beta=4/mu setting), the theorem's RHS is sqrt(2+4*gamma)*((sqrt(kappa)-1)/(sqrt(kappa)+1))^10 ≈ 0.250, while the true minimax polynomial value over the eigenvalue interval is 1/C_10(101/99) ≈ 0.264. Since the operator norm of the error matrix is at least the maximum of |p(lambda)| over the eigenvalues of M, no real stepsize sequence can achieve the stated bound on the worst-case ratio. The exact inequality in Theorem 1 is therefore false as written, independent of numerical SDP issues. Separately, the proof writes 'Algorithm 1 = min_eta max_sigma' even though Algorithm 1 solves the discretized SDP (31) with n_sample=200 and a fixed SCS iteration budget, with no optimality certificate and no grid-refinement bound; and the theorem applies to the unprojected problem (32), while experiments run the projected method (10), with only empirical projection-ratio evidence (Figure 6) bridging the gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a finite-horizon framework for tuning iterative algorithms under a fixed iteration budget T and instantiates it for the primal-dual method for linear programming (LP). For the standard-form LP, the primal update's projection is modeled as a random Bernoulli mask, the residue term in equation (24) is dropped, and the resulting worst-case stepsize design problem is reformulated as a semi-infinite SDP (30), then discretized as SDP (31). The polynomial coefficients obtained from the SDP are factored to produce the Finite Horizon stepsize rule (Algorithm 1). Theorem 1 claims an O(sqrt(kappa) log(1/epsilon)) rate at the pre-fixed T-th iteration for the unprojected problem (32), compared with an Omega(kappa log(1/epsilon)) lower bound for the optimal constant stepsize (Proposition 1). Experiments on the Netlib benchmark report an average 3.9x speedup and a 75% wall-clock time saving.","tokens_in":38895,"tokens_out":11481,"duration_ms":109207,"significance":"The finite-horizon viewpoint is timely, and the reported empirical speedup on a standard LP benchmark is potentially valuable. The paper provides code and uses a reproducible public benchmark. However, the central theoretical guarantee is not established for the algorithm as implemented, and the proof of Theorem 1 contains a concrete algebraic error in the Chebyshev bound. The framework and the empirical study are interesting enough to warrant a major revision, provided the theoretical claims are corrected and explicitly delimited.","major_comments":[{"comment":"The passage from (47) to (48) silently drops the factor 2 in the standard Chebyshev lower bound C_T(x) >= (x + sqrt(x^2-1))^T / 2. For x = (kappa+1)/(kappa-1), the correct upper bound on 1/C_T(x) is 2 * ((sqrt(kappa)-1)/(sqrt(kappa)+1))^T, not ((sqrt(kappa)-1)/(sqrt(kappa)+1))^T. Consequently the right-hand side of Theorem 1 is smaller than the true minimax polynomial value for concrete parameters (for kappa=100, T=10, gamma=1/3, the stated RHS is about 0.250, while 1/C_10(101/99) is about 0.264). Since the operator norm of the error matrix is at least the maximum of |p(lambda)| over the eigenvalues of M, no real stepsize sequence can satisfy the stated bound. The asymptotic complexity claim survives if the constant is corrected to 2*sqrt(2+4*gamma), but the theorem as written is false.","section":"Section 4.2, Eqs. (45)-(48)"},{"comment":"The proof uses the identity 'Algorithm 1 = min_eta max_sigma', but Algorithm 1 solves the discretized SDP (31) with nsample=200 grid points and an SCS solver run for a fixed number of iterations (sdp_iter, e.g., 100 or 20). No grid-refinement bound, optimality certificate, or exactness argument is provided, so the theorem does not apply to the polynomial coefficients actually returned by the solver. Additionally, the factorization step in Algorithm 1 assumes that the polynomial p(x) = 1 + a_1 x + ... + a_T x^T has real roots; this is neither guaranteed by the SDP formulation nor verified by the algorithm.","section":"Section 4.2, Step 4 and Algorithm 1"},{"comment":"Theorem 1 is stated for the unconstrained problem (32), where the update is the linear recurrence (33). The experiments in Section 5 run the projected primal-dual method (10) on standard-form LPs with the nonnegativity constraint x >= 0. The bridge between the two is the heuristic random-projection model in Section 2 and the numerical observation in Figure 6 that the projection ratio is small. This does not prove that the unprojected analysis transfers to the tested algorithm. The abstract's claim of a 'theoretical acceleration guarantee' for the method therefore overstates what is actually proved.","section":"Theorem 1 vs. Section 5 experiments"}],"minor_comments":[{"comment":"There are numerous typographical errors that should be corrected: 'posts' should be 'poses', 'eigenvlaues' should be 'eigenvalues', 'thse' should be 'these', 'asymtopic' should be 'asymptotic', 'intances' should be 'instances', 'primarilly' should be 'primarily', and 'Finit Horizon' should be 'Finite Horizon'.","section":"Throughout"},{"comment":"Algorithm 1 says to solve SDP (31) using Interior Point Methods, but Section 5.2 uses the SCS solver with sdp_iter=100 (and sdp_iter=20 for T=10). The solver and its accuracy settings should be stated consistently.","section":"Algorithm 1 and Section 5.2"},{"comment":"The SIERRA row reports 33931 iterations, which is identical to the PILOT row; this is likely a copy-paste error and should be checked.","section":"Table 1"},{"comment":"The proof uses the notation r_{i,1} and r_{i,2} without defining it; these are presumably the eigenvalues of B_i^2 from Lemma 2 and should be introduced explicitly.","section":"Section 4.2, Step 3"},{"comment":"The global optimization method is called 'Stimulated Annealing'; the standard name is 'Simulated Annealing'.","section":"Section 5.1"}],"recommendation":"major_revision","confidential_remarks":"The empirical study and the finite-horizon framework are promising, and the corrected Chebyshev argument would preserve the claimed O(sqrt(kappa)) versus Omega(kappa) complexity comparison. However, the paper currently proves a theorem for an idealized unprojected problem while claiming a guarantee for the projected algorithm that is actually tested. The authors should either extend the analysis or substantially weaken the theoretical claims in the abstract and introduction. If the theoretical claims are kept in their current form, rejection would be appropriate; with the factor-2 correction and an honest delimitation of the theorem's scope, a revised version could be publishable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know before you read. First, the core design problem is real and new: for the primal-dual update with nonsymmetric M, they find a hidden convexity that turns the finite-horizon worst-case stepsize search into a 4x4 SDP, and they verify a 3.9x average speedup on Netlib with code released. Second, the headline theorem as stated is quantitatively false. In the proof, the Chebyshev lower bound C_T(x) >= (x+sqrt(x^2-1))^T/2 gives a factor 2 in 1/C_T, and that factor is silently dropped between eqs. (47) and (48). Concretely, at kappa=100, T=10, gamma=1/3 the stated RHS is about 0.250 while the minimax polynomial value is about 0.264, so no stepsize sequence can meet the bound. The qualitative O(sqrt(kappa) log(1/epsilon)) claim survives with a factor 2 in the constant, but the exact inequality in Theorem 1 is wrong. What is genuinely good: the block-diagonalization argument (Lemma 2) and the 4x4 SDP reformulation are non-obvious; the related-work section is careful; and the experiments compare against the optimal constant stepsize with the same information (mu, L). The empirical result looks plausible and the code availability is a plus. The soft spots beyond the bug: (1) The proof writes 'Algorithm 1 = min_eta max_sigma' but Algorithm 1 solves a discretized SDP (nsample=200) with a fixed SCS iteration budget and no optimality certificate or grid-refinement bound. This is a gap between what is proved and what is computed. (2) The theorem covers the unprojected problem (32), while experiments run the projected method (10). The random-projection model and Figure 6's small projection ratio are suggestive but not a proof. To claim a theoretical acceleration guarantee for the actual method, they need either a proof of the transfer or a weaker statement. Final word: this is a preliminary working paper, and the abstract overclaims. But the idea is fresh, the empirical speedup is meaningful, and the flaws are fixable. I would send it to a serious referee, with a request to focus on the Theorem 1 constant and the projection gap.","headline":"Promising finite-horizon stepsize idea for primal-dual LP with a real bug in the headline theorem—still worth a serious referee.","tokens_in":39447,"tokens_out":3204,"would_cite":true,"duration_ms":32742,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C05","90C22","90C47"],"pacs":[],"model":"deepseek-v4-flash","headline":"Choosing stepsizes for a fixed T-iteration budget accelerates the primal-dual LP method from O(κ) to O(√κ).","keywords":["finite horizon optimization","primal-dual method","stepsize rule","semidefinite programming","minimax problem","Chebyshev polynomial","linear programming","Netlib benchmark"],"falsifier":"For a fixed matrix $A$ with known singular-value bounds, compute Algorithm 1's stepsizes and evaluate the actual worst-case contraction of $\\prod_{t=1}^T(I-\\eta_t M)$ over the interval $[\\mu,L]$ with a much finer grid; if the contraction exceeds $\\sqrt{2+4\\gamma}(1-2/(1+\\sqrt{\\kappa}))^T$, then the discretized SDP did not solve the continuous minimax problem and the theorem's bound does not hold for the implemented stepsizes.","tokens_in":38262,"feed_emoji":"⚡","tokens_out":9503,"duration_ms":78446,"temperature":0.7,"pith_summary":"This paper introduces finite horizon optimization, a framework for tuning an iterative algorithm's hyperparameters so that it performs well after exactly T steps, where T is a fixed and finite iteration budget, rather than as T grows to infinity. Applied to the primal-dual method for linear programming, the paper proposes a Finite Horizon stepsize rule that solves a convex semidefinite program with 4x4 matrix constraints; the SDP's optimality exploits a hidden convexity in the stepsize-selection minimax problem. The paper proves that, at the pre-fixed T-th iteration, this rule reaches $O(\\sqrt{\\kappa}\\log(1/\\epsilon))$ complexity, against the $\\Omega(\\kappa\\log(1/\\epsilon))$ lower bound for the optimal constant stepsize, for the unconstrained linear-system case. On more than 90 Netlib LP instances, the reported average is a 3.9x speedup over the optimal constant stepsize, saving about 75% of the wall-clock time to reach the same precision.","feed_headline":"Finite-horizon stepsizes accelerate LP solving 3.9x","feed_subtitle":"A convex SDP picks primal-dual stepsizes for a fixed iteration budget, beating the best constant stepsize on Netlib.","key_machinery":"The machinery is the block-diagonalization of the primal-dual update matrix $M=\\begin{bmatrix}\\beta A^\\top A & A^\\top\\\\ -A & 0\\end{bmatrix}$ into $2\\times 2$ blocks $B(\\sigma)=\\begin{bmatrix}\\beta\\sigma^2 & \\sigma\\\\ -\\sigma & 0\\end{bmatrix}$ using the singular value decomposition of $A$. With the cumulative product $\\Gamma=(I-\\eta_T M)\\cdots(I-\\eta_1 M)$, the objective $\\|\\Gamma\\|_{\\mathrm{op}}$ becomes the spectral norm of a $T$-th-degree matrix polynomial in $B(\\sigma)$, and the paper proves that controlling this norm is equivalent to a semidefinite program with $4\\times 4$ matrix variables (30); after discretizing the singular-value interval $[\\mu,L]$ into $n_{\\mathrm{sample}}$ samples, the SDP (31) is solved to obtain the polynomial coefficients. The stepsizes are the reciprocals of the polynomial's roots, computed via a companion matrix. The proof of Theorem 1 then uses the eigen-decomposition of $M$ (Lemma 1), a block-diagonal eigenvalue computation of $\\Gamma^\\top\\Gamma$ (Lemma 2), and the Chebyshev minimax polynomial to bound the resulting contraction by $(1-2/(1+\\sqrt{\\kappa}))^T$.","core_discovery":"The central discovery is that the minimax stepsize-selection problem for the primal-dual method—choose $\\eta_1,\\dots,\\eta_T$ to minimize the worst-case contraction $\\|(I-\\eta_T M)\\cdots(I-\\eta_1 M)\\|$ over LP constraint matrices with singular values in $[\\mu,L]$—is exactly convex, despite the non-symmetric update matrix $M$ and the product form of the objective. The paper establishes this by block-diagonalizing $M$ via the SVD of $A$ into $2\\times 2$ blocks $B(\\sigma)$, rewriting the contraction as a $T$-th-order matrix polynomial, and then casting the spectral-norm control as a linear matrix inequality of size $4\\times 4$. The resulting SDP (31) returns polynomial coefficients whose roots give the stepsizes. For the unconstrained case (32), where the LP reduces to solving $Ax=b$, Theorem 1 shows this stepsize rule attains $\\mathrm{dist}(z_T,\\mathcal{Z}^*)\\le \\sqrt{2+4\\gamma}(1-2/(1+\\sqrt{\\kappa}))^T\\mathrm{dist}(z_0,\\mathcal{Z}^*)$, an $O(\\sqrt{\\kappa}\\log(1/\\epsilon))$ guarantee at the $T$-th iteration, versus the $\\Omega(\\kappa\\log(1/\\epsilon))$ lower bound for the optimal constant stepsize. The experiments then report the 3.9x speedup on Netlib, with the theoretical guarantee applying to the unprojected update while the experiments use the projected update with small measured projection ratios.","pith_inferences":["Beyond the paper: the same 2x2 block-diagonalization trick should apply to any saddle-point algorithm whose update matrix is block-structured by a rank-revealing factorization of the constraint matrix, so the hidden-convexity route may extend to PDHG and other first-order LP solvers.","Beyond the paper: the sharp final-step increase in the stepsize schedule resembles the silver stepsize patterns in gradient descent; a direct comparison of the two schedules could clarify whether finite-horizon LP stepsize design and accelerated GD share the same underlying minimax principle.","Beyond the paper: the paper's own cyclical-repetition trick suggests an anytime variant: repeat the T-step schedule; testing whether the oracle complexity of the cyclic schedule is $O(\\sqrt{\\kappa}\\log(1/\\epsilon))$ with the same constant would give an asymptotic guarantee that the single-shot schedule lacks.","Beyond the paper: a proof that the projection ratio stays below some small threshold under finite-horizon stepsizes (not just empirical evidence below 5%) would upgrade the numerical speedup into the same theoretical guarantee as Theorem 1 for the projected method."],"forward_implications":["The same primal-dual algorithm, using only a different stepsize schedule, reduces the condition-number dependence at the T-th iteration from $O(\\kappa)$ to $O(\\sqrt{\\kappa})$ for the unconstrained case.","No guarantee is claimed for iterations before T; the experimental gap curves show the error barely improves until the final step, then drops sharply, so the schedule is tuned for one target horizon and must be cycled for longer runs.","The SDP subproblem involves only 4x4 matrix inequalities and costs a fixed, negligible time (an average 11.6 seconds, under 3.1% of total runtime on Netlib), independent of the LP dimension.","On more than 90 Netlib LP instances, the rule saves on average 74% of iterations and 75% of wall-clock time to reach the same precision as the optimal constant stepsize.","If the projection onto the nonnegative orthant rarely activates (measured below 5% in the experiments), the no-projection analysis is a good proxy for the projected method's behavior."],"supporting_citations":[{"why":"Supplies the original finite-horizon stepsize idea for quadratic minimization, which the paper extends to the non-symmetric primal-dual update.","marker":"[Young, 1953]"},{"why":"Provides the companion-matrix root-finding algorithm used to factor the polynomial into stepsizes.","marker":"[Horn and Johnson, 2012]"},{"why":"Provides the Netlib LP benchmark used for the reported speedups.","marker":"[Gay, 1985]"},{"why":"Supplies the spectral-radius identity used to define the asymptotic optimal constant stepsize baseline in Proposition 1.","marker":"[Saad, 2003]"},{"why":"Classical source for the minimax Chebyshev polynomial bound used in Theorem 1's Step 4.","marker":"[Markov and Grossmann, 1916]"},{"why":"Gives the modern statement of the Chebyshev minimax property and the polynomial bound used in the proof.","marker":"[Pedregosa, 2020]"}],"fun_headline_variants":["Finite-horizon stepsizes cut LP runtime 3.9x via convex SDP","LP speedup 3.9x from convex finite-horizon stepsize SDP","Hidden convexity in LP stepsizes yields 3.9x speedup","3.9x faster LP solving with finite-horizon stepsize rule","SDP picks finite-horizon LP stepsizes: 3.9x speedup"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument hinges on the discretized SDP that outputs the stepsizes being an exact solution of the continuous minimax problem; if that step is approximate, the stated $\\sqrt{\\kappa}$-rate guarantee at iteration $T$ does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Finite-horizon stepsizes cut LP runtime 3.9x via convex SDP","LP speedup 3.9x from convex finite-horizon stepsize SDP","Hidden convexity in LP stepsizes yields 3.9x speedup","3.9x faster LP solving with finite-horizon stepsize rule","SDP picks finite-horizon LP stepsizes: 3.9x speedup"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000252,"raw_usage":{"total_tokens":1672,"prompt_tokens":1169,"completion_tokens":503,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":785,"completion_tokens_details":{"reasoning_tokens":392}},"tokens_in":785,"tokens_out":503,"duration_ms":4948,"temperature":1.0,"reasoning_tokens":392,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T23:03:39.798606+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a fixed matrix $A$ with known singular-value bounds, compute Algorithm 1's stepsizes and evaluate the actual worst-case contraction of $\\prod_{t=1}^T(I-\\eta_t M)$ over the interval $[\\mu,L]$ with a much finer grid; if the contraction exceeds $\\sqrt{2+4\\gamma}(1-2/(1+\\sqrt{\\kappa}))^T$, then the discretized SDP did not solve the continuous minimax problem and the theorem's bound does not hold for the implemented stepsizes.","supporting_citations":[],"review_version":1}