{"id":"f151c2d2-d556-4f10-811d-d62146492f96","arxiv_id":"2412.11239","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A new training method for set functions learned from optimal subset oracles uses implicit differentiation, plus a convergence condition for the underlying fixed-point iterations.","lead":"This paper speeds up training of set-function models that learn from optimal-subset examples by replacing loop-unrolled gradients with implicit differentiation. It also proves a boundedness condition that guarantees the fixed-point iterations used during training converge.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.2 is internally sound, but the headline iDiffMF2/iDiffMF* variants solve the normalized fixed-point equation (27), not the equation (8) covered by the theorem, so the convergence and implicit-differentiation guarantees do not directly apply to the methods that are actually evaluated.","rationale":"The proof of Theorem 4.2 is internally sound: Lemma E.2 bounds the Hessian elements by 4 sup|F~|, the σ′ factor is at most 1/4, and the mean-value-theorem argument yields a Lipschitz constant ≤ |V| sup|F~|, so Assumption 4.1 is sufficient for a Banach contraction; Theorem 4.3 then follows by the implicit function theorem because ‖∂ψT‖_F < 1 implies I − ∂ψT is invertible. The problem is applicability rather than validity. The headline algorithms iDiffMF2 and iDiffMF* normalize the gradient by a ψ-dependent norm, which changes the fixed-point equation in a way not covered by the theorem, and the scalar-rescaled iDiffMFc is not checked against Assumption 4.1. The printed Algorithm 2 also omits the convergence loop, further separating the stated theory from the executed method. These observations match the reader's weakest assumption, and no new objection that would overturn the conditional verdict emerged. The theorem could still be correct and the heuristics could still work well in practice; the missing piece is a direct check that the implemented fixed-point map satisfies the contraction condition, or a separate theorem covering the normalized map. Therefore the reader's CONDITIONAL verdict is appropriate and should remain unchanged.","tokens_in":27453,"tokens_out":7792,"duration_ms":77580,"concrete_test":"Instrument the training code to record, under the best reported hyperparameters, the empirical Lipschitz constant of the actual fixed-point map used by iDiffMF2 and iDiffMF*, for example by finite differences over ψ around the converged fixed points, and compare it with 1. Also compute a Monte Carlo or exact bound on sup_{ψ∈[0,1]^|V|}|F~(ψ,θ)| for the unmodified F~ and compare with 1/|V|; note that for a multilinear relaxation this supremum is attained at a vertex, so for small |V| it can be checked exactly. If the normalized map has Jacobian norm ≥ 1 at the fixed point, or if Assumption 4.1 is violated for the unmodified map, rerun the Table 2 comparisons using the unmodified map Tθ with a temperature explicitly chosen so that sup|F~| < 1/|V|. If the Jaccard scores change materially, the reported advantage is attributable to the normalization heuristic, not to the proved theorem.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theoretical result is a contraction guarantee for the unmodified map Tθ(ψ) = σ(∇ψ F~(ψ,θ)) under Assumption 4.1. However, the methods evaluated in Section 5 do not run this map: Appendix I.3 replaces ∇ψ F~(ψ,θ) with 2∇ψ F~(ψ,θ)/(|V|Q), where Q = ‖∇ψ F~‖₂ for iDiffMF2, Q = ‖∇ψ F~‖* for iDiffMF*, and Q = c for iDiffMFc. For the two norm-normalized variants, Q depends on ψ, so the resulting map is not σ of a gradient field and is not the fixed-point equation whose contraction is proved. Theorem 4.2 and the implicit-differentiation formula A⁻¹B in Theorem 4.3 are stated for G(ψ,θ) = σ(∇ψ F~(ψ,θ)) − ψ; they do not cover the normalized equation actually solved. For iDiffMFc, the fixed-point equation is still of the same form with a rescaled function, so it could in principle be covered, but Assumption 4.1 is never verified at the chosen c. Moreover, Algorithm 2 as printed performs only one fixed-point update (lines 5–8) and contains no loop to convergence, so the pseudocode does not describe the root-finding procedure promised in the text and used in the experiments. The theorem is not internally contradictory, but the load-bearing gap is between the proved equation and the implemented equation: the empirical gains reported for iDiffMF2/iDiffMF* may be due to the normalization heuristic rather than to the proved implicit-differentiation framework. A separate contraction/invertibility analysis for the normalized maps, or an empirical verification of Assumption 4.1 for the unmodified map, would be needed to close this gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the problem of learning a set function from an optimal-subset oracle, in the framework of Ou et al. (2022) where the oracle is modeled by a Boltzmann distribution and mean-field variational inference leads to a fixed-point equation ψ = σ(∇ψ F~(ψ,θ)). The authors' contribution is twofold: (i) Theorem 4.2 gives a contraction guarantee and uniqueness for this fixed point under Assumption 4.1 (uniform bound on the multilinear relaxation), and (ii) Theorem 4.3 uses the implicit function theorem to compute the parameter gradient as A⁻¹B, avoiding backpropagation through the unrolled iterations. The proposed algorithm iDiffMF is evaluated against DiffMF, EquiVSet_ind, EquiVSet_copula on set anomaly detection, product recommendation, and compound selection datasets. The reported iDiffMF2/iDiffMF* variants achieve the best or second-best Jaccard coefficient in most cases, with constant GPU memory in the number of fixed-point iterations.","tokens_in":27893,"tokens_out":7436,"duration_ms":62367,"significance":"The convergence and implicit-differentiation results are cleanly stated, and the contraction proof in Appendix E is mathematically sound under Assumption 4.1. The paper's empirical results are promising, and the O(1) memory benefit is clearly demonstrated in Figure 1. However, the manuscript currently has a load-bearing disconnect between the proved fixed-point equation and the algorithm actually evaluated: the normalized variants iDiffMF2/iDiffMF* solve equation (27), not equation (7), and no convergence/invertibility analysis is given for that map. In addition, Algorithm 2 as printed does not contain the iterative root-finding loop described in the text. Both issues are fixable in revision. If addressed, this would be a solid contribution to the implicit-differentiation and neural-set-function literature.","major_comments":[{"comment":"Theorem 4.2 and Theorem 4.3 are stated for the fixed-point equation ψ = σ(∇ψ F~(ψ,θ)) and the corresponding implicit map G(ψ,θ) = σ(∇ψ F~(ψ,θ)) − ψ. The methods reported as the main empirical contribution, iDiffMF2 and iDiffMF*, instead solve Eq. (27), ψ = σ(2∇ψ F~(ψ,θ)/(|V|Q)), where Q = ||∇ψ F~(ψ,θ)||₂ or Q = ||∇ψ F~(ψ,θ)||★. Since Q depends on ψ, this map is not of the form σ(∇ψ F~) for a fixed function F~, so the contraction proof in App. E and the implicit-differentiation formula A⁻¹B of Theorem 4.3 do not apply to the evaluated variants. The iDiffMFc variant is covered in form (a constant rescaling of F~), but Assumption 4.1 is never verified at the chosen c, and the dynamic normalization in iDiffMF2/iDiffMF* changes the fixed point itself. Please provide an analysis of the normalized map or verify the contraction/invertibility conditions empirically (e.g., by tracking an estimate of sup_ψ |F~(ψ,θ)| during training), and state clearly which variants are covered by Theorem 4.2.","section":"§5.1, App. I.3, Eq. (27)"},{"comment":"The pseudocode for iDiffMF performs a single fixed-point update: lines 5–8 compute ψ* from ψ(0) without any loop or stopping criterion. However, the text (Sec. 5.1 and Sec. 4.3) and the reported results use a root-finding procedure with tolerance ε = 10⁻⁶, and Sec. 4.4 analyzes the number of iterations to convergence. This inconsistency makes the algorithm as printed not the algorithm evaluated. The pseudocode should either include the iterative loop (e.g., while ||ψ(k) − ψ(k−1)|| > ε) or be explicitly labeled as a simplified single-step illustration with the actual iterative procedure stated in the appendix.","section":"Algorithm 2, Sec. 5.1"},{"comment":"Assumption 4.1 is the precondition for both convergence and the invertibility of A in Theorem 4.3, yet the paper never checks it in any of the reported experiments. The claim that a Lipschitz-regularized network can satisfy the assumption by adjusting the temperature parameter is plausible but not demonstrated for the architectures and hyperparameters used. Without any empirical estimate of sup_ψ |F~(ψ,θ)| (or, failing that, a discussion of a practical enforcement mechanism), the theoretical guarantee remains disconnected from the experimental validation. Please add such a verification, at least for a representative set of datasets and checkpoints.","section":"Assumption 4.1, Sec. 5.1"}],"minor_comments":[{"comment":"The constraint \"for all i ∈ {i, . . . , n}\" should read \"for all i ∈ {1, . . . , N}\"; the current index set is self-referential.","section":"Eq. (9)"},{"comment":"The proof text contains \"we are ready to proof Thm. 4.2\" (should be \"prove\"), and Eq. (21) uses \"|0,1|\" where \"[0,1]\" is meant.","section":"App. E"},{"comment":"Several entries lack spacing (e.g., \"CelebA202,599100008\" and \"furniture32\"), which makes the table hard to read.","section":"Table 1"},{"comment":"The text describes iDiffMF2 and iDiffMF* as using \"Frobenius and nuclear norm scaling\", but App. I.3 defines Q as the ℓ₂ norm and the nuclear norm of the gradient; for a vector gradient the ℓ₂ norm is not the Frobenius norm, so the terminology should be aligned.","section":"Sec. 5.1 / App. I.3"},{"comment":"In the displayed complexity expression, the denominator is written as \"log ω\" but the same quantity is denoted q in App. H; unify the notation and make clear that ω is the Lipschitz constant of the fixed-point map.","section":"Sec. 4.4"}],"recommendation":"major_revision","confidential_remarks":"This is a promising paper for the implicit-differentiation community. The main concern is not the validity of the proofs but the gap between the analyzed and implemented fixed-point equations, which a revision can close. I would also encourage the authors to release the code at the time of the revised submission, since the current manuscript states that code will be made public only after review."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: the paper proves a real contraction theorem and applies implicit differentiation to a fixed-point problem where unrolling was expensive. That is a legitimate contribution. But the methods that actually get the good numbers solve a different fixed-point equation than the one covered by the theorem, and the printed algorithm has no loop to convergence. Those gaps are fixable, but they matter for the empirical claims.\n\nThe new thing is Theorem 4.2: under sup_{ψ}|F~(ψ,θ)| < 1/|V|, the map ψ ↦ σ(∇ψF~(ψ,θ)) is a contraction on the cube, so the DiffMF iterations converge to a unique fixed point from anywhere. I checked App. E; the proof is sound. Applying DEQ-style implicit differentiation to this system is a natural and useful move, and the memory measurements support the claimed O(1) backward memory. The citation pattern is fine, with the novelty over Ou et al. clearly stated. On the experimental side, iDiffMF2 and iDiffMF* are best or second-best on most of the Amazon and BindingDB tasks, which is a genuine improvement over the baselines.\n\nNow the soft spots. First, Assumption 4.1 is never verified for the trained networks. The authors say Lipschitz networks and temperature can make it hold, but they don't actually do it. Second, and more important: the two variants that get the good results, iDiffMF2 and iDiffMF*, replace ∇ψF~ by 2∇ψF~/(|V|Q) with Q the ψ-dependent norm. That is equation (27), not equation (8). The contraction theorem and the implicit-differentiation formula apply to G(ψ,θ)=σ(∇ψF~)−ψ, not to the normalized map. So the theoretical guarantees don't cover the headline methods. For iDiffMFc the fixed point is still of the same form with a constant scaling, so it could be covered, but c is chosen by cross-validation and Assumption 4.1 isn't checked at that c. Third, Algorithm 2 as printed performs a single fixed-point update per element and contains no loop to convergence; it doesn't match the root-finding procedure described in the text or used in the experiments. The supplement says code will be released after review; at the moment there's no public code.\n\nNone of this makes me think the method is wrong. The contraction proof is solid, and the normalization heuristics plausibly help. But the paper as submitted overclaims the connection between its theorem and its experiments. A revision should either extend the analysis to the normalized maps, or honestly frame the normalization as a heuristic and verify the original assumption on at least some datasets. The pseudocode needs to match the implementation.\n\nWho should read it: anyone working on learning set functions from optimal subset oracles, and people applying implicit differentiation to variational fixed points. It deserves a serious referee; I'd send it out. With the gaps closed, it would be a solid paper in a niche area.","headline":"Sound contraction theory plus a genuinely useful implicit-differentiation trick, but the evaluated variants solve a different fixed-point equation than the theorem covers, and the printed pseudocode omits the root-finding loop.","tokens_in":28368,"tokens_out":3664,"would_cite":false,"duration_ms":33700,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T07","65H10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that, under a uniform bound on the multilinear relaxation, the fixed-point iterations for learning set functions converge to a unique solution, and shows how to differentiate through that fixed point via implicit…","keywords":["set functions","optimal subset oracle","mean-field variational inference","fixed-point iteration","implicit differentiation","deep equilibrium models","multilinear relaxation","subset selection"],"falsifier":"Train a set function on any of the paper's datasets and measure $\\sup_{\\psi\\in[0,1]^{|V|}}|\\tilde{F}(\\psi,\\theta)|$ during training; if it exceeds $1/|V|$ while the fixed-point iterations still converge, or if two different starting points $\\psi^{(0)}$ lead to different limits, then the contraction condition is not necessary — and the guarantee as stated would not cover the practical regime. More directly, one could construct a simple set function (e.g., a quadratic multilinear extension) with $\\sup|\\tilde{F}|$ slightly above $1/|V|$ and check whether the fixed-point map has multiple fixed points or the iteration cycles.","tokens_in":27256,"feed_emoji":"🧮","tokens_out":5478,"duration_ms":43490,"temperature":0.7,"pith_summary":"This paper tackles a bottleneck in learning set functions from an optimal subset oracle: the mean-field variational inference of Ou et al. (2022) reduces training to a fixed-point iteration, but those iterations can diverge and backpropagating through them stacks huge Jacobians. The authors prove that if the multilinear relaxation of the utility function is bounded in absolute value by the reciprocal of the ground-set size, the fixed-point map is a contraction, so the iterations converge to a unique solution from any start. They then show how to differentiate through the converged fixed point using the implicit function theorem, replacing memory-hungry loop unrolling with a linear solve. If correct, this makes the method both theoretically grounded and practical on larger problems.","feed_headline":"Set-function learning gets a convergence proof and O(1) memory","feed_subtitle":"A boundedness condition guarantees unique fixed points; implicit differentiation replaces heavy unrolling with a linear solve.","key_machinery":"The load-bearing object is the map $T_\\theta(\\psi)=\\sigma(\\nabla_\\psi \\tilde{F}(\\psi,\\theta))$, built from the multilinear relaxation $\\tilde{F}(\\psi,\\theta)$ of the set function and the sigmoid. The proof that $T_\\theta$ is a contraction uses the multivariate mean value theorem, the fact that the sigmoid derivative is at most $1/4$, and a Hessian bound of $4\\sup|\\tilde{F}|$, yielding a Lipschitz constant of $|V|\\sup|\\tilde{F}| < 1$ under Assumption 4.1; Banach's fixed-point theorem then gives uniqueness and convergence. For differentiation, the implicit function theorem applied to $G(\\psi,\\theta)=\\sigma(\\nabla_\\psi \\tilde{F}(\\psi,\\theta))-\\psi=0$ turns the Jacobian into the solution of a linear system $A^{-1}B$, avoiding unrolled backpropagation.","core_discovery":"The central claim is Theorem 4.2: under the uniform bound $\\sup_{\\psi\\in[0,1]^{|V|}} |\\tilde{F}(\\psi,\\theta)| < 1/|V|$, the map $T_\\theta(\\psi)=\\sigma(\\nabla_\\psi \\tilde{F}(\\psi,\\theta))$ is a contraction on the unit hypercube, so the fixed-point equation $\\psi=\\sigma(\\nabla_\\psi \\tilde{F}(\\psi,\\theta))$ has a unique solution and the iterations $\\psi^{(k)}=T_\\theta(\\psi^{(k-1)})$ converge to it from any starting point. From this, Theorem 4.3 derives the gradient of the loss through the fixed point as $\\partial_\\theta \\psi^*(\\theta)=A^{-1}B$, where $A=I-\\Sigma'(\\nabla_\\psi \\tilde{F})\\nabla^2_\\psi \\tilde{F}$ and $B=\\Sigma'(\\nabla_\\psi \\tilde{F})\\partial_\\theta \\nabla_\\psi \\tilde{F}$, which requires only the final fixed point rather than all iterates. The paper further supports the theory with experiments on synthetic and real-world subset selection tasks, showing the implicit-differentiation variants match or exceed prior methods while using constant memory.","pith_inferences":["If the bound in Assumption 4.1 is hard to certify, a testable alternative is to enforce it during training (e.g., by spectral normalization of the network or by adaptive temperature), which would make the convergence guarantee apply to the actual training procedure rather than a scaled variant.","The contraction condition is only sufficient; the empirical success of the normalized variants suggests the true fixed-point map may be contracting in a wider region, or that the relevant quantity is the Lipschitz constant of $T_\\theta$ rather than the sup-norm bound on $\\tilde{F}$. A direct measurement of the Lipschitz constant during training would settle this.","The $A^{-1}B$ formula could be extended to other energy-based models with different link functions (e.g., softmax over subsets), where a similar implicit-differentiation treatment would avoid unrolling over the combinatorial state space."],"forward_implications":["Under Assumption 4.1, the variational mean-field solver inherits a rigorous convergence guarantee: uniqueness of the fixed point and global convergence from any initialization (Theorem 4.2).","The implicit-differentiation gradient formula $\\partial_\\theta \\psi^* = A^{-1}B$ (Theorem 4.3) holds at the fixed point, so training can use constant memory $O(1)$ instead of $O(K)$ in the number of iterations.","Because the gradient no longer requires unrolling, practitioners can run the fixed-point solver to a tight tolerance (e.g., $10^{-6}$) rather than the $K\\le 5$ iterations used by prior work.","The theory applies to any Lipschitz-regularized network with appropriately chosen Boltzmann temperature, since scaling the energy by a constant controls the bound in Assumption 4.1.","In experiments, the iDiffMF variants (with gradient normalization by $\\ell^2$ or nuclear norm) reach best-or-second-best Jaccard scores on most datasets, suggesting the practical value of implicit differentiation in this setting."],"supporting_citations":[{"why":"Supplies the learning-set-functions-from-optimal-subset-oracle framework, the energy-based/mean-field variational inference reduction to the fixed-point equation Eq. (8), and the DiffMF/EquiVSet baselines.","marker":"(Ou et al. 2022)"},{"why":"Defines the multilinear relaxation $\\tilde{F}$ and the gradient/Hessian identities of Lemma C.1 and Corollary C.2 used throughout the proof.","marker":"(Calinescu et al. 2011)"},{"why":"Provides Banach's fixed-point theorem, the contraction argument that underlies uniqueness and convergence in Theorem 4.2.","marker":"(Banach 1922)"},{"why":"Provides the implicit function theorem used to derive the gradient formula $\\partial_\\theta\\psi^*=A^{-1}B$ in Theorem 4.3.","marker":"(Krantz and Parks 2002)"},{"why":"Provides the modular implicit differentiation tool (used in the experiments) that makes the linear-system-based gradient computation practical.","marker":"(Blondel et al. 2022)"},{"why":"Introduces deep equilibrium models and the paradigm of differentiating through fixed points via implicit differentiation, which this paper adapts to set functions.","marker":"(Bai, Kolter, and Koltun 2019)"}],"fun_headline_variants":["Implicit diff makes set-function learning O(1) memory","Convergence proof for set-function fixed points","Efficient set-function learning via implicit diff","Set-function learning: constant memory, proven convergence","Implicit diff fixes set-function backprop bottleneck"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole convergence guarantee rests on Assumption 4.1, the uniform bound $|\\tilde{F}(\\psi,\\theta)| < 1/|V|$, but the paper never verifies this bound for the trained networks, and the implemented variants normalize the gradient or scale by a constant, so the fixed-point equation they actually solve is a different one.","fun_headline_variants_meta":{"raw":{"variants":["Implicit diff makes set-function learning O(1) memory","Convergence proof for set-function fixed points","Efficient set-function learning via implicit diff","Set-function learning: constant memory, proven convergence","Implicit diff fixes set-function backprop bottleneck"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000145,"raw_usage":{"total_tokens":1161,"prompt_tokens":910,"completion_tokens":251,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":526,"completion_tokens_details":{"reasoning_tokens":178}},"tokens_in":526,"tokens_out":251,"duration_ms":2808,"temperature":1.0,"reasoning_tokens":178,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T15:09:18.536435+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train a set function on any of the paper's datasets and measure $\\sup_{\\psi\\in[0,1]^{|V|}}|\\tilde{F}(\\psi,\\theta)|$ during training; if it exceeds $1/|V|$ while the fixed-point iterations still converge, or if two different starting points $\\psi^{(0)}$ lead to different limits, then the contraction condition is not necessary — and the guarantee as stated would not cover the practical regime. More directly, one could construct a simple set function (e.g., a quadratic multilinear extension) with $\\sup|\\tilde{F}|$ slightly above $1/|V|$ and check whether the fixed-point map has multiple fixed points or the iteration cycles.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the multilinear relaxation $\\tilde{F}$ and the gradient/Hessian identities of Lemma C.1 and Corollary C.2 used throughout the proof."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Banach's fixed-point theorem, the contraction argument that underlies uniqueness and convergence in Theorem 4.2."},{"cited_title":"G.; and Parks, H","cited_arxiv_id":null,"evidence_quote":"Provides the implicit function theorem used to derive the gradient formula $\\partial_\\theta\\psi^*=A^{-1}B$ in Theorem 4.3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the modular implicit differentiation tool (used in the experiments) that makes the linear-system-based gradient computation practical."},{"cited_title":"Z.; and Koltun, V","cited_arxiv_id":null,"evidence_quote":"Introduces deep equilibrium models and the paradigm of differentiating through fixed points via implicit differentiation, which this paper adapts to set functions."}],"review_version":1}