Social aspects · privacy

We study differentially private approximation algorithms for positive linear programs (LPs with nonnegative coefficients and variables), focusing on the fundamental families of packing, covering, and mixed packing-covering formulations. We focus on the high-sensitivity, constraint-private regime of Hsu-Roth-Roughgarden-Ullman (ICALP 2014), where neighboring instances may differ by an arbitrary single constraint, so one cannot hope to approximately satisfy every constraint under privacy. We give private solvers that return approximate solutions while violating only a controlled number of constraints. Our algorithms improve the prior instance-dependent guarantees, and also yield new data-independent bounds that depend only on the dimension. Our techniques involve a dense multiplicative weights update method developed from a regularized dual viewpoint, which we analyze in a way that exploits structure specific to positive LPs.

Machine unlearning aims to eliminate the influence of specific data from trained models to safeguard privacy. However, this presents a significant challenge in the context of continual learning (CL), where models update sequentially on dynamic datasets. A major limitation is that current certified unlearning algorithms fail to account for the complex, cumulative model evolution inherent to CL framework. In this work, we establish the first theoretical foundation bridging CL and machine unlearning. We formulate the CL's unlearning objective as the minimization of post-unlearning excess risk, which decomposes into CL excess risk and unlearning loss, characterizing the fundamental trade-off between preserving historical knowledge and targeted forgetting. Under mild assumptions, we first establish an upper bound for the CL excess risk in non-convex models. We then adapt two certified unlearning approaches, gradient-based and Hessian-based, to the CL framework. Our analysis reveals that while the gradient-based approach is less effective than the Hessian-based method in minimizing unlearning loss, it offers the distinct advantage of nearly zero storage overhead for enabling unlearning. This insight motivates a hybrid strategy that reduces storage costs while maintaining post-unlearning performance. Experimental results further validate our theoretical findings.

Federated Learning (FL) faces significant challenges due to domain heterogeneity, where data from different clients exhibit substantial statistical shifts that hinder the generalization of the global model. Although existing methods attempt to mitigate this by exchanging class prototypes, they fall short by representing an entire class's complex distribution with a single point. This oversimplification disregards the rich structural information within the data, especially across diverse domains. To address this limitation, we propose a paradigm shift from point-based representation to structure-based knowledge transfer. We introduce Federated Manifold Learning (FML), a novel framework that leverages perceptual manifolds—the intrinsic geometric structures of classes in the feature space—as rich knowledge carriers. In FML, clients transmit compressed manifolds, which are adaptively fused on the server using an attention-based Manifold Mutual Learning (MML) mechanism. This process enables domain-specific structures to learn from each other, creating a unified yet flexible global convergence target. Manifold-guided local training, enforced by a manifold approximation loss and a separation loss, further aligns local models with this global structure. Extensive experiments on the Digits and Office31 benchmarks demonstrate that FML substantially outperforms state-of-the-art methods, achieving accuracy improvements of up to 6.47%.

Retrieval-Augmented Generation (RAG) systems are increasingly deployed to provide query-based access to large knowledge bases, thereby introducing concrete privacy risks whereby the underlying corpus may be partially or fully extracted through the deployed service. Existing extraction attacks typically rely on locally driven search strategies, in which newly extracted content is inferred or expanded based on previously recovered fragments. However, real-world knowledge bases are often multi-source and heterogeneous, with pronounced semantic discontinuities across domains. Such gaps can trap extraction methods that rely on local semantic continuity in local optima, severely limiting large-scale corpus reconstruction. In this paper, we introduce an extraction framework (GeoEx) designed to navigate and reconstruct heterogeneous RAG knowledge bases without any prior knowledge. The framework plans extraction directly in the embedding space of a proxy retrieval model to improve global coverage, and employs an embedding inversion module to convert latent vectors into executable queries. We further propose a composite geometric strategy that combines orthogonal query synthesis for cross-domain exploration with local embedding perturbations for dense extraction within discovered clusters. Experiments on mixed corpora spanning eight diverse domains and multiple retrievers and LLMs show that GeoEx significantly outperforms baselines in both extraction coverage and query efficiency.

