Author name cluster

Yuhan Liu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

19 papers

2 author rows

AAAI Conference 2026 Conference Paper

Conditional Information Bottleneck for Multimodal Fusion: Overcoming Shortcut Learning in Sarcasm Detection

Yihua Wang
Qi Jia
Cong Xu
Feiyu Chen
Yuhan Liu
Haotian Zhang
Liang Jin
Lu Liu

Multimodal sarcasm detection is a complex task that requires distinguishing subtle complementary signals across modalities while filtering out irrelevant information. Many advanced methods rely on learning shortcuts from datasets rather than extracting intended sarcasm-related features. However, our experiments show that shortcut learning impairs the model's generalization in real-world scenarios. Furthermore, we reveal the weaknesses of current modality fusion strategies for multimodal sarcasm detection through systematic experiments, highlighting the necessity of focusing on effective modality fusion for complex emotion recognition. To address these challenges, we construct MUStARD++R by removing shortcut signals from MUStARD++. Then, a Multimodal Conditional Information Bottleneck (MCIB) model is introduced to enable efficient multimodal fusion for sarcasm detection. Experimental results show that the MCIB achieves the best performance without relying on shortcut learning.

PDF Details DOI

AAMAS Conference 2026 Conference Paper

EmoDebt: Bayesian-Optimized Emotional Intelligence for Strategic Agent-to-Agent Debt Recovery

Yunbo Long
Yuhan Liu
Liming Xu
Alexandra Brintrup

The rise of autonomous LLM agents has enabled strategic agentto-agent interactions, yet a critical vulnerability persists: in highstakes, emotion-sensitive domains like debt collection, LLM agents pre-trained on human dialogue are vulnerable to exploitation by adversarial counterparts who simulate negative emotions to derail negotiations. To fill this gap, we first contribute a novel dataset of simulated debt recovery scenarios and a multi-agent simulation framework. Within this framework, we introduce EmoDebt, an LLM agent architected for robust performance. Its core innovation isaBayesian-optimizedemotionalintelligenceenginethatreframes a model’s ability to express emotion in negotiation as a sequential decision-making problem. Through online learning, this engine continuously tunes EmoDebt’s emotional transition policies, discovering optimal counter-strategies against specific debtor tactics. Extensive experiments on our proposed benchmark demonstrate that EmoDebt achieves significant strategic robustness, substantially outperforming non-adaptive and emotion-agnostic baselines across key performance metrics, including success rate and operational efficiency. By introducing both a critical benchmark and a robustly adaptive agent, this work establishes a new foundation for deploying strategically LLM agents in adversarial debt interactions. The code is available at https: //github. com/Yunbo-max/EmoDebt.

PDF

JBHI Journal 2025 Journal Article

A Knowledge-Guided Multi-modal Neural Network for Breast Cancer Molecular Subtyping

Jinlin Ye
Yuhan Liu
Shangjie Ren
Changjun Wang
Yidong Zhou
Liang Yang
Wei Zhang

Precise determination of HER2 subtype is essential for selecting appropriate targeted therapies in breast cancer. However, current HER2 assessment methods remain dependent on invasive tissue biopsies, which are limited by tumor heterogeneity and sampling bias. To address these challenges, this paper proposes a knowledge-guided multi-modal neural network (KMNet) for non-invasive HER2 subtyping by integrating clinical data and ultrasound images. KMNet introduces a Graph-based Clinical Feature encoder (GCF), which constructs a causal graph among clinical indicators based on medical knowledge and extracts high-order feature relationships via the Graph Convolutional Network (GCN). Meanwhile, the Convolutional Neural Network (CNN) and Vision Transformer (ViT)-based hybrid image encoder (CVUIF) captures both local details (calcifications and blood flow) and global dependencies between intra- and peritumoral regions. In addition, the Reduced Dimensional Fusion (RDF) module integrates key information from clinical graph features, ultrasound image features, and structured clinical data to construct a unified multi-modal representation for downstream HER2 subtyping task. Experiments were conducted on the private datasets (HER2USC) and the public datasets (BCW, BCa and SIIM-ISIC). Experimental results demonstrate that KMNet outperformed other reported state-ofthe- art multi-modal algorithms in HER2 subtyping task, offering strong potential for clinical decision support in breast cancer treatment.

Details DOI

YNICL Journal 2025 Journal Article

Abnormal structural covariance network in major depressive disorder: Evidence from the REST-meta-MDD project

