{"id":"ead8ac47-98f2-44d6-97ea-6a7087fce575","arxiv_id":"2607.22263","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For inverse optimization of integer linear programs, the iteration budget for exact consistency via projected subgradient descent is made explicit in terms of sample size, dimension, feature ranges, and the Graver-basis norm of the constraint matrix.","lead":"This paper proves explicit formulas for how many steps a projected-gradient algorithm needs to exactly recover hidden objective weights from observed optimal solutions of integer linear programs. Previously only an abstract, uncomputable guarantee existed; now the iteration count depends concretely on sample size, dimension, feature ranges, and constraint structure.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Load-bearing concern: the explicit iteration counts compose an unproved companion theorem; the paper's own lower-bound proofs are conditionally sound.","rationale":"The reader's weakest_assumption focused on Assumptions 3.2 and 6.1 (unique integer features). I agree those are load-bearing for the lower bounds, but they are explicitly assumed and are natural for the ILP setting; the paper's lower-bound arguments are internally coherent and I did not find a concrete mathematical error in them. The more exposed link is the unverified import of the companion paper's iteration bound, which is exactly what converts the lower bounds into explicit iteration counts. That concern supports the reader's CONDITIONAL verdict without changing it: the paper should either reprove the composition or make the dependency precise. My agreement is partial because the reader emphasized the lattice assumptions, whereas I emphasize the black-box iteration bound as the single most decisive unverified dependency.","tokens_in":32150,"tokens_out":37506,"duration_ms":321818,"concrete_test":"Independently re-derive Corollary 4.8 (PSGD-SRSS) from the companion paper using the γ(ℓsub) defined in Eq. (4.3), verifying that all hypotheses of Theorem 4.5 (including the relative-interior structure of the minimizer set and Assumptions 4.1/4.2) hold under this manuscript's Assumptions 3.1/3.2. Then recompute Table 4 row 1 (general ILP) with the exact constants from the re-derived bound and the lower bound of Theorem 6.6. If the re-derivation fails, or the final T differs by more than a polynomial factor from the paper's O(N^{2d} d² ||m||^{2(d−1)} poly), the explicit iteration claim is not supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central deliverable—explicit iteration upper bounds for exact DDIOP on ILPs—is a two-step composition: (i) lower-bound γ(ℓsub) (new, proved here), and (ii) substitute into the iteration bounds T=O(1/γ(ℓsub)²) imported from Kitaoka (2024, Corollaries 4.8/4.9). Step (ii) is a black box. The manuscript quotes Theorem 4.5 and the corollaries but does not reprove them or restate their exact hypotheses (e.g., the relative-interior condition on the minimizer set, Assumptions 4.1/4.2 on the update map). If the companion's Q(γ) bound has a different definition of γ, a hidden assumption, or a numerical error, the explicit T values in Table 4 do not follow. Separately, the lower-bound proofs rely on Assumption 6.1 (integer-valued features) and Assumption 3.2 (unique optimal feature), and the lattice separating-hyperplane constructions in Theorems 6.4/6.6/6.24 (e.g., selecting affinely independent lattice points on facets of Q and Q′) are sketched rather than fully formal. These conditions are stated, but they are the least externally verified links in the chain.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the data-driven inverse optimization problem (DDIOP) for integer linear programs (ILPs), where one estimates objective-function weights from observed optimal solutions. Its central contribution is a set of explicit lower bounds on the geometric constant γ(ℓ_sub) that controls the finite-time exact-convergence guarantees of projected subgradient methods: a general ILP bound under Θ=Δ^{d-1} (Theorem 6.6), polynomial-in-dimension bounds for M-convex and M♮-convex sets (Theorems 6.13/6.14 and 6.18/6.19), a Graver-basis bound for linear-inequality-constrained ILPs (Theorems 6.23/6.24), and a matching exponential-in-dimension tightness example (Proposition 6.34). These lower bounds are then substituted into iteration-complexity results from the author's companion paper (Kitaoka 2024, Corollaries 4.8/4.9) to obtain explicit iteration counts, summarized in Tables 1 and 4.","tokens_in":32461,"tokens_out":11486,"duration_ms":102873,"significance":"If the results are correct, the paper provides a genuinely new quantification of a previously abstract constant: practitioners would be able to precompute an iteration budget that guarantees exact consistency before running the algorithm. The test-set reduction (Lemma 6.9) and the lattice-separating-hyperplane arguments are elegant, and the structural separation between polynomial-in-dimension bounds (M-convex, M♮-convex, totally unimodular) and exponential-in-dimension worst cases for general ILPs is valuable. The tightness construction in Proposition 6.34 is a particular strength because it shows the exponential dependence is not an artifact of the proof. No fitted parameters appear; the lower bounds are derived from test sets, Graver bases, and lattice geometry. However, the final explicit iteration counts are conditional on the author's companion paper, and the scope is restricted by exact-data, uniqueness, and integrality assumptions that are not fully discussed.","major_comments":[{"comment":"The explicit iteration counts in Table 4 are obtained by substituting the new lower bounds into Q_{L(ℓsub),θ1}(γ(ℓsub)) from the companion paper, but Theorem 4.5 is only quoted, not proved, and its statement here omits the relative-interior-point condition that §2 identifies as essential. Assumptions 4.1/4.2 are conditions on an abstract update map, and the reader is not shown how the PSGD variants satisfy them in this setting. If the companion's γ has a different normalization, or if a hidden hypothesis (e.g., relative interior of argmin_Θ ℓsub) is needed, then every row of Table 4 is unsupported. Please restate the exact companion theorem and corollaries with all hypotheses, and either prove them or provide a self-contained verification for ℓsub under Assumptions 3.1/3.2.","section":"§4.1, Theorem 4.5 and Corollaries 4.8/4.9"},{"comment":"The lattice-separation mechanism is the backbone of the general-ILP lower bounds: the integrality of the normal vector a and the inequality a·P−c≥1 require Assumption 6.1 (integer-valued features) and Assumption 3.2 (unique optimal feature). If features are real-valued or the data contain ties, the m_i-based and C-based bounds lose their lattice support and need not hold. The paper states these assumptions but does not discuss their necessity or provide examples showing they are tight. Additionally, Theorems 6.4 and 6.23 require full-dimensionality conditions (dim Conv(W)=d and dim Conv(S+)=d) that are not derived from the ILP data; Remark 6.5 gives only a sufficient condition. Please state explicitly which claims fail without these assumptions and add verification criteria or counterexamples.","section":"§6.6, Propositions 6.30/6.33 and Theorems 6.4/6.6/6.23/6.24"},{"comment":"Lemma 6.9 assumes Y(n)⊆X(s(n)) and identity features, but the inclusion is not justified in the text. For a bounded integer set X, the vertices of Conv(X) are indeed elements of X, so the assertion is true; nonetheless it should be stated and proved explicitly because it is used in all M-convex and M♮-convex theorems. More importantly, the lower bounds in Theorems 6.13/6.14 and 6.18/6.19 depend on choosing a θ† that is ordered relative to the unknown true θ*. The resulting bounds are independent of θ*, so this is not a circularity, but the presentation should clarify that the bound is existential rather than constructed from data.","section":"§6.2–6.4, Lemma 6.9 and M-convex/M♮-convex bounds"}],"minor_comments":[{"comment":"The unit ball is consistently written as 'Bd' rather than 'B^d', which is easy to misread as 'B_d'. Please use a consistent notation.","section":"§6.1, Theorems 6.4/6.13/6.18"},{"comment":"The acronyms UPA and RPA are used without definition. Please define these methods or cite the exact references from which the rates are taken.","section":"§5, Tables 2 and 3"},{"comment":"The handling of the degenerate case θ*=0 is embedded in the proof. It would be clearer to state at the start that if θ*=0 then Assumption 3.2 forces every X(s(n)) to be a singleton, in which case γ(ℓsub)=+∞ and the bound is trivial, and otherwise the proof proceeds.","section":"§6.4.1, Theorem 6.18"},{"comment":"The constant C=g∞(eA) is described as 'determined by A alone', but computing a Graver basis can be expensive. The paper should state explicitly whether C is assumed to be known to the practitioner or whether only its bounds (e.g., Proposition 6.27) are intended to be used in the stopping criterion.","section":"§6.5, Proposition 6.22"}],"recommendation":"major_revision","confidential_remarks":"The paper's central deliverable depends almost entirely on the author's companion arXiv:2405.14273, which is not proved or even fully restated here. I recommend that the editor ensure this companion is available and verified, or ask the authors to append the relevant proofs. The exact-data, unique-optimum, and integer-feature assumptions further limit the applicability of the explicit bounds; these restrictions should be prominent in the final version. The new lower-bound work itself appears sound and is a worthwhile contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on arXiv:2607.22263. The paper makes good on its headline claim: for ILP inverse optimization, the abstract constant γ(ℓ_sub) of the companion paper finally gets explicit lower bounds in terms of N, d, feature range, and the Graver-basis norm C. Substituting those into the iteration bounds yields finite iteration counts you can precompute. That is a real gap to close, and the paper closes it.\n\nThe lower-bound proofs are the core, and they mostly hold up. The test-set reductions for M-convex and M♮-convex sets are clean, and the Graver-basis bound for linear-inequality constraints is a nice use of conformal decomposition. Proposition 6.34's tightness example is genuinely informative: it shows the exponential-in-d dependence is not an artifact. The author is honest about the assumptions—integer-valued features, unique optimal feature (Assumption 3.2), exact data—and about the fact that the outer iteration bound comes from his own companion paper.\n\nThe soft spots are in proportion. First, the composition is a black box: Corollaries 4.8/4.9 and Theorem 4.5 are quoted, not reproved, and the reader cannot verify the exact hypotheses (e.g., the relative-interior condition under Assumptions 4.1/4.2) without going to the companion paper. That's a dependency, not an error, but it makes the final table conditional on the companion being right. I'd want the author to restate the hypotheses or give the derivation. Second, the lattice-separation constructions in Theorem 6.23 and parts of 6.24 are sketched; the cofactor arguments should be spelled out at least in an appendix. Third, there's a possible inconsistency I'd check before publication: Table 4's general-ILP row appears to show N^2, while Theorem 6.6's bound puts N^d in the denominator, which would give N^{2d} in the iteration count. Might be an OCR artifact, but it needs confirming.\n\nMinor issues: the nondegeneracy and full-dimensionality conditions in Theorems 6.4 and 6.23 are required but tucked into the theorem statements; the summary tables could remind readers of these. The practical scope is narrow—exact data, no noise, integer features—but that's the point of an ILP-specific theory paper.\n\nWho gets value: theorists in inverse optimization and integer programming who want quantitative finite-termination guarantees. It deserves a serious referee. My recommendation: accept the paper for review; ask for a restatement of the companion's hypotheses and fuller lattice-cofactor proofs.","headline":"A genuinely new explicit lower bound on γ(ℓ_sub) for ILPs, with mostly solid proofs, but the iteration-count conclusion rests on an unproved companion theorem and a couple of technical gaps to patch.","tokens_in":32930,"tokens_out":8593,"would_cite":true,"duration_ms":69700,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C90","90C25","90C52","90C11","90C05","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes explicit problem-size-dependent lower bounds on the geometric constant γ(ℓ_sub) that governs finite-time exact consistency of gradient-based inverse optimization for integer linear programs, yielding iteration counts a","keywords":["inverse optimization","integer linear programming","suboptimality loss","projected subgradient method","Graver basis","M-convexity","total unimodularity","finite-time convergence"],"falsifier":"Take an explicit ILP instance with N=1, d=2, feature ranges m=(1,1), and a feasible region whose vertex set is, say, {(0,0),(1,0),(0,1)}; compute the min-max on the right side of Equation (4.3) exactly and compare to the lower-bound value 1/(2·2·√2·√2)=1/4. Any instance yielding a value below 1/4 would refute Theorem 6.6 under its stated assumptions.","tokens_in":31978,"feed_emoji":"🧮","tokens_out":4816,"duration_ms":47962,"temperature":0.7,"pith_summary":"This paper seeks to turn a qualitative finite-termination guarantee into a quantitative one for data-driven inverse optimization of integer linear programs. Earlier work showed that projected subgradient descent on the suboptimality loss reaches exact consistency with observed data in finitely many iterations, with the count controlled by an abstract geometric constant γ(ℓ_sub). The paper proves explicit lower bounds on γ(ℓ_sub) in terms of sample size, feature dimension, feature ranges, and, for linear inequality constraints, the Graver-basis norm of the constraint matrix. Substituted into the known iteration bounds, these yield explicit finite iteration budgets that can be computed before running the algorithm. For structured feasible regions such as M-convex and M♮-convex sets, the bounds are polynomial in the dimension and independent of feature ranges; for general ILPs they are exponentially small in dimension, and the paper shows this exponential dependence is inherent.","feed_headline":"Explicit iteration counts for inverse ILP become computable","feed_subtitle":"The geometric constant that controls finite-time exact learning is now bounded by sample size, dimension, and feature ranges.","key_machinery":"The carrying object is the geometric constant γ(ℓ_sub), defined as the maximum over weights of the minimum normalized score advantage of the observed features over any other combination of vertices from the sample-wise feature vertex sets. The arguments reduce γ to a distance problem between the observed sum P and the convex hull of alternative sums Conv(W), then use an integral separating hyperplane: because all features are integers, the separating normal is an integer vector whose norm is bounded through Hadamard's inequality and the feature ranges. For structured regions, explicit test sets—single exchanges for M-/M♮-convex sets, Graver basis elements for linear inequality systems—give t","core_discovery":"For integer linear programs, the geometric constant γ(ℓ_sub)—the largest margin separating the observed feature sums from all alternative feature tuples—can be lower-bounded explicitly from problem data. Under the probability-simplex weight set, γ ≥ 1/(N^d max(d−1,√2)‖m‖_2^{d−1}) for general ILPs; when the feasible region is M-convex or M♮-convex, γ ≥ 2/(N d(d−1)) (resp. 2/(N d(d+1))) independent of feature ranges; and for linear inequality constraints Ax ≤ b it is Ω(1/(N d^{(d+1)/2}(2C)^{d−1})), with C the ℓ∞ norm of the Graver basis of the slack-augmented matrix [A|I]. These bounds make the previously abstract iteration upper bound T = O(1/γ²) an explicit function of the problem size.","pith_inferences":["A natural testable extension is whether the same explicit bounds can be derived for mixed-integer programs by applying the lattice separating hyperplane to the integer part; the current result covers pure ILPs.","The striking gap between the strong M-convex bound and the weaker general linear-inequality bound for the same region suggests that the choice of structural representation itself changes the complexity estimate by an exponential factor, and algorithm designers should exploit combinatorial type rather than the inequality description.","Real-world data noise or tie-breaking suboptimality in observed solutions would violate the uniqueness assumption; measuring how γ degrades under small perturbations would indicate how quickly these explicit budgets erode.","The bounds are for exact consistency; for approximate consistency one would expect much smaller budgets, and the explicit form of γ could yield an ε-dependent complexity that interpolates smoothly between asymptotic and exact regimes."],"forward_implications":["Practitioners can precompute a sufficient iteration budget before running the algorithm, turning the finite-time guarantee into an a priori stopping criterion.","The finite-step exact-consistency guarantee can now be compared fairly with asymptotic regret bounds, both expressed as functions of the problem size.","For M-convex and M♮-convex feasible regions, the iteration count is polynomial in dimension and independent of feature ranges, making exact inverse optimization computationally attractive for those structures.","For general ILPs, the exponential dependence of the iteration bound on dimension is unavoidable, consistent with the known hardness of inverse optimization under noisy data.","The same lower bounds yield explicit iteration counts for attaining zero prediction loss of features (PLF), not just zero suboptimality loss."],"fun_headline_variants":["Explicit bounds for inverse ILP iteration complexity","Now computable: iteration counts for inverse integer programming","Inverse ILP iterations: explicit bounds from problem data","Inverse ILP iteration bounds: now explicit from data","Iteration complexity for inverse ILP: now fully explicit"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The entire chain rests on every observed sample being generated exactly by a single true weight with a unique optimal feature vector, and on all features being integer-valued; if either fails, the lattice-based lower bounds that make the iteration count explicit do not follow.","fun_headline_variants_meta":{"raw":{"variants":["Explicit bounds for inverse ILP iteration complexity","Now computable: iteration counts for inverse integer programming","Inverse ILP iterations: explicit bounds from problem data","Inverse ILP iteration bounds: now explicit from data","Iteration complexity for inverse ILP: now fully explicit"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000689,"raw_usage":{"total_tokens":3008,"prompt_tokens":842,"completion_tokens":2166,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":586,"completion_tokens_details":{"reasoning_tokens":2088}},"tokens_in":586,"tokens_out":2166,"duration_ms":14546,"temperature":1.0,"reasoning_tokens":2088,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T05:17:52.982380+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take an explicit ILP instance with N=1, d=2, feature ranges m=(1,1), and a feasible region whose vertex set is, say, {(0,0),(1,0),(0,1)}; compute the min-max on the right side of Equation (4.3) exactly and compare to the lower-bound value 1/(2·2·√2·√2)=1/4. Any instance yielding a value below 1/4 would refute Theorem 6.6 under its stated assumptions.","supporting_citations":[],"review_version":1}