{"id":"b5ddd197-9147-4953-ad23-6681dd7ca9aa","arxiv_id":"1908.02894","paper_version":4,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A single pseudo-dimension theorem covers any parameterized algorithm whose performance is piecewise constant, linear, or piecewise structured in its parameters, recovering prior bounds and yielding new ones for computational biology and voting.","lead":"This paper proves general sample-size guarantees for tuning an algorithm's parameters from training data, whenever the algorithm's performance changes in structured jumps or straight lines as parameters vary. It unifies earlier case-by-case results and adds new guarantees for sequence alignment, RNA folding, and voting mechanisms.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Tie-breaking at lower-dimensional ties is not handled in the piecewise-decomposability lemmas, leaving a gap in the DP and voting-mechanism applications.","rationale":"The central Theorem 3.3 is well-argued and the proof via Sauer's lemma on the dual class is sound. However, the applications to computational biology and voting mechanisms rely on exhibiting (F,G,k)-piecewise decomposability of the dual class. The lemmas use strict halfspace boundary functions, which do not separate lower-dimensional tie faces from open regions. On a tie face, the bit vector is shared with an adjacent open region, and the algorithm's tie-breaking output may differ from that region's output, so the required equality fails. The paper's co-optimal-constant assumption does not close this gap. This is significant because the claimed pseudo-dimension bounds for these algorithms — a headline contribution — depend on these lemmas. The issue is likely patchable (e.g., by refining the partition to include faces and adjusting k or G, or by assuming tie-breaking is consistent with one side), but as written the application lemmas are not fully proven. The experiments and lower bounds are unaffected in their main conclusions. Therefore, I recommend conditional acceptance pending a rigorous treatment of boundary tie-breaking.","tokens_in":55446,"tokens_out":23074,"duration_ms":248250,"concrete_test":"Take a one-parameter algorithm with two candidate outputs A and B whose scores are rho and 1-rho, and a tie-breaking rule that outputs B at rho=1/2. For the single input instance, the dual function is u(rho)=u_A for rho>1/2 and u_B for rho<=1/2. With G={I{rho-theta<0}} and F the constant functions, choose boundary function g(rho)=I{rho-1/2<0}. At rho=1/2, b=0, and the piece function for b=0 must equal u_A to match the region rho>1/2, but the actual value is u_B. Hence the equality in Definition 3.2 fails at rho=1/2, so the dual class is not (F,G,1)-piecewise decomposable under this tie-breaking. This directly contradicts the claimed decomposition in Lemma 4.1.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 4.1 (and similarly 4.2, 4.4, 4.5, 4.6, 5.1) claims that the dual class is (F,G,k)-piecewise decomposable with G the class of strict halfspace indicators g_a(u_rho)=I{a·rho<theta}. On a parameter point where two or more candidate solutions tie (a·rho=theta), the bit vector b assigned by these strict indicators is the same as on the side a·rho>theta. The piece function for that b is the utility of that open region. But the algorithm's output at the tie is set by tie-breaking, which may differ from the output on that side. The paper's co-optimal-constant assumption only says the output is fixed on any region where the set of co-optimal solutions is fixed; it does not require that fixed output to equal the output in the adjacent open region sharing the same bit vector. Thus the defining equality h(y)=f_{b_y}(y) can fail on the boundary. Since the pseudo-dimension bound for U is proved by partitioning the whole parameter space into pieces P_j and using the piece functions to count labelings, such boundary failures are not covered. The issue is not a measure-zero nuisance: uniform convergence must hold for every parameter setting, and tie points can produce utility values that occur in no open region.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a unified generalization framework for data-driven algorithm design. It introduces the notion of an (F,G,k)-piecewise-decomposable dual function class and proves Theorem 3.3, which bounds the pseudo-dimension of the primal parameterized algorithm class in terms of the pseudo-dimension of F* and the VC-dimension of G*. This yields sample-complexity guarantees that apply to any parameter tuning procedure. The authors instantiate the framework for sequence alignment, RNA folding, topologically associating domain prediction, and neutral affine maximizers, and they show that prior bounds for clustering, integer programming, greedy algorithms, and revenue-maximizing mechanisms are recovered as special cases. They also provide lower bounds showing tightness up to logarithmic factors for sequence alignment and voting mechanisms, and they complement the theory with experiments on alignment accuracy and mechanism-design estimation error.","tokens_in":1405,"tokens_out":1510,"duration_ms":116882,"significance":"If the framework is fully correct, it is a significant unification: it replaces case-by-case pseudo-dimension analyses with a single structural condition, and it yields new bounds for computational biology algorithms and voting mechanisms. The proof of Theorem 3.3 is transparent and rests on standard Sauer/Pollard arguments, and the paper carefully extracts the key counting lemma (Lemma 3.4). The recovery of prior results is a genuine strength, as is the inclusion of tightness lower bounds for two concrete application families. The experimental section is a useful illustration, though it is not the main contribution. The main caveat, developed below, is that the application lemmas prove piecewise constancy only on open cells of hyperplane arrangements, whereas the definition of piecewise decomposability requires equality on all parameter vectors, including lower-dimensional tie points.","major_comments":[{"comment":"The proof of Theorem 3.3 and the application lemmas require the equality u*_x(u_rho) = f_{b_x(rho)}(u_rho) to hold for every parameter vector rho, including parameter values lying on the boundary hyperplanes. The lemmas only establish that the algorithm's output is fixed on the open connected components of R^d \\ H. On a boundary face, the strict sign vector b is the same as on one adjacent open cell, and the construction either assigns the piece function of that adjacent cell or assigns f_0 to sign patterns not corresponding to open cells. If tie-breaking at the boundary selects a different co-optimal solution---or a solution that is co-optimal only on the face---the utility at the boundary differs from the assigned piece function, so the decomposability equality fails. The co-optimal-constant assumption does not repair this, because the set of co-optimal solutions on the face is different from the set on either adjacent open cell, and the assumption only fixes the output once that set is fixed. Since pseudo-dimension is a worst-case quantity over all parameters, these lower-dimensional tie points cannot be ignored. This affects the pseudo-dimension bounds claimed for sequence alignment, RNA folding, TAD prediction, and voting mechanisms. A repair would be to include both strict and non-strict halfspace indicators as boundary functions so that each face of the arrangement receives its own sign pattern, and to assign a piece function to every such face; with the co-optimal-constant property on faces, the asymptotic bounds should be preserved up to constant factors.","section":"Section 4, Definition 3.2, and Lemmas 4.1, 4.2, 4.4, 4.5, 4.6, 5.1"},{"comment":"The abstract states that the guarantees are 'tight up to logarithmic factors in the worst case,' but the lower bounds in Theorem 3.6 are proved only for two concrete classes (sequence alignment and voting mechanisms), not for the general (F,G,k)-piecewise-decomposable setting. Please qualify the tightness claim so that it refers to the demonstrated lower-bound instances, or provide a general lower bound matching Theorem 3.3.","section":"Abstract and Section 3, Theorem 3.6"}],"minor_comments":[{"comment":"The caption and the body text appear to disagree about which line is the anonymous-SPA upper bound and which is the non-anonymous-SPA empirical estimation error: the caption says the orange dashed line is the AA upper bound and the blue solid line is the AN lower bound, while the text near Equation (22) describes the blue solid line as the right-hand side of Equation (22). Please reconcile these labels.","section":"Section 7.2.1, Figure 7"},{"comment":"The word 'pseduo-dimension' is misspelled and should be 'pseudo-dimension'.","section":"Page 9, proof of Theorem 3.3"},{"comment":"Reference [16] is malformed: it appears to merge the authors of the present paper with unrelated text ('Dimitris Bertsimas and Vassilis Digalakis Jr.'). Please correct this entry.","section":"References"},{"comment":"The term 'co-optimal-constant' is used informally in the text and in Theorem 4.3; please provide a formal definition at its first use, since it is central to the tie-breaking discussion.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"The skeptic's concern is real: the application lemmas establish piecewise structure only on open cells, while Definition 3.2 requires equality on all of parameter space, including tie points. This is a load-bearing gap for the applications, but it appears repairable within the manuscript's scope by refining the boundary functions and assigning piece functions to all faces of the arrangement. The central Theorem 3.3 itself is sound; I would not reject the paper over this issue. The authors should also clean up the figure-label inconsistency and the malformed reference."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main theorem is a real unification: if the dual class is (F,G,k)-piecewise decomposable, the pseudo-dimension bound in terms of Pdim(F*) and VCdim(G*) is proved cleanly with a Sauer/dual-class counting argument, and it recovers the prior case-by-case bounds while adding new applications. The lower bounds (Ω(log n) for sequence alignment, Ω(n) for voting) are solid. The framework deserves a serious referee.\n\nThe soft spot is the boundary tie-breaking in the applications. The decomposability lemmas use strict halfspace indicators (e.g., I{a·ρ<0}), so a parameter point where two candidate solutions tie has the same bit vector as one open side. The co-optimal-constant assumption only says that within a region with a fixed set of co-optimal solutions, the output is fixed; it does not say the tie point's output matches the adjacent open region. Thus h(y)=f_b(y) can fail exactly on the boundaries, and uniform convergence is over every parameter setting. This is not a measure-zero nuisance — boundary points can produce labelings that occur in no open region. The general theorem is safe if the decomposability holds exactly, but the applications as stated do not establish that. A fix likely requires an explicit tie-breaking rule or a decomposition that accounts for lower-dimensional faces, which could change the bit counts in the lemmas.\n\nThere are minor issues too: in Section 7.2.1 the text says the optimal non-anonymous SPA has revenue 0.38 and the anonymous has 0.57, but describes the former as \"larger\" — the numbers say the opposite. Also, the proof of Theorem 5.2 has a typo where \"if b_l=0\" appears in the second claim; it should be b_l=1.\n\nWho this is for: anyone working on sample complexity of algorithm configuration. The paper should be sent back to the authors with major revisions. The framework will likely survive a patched tie-breaking argument, but the current version overclaims for the DP and voting applications. I'd accept it after the boundary issue is handled.","headline":"Genuinely unifying sample-complexity theorem, but the application lemmas have an unhandled tie-breaking problem at parameter boundaries that, as written, breaks the piecewise-decomposability claims.","tokens_in":56221,"tokens_out":7274,"would_cite":true,"duration_ms":86002,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves a unified sample-complexity theorem for data-driven algorithm design whenever an algorithm's performance is piecewise-structured in its parameters.","keywords":["data-driven algorithm design","sample complexity","generalization bounds","pseudo-dimension","dual class","piecewise decomposability","algorithm configuration","sequence alignment"],"falsifier":"Run the proof's core counting inequality directly: build N dual functions from a candidate (F,G,k)-piecewise decomposable class, enumerate all sign patterns relative to thresholds, and check whether 2^N exceeds (ekN)^{VCdim(G*)} (eN)^{Pdim(F*)}; exceeding it would contradict the proof of Theorem 3.3 and give a concrete counterexample.","tokens_in":55192,"feed_emoji":"🧮","tokens_out":10291,"duration_ms":109036,"temperature":0.7,"pith_summary":"This paper tries to establish a general theorem saying how many training instances suffice to guarantee that a parameter setting with strong average performance will also perform well on unseen instances. Its central claim is that whenever every fixed instance induces a performance function over the parameter space that is piecewise constant, piecewise linear, or more generally piecewise structured, the pseudo-dimension of the utility class is controlled by the complexity of the boundary and piece classes. Concretely, the pseudo-dimension is O((Pdim(F*) + VCdim(G*)) ln(Pdim(F*) + VCdim(G*)) + VCdim(G*) ln k), which translates into a uniform bound of O~(H sqrt((Pdim(U) + ln(1/delta))/N)) on the gap between training and expected performance. A sympathetic reader would care because this is a single structural condition that unifies previous case-by-case guarantees for greedy algorithms, clustering, integer programming, and selling mechanisms, and it gives new guarantees for voting mechanisms and computational biology algorithms.","feed_headline":"A single bound fixes how much data tuning an algorithm needs","feed_subtitle":"Algorithms with piecewise-structured performance generalize once training sets pass a bound set by their dual class.","key_machinery":"The carrying object is the dual class U* = {u_x | x in X}, the set of performance functions that fix a problem instance and vary the parameter vector; each u_x maps the primal class U to [0,H]. The paper combines two complexity measures: the pseudo-dimension of the dual piece class F* and the VC-dimension of the dual boundary class G*. Its proof counts sign patterns: for N instances, the union of their boundary functions induces at most (ekN)^{VCdim(G*)} regions of the parameter space, by Lemma 3.4 and Sauer's lemma on the dual boundary class; within any one region, the N piece functions can produce at most (eN)^{Pdim(F*)} labelings relative to fixed thresholds. Multiplying the region count by the per-region labeling count and solving 2^N <= (ekN)^{VCdim(G*)} (eN)^{Pdim(F*)} yields the pseudo-dimension bound.","core_discovery":"The central discovery is that the hard part of data-driven algorithm design is not the particular algorithm but the geometry of how its performance depends on its parameters. For a fixed problem instance, the algorithm's utility as a function of the parameter vector belongs to the dual class U*; this paper defines U* to be (F,G,k)-piecewise decomposable when at most k boundary functions from G partition the parameter space into regions and on each region the utility equals one of the piece functions from F. Theorem 3.3 states that under this condition Pdim(U) = O((Pdim(F*) + VCdim(G*)) ln(Pdim(F*) + VCdim(G*)) + VCdim(G*) ln k). Feeding this through the classic Pollard pseudo-dimension bound, the paper obtains that with probability 1-delta over N training instances, for every parameter setting the difference between average and expected performance is O~(H sqrt((Pdim(U) + ln(1/delta))/N)). This establishes that piecewise structure alone, regardless of how parameters are tuned, is enough for uniform convergence.","pith_inferences":["The same counting argument could in principle yield sample-complexity bounds for portfolio-based algorithm selection, where the learned object is a mapping from instance features to an algorithm choice rather than a single parameter vector; the paper lists portfolio learning as future work.","The theorem's dependence on VCdim(G*) rather than the primal boundary complexity suggests a transferable design principle: high-dimensional parameter spaces are tractable whenever the boundary class is simple, as in Lemma 3.10 where halfspace boundaries give O(d ln(dk)).","A testable extension would be to relax the co-optimal tie-breaking assumption: algorithms whose output is not fixed on open co-optimal regions may still admit a decomposable dual if the tie-breaking rule itself is piecewise structured, extending the computational biology bounds."],"forward_implications":["For any algorithm family whose dual functions are (F,G,k)-piecewise decomposable, O~(H^2 (Pdim(F*) + VCdim(G*) ln k)/epsilon^2) training instances guarantee that empirical average performance is within epsilon of expected performance uniformly over all parameter settings.","The theorem recovers the existing generalization bounds for greedy knapsack and maximum-weight independent set algorithms, linkage-based clustering, branch-and-bound and SDP rounding for integer programs, and revenue-maximizing selling mechanisms.","New guarantees follow for computational biology: pairwise and progressive sequence alignment and RNA folding have pseudo-dimension O(ln n) in the affine-gap model, while TAD prediction has pseudo-dimension O(n^2), all under piecewise-constant duals.","Neutral affine maximizer voting mechanisms have pseudo-dimension O(n ln m), and a matching lower bound of Omega(n) shows the main theorem is tight up to logarithmic factors.","Because the guarantees do not depend on how the parameter search is conducted, they apply equally to manual tuning, automated configuration, and any future search procedure."],"supporting_citations":[{"why":"Supplies the classic pseudo-dimension-based uniform convergence bound, Equation (2), which converts a pseudo-dimension bound into the paper's generalization guarantee.","marker":"[83]"},{"why":"Sauer's lemma is the combinatorial engine used in Lemma 3.4 to bound the number of regions and sign patterns in the proof of Theorem 3.3.","marker":"[90]"},{"why":"Formalizes the dual class, the central object the paper analyzes to extract piecewise structure from the parameter-dependent performance functions.","marker":"[3]"},{"why":"Introduced the distributional model of data-driven algorithm design and the greedy algorithm families whose generalization bounds the paper recovers.","marker":"[48]"},{"why":"Supplies the clustering and integer-programming piecewise-structure lemmas that Section 6 reproduces through the general theorem.","marker":"[7]"},{"why":"Source of the branch-and-bound hyperplane structure and variable-selection-policy bounds recovered in Section 6.2.","marker":"[8]"},{"why":"Provides the delineability condition for selling mechanisms, which translates directly into piecewise decomposability and is recovered in Section 6.4.","marker":"[10]"},{"why":"Prior parametric sequence-alignment analyses supply the O(n^{3/2}) bound on the number of distinct alignments that Lemma 4.2 relies on.","marker":"[36, 50, 81]"},{"why":"Defines the TAD-prediction dynamic programming algorithm whose piecewise structure is analyzed in Lemma 4.6.","marker":"[37]"},{"why":"Defines the RNA folding algorithm whose piecewise structure is analyzed in Lemma 4.5.","marker":"[80]"}],"fun_headline_variants":["How much data? One bound settles it","Tuning algorithms? One bound to go","Piecewise structure yields sample bounds","A universal data bound for algorithm tuning","Generalize from less data? Yes, with this bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the paper's co-optimal-constant assumption: in any region of parameter space where the set of co-optimal solutions is fixed, the algorithm's output is also fixed, so the utility function cannot vary because of tie-breaking within that region.","fun_headline_variants_meta":{"raw":{"variants":["How much data? One bound settles it","Tuning algorithms? One bound to go","Piecewise structure yields sample bounds","A universal data bound for algorithm tuning","Generalize from less data? Yes, with this bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00193,"raw_usage":{"total_tokens":7606,"prompt_tokens":1049,"completion_tokens":6557,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":665,"completion_tokens_details":{"reasoning_tokens":6491}},"tokens_in":665,"tokens_out":6557,"duration_ms":54701,"temperature":1.0,"reasoning_tokens":6491,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:31:15.761314+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the proof's core counting inequality directly: build N dual functions from a candidate (F,G,k)-piecewise decomposable class, enumerate all sign patterns relative to thresholds, and check whether 2^N exceeds (ekN)^{VCdim(G*)} (eN)^{Pdim(F*)}; exceeding it would contradict the proof of Theorem 3.3 and give a concrete counterexample.","supporting_citations":[{"cited_title":"Convergence of Stochastic Processes","cited_arxiv_id":null,"evidence_quote":"Supplies the classic pseudo-dimension-based uniform convergence bound, Equation (2), which converts a pseudo-dimension bound into the paper's generalization guarantee."},{"cited_title":"On the density of families of sets","cited_arxiv_id":null,"evidence_quote":"Sauer's lemma is the combinatorial engine used in Lemma 3.4 to bound the number of regions and sign patterns in the proof of Theorem 3.3."},{"cited_title":"A PAC approach to application-specific algorithm se- lection","cited_arxiv_id":null,"evidence_quote":"Introduced the distributional model of data-driven algorithm design and the greedy algorithm families whose generalization bounds the paper recovers."},{"cited_title":"Fast algorithm for predicting the secondary structure of single-stranded RNA","cited_arxiv_id":null,"evidence_quote":"Defines the RNA folding algorithm whose piecewise structure is analyzed in Lemma 4.5."}],"review_version":1}