Canada

We study a private variant of ADMM with (strongly) convex objective functions. We consider a privacy model in which each iteration corresponds to a user whose private function is accessed only to update the primal variable, which is masked with Gaussian noise to achieve local privacy, while no noise is directly added to the dual variable. 

Privacy amplification by iteration can be interpreted from the perspective of the user from the first iteration. A recent work by Cyffers et al. [ICML 2023] has investigated privacy amplification by iteration for the proximal variant of ADMM, in which the entire private function of a user is accessed. In contrast, we consider a private variant of ADMM that needs only one gradient access to a user&#39;s private function. However, in this variant, both the primal and the dual variables need to be passed between successive iterations.

In order to apply the coupling framework in Balle et al. [NeurIPS 2019] to this gradient variant of ADMM, we need some novel ideas to resolve the following technical hurdles. First, we need that each ADMM iteration corresponds to a non-expansive mapping that unfortunately does not hold under the usual norm on the joint space of the primal and the dual variables, which we resolve by considering a customized norm.  Second, since the dual variable is not masked with any noise in each iteration, one iteration of noisy ADMM does not have a strong enough privacy guarantee, which we resolve by considering two consecutive noisy ADMM iterations together as a Markov operator.  

Our main result is that the privacy guarantee for the gradient variant of ADMM can be amplified by a factor proportional to the number of iterations; for strongly convex objective functions, the amplification is exponential in the number of iterations. These amplification results are consistent with the previous special case of stochastic gradient descent.

AAAI 2024

Privacy Amplification by Iteration for ADMM with (Strongly) Convex Objective Functions

privacy-aware ml

privacy and security

stochastic optimization

We study a private variant of ADMM with (strongly) convex objective functions. We consider a privacy model in which each iteration corresponds to a user whose private function is accessed only to update the primal variable, which is masked with Gaussian noise to achieve local privacy, while no noise is directly added to the dual variable. 

Privacy amplification by iteration can be interpreted from the perspective of the user from the first iteration. A recent work by Cyffers et al. [ICML 2023] has investigated privacy amplification by iteration for the proximal variant of ADMM, in which the entire private function of a user is accessed. In contrast, we consider a private variant of ADMM that needs only one gradient access to a user's private function. However, in this variant, both the primal and the dual variables need to be passed between successive iterations.

In order to apply the coupling framework in Balle et al. [NeurIPS 2019] to this gradient variant of ADMM, we need some novel ideas to resolve the following technical hurdles. First, we need that each ADMM iteration corresponds to a non-expansive mapping that unfortunately does not hold under the usual norm on the joint space of the primal and the dual variables, which we resolve by considering a customized norm.  Second, since the dual variable is not masked with any noise in each iteration, one iteration of noisy ADMM does not have a strong enough privacy guarantee, which we resolve by considering two consecutive noisy ADMM iterations together as a Markov operator.  

Our main result is that the privacy guarantee for the gradient variant of ADMM can be amplified by a factor proportional to the number of iterations; for strongly convex objective functions, the amplification is exponential in the number of iterations. These amplification results are consistent with the previous special case of stochastic gradient descent.

technical paper

We are pleased to announce the Thirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24), which will be held in Vancouver, British Columbia at the Vancouver Convention Centre – West Building from 20-27 February, 2024.

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-24 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.

We expect for AAAI-24 to be an in-person conference – one author of all accepted papers will be expected to present work in person unless there are exceptional circumstances that prevent this.<br><br><br><br>

