Task arithmetic refers to editing the pre-trained model by adding a weighted sum of task vectors, each of which is the weight update from the pre-trained model to fine-tuned models for certain tasks. This approach recently gained attention as a computationally efficient inference method for model editing, e.g., multi-task learning, forgetting, and out-of-domain generalization capabilities. However, the theoretical understanding of why task vectors can execute various conceptual operations remains limited, due to the highly non-convexity of training Transformer-based models. To the best of our knowledge, this paper provides the first theoretical characterization of the generalization guarantees of task vector methods on nonlinear Transformers. We consider a conceptual learning setting, where each task is a binary classification problem based on a discriminative pattern. We theoretically prove the effectiveness of task addition in simultaneously learning a set of irrelevant or aligned tasks, as well as the success of task negation in unlearning one task from irrelevant or contradictory tasks. Moreover, we prove the proper selection of linear coefficients for task arithmetic to achieve guaranteed generalization to out-of-domain tasks. All of our theoretical results hold for both dense-weight parameters and their low-rank approximations. Although established in a conceptual setting, our theoretical findings were validated on a practical machine unlearning task using the large language model Phi-1.5 (1.3B).

Many machine learning problems today have multiple objective functions, which are often tackled by the multi-objective learning (MOL) framework. Albeit many encouraging results are obtained by MOL algorithms, a recent theoretical study [1] revealed that these gradient-based MOL methods (e.g., MGDA, CAGrad) all reflect an inherent trade-off between optimization convergence speeds and conflict-avoidance abilities. To this end, we develop an improved stochastic variance-reduced multi-objective gradient correction method for MOL, achieving the ${\mathcal{O}}\left({{\varepsilon ^{ - 1.5}}}\right)$ sample complexity. In addition, our proposed method simultaneously improves the theoretical guarantees for conflict avoidance and convergence rate compared to prior stochastic gradient-based MOL methods in the non-convex setting. We further validate the effectiveness of the proposed method empirically using popular multi-task learning (MTL) benchmarks.

This paper studies the transfer reinforcement learning (RL) problem where multiple RL problems have different reward functions but share the same underlying transition dynamics. In this setting, the Q-function of each RL problem (task) can be decomposed into a successor feature (SF) and a reward mapping: the former characterizes the transition dynamics, and the latter characterizes the task-specific reward function. This Q-function decomposition, coupled with a policy improvement operator known as generalized policy improvement (GPI), reduces the sample complexity of finding the optimal Q-function, and thus the SF & GPI framework exhibits promising empirical performance compared to traditional RL methods like Q-learning. However, its theoretical foundations remain largely unestablished, especially when learning the successor features using deep neural networks (SF-DQN). This paper studies the provable knowledge transfer using SFs-DQN in transfer RL problems. We establish the first convergence analysis with provable generalization guarantees for SF-DQN with GPI. The theory reveals that SF-DQN with GPI outperforms conventional RL approaches, such as deep Q-network, in terms of both faster convergence rate and better generalization. Numerical experiments on real and synthetic RL tasks support the superior performance of SF-DQN & GPI, aligning with our theoretical findings.

The sparsely gated mixture of experts (MoE) architecture sends different inputs to different subnetworks (experts), through trainable routers. MoE reduces the training computation significantly for large models, but its deployment can be still memory/computation expensive for some downstream tasks. Model pruning is a popular approach to reduce inference computation, but its application in MoE architecture is largely unexplored. To the best of our knowledge, this paper provides the first provably efficient technique for pruning experts in fine-tuned MoE models. We theoretically prove that prioritizing the pruning of the experts with a smaller change of the router’s $l_2$ norm from the pre-trained model guarantees the preservation of test accuracy, while significantly reducing the model size and the computational requirements. Although our theoretical analysis is centered on binary classification tasks on simplified MoE architecture, our expert pruning method is verified on large vision MoE models such as V-MoE and $\text{E}^3$-MoE fine-tuned on benchmark datasets such as CIFAR-10, CIFAR-100, and ImageNet.

Transformer-based large language models have displayed impressive in-context learning capabilities, where a pre-trained model can handle new tasks without fine-tuning by simply augmenting the query with some input-output examples from that task. Despite the empirical success, the mechanics of how to train a Transformer to achieve ICL and the corresponding ICL capacity is mostly elusive due to the technical challenges of analyzing the nonconvex training problems resulting from the nonlinear self-attention and nonlinear activation in Transformers. To the best of our knowledge, this paper provides the first theoretical analysis of the training dynamics of Transformers with nonlinear self-attention and nonlinear MLP, together with the ICL generalization capability of the resulting model. Focusing on a group of binary classification tasks, we train Transformers using data from a subset of these tasks and quantify the impact of various factors on the ICL generalization performance on the remaining unseen tasks with and without data distribution shifts. We also analyze how different components in the learned Transformers contribute to the ICL performance. Furthermore, we provide the first theoretical analysis of how model pruning affects ICL performance and prove that proper magnitude-based pruning can have a minimal impact on ICL while reducing inference costs. These theoretical findings are justified through numerical experiments.