Large language models can memorize information that must be removed—ranging from copyright-sensitive content (e.g., book chapters) to personally identifiable information (e.g., income)—to ensure responsible and compliant behavior. Unlearning has emerged as an efficient alternative to full retraining, aiming to remove specific knowledge. However, users may still expect model to leverage the removed information when it is re-introduced in the prompt. Existing evaluations of unlearning methods focus on (1) the extent of forgetting of the target knowledge (forget set) and (2) performance preservation on the retain set (i.e., utility), but overlook this critical usability dimension. Through a systematic evaluation of six state-of-the-art unlearning methods, we show that they consistently degrade such contextual utility—the model's ability to use forgotten knowledge when it is provided in context. To address this, we augment unlearning objectives with a plug-in term that explicitly preserves contextual utility. Extensive experiments demonstrate that our approach restores contextual utility to near original levels while still maintaining effective forgetting and retain-set utility.

Graph Federated Learning (GFL) enables distributed graph representation learning while preserving graph data privacy. However, it suffers from heterogeneity in node features and graph structures across clients. To address this challenge, we propose a novel graph Federated learning method via Semantic and Structural Alignment (FedSSA). For node feature heterogeneity, FedSSA infers class-wise node distributions through a variational model, clusters clients according to the inferred distributions, and aligns local distributions with cluster-level representatives. For structural heterogeneity, FedSSA employs spectral Graph Neural Networks (GNNs) and introduces a spectral energy measure to characterize graph topology, enabling structural alignment between local and cluster-level spectral GNNs. Experiments on eleven homophilic and heterophilic graph datasets under non-overlapping and overlapping partitioning settings demonstrate that FedSSA consistently outperforms eleven state-of-the-art methods. Our code is available at https://github.com/blgpb/FedSSA.

Generating high-quality synthetic text under differential privacy (DP) is critical for training and evaluating language models without compromising user privacy. Prior work on synthesizing DP *datasets* often fail to preserve key statistical attributes, suffer utility loss from the noise required by DP, and lack fine-grained control over generation. To address these challenges, we make two contributions. First, we introduce a hierarchical framework that decomposes DP synthetic text generation into two subtasks: *feature learning* and *conditional text generation*. This design explicitly incorporates learned features into the generation process and simplifies the end-to-end synthesis task. Through systematic ablations, we identify the most effective configuration: a rich tabular schema as feature, a DP tabular synthesizer, and a DP fine-tuned conditional generator, which we term ACTG (**A**ttribute-**C**onditioned **T**ext **G**eneration). Second, we propose Anchored RL (ARL), a post-training method that improves the instruction-following ability of ACTG for conditional generation. ARL combines RL to boost control with an SFT anchor on best-of-$N$ data to prevent reward hacking. Together, these components form our end-to-end algorithm **ACTG-ARL**, which advances both the quality of DP synthetic text (+20% MAUVE over prior work) and the control of the conditional generator under strong privacy guarantees. Our code is at https://github.com/actg-arl/ACTG-ARL.

We prove the conjecture stated in Appendix F.3 of Zhu et al.: among all conversion rules that map a Rényi Differential Privacy (RDP) profile $\tau \mapsto \rho(\tau)$ to a valid hypothesis-testing trade-off $f$ (or equivalently, an $(\varepsilon,\delta)$-Differential Privacy curve), the rule based on the intersection of single-order RDP privacy regions is optimal. This optimality holds simultaneously for all valid RDP profiles and for all Type I error levels $\alpha$. Concretely, we show that in the space of trade-off functions, the tightest possible bound is $f_{\rho(\cdot)}(\alpha) = \sup_{\tau \geq 0.5} f_{\tau,\rho(\tau)}(\alpha)$: the pointwise maximum of the single-order bounds for each RDP privacy region. Our proof unifies and sharpens the insights of Balle et al., Asoodeh et al., and Zhu et al.. Our analysis relies on a precise geometric characterization of the RDP privacy region, leveraging its convexity and the fact that its boundary is determined exclusively by Bernoulli mechanisms. Our results establish that the "intersection-of-RDP-privacy-regions" rule is not only valid, but optimal: no other black-box conversion can uniformly dominate it in the Blackwell sense, marking the fundamental limit of what can be inferred about a mechanism's privacy solely from its RDP guarantees.