In order to access the AAAI-24 event page you need to register [here](https://aaai.org/aaai-conference/registration/)

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. 

Artificial intelligence (AI) has immense potential in time series prediction, but most explainable tools have limited capabilities in providing a systematic understanding of important features over time. These tools typically rely on evaluating a single time point, overlook the time ordering of inputs, and neglect the time-sensitive nature of time series applications. These factors make it difficult for users, particularly those without domain knowledge, to comprehend AI model decisions and obtain meaningful explanations. We propose CGS-Mask, a post-hoc and model-agnostic cellular genetic strip mask-based saliency approach to address these challenges. CGS-Mask uses consecutive time steps as a cohesive entity to evaluate the impact of features on the final prediction, providing binary and sustained feature importance scores over time. Our algorithm optimizes the mask population iteratively to obtain the optimal mask in a reasonable time. We evaluated CGS-Mask on synthetic and real-world datasets, and it outperformed state-of-the-art methods in elucidating the importance of features over time.  According to our pilot user study via a questionnaire survey, CGS-Mask is the most effective approach in presenting easily understandable time series prediction results, enabling users to comprehend the decision-making process of AI models with ease.

CGS-Mask: Making Time Series Predictions Intuitive for All

Diffusion models have demonstrated exceptional capability in generating high-quality images, videos, and audio. Due to their adaptiveness in iterative refinement, they provide a strong potential for achieving better non-autoregressive sequence generation. However, existing text diffusion models still fall short in their performance due to a challenge in handling the discreteness of language. This paper thoroughly analyzes text diffusion models and uncovers two significant limitations: degradation of self-conditioning during training and misalignment between training and sampling. Motivated by our findings, we propose a novel Text Diffusion model called TReC, which mitigates the degradation with Reinforced Conditioning and the misalignment by Time-Aware Variance Scaling. Our extensive experiments demonstrate the competitiveness of TReC against autoregressive, non-autoregressive, and diffusion baselines. Moreover, qualitative analysis shows its advanced ability to fully utilize the diffusion process in refining samples.

Text Diffusion with Reinforced Conditioning

Recently, the paradigm of pre-training and fine-tuning graph neural networks has been intensively studied and applied in a wide range of graph mining tasks. 
Its success is generally attributed to the structural consistency between pre-training and downstream datasets, which, however, does not hold in many real-world scenarios. 
Existing works have shown that the structural divergence between pre-training and downstream graphs significantly limits the transferability when using the vanilla fine-tuning strategy. This divergence leads to model overfitting on pre-training graphs and causes difficulties in capturing the structural properties of the downstream graphs. 
In this paper, we identify the fundamental cause of structural divergence as the discrepancy of generative patterns between the pre-training and downstream graphs.
Furthermore, we propose G-Tuning to preserve the generative patterns of downstream graphs. 
Given a downstream graph G, the core idea is to tune the pre-trained GNN so that it can reconstruct the generative patterns of G, the graphon W.
However, the exact reconstruction of a graphon is known to be computationally expensive. To overcome this challenge, we provide a theoretical analysis that establishes the existence of a set of alternative graphons called graphon bases for any given graphon. By utilizing a linear combination of these graphon bases, we can efficiently approximate W. This theoretical finding forms the basis of our proposed model, as it enables effective learning of the graphon bases and their associated coefficients.
Compared with existing algorithms, G-Tuning demonstrates an average improvement of 0.5% and 2.6% on in-domain and out-of-domain transfer learning experiments, respectively.

Fine-Tuning Graph Neural Networks by Preserving Graph Generative Patterns

In this paper, we derive a PAC-Bayes bound on the generalisation gap, in a supervised time-series setting for a special class of discrete-time non-linear dynamical systems. This class includes stable recurrent neural networks (RNN), and the motivation for this work was its application to RNNs. In order to achieve the results, we impose some stability constraints, on the allowed models. 
Here, stability is understood in the sense of dynamical systems. For RNNs, these stability conditions can be expressed in terms of conditions on the weights. 
We assume the processes involved are essentially bounded and the loss functions are Lipschitz. The proposed bound on the generalisation gap depends on the mixing coefficient of the data distribution, and the essential supremum of the data. Furthermore, the bound converges to zero as the dataset size increases.
In this paper, we 1) formalize the learning problem, 2) derive a PAC-Bayesian error bound for such systems, 3) discuss various consequences of this error bound, and 4) show an illustrative example, with discussions on computing the proposed bound. Unlike other available bounds  the derived bound holds for non i.i.d. data (time-series) and it does not grow with the number of steps of the RNN.

PAC-Bayes Generalisation Bounds for Dynamical Systems including Stable RNNs

Finding node correspondence across networks, namely multi-network alignment, is an essential prerequisite for joint learning on multiple networks. Despite great success in aligning networks in pairs, the literature on multi-network alignment is sparse due to the exponentially growing solution space and lack of high-order discrepancy measures. To fill this gap, we propose a hierarchical multi-marginal optimal transport framework named HOT for multi-network alignment. To handle the large solution space, multiple networks are decomposed into smaller aligned clusters via the fused Gromov-Wasserstein (FGW) barycenter. To depict high-order relationships across multiple networks, the FGW distance is generalized to the multi-marginal setting, based on which networks can be aligned jointly. A fast proximal point method is further developed with guaranteed convergence to a local optimum. Extensive experiments and analysis show that our proposed HOT achieves significant improvements over the state-of-the-art in both effectiveness and scalability.

Hierarchical Multi-Marginal Optimal Transport for Network Alignment