Graph Transformers, which incorporate self-attention and positional encoding, have recently emerged as a powerful architecture for various graph learning tasks. Despite their impressive performance, the complex non-convex interactions across layers and the recursive graph structure have made it challenging to establish a theoretical foundation for learning and generalization. This study introduces the first theoretical investigation of a shallow Graph Transformer for semi-supervised node classification, comprising a self-attention layer with relative positional encoding and a two-layer perception. Focusing on a graph data model with discriminative nodes that determine node labels and non-discriminative nodes that are class-irrelevant, we characterize the sample complexity required to achieve a desirable generalization error by training with stochastic gradient descent (SGD). This paper provides the quantitative characterization of the sample complexity and number of iterations for convergence dependent on the fraction of discriminative nodes, the dominant patterns, and the initial model errors. Furthermore, we demonstrate that self-attention and positional encoding enhance generalization by making the attention map sparse and promoting the core neighborhood during training, which explains the superior feature representation of Graph Transformers. Our theoretical results are supported by empirical experiments on synthetic and real-world benchmarks.

In deep learning, mixture-of-experts (MoE) activates one or few experts (sub-networks) on a per-sample or per-token basis, resulting in significant computation reduction. The recently proposed patch-level routing in MoE (pMoE) divides each input into $n$ patches (or tokens) and sends $l$ patches ($l\ll n$) to each expert through prioritized routing. pMoE has demonstrated great empirical success in reducing training and inference costs while maintaining test accuracy. However, the theoretical explanation of pMoE and the general MoE remains elusive. Focusing on a supervised classification task using a mixture of two-layer convolutional neural networks (CNNs), we show for the first time that pMoE provably reduces the required number of training samples to achieve desirable generalization (referred to as the sample complexity) by a factor in the polynomial order of $n/l$, and outperforms its single-expert counterpart of the same or even larger capacity. The advantage results from the discriminative routing property, which is justified in both theory and practice that pMoE routers can filter label-irrelevant patches and route similar class-discriminative patches to the same expert. Our experimental results on MNIST, CIFAR-10, and CelebA support our theoretical findings on pMoE's generalization and show that pMoE can avoid learning spurious correlations.

Graph convolutional networks (GCNs) have recently achieved great empirical success in learning graph-structured data. To address its scalability issue due to the recursive embedding of neighboring features, graph topology sampling has been proposed to reduce the memory and computational cost of training GCNs, and it has achieved comparable test performance to those without topology sampling in many empirical studies. To the best of our knowledge, this paper provides the first theoretical justification of graph topology sampling in training (up to) three-layer GCNs for semi-supervised node classification. We formally characterize some sufficient conditions on graph topology sampling such that GCN training leads to diminishing generalization error. Moreover, our method tackles the non-convex interaction of weights across layers, which is under-explored in the existing theoretical analyses of GCNs. This paper characterizes the impact of graph structures and topology sampling on the generalization performance and sample complexity explicitly, and the theoretical findings are also justified through numerical experiments.

This paper presents a novel data-driven framework to aid in system state estimation when the power system is under unobservable false data injection attacks. The proposed framework dynamically detects and classifies false data injection attacks. Then, it retrieves the control signal using the acquired information. This process is accomplished in three main modules, with novel designs, for detection, classification, and control signal retrieval. The detection module monitors historical changes of phasor measurements and captures any deviation pattern caused by an attack on a complex plane. This approach can help to reveal characteristics of the attacks including the direction, magnitude, and ratio of the injected false data. Using this information, the signal retrieval module can easily recover the original control signal and remove the injected false data. Further information regarding the attack type can be obtained through the classifier module. The proposed ensemble learner is compatible with harsh learning conditions including the lack of labeled data, concept drift, concept evolution, recurring classes, and independence to external updates. The proposed novel classifier can dynamically learn from data and classify attacks under all these harsh learning conditions. The introduced framework is evaluated w.r.t. real-world data captured from the Central New York Power System. The obtained results indicate the efficacy and stability of the proposed framework.