Changmin Chen
Yuhan Liu
Yu Sun
Wenhao Jiang
Yonggui Yuan
Zhao Qing

BACKGROUND: Major depressive disorder (MDD) is a common mental illness associated with brain morphological abnormalities. Although extensive studies have examined gray matter volume (GMV) changes in MDD, inconsistencies persist in reported findings. In the current study, we employed source-based morphometry (SBM) and structural covariance network (SCN) analyses to a large multi-center sample from the REST-meta-MDD database, aiming to characterize robust results of structural abnormalities in MDD. METHODS: We analyzed 798 MDD patients and 974 healthy controls (HCs) from the REST-meta-MDD consortium. Voxel-based morphometry was applied to generate GMV maps. SBM was used to adaptively parcellate brain into different components, and SCN was constructed based on SBM components. Volume scores in each component and SCNs between the components were both compared between MDD and HC groups, as well as between first-episode drug-naive (FEDN) and recurrent MDD subgroups. RESULTS: SBM identified 20 stable components. Three components encompassing the middle temporal gyrus, middle orbitofrontal gyrus and superior frontal gyrus exhibited volumetric differences between the MDD and HC groups. Volume differences were observed in the cingulate cortex and medial frontal gyrus between the FEDN and recurrent groups. SCN analysis revealed 9 aberrant pairs in MDD vs. HCs, and 7 pairs in FEDN vs. recurrent groups. All aberrant component pairs in the SCN implicated the prefrontal cortex. CONCLUSIONS: These findings demonstrated brain structural deficits in MDD, and highlighted the prefrontal cortex as a central hub of SCN alterations. Our findings advance the understanding of MDD's neural mechanisms and suggest directions for diagnostic research.

Details DOI

FOCS Conference 2025 Conference Paper

Adversarially Robust Quantum State Learning and Testing

Maryam Aliakbarpour
Vladimir Braverman
Nai-Hui Chia
Yuhan Liu

Quantum state learning is a fundamental problem in physics and computer science. As near-term quantum devices are error-prone, it is important to design error-resistant algorithms. Apart from device errors, other unexpected factors could also affect the algorithm, such as careless human read-out error, or even a malicious hacker deliberately altering the measurement results. Thus, we want our algorithm to work even in the worst case when things go against our favor. We consider the practical setting of single-copy measurements and propose the $\gamma$-adversarial corruption model where an imaginary adversary can arbitrarily change $\gamma$-fraction of the measurement outcomes. This is stronger than the $\gamma$-bounded SPAM noise model, where the post-measurement state changes by at most $\gamma$ in trace distance. Under our stronger model of corruption, we design an algorithm using non-adaptive measurements that can learn an unknown rank- r state up to $\tilde{O}(\gamma \sqrt{r})$ in trace distance, provided that the number of copies is sufficiently large. We further prove an information-theoretic lower bound of $\Omega(\gamma \sqrt{r})$ for non-adaptive measurements, demonstrating the optimality of our algorithm. Our upper and lower bounds also hold for quantum state testing, where the goal is to test whether an unknown state is equal to a given state or far from it. Our results are intriguingly optimistic and pessimistic at the same time. For general states, the error is dimension-dependent and $\gamma \sqrt{d}$ in the worst case, meaning that only corrupting a very small fraction $(1 / \sqrt{d})$ of the outcomes could totally destroy any non-adaptive learning algorithm. However, for constant-rank states that are useful in many quantum algorithms, it is possible to achieve dimension-independent error, even in the worst-case adversarial setting.

Details

NeurIPS Conference 2025 Conference Paper

Boundary-to-Region Supervision for Offline Safe Reinforcement Learning

Huikang Su
Dengyun Peng
Zifeng Zhuang
Yuhan Liu
Qiguang Chen
Donglin Wang
Qinghe Liu

Offline safe reinforcement learning aims to learn policies that satisfy predefined safety constraints from static datasets. Existing sequence-model-based methods condition action generation on symmetric input tokens for return-to-go and cost-to-go, neglecting their intrinsic asymmetry: RTG serves as a flexible performance target, while CTG should represent a rigid safety boundary. This symmetric conditioning leads to unreliable constraint satisfaction, especially when encountering out-of-distribution cost trajectories. To address this, we propose Boundary-to-Region (B2R), a framework that enables asymmetric conditioning through cost signal realignment. B2R redefines CTG as a boundary constraint under a fixed safety budget, unifying the cost distribution of all feasible trajectories while preserving reward structures. Combined with rotary positional embeddings, it enhances exploration within the safe region. Experimental results show that B2R satisfies safety constraints in 35 out of 38 safety-critical tasks while achieving superior reward performance over baseline methods. This work highlights the limitations of symmetric token conditioning and establishes a new theoretical and practical approach for applying sequence models to safe RL.