Graph neural networks have been widely used to represent 3D molecules, which capture molecular attributes and geometric information through various message-passing mechanisms.
This study proposes a novel quaternion message-passing (QMP) module that can be plugged into many existing 3D molecular representation models and enhance their power for distinguishing molecular conformations.
In particular, our QMP module represents the 3D rotations between one chemical bond and its neighbor bonds as a quaternion sequence. 
Then, it aggregates the rotations by the chained Hamilton product of the quaternions. 
The real part of the output quaternion is invariant to the global 3D rotations of molecules but sensitive to the local torsions caused by twisting bonds, providing discriminative information for training molecular conformation representation models. 
In theory, we prove that considering these features enables invariant GNNs to distinguish the conformations caused by bond torsions. 
We encapsulate the QMP module with acceleration, so combining existing models with the QMP requires merely one-line code and little computational cost. 
Experiments on various molecular datasets show that plugging our QMP module into existing invariant GNNs leads to consistent and significant improvements in molecular conformation representation and downstream tasks.

A Plug-and-Play Quaternion Message-Passing Module for Molecular Conformation Representation

Quantum error correction codes (QECC) are a key component for realizing the potential of quantum computing. QECC, as its classical counterpart (ECC), enables the reduction of error rates, by distributing quantum logical information across redundant physical qubits, such that errors can be detected and corrected. In this work, we efficiently train novel \emph{end-to-end} deep quantum error decoders. We resolve the quantum measurement collapse by augmenting syndrome decoding to predict an initial estimate of the system noise, which is then refined iteratively through a deep neural network. The logical error rates calculated over finite fields are directly optimized via a differentiable objective, enabling efficient decoding under the constraints imposed by the code. Finally, our architecture is extended to support faulty syndrome measurement, to allow efficient decoding over repeated syndrome sampling. The proposed method demonstrates the power of neural decoders for QECC by achieving state-of-the-art accuracy, outperforming for small distance topological codes, the existing end-to-end neural and classical decoders, which are often computationally prohibitive.

Deep Quantum Error Correction

Coresets for $k$-means and $k$-median problems yield a small summary of the data, which preserves the clustering cost with respect to any set of $k$ centers. Recently coresets have also been constructed for constrained $k$-means and $k$-median problems. However, the notion of coresets has the drawback that (i) they can only be applied in settings where the input points are allowed to have weights, and (ii) in general metric spaces, the size of the coresets can depend logarithmically on the number of points. The notion of {\em weak coresets}, which have less stringent requirements than coresets,  has been studied in the context of classical $k$-means and $k$-median problems. A weak coreset is a pair $(J,S)$ of subsets of points, where $S$ acts as a summary of the point set and $J$ as a  set of potential centers. This pair satisfies the properties that (i) $S$ is a good summary of the data as long as the $k$ centers are chosen from $J$ only, and (ii) there is a good choice of $k$ centers in $J$ with a cost close to the optimal cost.  We develop this framework, which we call {\em universal weak coresets}, for constrained clustering settings. In conjunction with recent coreset constructions for constrained settings, our designs give greater data compression, are conceptually simpler, and apply to a wide range of constrained $k$-median and $k$-means problems.

Universal Weak Coreset

Decentralized learning has emerged as an alternative method to the popular parameter-server framework which suffers from high communication burden, single-point failure and scalability issues due to the need of a central server.  However, most existing works focus on a single shared model for all workers regardless of the data heterogeneity problem, rendering the resulting model performing poorly on individual workers.  In this work, we propose a novel personalized decentralized learning algorithm named DePRL via shared representations.  Our algorithm  relies on ideas from representation learning theory to learn a low-dimensional global representation collaboratively among all workers in a fully decentralized manner, as well as a user-specific low-dimensional local head leading to a personalized solution for each worker.  We show that DePRL achieves, for the first time, a provable \textit{linear speedup for convergence} with general non-linear representations (i.e., the convergence rate is improved linearly with respect to the number of workers). Experimental results support our theoretical findings showing the superiority of our method in data heterogeneous environments.

DePRL: Achieving Linear Convergence Speedup in Personalized Decentralized Learning with Shared Representations

Imitation learning (IL) has achieved considerable success in solving complex sequential decision-making problems. However, current IL methods mainly assume that the environment for learning policies is the same as the environment for collecting expert datasets. Therefore, these methods may fail to work when there are slight differences between the learning and expert environments, especially for challenging problems with high-dimensional image observations. However, in real-world scenarios, it is rare to have the chance to collect expert trajectories precisely in the target learning environment. To address this challenge, we propose a novel robust imitation learning approach, where we develop an inverse dynamics state representation learning objective to align the expert environment and the learning environment. With the abstract state representation, we design an effective reward function, which thoroughly measures the similarity between behavior data and expert data not only element-wise, but also from the trajectory level. We conduct extensive experiments to evaluate the proposed approach under various visual perturbations and in diverse visual control tasks. Our approach can achieve a near-expert performance in most environments, and significantly outperforms the state-of-the-art visual IL methods and robust IL methods.

Privacy Amplification by Iteration for ADMM with (Strongly) Convex Objective Functions

Downloads

Next from AAAI 2024

CGS-Mask: Making Time Series Predictions Intuitive for All

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES