{"id":"fed84a48-6c0a-4571-ad74-3f17b93b3674","arxiv_id":"2608.11003","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"A perturbed ADMM algorithm with convergence-rate guarantees is developed for finite-alphabet information bottleneck problems that impose exact independence from a sensitive variable.","lead":"This paper builds an ADMM-style solver for rate-limited representation learning under perfect privacy, proving the algorithm converges to an approximately private solution. A generalist should read it because privacy-preserving data representations are central to trustworthy machine learning, and here the solver comes with formal guarantees.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Assumption 2 (uniform positivity of all iterates) is the load-bearing premise; it is neither enforced nor verified, and it can fail exactly at the active-rate boundary the paper targets.","rationale":"The reader's weakest-assumption analysis correctly identifies Assumption 2 as the most load-bearing premise. The theorem statements are internally coherent, and the proofs are detailed; the KŁ-based rate analysis is appropriate and the definability argument in Appendix M is a genuine step toward the KŁ property. However, the central guarantee is conditional on an iterate-level positivity condition that the algorithm does not enforce and the experiments do not verify. This is particularly acute in the active-rate regime, where binding rate constraints push solutions toward the boundary of the probability simplex; the paper's own numerical section compares rate-utility curves but never reports the minimum probability entry, so it cannot establish that Assumption 2 holds. A secondary gap is the asserted reduction from (P1) to the Lagrangian (P2) in Section III (Remark 6), which is not proven; even if the convergence analysis is correct, the connection to the original rate-constrained problem remains heuristic. That gap reinforces, rather than replaces, the Assumption 2 concern: both need to be resolved before the paper can claim a provably convergent solver for the active-rate perfect-privacy IB problem. Because the issues are concrete and potentially addressable, the CONDITIONAL verdict remains appropriate.","tokens_in":72,"tokens_out":12380,"duration_ms":185001,"concrete_test":"Reproduce the Section VIII experiment with the reported synthetic distribution and |U| = 2. At every outer iteration, record m_k = min_{u,x} min(p_U^k(u), p_{U|X}^k(u|x)) over the full range of tested tradeoff parameters. If m_k decreases monotonically and falls below the chosen epsilon (or reaches machine zero) before the termination criterion is met, then Assumption 2 is violated by the algorithm's own trajectory. In addition, for the same small-alphabet instance, compute a global optimum of (P1) for a grid of R in (0, R*) using exhaustive discretization or branch-and-bound; if any optimal P_{U|X} has a zero entry, then no sequence converging to that optimum can satisfy Assumption 2, so Theorems 1–3 do not cover the active-rate solution set.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Every convergence result in Sections V–VI (Lemmas 1–6, Theorems 1–3, Corollary 1) is stated under Assumption 2, which requires a fixed epsilon > 0 with p_U^k(u) >= epsilon and p_{U|X}^k(u|x) >= epsilon for every iterate and every u,x. This is not a regularity condition on the problem data: it is a condition on the trajectory generated by Algorithm 1. Algorithm 1 contains no projection, barrier, or restart that keeps iterates away from the boundary of the probability simplex, and Section VIII reports no monitoring of min_{u,x} min(p_U^k(u), p_{U|X}^k(u|x)). If an iterate reaches the boundary, the restricted-weak-convexity estimate for H0 from [20, Lemma 3] is no longer available: the Hessian of the concave term beta H(U;Y) contains entries of order -1/q_{u|y}, which become unbounded as conditional probabilities approach zero. Consequently the matrices E_z and M_z in Proposition 1 and Lemma 1 cannot be formed with finite constants, and the sufficient-descent argument stops. In the active-rate regime 0 < R < R* (Section III), the rate constraint is binding, so the optimal mechanism is naturally expected to lie at the boundary of the mechanism polytope; the paper gives no argument that Assumption 2 holds there. The theorems therefore describe paths that never touch the boundary, not the solver's behavior in the regime the paper claims to solve.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the information bottleneck problem with a perfect-privacy constraint I(S;U)=0 and a representation-rate constraint I(X;U)≤R, focusing on the active-rate regime 0<R<R*. It reformulates the rate-constrained problem into a Lagrangian form (P2) with tradeoff parameter β, then into a linearly constrained composite problem (P4), and proposes a proximal perturbed ADMM algorithm (Algorithm 1). Under Assumptions 1–2 and a set of parameter conditions (6), the authors prove sufficient descent of a Lyapunov function, boundedness of the iterates, vanishing successive differences, and that every accumulation point is an ε-KKT point of (P4) with ε=(τ/ρ)limsup‖λ^k‖ (Theorem 1). Using the Kurdyka–Łojasiewicz property of the Lyapunov function, they establish whole-sequence convergence with rates depending on the KŁ exponent (Theorems 2–3, Corollary 1), and extend the analysis to inexact block updates (Proposition 3). Numerical experiments on a synthetic distribution compare the resulting rate–utility curves with those of conventional IB algorithms.","tokens_in":29393,"tokens_out":6239,"duration_ms":60077,"significance":"If the central claim is taken as stated, the paper would provide the first provably convergent ADMM-type solver for the rate-constrained perfect-privacy information bottleneck in the active-rate regime. The optimization machinery is largely self-contained: the perturbed dual update, the construction of a Lyapunov function adapted to the probability-simplex constraints, the use of the Kurdyka–Łojasiewicz framework, and the o-minimal definability proof for the entropy terms are technically substantial and appear internally consistent for the Lagrangian problem (P4). The extension to inexact block updates is a practical and welcome feature. However, the paper's claimed contribution to the rate-constrained problem (P1) is not supported by the analysis: the bridge from (P1) to (P2) is asserted rather than proved, and the central convergence theorems are conditional on an unenforced trajectory assumption that may fail exactly in the active-rate regime. The value of the paper therefore depends on whether these gaps can be closed or the claims appropriately narrowed.","major_comments":[{"comment":"The central claim of the paper concerns the rate-constrained perfect-privacy problem (P1), but the algorithm and all convergence theorems are for the Lagrangian form (P2) and its equivalent (P4). The statement in Remark 6 that “the rate constraint can be represented through an appropriate Lagrange multiplier β” is asserted without proof. No argument is given that for every R in the active-rate regime 0<R<R* there exists a β such that a solution of (P2) is feasible and optimal for (P1), nor is the mapping between R and β established. In particular, the claim that “0<R<R* corresponds to the nontrivial parameter range 0<β<β*” and the subsequent restriction to “1<β<β*” are not derived. Because the rate constraint I(X;U)≤R never appears in the algorithmic formulation, Theorems 1–3 and Corollary 1 only characterize stationary points of (P4), not solutions of the rate-constrained problem that the abstract and introduction promise. The authors should either prove the equivalence (or a valid relaxation) or explicitly reframe the contribution as a solver for the Lagrangian (P2).","section":"Section III, Remark 6 and (P2)"},{"comment":"Assumption 2 is a condition on the trajectory generated by Algorithm 1, not on the problem data or the optimal set. It requires a fixed ε>0 such that p_U^k(u)≥ε and p_{U|X}^k(u|x)≥ε for every iterate and every u,x. Algorithm 1 contains no projection, barrier, or restart mechanism that enforces this condition, and Section VIII reports no monitoring of min_{u,x} min(p_U^k(u), p_{U|X}^k(u|x)). The restricted weak convexity of H_0 from [20, Lemma 3] and the strong convexity of F_0 are used throughout the descent analysis; as the proof of Proposition 1 shows, the curvature terms involve entries of order -1/q_{u|y}, which become unbounded as conditional probabilities approach zero. Consequently, the matrices E_z and M_z in Lemma 1 cannot be formed with finite constants, and the sufficient descent estimate and all subsequent convergence results cease to apply. This is not a harmless regularity condition: in the active-rate regime the rate constraint is binding, and the paper gives no argument that optimal mechanisms or generated iterates remain in the interior of the probability simplex. The theorems therefore describe paths that never reach the boundary, not the behavior of the solver in the regime the paper claims to solve. The authors should enforce the condition algorithmically and prove invariance, or verify it in the numerical experiments and explicitly state the limitation of the convergence guarantee.","section":"Section V, Assumption 2"},{"comment":"The numerical section states that “the RCPP curve is generated by solving the proposed problem under different representation-rate constraints,” but Algorithm 1 solves (P2) with a fixed β and contains no rate constraint. Varying β and plotting the achieved (I(X;U), I(U;Y)) points produces a tradeoff curve only if the Lagrangian equivalence of Remark 6 is valid; otherwise the points are simply solutions of (P2) at different β values. The claim that each point represents the utility achieved for a different rate limit R is therefore not justified by the experiments, and the same issue affects the comparison with the baseline IB curves and the statement that the RCPP solution approaches the perfect-privacy utility as R increases. If the equivalence is not proved, the experimental section should be described as demonstrating the behavior of the Lagrangian solver, not of the rate-constrained problem.","section":"Section VIII, Fig. 1 and surrounding text"}],"minor_comments":[{"comment":"The text first states that the active-rate regime 0<R<R* corresponds to 0<β<β*, then immediately restricts the subsequent analysis to “1<β<β*”. The lower bound changes from 0 to 1 without explanation; the role of the interval (0,1] should be clarified.","section":"Section III, after Eq. (1)"},{"comment":"The Require line of Algorithm 1 asks for parameters ρ,τ,γ,Q “satisfying (6)”, but condition (6) is stated in Lemma 1 using auxiliary constants d and η_1 that are not defined or listed at that point. Please clarify that d and η_1 are analysis-only constants whose existence is required, not algorithm parameters.","section":"Algorithm 1 and Lemma 1"},{"comment":"The displayed definition of ̅C in Lemma 6 is typeset ambiguously as ̅C:=C1C2 3 C2 2; from the proof in Appendix H it should be C1 C3^2 / C2^2. The notation should be corrected for readability.","section":"Section VI, Lemma 6"},{"comment":"The definability proof invokes Wilkie's theorem and [35], which is appropriate, but the main text never introduces the structure R_exp before Appendix M. A one-sentence definition or reference in Section II would help the reader.","section":"Appendix M"}],"recommendation":"major_revision","confidential_remarks":"The paper's technical core for the Lagrangian problem (P4) appears sound and is likely publishable after revision. The blocking issue is that the advertised contribution—a solver for the rate-constrained problem (P1)—is not established: the (P1)-to-(P2) reduction is asserted, and Assumption 2 is not enforced or verified. If the authors can prove or carefully reframe the Lagrangian equivalence, and either enforce Assumption 2 or clearly delimit the scope of the convergence theorem, the paper could be accepted. Otherwise the present claims overstate what is proved."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real contribution to a narrow problem, and the proof effort is honest, but the headline claim is over-broad. The convergence guarantee is for the Lagrangian (P2), not for the stated rate-constrained problem (P1), and the bridge between them is a one-sentence Remark 6. On top of that, every theorem in Sections V and VI sits on Assumption 2, uniform positivity of all iterates, which the algorithm neither enforces nor checks. In the active-rate regime, where the optimum sits on the boundary of the mechanism polytope, that assumption can fail exactly where the paper claims to operate.\n\nWhat is genuinely new: the formulation itself, exact I(S;U)=0 with a rate constraint in finite alphabet, is absent from the cited literature. The algorithm is tailored, not blindly imported. The Lyapunov analysis is detailed, the Kurdyka-Lojasiewicz rates are derived rather than assumed, and the o-minimal definability proof is a real plus. The abstract does say \"under suitable regularity conditions,\" so the authors are not hiding the caveat. I do not see circularity or target-dependent fitting; the convergence proof is a self-contained derivation against external benchmarks.\n\nWhere it is soft, in proportion: the P1-to-P2 reduction is asserted, not proven. In the IB literature the Lagrangian equivalence is nontrivial, and since the paper claims to solve the rate-constrained problem, this gap matters. The epsilon-KKT residue is tau/rho times the limsup of the dual norm, which is never quantified; the algorithm can stop at a point with nonzero feasibility residual. Assumption 2 is load-bearing: the restricted weak convexity of H0 from [20, Lemma 3] requires lower bounds on probabilities, and the Hessian of beta H(U;Y) has entries of order -1/q_{u|y}, which blow up as any conditional probability approaches zero. No projection, barrier, or restart keeps iterates away from the boundary, and the experiments do not monitor the margin. Finally, the numerical section is a proof of concept, not a validation: no code, no hyperparameters, no baseline that enforces the same constraints, and privacy leakage is reported as machine precision without a threshold analysis.\n\nWho gets value from this paper: people working on perfect-privacy IB, on nonconvex ADMM with probability-simplex constraints, and on K-L-based convergence analysis. It deserves a serious referee; the analysis is worth engaging with and the gaps are addressable. I would not cite it as a solver for (P1) until the Lagrangian bridge is justified and Assumption 2 is either relaxed, enforced, or empirically verified. Recommended path: conditional acceptance with a heavy revision request, not desk rejection.","headline":"A serious proof of a narrower-than-claimed result: convergence of a perturbed ADMM for the Lagrangian relaxation of perfect-privacy IB, conditional on an unverified uniform-positivity assumption.","tokens_in":29979,"tokens_out":2603,"would_cite":false,"duration_ms":27319,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","94A17","90C30"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proposes a proximal perturbed ADMM for the finite-alphabet information bottleneck with an active rate constraint and a perfect privacy constraint, and proves that the whole iterate sequence converges to approximate KKT points…","keywords":["information bottleneck","perfect privacy","privacy-utility tradeoff","ADMM","nonconvex optimization","Kurdyka-Lojasiewicz property","convergence rate","active-rate regime"],"falsifier":"Take a joint distribution for which the optimal perfect-private mechanism lies on the boundary of the probability simplex, run Algorithm 1 from several initializations, and record min_{u,x}{p_U^k(u), p_{U|X}^k(u|x)}; if this minimum crosses any fixed epsilon>0 before the residual ||Ax^k−Bz^k|| reaches the desired tolerance, then Assumption 2 is violated at exactly the operating points the convergence guarantee is meant to cover.","tokens_in":28853,"feed_emoji":"🔒","tokens_out":7376,"duration_ms":68332,"temperature":0.7,"pith_summary":"The paper tackles the information bottleneck with a rate constraint and a perfect privacy constraint: build a representation U that keeps information about a useful variable Y, spends at most R bits of I(X;U), and is statistically independent of a sensitive variable S. It argues that in the active-rate regime this problem cannot be reduced to existing linear programming or leakage-penalty methods, so it reformulates it as a two-block linearly constrained composite program and proposes a proximal perturbed ADMM. Under a uniform-positivity assumption on the iterates and a parameter condition, the paper proves that the generated sequence is bounded, its successive differences vanish, and every accumulation point satisfies an epsilon-KKT condition. It further proves whole-sequence convergence with rates depending on the Kurdyka–Łojasiewicz exponent, and extends the guarantee to inexact block updates. If correct, this supplies the first convergence-guaranteed numerical solver for the rate-constrained perfect-privacy information bottleneck in the active-rate regime.","feed_headline":"Perfect-privacy bottleneck gets a convergent ADMM solver","feed_subtitle":"The algorithm enforces zero leakage and a rate budget, and its proof yields convergence rates from the Kurdyka-Lojasiewicz exponent.","key_machinery":"The load-bearing object is the perturbed augmented Lagrangian L_{ρ,τ}(x,z,λ)=F_0(x)+F_1(x)+H_0(z)+H_1(z)+⟨(1−τ)λ,Ax−Bz⟩+(ρ/2)||Ax−Bz||^2 with the multiplier update $λ^{{k+1}}$=(1−τ)λ^k+ρ($Ax^{{k+1}}$−$Bz^{{k+1}}$). Because the constraint matrices are rank deficient and the probability constraints introduce nonsmooth indicators, the standard ADMM descent argument fails; instead the paper constructs a Lyapunov function P($w^{{k+1}}$) that adds scaled memory terms d||$z^{{k+1}}$−z^k||_{D_z}^2 + d(1−τ)/(2ρ)||$λ^{{k+1}}$−λ^k||^2 to the shifted augmented Lagrangian. The perturbation τ makes the dual increase controllable, the Lyapunov correction absorbs history-dependent terms, and the Kurdyka–Łojasiewicz property of P, established by definability in R_exp, converts the descent and subgradient estimates into finite length and explicit convergence rates.","core_discovery":"The paper establishes that the rate-constrained perfect-privacy information bottleneck can be written as min F(x)+H(z) subject to Ax−Bz=0, where x encodes the marginal distribution of the representation, z encodes the release mechanism, and the linear constraint enforces both marginal consistency and perfect privacy. It then defines a proximal perturbed ADMM whose block updates keep the probability constraints inside the subproblems and whose dual update is $λ^{{k+1}}$=(1−τ)λ^k+ρ($Ax^{{k+1}}$−$Bz^{{k+1}}$). Under Assumptions 1–2 and the parameter condition (6), the Lyapunov function decreases sufficiently, the dual sequence is bounded, successive differences vanish, and every accumulation point is an epsilon-KKT point with epsilon=(τ/ρ) limsup ||λ^k||. Using the Kurdyka–Łojasiewicz property of the Lyapunov function, the paper proves finite-length and whole-sequence convergence, with finite termination when the KŁ exponent is zero, linear convergence when it is in (0,1/2], and sublinear convergence when it is in (1/2,1). The inexact variant shows that square-summable subproblem residuals preserve these conclusions.","pith_inferences":["Beyond the paper's claims, the uniform-positivity assumption could be turned into an algorithmic feature by projecting iterates onto a probability simplex with a small floor, which would let the convergence guarantees extend to boundary solutions the unmodified algorithm cannot certify.","The perturbed-dual Lyapunov construction appears portable to other finite-alphabet information-theoretic optimizations with rank-deficient linear constraints, such as zero-leakage variants of the privacy funnel.","The residual bound epsilon=(τ/ρ)limsup||λ^k|| suggests a practical hyperparameter tradeoff that the paper does not explore numerically: shrinking τ or enlarging ρ should shrink the limiting feasibility gap, but condition (6) couples these parameters in a way that could be mapped empirically.","The numerical results use one synthetic distribution; a stress test on distributions whose optimal perfect-private mechanism sits on the boundary of the simplex would separate the solver's practical behavior from the coverage of Assumption 2."],"forward_implications":["In the active-rate regime, a user can compute a representation that is independent of the sensitive variable up to numerical precision while respecting an explicit rate budget, instead of tuning an unknown privacy penalty.","The whole sequence converges under the KŁ property, not just a subsequence, so the final iterate carries a certified approximate-stationarity guarantee.","Inexact subproblem solutions with square-summable residuals preserve convergence, permitting inner projected-gradient iterations in practice.","The asymptotic feasibility gap is controlled by τ/ρ times the asymptotic dual norm, so the parameter choices in condition (6) trade off the final epsilon against the convergence behavior.","The convergence rates split into finite termination, linear, and sublinear regimes depending on the KŁ exponent, giving a concrete prediction of the algorithm's tail behavior."],"supporting_citations":[{"why":"Defines the original information bottleneck objective and rate-relevance tradeoff that the rate-constrained perfect-privacy problem extends.","marker":"[1]"},{"why":"Characterizes perfect privacy and the nontriviality condition used in Definition 9 of the paper.","marker":"[9]"},{"why":"Supplies the rate-constrained perfect-privacy formulation for the inactive-rate case and the synthetic distribution used in the numerical experiments.","marker":"[11]"},{"why":"Provides the strongly convex-weakly convex decomposition of the IB entropy objective and the ADMM treatment that the proposed method builds on.","marker":"[19]"},{"why":"Supplies the restricted weak convexity notion used for H_0 and the Markovian information-theoretic ADMM/DRS framework.","marker":"[20]"},{"why":"Provides the perturbed proximal ADMM principle for nonconvex nonsmooth optimization that the dual-update perturbation is specialized from.","marker":"[25]"},{"why":"Gives the KŁ descent framework used to derive the finite-length property and whole-sequence convergence rates.","marker":"[27]"},{"why":"Establishes that definable functions satisfy the Kurdyka–Łojasiewicz property, which is used to prove that the Lyapunov function is KŁ.","marker":"[33]"}],"fun_headline_variants":["Convergent ADMM for perfect-privacy bottleneck","Zero-leakage bottleneck: ADMM convergence guaranteed","Privacy-preserving IB: ADMM with proven convergence rates","Perfect privacy bottleneck: global convergence via ADMM","Rate-constrained privacy: convergent ADMM from KL analysis"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof requires a fixed positive lower bound on every probability entry p_U^k(u) and p_{U|X}^k(u|x) of every iterate, and the algorithm neither enforces nor verifies this bound.","fun_headline_variants_meta":{"raw":{"variants":["Convergent ADMM for perfect-privacy bottleneck","Zero-leakage bottleneck: ADMM convergence guaranteed","Privacy-preserving IB: ADMM with proven convergence rates","Perfect privacy bottleneck: global convergence via ADMM","Rate-constrained privacy: convergent ADMM from KL analysis"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000421,"raw_usage":{"total_tokens":2145,"prompt_tokens":908,"completion_tokens":1237,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":524,"completion_tokens_details":{"reasoning_tokens":1160}},"tokens_in":524,"tokens_out":1237,"duration_ms":10930,"temperature":1.0,"reasoning_tokens":1160,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:16:32.913099+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a joint distribution for which the optimal perfect-private mechanism lies on the boundary of the probability simplex, run Algorithm 1 from several initializations, and record min_{u,x}{p_U^k(u), p_{U|X}^k(u|x)}; if this minimum crosses any fixed epsilon>0 before the residual ||Ax^k−Bz^k|| reaches the desired tolerance, then Assumption 2 is violated at exactly the operating points the convergence guarantee is meant to cover.","supporting_citations":[{"cited_title":"On perfect privacy,","cited_arxiv_id":null,"evidence_quote":"Characterizes perfect privacy and the nontriviality condition used in Definition 9 of the paper."},{"cited_title":"Optimal privacy-utility trade-off under a rate constraint,","cited_arxiv_id":null,"evidence_quote":"Supplies the rate-constrained perfect-privacy formulation for the inactive-rate case and the synthetic distribution used in the numerical experiments."},{"cited_title":"A provably convergent information bottleneck solution via admm,","cited_arxiv_id":null,"evidence_quote":"Provides the strongly convex-weakly convex decomposition of the IB entropy objective and the ADMM treatment that the proposed method builds on."},{"cited_title":"A linearly convergent douglas-rachford splitting solver for markovian information-theoretic optimization problems,","cited_arxiv_id":null,"evidence_quote":"Supplies the restricted weak convexity notion used for H_0 and the Markovian information-theoretic ADMM/DRS framework."},{"cited_title":"Perturbed proximal gradient admm for nonconvex composite optimization,","cited_arxiv_id":null,"evidence_quote":"Provides the perturbed proximal ADMM principle for nonconvex nonsmooth optimization that the dual-update perturbation is specialized from."}],"review_version":1}