PDF Details

NeurIPS Conference 2025 Conference Paper

EPA: Boosting Event-based Video Frame Interpolation with Perceptually Aligned Learning

Yuhan Liu
LingHui Fu
Zhen Yang
Hao Chen
Youfu Li
Yongjian Deng

Event cameras, with their capacity to provide high temporal resolution information between frames, are increasingly utilized for video frame interpolation (VFI) in challenging scenarios characterized by high-speed motion and significant occlusion. However, prevalent issues of blur and distortion within the keyframes and ground truth data used for training and inference in these demanding conditions are frequently overlooked. This oversight impedes the perceptual realism and multi-scene generalization capabilities of existing event-based VFI (E-VFI) methods when generating interpolated frames. Motivated by the observation that semantic-perceptual discrepancies between degraded and pristine images are considerably smaller than their image-level differences, we introduce EPA. This novel E-VFI framework diverges from approaches reliant on direct image-level supervision by constructing multilevel, degradation-insensitive semantic perceptual supervisory signals to enhance the perceptual realism and multi-scene generalization of the model's predictions. Specifically, EPA operates in two phases: it first employs a DINO-based perceptual extractor, a customized style adapter, and a reconstruction generator to derive multi-layered, degradation-insensitive semantic-perceptual features ($\mathcal{S}$). Second, a novel Bidirectional Event-Guided Alignment (BEGA) module utilizes deformable convolutions to align perceptual features from keyframes to ground truth with inter-frame temporal guidance extracted from event signals. By decoupling the learning process from direct image-level supervision, EPA enhances model robustness against degraded keyframes and unreliable ground truth information. Extensive experiments demonstrate that this approach yields interpolated frames more consistent with human perceptual preferences. *The code will be released upon acceptance. *

PDF Details

EAAI Journal 2025 Journal Article

Event-based video interpolation via complementary motion information

Yuhan Liu
LingHui Fu
Hao Chen
Zhen Yang
Youfu Li
Yongjian Deng

Video frame interpolation, the task of synthesizing intermediate frames to increase temporal resolution, often struggles with complex scenarios when constrained by the assumption of linear motion The advent of event cameras has led to significant progress in addressing this issue. Event cameras, with microsecond-level temporal resolution, bridge the gap between frames by providing accurate motion cues. However, current event-based video frame interpolation methods often overlook that event data primarily offers high-confidence features at scene edges during multi-modal feature fusion, which may limit the contribution of event signals to optical flow estimation. To address this, we propose a novel end-to-end learning framework that explicitly leverages the complementary characteristics of event signals and frames. Our method synergistically fuses dense contextual information from frames with sparse but precise edge motion from events via a proposed Edge Guided Attention (EGA) module. The EGA employs a coarse-to-fine strategy, where event-based optical flow directly refines the frame-based motion estimation at each level of a pyramidal architecture. Additionally, we introduce an event-based visibility map, co-learned within our event-processing network, to adaptively mitigate occlusions during the warping process. Extensive experiments conducted on a diverse suite of six benchmarks, including four synthetic and two real-world datasets validate the effectiveness of this novel approach. A dedicated discussion of the method’s trade-offs and potential limitations is presented in the Limitations section.

Details DOI

IROS Conference 2025 Conference Paper

Failure Forecasting Boosts Robustness of Sim2Real Rhythmic Insertion Policies

Yuhan Liu
Xinyu Zhang
Haonan Chang
Abdeslam Boularias