The lottery ticket hypothesis (LTH) states that learning on a properly pruned network (the winning ticket) has improved test accuracy over the original unpruned network. Although LTH has been justified empirically in a broad range of deep neural network (DNN) involved applications like computer vision and natural language processing, the theoretical validation of the improved generalization of a winning ticket remains elusive. To the best of our knowledge, our work, for the first time, characterizes the performance of training a pruned neural network by analyzing the geometric structure of the objective function and the sample complexity to achieve zero generalization error. We show that the convex region near a desirable model with guaranteed generalization enlarges as the neural network model is pruned, indicating the structural importance of a winning ticket. Moreover, as the algorithm for training a pruned neural network is specified as an (accelerated) stochastic gradient descent algorithm, we theoretically show that the number of samples required for achieving zero generalization error is proportional to the number of the non-pruned weights in the hidden layer. With a fixed number of samples, training a pruned neural network enjoys a faster convergence rate to the desired model than training the original unpruned one, providing a formal justification of the improved generalization of the winning ticket. Our theoretical results are acquired from learning a pruned neural network of one hidden layer, while experimental results are further provided to justify the implications in pruning multi-layer neural networks.

We analyze the learning problem of one-hidden-layer nonoverlapping convolutional neural networks with the rectified linear unit (ReLU) activation function from the perspective of model estimation. The training outputs are assumed to be generated by the neural network with the unknown ground-truth parameters plus some additive noise, and the objective is to estimate the model parameters by minimizing a nonconvex squared loss function of the training data. Assuming that the training set contains a finite number of samples generated from the Gaussian distribution, we prove that the accelerated gradient descent (GD) algorithm with a proper initialization converges to the ground-truth parameters (up to the noise level) with a linear rate even though the learning problem is nonconvex. Moreover, the convergence rate is proved to be faster than the vanilla GD. The initialization can be achieved by the existing tensor initialization method. In contrast to the existing works that assume an infinite number of samples, we theoretically establish the sample complexity of the required number of training samples. Although the neural network considered here is not deep, this is the first work to show that accelerated GD algorithms can find the global optimizer of the nonconvex learning problem of neural networks. This is also the first work that characterizes the sample complexity of gradient-based methods in learning convolutional neural networks with the nonsmooth ReLU activation function. This work also provides the tightest bound so far of the estimation error with respect to the output noise.

Although graph neural networks (GNNs) have made great progress recently on learning from graph-structured data in practice, their theoretical guarantee on generalizability remains elusive in the literature. In this paper, we provide a theoretically-grounded generalizability analysis of GNNs with one hidden layer for both regression and binary classification problems. Under the assumption that there exists a ground-truth GNN model (with zero generalization error), the objective of GNN learning is to estimate the ground-truth GNN parameters from the training data. To achieve this objective, we propose a learning algorithm that is built on tensor initialization and accelerated gradient descent. We then show that the proposed learning algorithm converges to the ground-truth GNN model for the regression problem, and to a model sufficiently close to the ground-truth for the binary classification problem. Moreover, for both cases, the convergence rate of the proposed learning algorithm is proven to be linear and faster than the vanilla gradient descent algorithm. We further explore the relationship between the sample complexity of GNNs and their underlying graph properties. Lastly, we provide numerical experiments to demonstrate the validity of our analysis and the effectiveness of the proposed learning algorithm for GNNs.

This paper studies the low-rank matrix recovery problem from partially lost and partially corrupted measurements. It shows both analytically and numerically that the recovery performance can be greatly enhanced if one further exploits the temporal correlations among a sequence of low-rank matrices. The matrix recovery problem is formulated as a non-convex optimization problem, and the recovery error is quantified analytically. A fast iterative algorithm is proposed to solve the non-convex problem, and every sequence generated by the algorithm converges to a critical point of the optimization problem. The method is numerically evaluated on the synthetic datasets.

This paper studies the robust principal component analysis (RPCA) problem with the objective to decompose a low-rank matrix and a sparse error matrix from their algebraic summation. If all the measurements in one column are erroneous, existing RPCA methods cannot recover the actual data in that column without additional prior information. Motivated by power system monitoring and magnetic resonance imaging (MRI) imaging, low-rank Hankel matrices are recently exploited to characterize the additional correlations among columns besides low-rankness. Exploiting the low-rank Hankel property, this paper develops an alternating-projection-based fast matrix decomposition algorithm, which can accurately recover the low-rank matrix with provable guarantees when simultaneous bad measurements happen across multiple columns consecutively. Numerical results are reported to evaluate the proposed algorithm.

Sparse recovery can recover sparse signals from a set of underdetermined linear measurements. Motivated by the need to monitor the key characteristics of large-scale networks from a limited number of measurements, this paper addresses the problem of recovering sparse signals in the presence of network topological constraints. Unlike conventional sparse recovery where a measurement can contain any subset of the unknown variables, we use a graph to characterize the topological constraints and allow an additive measurement over nodes (unknown variables) only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs, and the number of measurements by our construction is less than that needed by existing random constructions. Moreover, our construction for a line network is provably optimal in the sense that it requires the minimum number of measurements. A measurement construction algorithm for general graphs is also proposed and evaluated. For any given graph$G$with$n$nodes, we derive bounds of the minimum number of measurements needed to recover any$k$-sparse vector over$G$($M^{G}_{k,n}$). Using the Erdős-Rényi random graph as an example, we characterize the dependence of$M^{G}_{k,n}$on the graph structure. This paper suggests that$M^{G}_{k,n}$may serve as a graph connectivity metric.