In this paper, we reveal a significant shortcoming in class unlearning evaluations: overlooking the underlying class geometry can cause information leakage about the forgotten class. We further propose a simple unlearning strategy to mitigate this issue. We introduce Class Membership Inference Attack (CMIA) that uses the probabilities the model assigns to neighboring classes to detect unlearned samples. We find that existing unlearning methods are vulnerable to CMIA across multiple datasets. We then propose a new fine-tuning objective that mitigates this privacy leakage by approximating, for forget-class inputs, the distribution over the remaining classes that a retrained-from-scratch model would produce. To construct this approximation, we estimate inter-class similarity and tilt the target model’s distribution accordingly. The resulting Tilted REWeighting (TREW) distribution serves as the desired distribution during fine-tuning. We also show that across multiple benchmarks, TREW matches or surpasses existing unlearning methods on prior unlearning metrics. More specifically, on CIFAR-10, it reduces the gap with retrained models by $19\%$ and $46\%$ for U-LiRA and CMIA scores, accordingly, compared to the SOTA method for each category.

We study ridge regression and ridge-regularized empirical risk minimization (ERM) under $(\varepsilon,\delta)$-differential privacy via output perturbation. In classical private ERM, the ridge parameter simultaneously controls statistical regularization and the estimator’s global sensitivity. Larger regularization reduces the DP noise scale but increases bias. So choosing the tuning parameter becomes a privacy--accuracy bottleneck. We propose a framework that makes these two roles explicit by decoupling regularization into (i) a statistical penalty $\alpha$, defining the target ridge/ERM solution, and (ii) a privacy-stabilization parameter $c$, used only to enforce a curvature floor and hence a tight sensitivity bound. We apply this framework to ridge regression, where $c$ is used to boost the minimum eigenvalue of the empirical Gram matrix. We derive an explicit bias--variance--DP-variance risk decomposition and characterize optimal $(\alpha,c)$ in several regimes, yielding sharp tuning guidance and improved accuracy relative to single-parameter regularization. Finally, we extend the same decoupling principle to general ridge-regularized ERM. We support the theory with simulations.

Modern database workloads are highly predictable: query streams are dominated by recurring jobs and templates, even when their arrival order is not known in advance. This motivates a learning-augmented view of online differentially private (DP) analytics: can algorithms utilize predictions about *which* queries will occur to improve utility under a single global privacy budget, while remaining robust when predictions are wrong? We study online DP query answering, where a curator must answer a stream $Q$ of $S$ linear queries arriving in uniformly random order under privacy budget $(\epsilon,\delta)$. We present *LAPRAS*, which assumes access to an oracle that outputs a prediction set of queries likely to appear in the stream and uses it to guide privacy spending. LAPRAS answers predicted queries using the offline-optimal Matrix Mechanism and answers the remaining queries online from a residual budget. To pace spending across an unknown number of unpredicted queries, we introduce *Smooth Allocation*, which forms an unbiased stopping-time estimate $\widehat{B}$ from the first $T=\Theta(\log^2 S)$ unpredicted queries and continuously recalibrates per-query expenditure. Empirically, over two real datasets, we validate the intended consistency--robustness trade-off: LAPRAS achieves near-offline utility under high overlap and degrades gracefully to baseline-level performance when overlap is low.

We provide the first study of the problem of finding differentially private (DP) second-order stationary points (SOSP) in stochastic (non-convex) minimax optimization. Existing literature either focuses only on first-order stationary points for minimax problems or on SOSP for classical stochastic minimization problems. This work provides, for the first time, a unified and detailed treatment of both empirical and population risks. Specifically, we propose a purely first-order method that combines a nested gradient descent--ascent scheme with SPIDER-style variance reduction and Gaussian perturbations to ensure privacy. A key technical device is a block-wise ($q$-period) analysis that controls the accumulation of stochastic variance and privacy noise without summing over the full iteration horizon, yielding a unified treatment of both empirical-risk and population formulations. Under standard smoothness, Hessian-Lipschitzness, and strong concavity assumptions, we establish high-probability guarantees for reaching an $(\alpha,\sqrt{\rho_\Phi \alpha})$-approximate second-order stationary point with $\alpha = \mathcal{O}( (\frac{\sqrt{d}}{n\varepsilon})^{2/3})$ for empirical risk objectives and $\mathcal{O}(\frac{1}{n^{1/3}} + (\frac{\sqrt{d}}{n\varepsilon})^{1/2})$ for population objectives, matching the best known rates for private first-order stationarity.