This paper addresses the challenges of Rhythmic Insertion Tasks (RIT), where a robot must repeatedly perform high-precision insertions, such as screwing a nut into a bolt with a wrench. The inherent difficulty of RIT lies in achieving millimeter-level accuracy and maintaining consistent performance over multiple repetitions, particularly when factors like nut rotation and friction introduce additional complexity. We propose a sim-to-real framework that integrates a reinforcement learning-based insertion policy with a failure forecasting module. By representing the wrench’s pose in the nut’s coordinate frame rather than the robot’s frame, our approach significantly enhances sim-to-real transferability. The insertion policy, trained in simulation, leverages real-time 6D pose tracking to execute precise alignment, insertion, and rotation maneuvers. Simultaneously, a neural network predicts potential execution failures, triggering a simple recovery mechanism that lifts the wrench and retries the insertion. Extensive experiments in both simulated and real-world environments demonstrate that our method not only achieves a high one-time success rate but also robustly maintains performance over long-horizon repetitive tasks. For more information please refer to the website: jaysparrow.github.io/rit.

Details

EAAI Journal 2025 Journal Article

Tensor product-fault diagnosis-Transformer based wind turbine blade fault prediction method

Linfei Yin
Yuhan Liu
Nannan Wang

With the continuous iterative updating of wind turbine (WT) blade fault diagnosis (FD) technology, intelligent prediction methods based on supervisory control and data acquisition (SCADA) systems have gradually become advanced mainstream technology in the industry. However, despite the many advantages of SCADA data in fault prediction, its high-dimensional characteristics and highly unstable nature still pose significant challenges for practical applications. Accordingly, this study proposes an innovative WT blade fault prediction method based on tensor product dimensionality reduction and FD-Transformer (TP-FD-Transformer) methodology, which aims to effectively solve the problem of timely and accurate prediction of WT blade faults. The TP-FD-Transformer method combines the quantum dimensionality reduction technique with the FD-Transformer model to form a new framework for data processing and analysis. The TP-FD-Transformer method adopts the tensor product-relative position matrix composite dimensionality reduction technique, which effectively reduces the dimensionality and complexity of SCADA data while preserving its features. After data processing is completed, the TP-FD-Transformer method utilizes the FD-Transformer model for deep learning training. The FD-Transformer model has been improved for complex time series data and can effectively capture potential features in the data. The experiments under the open dataset show that the TP-FD-Transformer method demonstrates excellent prediction ability in the field of WT blade FD, with an accuracy rate of 93. 65 %. The research findings verify that TP-FD-Transformer method provides a feasible solution for the intelligent diagnosis of WT blade faults, with broad application prospects and significant practical significance.

Details DOI

IROS Conference 2024 Conference Paper

DAP: Diffusion-based Affordance Prediction for Multi-modality Storage

Haonan Chang
Kowndinya Boyalakuntla
Yuhan Liu
Xinyu Zhang
Liam Schramm
Abdeslam Boularias

Solving storage problems—where objects must be accurately placed into containers with precise orientations and positions—presents a distinct challenge that extends beyond traditional rearrangement tasks. These challenges are primarily due to the need for fine-grained 6D manipulation and the inherent multi-modality of solution spaces, where multiple viable goal configurations exist for the same storage container. We present a novel Diffusion-based Affordance Prediction (DAP) pipeline for the multi-modal object storage problem. DAP leverages a two-step approach, initially identifying a placeable region on the container and then precisely computing the relative pose between the object and that region. Existing methods either struggle with multi-modality issues or computation-intensive training. Our experiments demonstrate DAP’s superior performance and training efficiency over the current state-of-the-art RPDiff, achieving remarkable results on the RPDiff benchmark. Additionally, our experiments showcase DAP’s data efficiency in real-world applications, an advancement over existing simulation-driven approaches. Our contribution fills a gap in robotic manipulation research by offering a solution that is both computationally efficient and capable of handling real-world variability. Code and supplementary material can be found at: https://github.com/changhaonan/DPS.git.

Details

IJCAI Conference 2024 Conference Paper

From Skepticism to Acceptance: Simulating the Attitude Dynamics Toward Fake News

Yuhan Liu
Xiuying Chen
Xiaoqing Zhang
Xing Gao
Ji Zhang
Rui Yan

In the digital era, the rapid propagation of fake news and rumors via social networks brings notable societal challenges and impacts public opinion regulation. Traditional fake news modeling typically forecasts the general popularity trends of different groups or numerically represents opinions shift. However, these methods often oversimplify real-world complexities and overlook the rich semantic information of news text. The advent of large language models (LLMs) provides the possibility of modeling subtle dynamics of opinion. Consequently, in this work, we introduce a Fake news Propagation Simulation framework (FPS) based on LLM, which studies the trends and control of fake news propagation in detail. Specifically, each agent in the simulation represents an individual with a distinct personality. They are equipped with both short-term and long-term memory, as well as a reflective mechanism to mimic human-like thinking. Every day, they engage in random opinion exchanges, reflect on their thinking, and update their opinions. Our simulation results uncover patterns in fake news propagation related to topic relevance, and individual traits, aligning with real-world observations. Additionally, we evaluate various intervention strategies and demonstrate that early and appropriately frequent interventions strike a balance between governance cost and effectiveness, offering valuable insights for practical applications. Our study underscores the significant utility and potential of LLMs in combating fake news.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Echo of Neighbors: Privacy Amplification for Personalized Private Federated Learning with Shuffle Model

Yixuan Liu
Suyun Zhao
Li Xiong
Yuhan Liu
Hong Chen

Federated Learning, as a popular paradigm for collaborative training, is vulnerable against privacy attacks. Different privacy levels regarding users' attitudes need to be satisfied locally, while a strict privacy guarantee for the global model is also required centrally. Personalized Local Differential Privacy (PLDP) is suitable for preserving users' varying local privacy, yet only provides a central privacy guarantee equivalent to the worst-case local privacy level. Thus, achieving strong central privacy as well as personalized local privacy with a utility-promising model is a challenging problem. In this work, a general framework (APES) is built up to strengthen model privacy under personalized local privacy by leveraging the privacy amplification effect of the shuffle model. To tighten the privacy bound, we quantify the heterogeneous contributions to the central privacy user by user. The contributions are characterized by the ability of generating “echos” from the perturbation of each user, which is carefully measured by proposed methods Neighbor Divergence and Clip-Laplace Mechanism. Furthermore, we propose a refined framework (S-APES) with the post-sparsification technique to reduce privacy loss in high-dimension scenarios. To the best of our knowledge, the impact of shuffling on personalized local privacy is considered for the first time. We provide a strong privacy amplification effect, and the bound is tighter than the baseline result based on existing methods for uniform local privacy. Experiments demonstrate that our frameworks ensure comparable or higher accuracy for the global model.

PDF Details DOI

ICRA Conference 2023 Conference Paper

Learning Continuous Control Policies for Information-Theoretic Active Perception

Pengzhi Yang
Yuhan Liu
Shumon Koga
Arash Asgharivaskasi
Nikolay Atanasov 0001

This paper proposes a method for learning continuous control policies for exploration and active landmark localization. We consider a mobile robot detecting landmarks within a limited sensing range, and tackle the problem of learning a control policy that maximizes the mutual information between the landmark states and the sensor observations. We employ a Kalman filter to convert the partially observable problem in the landmark states to a Markov decision process (MDP), a differentiable field of view to shape the reward function, and an attention-based neural network to represent the control policy. The approach is combined with active volumetric mapping to promote environment exploration in addition to landmark localization. The performance is demonstrated in several simulated landmark localization tasks in comparison with benchmark methods.

Details

NeurIPS Conference 2022 Conference Paper

TwiBot-22: Towards Graph-Based Twitter Bot Detection

Shangbin Feng
Zhaoxuan Tan
Herun Wan
Ningnan Wang
Zilong Chen
Binchi Zhang
Qinghua Zheng
Wenqian Zhang

