A common assumption in matrix completion (MC) and tensor completion (TC) is that the missing locations are sampled randomly. However, in real-world scenarios, the unobserved elements are often not arbitrarily located, and may concentrate within entire rows or columns. We refer to this missing mechanism as structural missingness, and traditional MC and TC schemes suffer from drastic degradation under these circumstances. This work addresses the challenge of restoring structural missingness by introducing a novel framework for simultaneously reconstructing multiple matrices, called multi-matrix completion (MMC). In MMC, tri-factorization across matrices captures the correlation between matrices, and Tikhonov regularization on each matrix exploits its correlation. This design enables MMC to efficiently handle both random and structural missingness. In addition, MMC is not affected by the smoothness along matrices which makes it suitable for a wider variety of data compared to Fourier transform based TC methods. The alternating direction method of multipliers is utilized to solve the resultant optimization problem. The global convergence of the algorithm is supported by comprehensive theoretical analyses. We demonstrate the versatility of MMC through extensive experiments in image and video restoration, and showcase its superior performance in comparison to traditional MC and TC methods.

Byzantine-robust federated learning aims to maintain resilient performance in the presence of malicious attacks that can impede the convergence of learning algorithms. Although numerous robust aggregators have been developed to merge the collected gradient information in the server, they either require data homogeneity and are suboptimal for heterogeneous data, or their breakdown points—the smallest proportion of outliers that can make the aggregators fail—are not theoretically analyzed or less than 0.5. In contrast to existing aggregators, this paper formulates the aggregation process as a low-rank plus sparse decomposition model, where the low-rank component, with a rank of one, facilitates accurate gradient computation, while the sparse component, penalized by the ℓ2,0-norm, mitigates the impact of outliers. We prove that the devised rule achieves the maximum breakdown point of 0.5. Besides, we apply our aggregation rule to Byzantine-robust federated learning and employ the Polyak’s momentum to reduce gradient variance among honest workers. It is analyzed that our aggregator achieves order-optimal Byzantine-resilient federated learning for heterogeneous data. Experimental results using MNIST, Fashion-MNIST and CIFAR-10 demonstrate that the developed approach yields higher classification accuracy than the competing aggregators under different attack types and heterogeneity levels.

Byzantine-robust distributed or federated learning (FL) refers to providing reliable performance under Byzantine attacks, which violate the prescribed protocols and transmit arbitrary information to the server to hamper the convergence of machine learning (ML) algorithms, via designing resilient aggregation rules to combat attacks. Although numerous robust rules have been suggested, their performance degrades for heterogeneous data. A few techniques have been exploited to handle this problem, but they either require preaggregation operations, hence increasing the computational load, or lack breakdown point analysis of their rules. This article proposes a new aggregation rule, which clips the gradients received from all workers according to the distance between the gradient and the aggregation center. That is, when the distance is larger than the radius $\gamma $ , the gradient will be clipped, and the longer the distance, the closer the clipped gradient is to the center. We theoretically analyze that the breakdown point of the developed rule is 0.5, the maximum value for robust aggregators. Moreover, our rule achieves order-optimal Byzantine-robust training error under data heterogeneity, while the median-based schemes, such as coordinate-wise median (CM) and geometric median (GM), are suboptimal. Experimental results demonstrate that the devised aggregation mechanism can handle different attacks well and outperforms the existing rules.

As large language models continue to grow in size, parameter-efficient fine-tuning (PEFT) has become increasingly crucial.While lowrank adaptation (LoRA) offers a solution through low-rank updates, its static rank allocation may yield suboptimal results.Adaptive low-rank adaptation (AdaLoRA) improves this with dynamic allocation but remains sensitive to initial and target rank configurations.We introduce AROMA, a framework that automatically constructs layer-specific updates by iteratively building up rank-one components with very few trainable parameters that gradually diminish to zero.Unlike existing methods that employ rank reduction mechanisms, AROMA introduces a dual-loop architecture for rank growth.The inner loop extracts information from each rank-one subspace, while the outer loop determines the number of rankone subspaces, i.e., the optimal rank.We reset optimizer states to maintain subspace independence.AROMA significantly reduces parameters compared to LoRA and AdaLoRA while achieving superior performance on natural language understanding and generation, commonsense reasoning, offering new insights into adaptive PEFT.

In robust matrix completion (MC), the Welsch function, also referred to as the maximum correntropy criterion with Gaussian kernel, has been widely employed. However, it suffers from the drawback of down-weighing normal data. This work is the first to uncover the explicit regularizer (ER) for the Welsch function based on the multiplicative form of half-quadratic (HQ) minimization. Leveraging this discovery, we develop a new function called t-Welsch, also with ER, which provides unity weight to normal data and exhibits stronger robustness against large-magnitude outliers compared to Huber's weight. We apply the t-Welsch to rank-one matching pursuit, enabling accurate and robust low-rank matrix recovery without the need of rank information and singular value decomposition (SVD). The resultant MC algorithm is realized via block coordinate descent (BCD), whose analyses of convergence and computational complexity are produced. Experiments are conducted using synthetic random data, as well as real-world images with salt-and-pepper noise and multiple-input multiple-output (MIMO) radar signals in the presence of Gaussian mixture disturbances. In all three scenarios, the proposed algorithm outperforms the state-of-the-art robust MC methods in terms of recovery accuracy. The code is available at https://github.com/ShuDun23/t-Welsch-and-RAR1MC.