Machine unlearning seeks to remove the influence of specified data from a trained model. While the unlearning accuracy provides a widely used metric for assessing unlearning performance, it falls short in assessing the reliability of forgetting. In this paper, we find that the forgetting data points misclassified by unlearning accuracy still have their ground truth labels included in the conformal prediction set from the uncertainty quantification perspective, leading to a phenomenon we term fake forgetting. To address this issue, we propose a novel metric CR, inspired by conformal prediction, that offers a more reliable assessment of forgetting quality. Building on these insights, we further propose an unlearning framework CPU that incorporates conformal prediction into the Carlini & Wagner adversarial attack loss, enabling the ground truth label to be effectively removed from the conformal prediction set. Through extensive experiments on image classification tasks, we demonstrate both the effectiveness of our proposed metric and the superior forgetting quality achieved by our framework. Code is available at https://github.com/TIML-Group/Conformal-Prediction-Unlearning.

Large language models (LLMs) are pretrained on corpora containing trillions of tokens and, therefore, inevitably memorize sensitive information. Locate-then-edit methods, as a mainstream paradigm of model editing, offer a promising solution by modifying model parameters without retraining. However, in this work, we reveal a critical vulnerability of this paradigm: the parameter updates inadvertently serve as a side channel, enabling attackers to recover the edited data. We propose a two-stage reverse-engineering attack named KSTER (KeySpaceReconsTruction-then-EntropyReduction) that leverages the low-rank structure of these updates. First, we theoretically show that the row space of the update matrix encodes a "fingerprint" of the edited subjects, enabling accurate subject recovery via spectral analysis. Second, we introduce an entropy-based prompt recovery attack that reconstructs the semantic context of the edit. Extensive experiments on multiple LLMs demonstrate that our attacks can recover edited data with high success rates. Furthermore, we propose subspace camouflage, a defense strategy that obfuscates the update fingerprint with semantic decoys. This approach effectively mitigates reconstruction risks without compromising editing utility. Our code is available at https://github.com/reanatom/EditingAttack.

Modern LLM-powered autonomous agents increasingly rely on rich user interface (UI) state observations to achieve reliable action grounding in complex digital environments. However, many deployments transmit the full UI state to remote inference servers even when most elements are irrelevant to the current task, which can leak sensitive but unnecessary context such as authentication codes, private notifications, and background application states. We propose MINIM, a trusted local broker that performs privacy-aware minimization on the client side before any observation leaves the device. Grounded in Contextual Integrity (CI), MINIM learns a dual-score representation for each UI element by predicting an inherent sensitivity score ($s$) and a task-conditioned necessity score ($n$). These scores drive a ternary disclosure policy that keeps essential elements, abstracts sensitive attributes when needed, and removes task-irrelevant content. We optimize a CI-aware objective that penalizes necessity errors more strongly on high-risk content, enabling aggressive pruning while preserving task-critical information. Experiments on real-world UI observations derived from WebArena show that MINIM substantially reduces task-irrelevant sensitive leakage while preserving task-critical semantic context and the interactive affordances required for reliable agent actions.

In this paper, we study the private and robust alignment of language models from a theoretical perspective by establishing upper bounds on the suboptimality gap in both offline and online settings. We consider preference labels subject to privacy constraints and/or adversarial corruption, and analyze two distinct interplays between them: privacy-first and corruption-first. For the privacy-only setting, we show that log loss with an MLE-style algorithm achieves near-optimal rates, in contrast to conventional wisdom. For the joint privacy-and-corruption setting, we first demonstrate that existing offline algorithms in fact provide stronger guarantees---simultaneously in terms of corruption level and privacy parameters---than previously known, which further yields improved bounds in the corruption-only regime. In addition, we also present the first set of results for private and robust online alignment. Our results are enabled by new uniform convergence guarantees for log loss and square loss under privacy and corruption, which we believe have broad applicability across learning theory and statistics.

