{"id":"0c936ba0-86a1-4188-839a-4b6b7f441f8a","arxiv_id":"2605.14409","paper_version":1,"verdict":"CONDITIONAL","confidence":"LOW","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Requiring LICQ/SCS/SOSC everywhere in bilevel optimization is non-prevalent and rigid, while holding almost everywhere is prevalent, but the distinction introduces fundamental difficulties.","lead":"This paper proves that requiring standard regularity conditions (LICQ, SCS, SOSC) to hold at every upper-level point x in constrained bilevel optimization is a strong, non-generic assumption: small random perturbations of the lower-level problem cannot make them hold everywhere. The weaker version holding at almost every x is generic under perturbation, yet the measure-zero gap creates deep theoretical and computational obstacles.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.3","headline":"Rigidity theorems may fail to force global invariance of active-set signatures if local constancy from SCS/LICQ does not extend over the full domain of x","rationale":"The reader's weakest_assumption directly identifies the same potential failure point in the rigidity step. Because the non-prevalence result is obtained by contraposition (different invariants at two points imply no everywhere-regular perturbation exists), any gap in forcing invariance undermines the central distinction between 'every x' and 'almost every x'. The rest of the argument (prevalence of a.e. regularity, computational difficulties) is downstream of this step.","tokens_in":1810,"tokens_out":388,"duration_ms":41672,"concrete_test":"Extract the precise statement of the rigidity theorem (likely Theorem 3.1 or 3.2) and re-derive the claim that the active-set signature must be identical at every pair x1, x2; verify whether the argument uses only the local constancy implied by SCS+LICQ at each point or additionally invokes path-connectedness of the upper-level domain and continuous dependence of the KKT map on x.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The non-prevalence claim requires that whenever LICQ, SCS and SOSC hold at every x, certain structural invariants (active-set signature, multiplier signs, etc.) are necessarily constant across all x. The counterexamples then exhibit problems where no single invariant can be realized at two different x values. If the rigidity step only establishes local constancy (via implicit-function theorem on the KKT system) but the domain of x is not connected or the continuation argument across x is incomplete, then a perturbation could still produce everywhere-regularity by allowing the active set to jump on a measure-zero set while satisfying the conditions everywhere else. The abstract does not indicate whether the proof supplies a global topological argument or merely patches local constancy.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper studies regularity conditions (LICQ, SCS, SOSC) for the lower-level problem in bilevel optimization, typically imposed at every upper-level x. It proves rigidity theorems establishing that these conditions force structural invariants (active-set signatures, multiplier signs) to be constant across all x. Counterexamples demonstrate that no single invariant can hold for all x in certain problems, showing the everywhere requirement is non-prevalent (no small perturbation of lower-level data achieves it). In contrast, the almost-everywhere version is prevalent: random perturbations make each condition hold a.e. with probability 1. The manuscript further examines theoretical and computational difficulties arising from the measure-zero gap between the two requirements.","tokens_in":1965,"tokens_out":487,"duration_ms":32879,"significance":"If the central claims hold, the work provides a precise measure-theoretic and structural characterization of common assumptions in bilevel optimization. The rigidity theorems and explicit counterexamples rigorously separate the everywhere and a.e. cases, while the probabilistic prevalence result supplies a generic positive counterpart. This has direct implications for the scope of existing theory and algorithms that rely on global regularity, and the analysis of the gap between the two notions is a substantive contribution.","major_comments":[{"comment":"Rigidity theorems (as described in the abstract and introduction): the argument that LICQ/SCS/SOSC everywhere implies global constancy of active-set signatures and related invariants relies on extending local constancy (via implicit-function theorem on the KKT system) to the full domain of x. If the proof supplies only local patches without a global topological or continuation argument (e.g., when the domain of x is disconnected), then the non-prevalence claim is at risk, since a perturbation could still achieve everywhere-regularity by allowing jumps on a measure-zero set.","section":"Rigidity theorems"}],"minor_comments":[{"comment":"The abstract states that the gap between every-x and a.e.-x versions 'introduces fundamental difficulties in both theory and computation,' but the manuscript should explicitly reference the section(s) containing this analysis so readers can locate the concrete examples or theorems.","section":"Abstract"},{"comment":"Notation for the lower-level problem and the perturbation measure should be introduced with a brief reminder of the ambient function space (e.g., C^2 or Sobolev) to make the prevalence statements fully precise.","section":"Introduction"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful reading and constructive comments on our manuscript. The feedback highlights an important point regarding the global extension in our rigidity theorems, which we address below.","responses":[{"response":"We thank the referee for this observation. Our rigidity proofs begin with local constancy of active-set signatures and multiplier signs via the implicit-function theorem on the KKT system. Global constancy then follows because the set of x where the regularity conditions hold is both open (by the implicit-function theorem and continuity of the data) and closed relative to the upper-level domain (by continuation along paths). We explicitly assume the upper-level domain is connected, which is standard in bilevel optimization (e.g., convex or interval domains). On each connected component the invariants are therefore constant. Our counterexamples are constructed precisely on connected domains where the invariants differ between two points, so no small perturbation can enforce the conditions everywhere. For disconnected domains the invariants remain constant per component, but this does not affect the non-prevalence result on connected domains. We will add an explicit statement of the connectedness assumption and a brief remark on the disconnected case in the revision.","revision_made":"partial","referee_comment":"[Rigidity theorems] Rigidity theorems (as described in the abstract and introduction): the argument that LICQ/SCS/SOSC everywhere implies global constancy of active-set signatures and related invariants relies on extending local constancy (via implicit-function theorem on the KKT system) to the full domain of x. If the proof supplies only local patches without a global topological or continuation argument (e.g., when the domain of x is disconnected), then the non-prevalence claim is at risk, since a perturbation could still achieve everywhere-regularity by allowing jumps on a measure-zero set."}],"tokens_in":1438,"tokens_out":379,"duration_ms":23503,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main point here is that the usual demand for linear independence, strict complementarity, and second-order sufficiency to hold at every upper-level x is a strong condition that fails to be prevalent. Small changes to the lower-level objective and constraints cannot make it true everywhere in some cases. The paper proves rigidity results that tie those regularity conditions to fixed structural features like active-set signatures across the whole domain, then gives explicit counterexamples where those features cannot stay constant. In contrast, the weaker almost-everywhere version turns out to be prevalent: random perturbations make the conditions hold almost everywhere with probability one. They also spell out why the measure-zero gap still creates real problems for proofs and algorithms. This is new work. Prior bilevel literature often just assumes the everywhere version without checking how generic it is, and these rigidity theorems plus the prevalence argument for the weaker version do not appear in the references. The counterexamples are concrete and separate the two cases cleanly. The argument stays within standard nonlinear programming definitions and does not rely on circular constructions. One soft spot is the global reach of the rigidity step. If the local constancy from the implicit-function theorem on the KKT system does not extend across the full x-domain without extra topological work, a perturbation might still achieve everywhere-regularity by allowing jumps on null sets. The abstract indicates they close this, but the full proofs would need checking on that point. Minor gaps in the measure arguments could also surface. This paper is for researchers who build convergence theory or algorithms for bilevel problems with constraints. It gives a clear reason to prefer the almost-everywhere assumption in many settings. I would send it to peer review.","headline":"Requiring LICQ/SCS/SOSC everywhere in constrained bilevel problems is non-generic, while the almost-everywhere version holds after generic small perturbations.","tokens_in":2501,"tokens_out":407,"would_cite":true,"duration_ms":26227,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[{"relation":"unclear","rs_module":"IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean","rs_theorem":"reality_from_one_distinction","paper_passage":"rigidity theorems showing that certain structural quantities of the lower-level problem must remain invariant across all x whenever these conditions hold everywhere"},{"relation":"unclear","rs_module":"IndisputableMonolith/Cost/FunctionalEquation.lean","rs_theorem":"washburn_uniqueness_aczel","paper_passage":"LICQ, SCSC, and uniform SOSC together imply the number of local minimizers on each stratum is constant"}],"headline":"Bilevel regularity rigidity theorems orthogonal to RS distinction-forcing chain","alignment":"orthogonal","rationale":"Paper centers on prevalence/non-prevalence of LICQ/SCSC/SOSC via rigidity of active-set strata, KKT trajectories, and stratum-wise minimizer counts under C2 perturbations (Theorems 2.1, 2.5, 2.8; Counterexamples 2.3-2.10), using Sard/transversality and implicit-function arguments. No J-cost, golden-ratio identities, 8-tick periodicity, or parameter-free constant derivation appears. Domain (math.OC bilevel) lies outside RS forcing from single distinction (reality_from_one_distinction, AbsoluteFloorClosure, Cost/FunctionalEquation).","tokens_in":61006,"confidence":"high","tokens_out":327,"duration_ms":10046,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Requiring lower-level regularity conditions at every upper-level point in bilevel optimization is non-prevalent, as structural invariants cannot be made consistent by small perturbations.","keywords":["bilevel optimization","regularity conditions","constraint qualifications","prevalence","rigidity theorems","active sets","bilevel programming"],"falsifier":"An explicit lower-level problem in which the active-set pattern or the sign pattern of multipliers changes between two upper-level points x1 and x2, such that no small perturbation of the objective and constraints can make the three regularity conditions hold simultaneously at both points.","tokens_in":2690,"feed_emoji":"","tokens_out":748,"duration_ms":39568,"temperature":0.7,"pith_summary":"The paper shows that the common requirements of linear independence constraint qualification, strict complementary slackness, and second-order sufficient conditions for the lower-level problem must hold at every upper-level variable x. This global demand is strong because it forces certain structural features of the lower-level problem to stay fixed for all x, and explicit constructions demonstrate that these features can differ at distinct points x. In contrast, the same conditions hold at almost every x after a generic random perturbation of the lower-level objective and constraints. The paper establishes that the difference between the two requirements, although limited to a measure-zero set, creates basic obstacles for both the theoretical development and the numerical solution of bilevel problems.","feed_headline":"Everywhere regularity in bilevel problems is non-prevalent","feed_subtitle":"Structural invariants cannot be made consistent by small perturbations, yet the conditions hold almost everywhere after generic random ones.","key_machinery":"Rigidity theorems establishing that active-set signatures and related structural quantities of the lower-level problem must be invariant across all upper-level variables whenever the regularity conditions hold at every x.","core_discovery":"When the regularity conditions are required at every upper-level variable x, rigidity theorems prove that structural quantities of the lower-level problem, such as active-set signatures, must remain invariant over the entire upper-level domain. Counterexamples are constructed in which these invariants take different values at two distinct points x, showing that no sufficiently small perturbation of the lower-level data can enforce the conditions everywhere. In comparison, random perturbations of the lower-level objective and constraints make each condition hold at almost every x with probability one. The gap between the everywhere and almost-everywhere versions introduces fundamental theory-","pith_inferences":["Bilevel algorithms that assume everywhere regularity may need reformulation to accommodate generic problems where violations occur only on null sets.","Prevalence results indicate that bilevel problems can often be replaced by nearby ones satisfying the conditions almost everywhere for practical purposes.","Similar prevalence arguments may apply in other nested optimization problems that impose pointwise regularity on inner problems."],"forward_implications":["If regularity conditions hold at every x, then active-set structures and multiplier signs must be identical at all upper-level points.","Counterexamples exist where these structural invariants differ at distinct values of x, so the everywhere requirement cannot be met by small perturbations.","The almost-everywhere versions of the conditions hold with probability one after random perturbation of the lower-level data.","The measure-zero difference between the two requirements produces essential obstacles for theoretical analysis and for algorithm design in bilevel optimization."],"fun_headline_variants":["Bilevel regularity non-prevalent everywhere","Rigidity blocks bilevel regularity everywhere","Perturbations ensure regularity almost everywhere in bilevel","Structural rigidity in bilevel prevents full regularity"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The lower-level objective and constraint functions are smooth enough for active-set signatures and multiplier properties to be well-defined and constant when the regularity conditions hold at every upper-level point.","fun_headline_variants_meta":{"raw":{"variants":["Bilevel regularity non-prevalent everywhere","Rigidity blocks bilevel regularity everywhere","Perturbations ensure regularity almost everywhere in bilevel","Structural rigidity in bilevel prevents full regularity"]},"model":"grok-4.3","cost_usd":0.010252,"raw_usage":{"total_tokens":4500,"prompt_tokens":745,"num_sources_used":0,"completion_tokens":53,"cost_in_usd_ticks":102515500,"prompt_tokens_details":{"text_tokens":745,"audio_tokens":0,"image_tokens":0,"cached_tokens":64},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":3702,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":745,"tokens_out":53,"duration_ms":46786,"temperature":1.0,"reasoning_tokens":3702,"cache_read_input_tokens":64,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-15T01:53:42.973453+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit lower-level problem in which the active-set pattern or the sign pattern of multipliers changes between two upper-level points x1 and x2, such that no small perturbation of the objective and constraints can make the three regularity conditions hold simultaneously at both points.","supporting_citations":[],"review_version":1}