Compressed sensing (CS) theory promises one can recover real-valued sparse signal from a small number of linear measurements. Motivated by network monitoring with link failures, we for the first time consider the problem of recovering signals that contain both real-valued entries and corruptions, where the real entries represent transmission delays on normal links and the corruptions represent failed links. Unlike conventional CS, here a measurement is real-valued only if it does not include a failed link, and it is corrupted otherwise. We prove that O((d + 1)max(d, k) log n) nonadaptive measurements are enough to recover all n-dimensional signals that contain k nonzero real entries and d corruptions. We provide explicit constructions of measurements and recovery algorithms. We also analyze the performance of signal recovery when the measurements contain errors.

This paper addresses the problem of sparse recovery with graph constraints in the sense that we can take additive measurements over nodes only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs. A general measurement construction algorithm is also proposed and evaluated. For any given graph G with n nodes, we derive order optimal upper bounds of the minimum number of measurements needed to recover any k-sparse vector over G (Mk,nG). Our study suggests that Mk,nGmay serve as a graph connectivity metric.

It is known that a high-dimensional sparse vector x* in TV can be recovered from low-dimensional measurements y = Ax* where Am×n(mp-minimization (0 ≤ p ≤ 1) as p varies, where ℓp-minimization returns a vector with the least ℓpquasi norm among all the vectors x satisfying Ax = y. Besides analyzing the performance of strong recovery where ℓp-minimization is re quired to recover all the sparse vectors up to certain sparsity, we also for the first time analyze the performance of "weak" recovery of ℓp-minimization (0 ≤ pm/n) → 1, we provide sharp thresholds of the sparsity ratio (i.e., percentage of nonzero entries of a vector) that differentiates the success and failure via ℓp-minimization. For strong recovery, the threshold strictly decreases from 0.5 to 0.239 as p increases from 0 to 1. Surprisingly, for weak recovery, the threshold is 2/3 for all p in [0, 1), while the threshold is 1 for ℓ1-minimization. We also explicitly demonstrate that ℓp-minimization (pp-minimization. For any a G (0.1), we provide bounds of the sparsity ratio for strong recovery and weak recovery, respectively, below which ℓp-minimization succeeds. Our bound of strong recovery improves on the existing bounds when a is large. In particular, regarding the recovery threshold, this paper argues that ℓp-minimization has a higher threshold with smaller p for strong recovery; the threshold is the same for all p for sectional recovery; and ℓp-minimization can outperform ℓp-minimization for weak recovery. These are in contrast to traditional wisdom that ℓp-minimization, though computationally more expensive, always has better sparse recovery ability than ℓ0-minimization since it is closer to ℓ1-minimization. Finally, we provide an intuitive explanation to our findings. Numerical examples are also used to un ambiguously confirm and illustrate the theoretical predictions.

This paper studies the performance difference of joint routing and congestion control when either single-path routes or multipath routes are used. Our performance metric is the total utility achieved by jointly optimizing transmission rates using congestion control and paths using source routing. In general, this performance difference is strictly positive and hard to determine-in fact an NP-hard problem. To better estimate this performance gap, we develop analytical bounds to this “cost of not splitting” in routing. We prove that the number of paths needed for optimal multipath routing differs from that of optimal single-path routing by no more than the number of links in the network. We provide a general bound on the performance loss, which is independent of the number of source-destination pairs when the latter is larger than the number of links in a network. We also propose a vertex projection method and combine it with a greedy branch-and-bound algorithm to provide progressively tighter bounds on the performance loss. Numerical examples are used to show the effectiveness of our approximation technique and estimation algorithms.

An unknown vector f in Rncan be recovered from corrupted measurements y = Af + e where Am×n(m ≥ n) is the coding matrix if the unknown error vector e is sparse. We investigate the relationship of the fraction of errors and the recovering ability of lp-minimization (0p-norm" of y-Ax. We give sharp thresholds of the fraction of errors that is recoverable. If e is an arbitrary unknown vector, the threshold strictly decreases from 0.5 to 0.239 as p increases from 0 to 1. If e has fixed support and fixed signs on the support, the threshold is 2/3 for all p in (0, 1), and 1 for p = 1.

This paper investigates the network performance loss of using only single-path routing when multiple paths are available. The performance metric is the aggregate utility achieved by the joint optimization of congestion control and routing. As computing the exact loss for a general network topology is NP-hard, we develop analytical bounds on this "cost of not splitting". Our bound is independent of the number of source-destination pairs when the latter one is larger than the number of links in a network. We also propose a vertex projection method and combine it with branch-and-bound to provide progressively tighter bounds on the performance loss. Numerical examples are used to show the effectiveness of our approximation technique.