Twitter bot detection has become an increasingly important task to combat misinformation, facilitate social media moderation, and preserve the integrity of the online discourse. State-of-the-art bot detection methods generally leverage the graph structure of the Twitter network, and they exhibit promising performance when confronting novel Twitter bots that traditional methods fail to detect. However, very few of the existing Twitter bot detection datasets are graph-based, and even these few graph-based datasets suffer from limited dataset scale, incomplete graph structure, as well as low annotation quality. In fact, the lack of a large-scale graph-based Twitter bot detection benchmark that addresses these issues has seriously hindered the development and evaluation of novel graph-based bot detection approaches. In this paper, we propose TwiBot-22, a comprehensive graph-based Twitter bot detection benchmark that presents the largest dataset to date, provides diversified entities and relations on the Twitter network, and has considerably better annotation quality than existing datasets. In addition, we re-implement 35 representative Twitter bot detection baselines and evaluate them on 9 datasets, including TwiBot-22, to promote a fair comparison of model performance and a holistic understanding of research progress. To facilitate further research, we consolidate all implemented codes and datasets into the TwiBot-22 evaluation framework, where researchers could consistently evaluate new models and datasets. The TwiBot-22 Twitter bot detection benchmark and evaluation framework are publicly available at \url{https: //twibot22. github. io/}.

PDF Details

ICRA Conference 2021 Conference Paper

Auto-calibration Method Using Stop Signs for Urban Autonomous Driving Applications

Yunhai Han
Yuhan Liu
David Paz
Henrik I. Christensen

Calibration of sensors is fundamental to robust performance for intelligent vehicles. In natural environments, disturbances can easily challenge calibration. One possibility is to use natural objects of known shape to recalibrate sensors. An approach based on recognition of traffic signs, such as stop signs, and use of them for recalibration of cameras is presented. The approach is based on detection, geometry estimation, calibration, and recursive updating. Results from natural environments are presented that clearly show convergence and improved performance.

Details

NeurIPS Conference 2021 Conference Paper

Distributed Estimation with Multiple Samples per User: Sharp Rates and Phase Transition

Jayadev Acharya
Clement Canonne
Yuhan Liu
Ziteng Sun
Himanshu Tyagi

We obtain tight minimax rates for the problem of distributed estimation of discrete distributions under communication constraints, where $n$ users observing $m $ samples each can broadcast only $\ell$ bits. Our main result is a tight characterization (up to logarithmic factors) of the error rate as a function of $m$, $\ell$, the domain size, and the number of users under most regimes of interest. While previous work focused on the setting where each user only holds one sample, we show that as $m$ grows the $\ell_1$ error rate gets reduced by a factor of $\sqrt{m}$ for small $m$. However, for large $m$ we observe an interesting phase transition: the dependence of the error rate on the communication constraint $\ell$ changes from $1/\sqrt{2^{\ell}}$ to $1/\sqrt{\ell}$.

PDF Details

ICML Conference 2021 Conference Paper

SagaNet: A Small Sample Gated Network for Pediatric Cancer Diagnosis

Yuhan Liu
Shiliang Sun

The scarcity of available samples and the high annotation cost of medical data cause a bottleneck in many digital diagnosis tasks based on deep learning. This problem is especially severe in pediatric tumor tasks, due to the small population base of children and high sample diversity caused by the high metastasis rate of related tumors. Targeted research on pediatric tumors is urgently needed but lacks sufficient attention. In this work, we propose a novel model to solve the diagnosis task of small round blue cell tumors (SRBCTs). To solve the problem of high noise and high diversity in the small sample scenario, the model is constrained to pay attention to the valid areas in the pathological image with a masking mechanism, and a length-aware loss is proposed to improve the tolerance to feature diversity. We evaluate this framework on a challenging small sample SRBCTs dataset, whose classification is difficult even for professional pathologists. The proposed model shows the best performance compared with state-of-the-art deep models and generalization on another pathological dataset, which illustrates the potentiality of deep learning applications in difficult small sample medical tasks.

Details

NeurIPS Conference 2020 Conference Paper

Learning discrete distributions: user vs item-level privacy

Yuhan Liu
Ananda Theertha Suresh
Felix Xinnan X. Yu
Sanjiv Kumar
Michael Riley

Much of the literature on differential privacy focuses on item-level privacy, where loosely speaking, the goal is to provide privacy per item or training example. However, recently many practical applications such as federated learning require preserving privacy for all items of a single user, which is much harder to achieve. Therefore understanding the theoretical limit of user-level privacy becomes crucial. We study the fundamental problem of learning discrete distributions over $k$ symbols with user-level differential privacy. If each user has $m$ samples, we show that straightforward applications of Laplace or Gaussian mechanisms require the number of users to be $\mathcal{O}(k/(m\alpha^2) + k/\epsilon\alpha)$ to achieve an $\ell_1$ distance of $\alpha$ between the true and estimated distributions, with the privacy-induced penalty $k/\epsilon\alpha$ independent of the number of samples per user $m$. Moreover, we show that any mechanism that only operates on the final aggregate should require a user complexity of the same order. We then propose a mechanism such that the number of users scales as $\tilde{\mathcal{O}}(k/(m\alpha^2) + k/\sqrt{m}\epsilon\alpha)$ and further show that it is nearly-optimal under certain regimes. Thus the privacy penalty is $\tilde{\Theta}(\sqrt{m})$ times smaller compared to the standard mechanisms. We also propose general techniques for obtaining lower bounds on restricted differentially private estimators and a lower bound on the total variation between binomial distributions, both of which might be of independent interest.

PDF Details