Federated learning (FL) faces significant challenges from modality heterogeneity, which motivates multimodal federated learning (MFL) to leverage complementary modalities across decentralized clients for improved performance. However, modality imbalance introduces a new attack surface, making MFL more vulnerable to membership inference attacks (MIAs), an issue that remains largely unexplored. In this work, we present the first systematic study of MIAs against MFL and propose a modality-aware attack framework. We show that multimodal models are inherently more susceptible to MIAs due to heterogeneous modality contributions, and existing attacks are suboptimal as they treat multimodal parameters as a whole. By performing MIAs on individual modalities, we find that (i) attacking the dominant modality achieves comparable accuracy with lower overhead, and (ii) different modalities expose distinct membership patterns. To identify members with different patterns, we propose a modality-aware framework that exploits cross-modal performance gaps to adaptively select attack modalities and calibrate inference results. Experiments on three datasets show our approach outperforms baselines across multiple metrics.

Discrete Diffusion Large Language Models (dLLMs) have recently emerged as a promising non-autoregressive paradigm, offering faster inference while achieving strong performance in code generation and mathematical reasoning tasks. In this work, we show that dLLMs’ decoding mechanism not only improves utility but also enables effective model attribution: by analyzing a response’s decoding trajectory, we can identify its source model and help mitigate risks from model misuse. A key challenge is the diversity of attribution scenarios, ranging from distinguishing different models to identifying different checkpoints or backups of the same model. To ensure broad applicability, we focus on two core questions: what information to extract from the decoding trajectory, and how to use it effectively. We first observe that per-step model confidence is ineffective, as the bidirectional nature of dLLMs causes mutual influence among decoded tokens, leading to highly redundant confidence signals that obscure structural information about decoding order and dependencies. To overcome this, we propose a novel information extraction scheme called the \textit{Directed Decoding Map (DDM)}, which captures structural relationships between decoding steps and reveals model-specific behaviors. Furthermore, to fully leverage the extracted structure, we propose \textit{Gaussian-Trajectory Attribution (GTA)}, which fits a cell-wise Gaussian distribution at each decoding position for each model and uses log-likelihood differences between trajectories as the attribution score. Extensive experiments across diverse models, datasets and different model access assumptions validate the effectiveness of our approach.

Securing Contextual Integrity (CI) is critical for privacy-preserving Large Language Model (LLM) agent execution. However, existing agents struggle to balance the agility of direct generation against the prohibitive latency of CI-constrained thinking. To address this, we propose PrivGate, a framework that selectively invokes explicit reasoning based on internal privacy signals. Our approach is grounded in the discovery of a privacy manifold, where models linearly encode privacy sensitivity within their residual streams, even during non-compliant generation. Leveraging this structure, PrivGate employs Latent Gating, a training-free mechanism that requires no fine-tuning of the base LLM and triggers explicit reasoning only when high latent risk is detected, thereby optimizing the efficiency-privacy trade-off by minimizing unnecessary compute. On the contextual PrivacyLens benchmark, PrivGate maintains consistently high performance in out-of-distribution risk identification, validating the generalizability of the discovered manifold. End-to-end evaluations show that PrivGate achieves a 62.6% average relative reduction in privacy leakage with 15.9% token overhead, offering a practical pathway to reconcile rigorous CI requirements with the performance demands of LLM agents.

Graph Neural Networks (GNNs) are increasingly deployed on sensitive relational data, from social networks to healthcare records. However, their outputs can leak private graph structure, enabling link-stealing attacks that infer whether a connection between two entities existed in the training graph. While prior work demonstrates high average performance for such attacks, privacy is fundamentally a worst-case property, not an average one. The key question is whether an adversary can reliably compromise even a small set of critical links under strict precision constraints. We revisit posterior-only link-stealing attacks in a strict black-box setting and show that they remain effective at extremely low false-positive rates, revealing tail-risk vulnerabilities that current evaluations overlook. We further find that intra-class vulnerabilities are suppressed by geometric bottlenecks that collapse discriminative directions in posterior space. Building on this insight, we propose a geometry-aware reconditioning method that reshapes intra-class distances, substantially improving separability without harming reliability. Across multiple real-world graphs and GNNs, this diagnostic correction achieves up to $2\times$ higher success on intra-class pairs than generic attacks, redefining link-privacy evaluation as a tail-risk problem and revealing that posterior leakage remains substantially under-measured in current GNN deployments.