Sequential Manipulation Against Rank Aggregation: Theory and Algorithm.

Rank aggregation with pairwise comparisons is widely encountered in sociology, politics, economics, psychology, sports, etc. Given the enormous social impact and the consequent incentives, the potential adversary has a strong motivation to manipulate the ranking list. However, the ideal attack opportunity and the excessive adversarial capability cause the existing methods to be impractical. To fully explore the potential risks, we leverage an online attack on the vulnerable data collection process. Since it is independent of rank aggregation and lacks effective protection mechanisms, we disrupt the data collection process by fabricating pairwise comparisons without knowledge of the future data or the true distribution. From the game-theoretic perspective, the confrontation scenario between the online manipulator and the ranker who takes control of the original data source is formulated as a distributionally robust game that deals with the uncertainty of knowledge. Then we demonstrate that the equilibrium in the above game is potentially favorable to the adversary by analyzing the vulnerability of the sampling algorithms such as Bernoulli and reservoir methods. According to the above theoretical analysis, different sequential manipulation policies are proposed under a Bayesian decision framework and a large class of parametric pairwise comparison models. For attackers with complete knowledge, we establish the asymptotic optimality of the proposed policies. To increase the success rate of the sequential manipulation with incomplete knowledge, a distributionally robust estimator, which replaces the maximum likelihood estimation in a saddle point problem, provides a conservative data generation solution. Finally, the corroborating empirical evidence shows that the proposed method manipulates the results of rank aggregation methods in a sequential manner.

Global burden of cardiovascular diseases attributed to low physical activity: An analysis of 204 countries and territories between 1990 and 2019.

Background: Low physical activity is a major risk factor for cardiovascular diseases (CVDs). This study aimed to estimate the global, regional, national, and sex-age-specific burden of CVDs attributed to low physical activity from 1990 to 2019. Methods: We leveraged data from the Global Burden of Disease Study 2019 to compute the number of fatalities, disability-adjusted life years (DALYs), age-adjusted mortality rates (ASMR), and age-adjusted DALY rates (ASDR) attributed to CVDs resulting from low physical activity. Furthermore, we scrutinized the trends and correlations of these metrics in connection with the socio-demographic index (SDI) across 21 regions and 204 countries and territories. Results: The global deaths and DALYs due to CVDs caused by low physical activity increased from 371,042.96 [95 % UI: 147,621.82-740,490] and 6,282,524.95 [95 % UI: 2,334,970.61-13,255,090.08] in 1990 to 639,174.92 [95 % UI: 272,011.34-1,216,528.4] and 9,996,080.17 [95 % UI: 4,130,111.16-20,323,339.89] in 2019, respectively. The corresponding ASMR and ASDR decreased from 12.55 [95 % UI: 5.12-24.23] and 181.64 [95 % UI: 71.59-374.01] in 1990 to 8.6 [95 % UI: 3.68-16.28] and 127.52 [95 % UI: 53.07-256.55] in 2019, respectively. Deaths and DALYs attributed to low physical activity were initially higher in males but shifted to females after 70-74 age group. Both genders had increasing death rates, peaking at 80-84 age group. Most CVDs deaths and DALYs number are caused by ischemic heart disease. The highest burden of CVDs attributed to low physical activity was observed in North Africa and the Middle East. The lowest burden was observed in Oceania and High-income Asia Pacific. There was a distinctive 'n-shape' relationship between the regional SDI and the ASDR of CVDs attributed to low physical activity from 1990 to 2019. Conclusion: The global impact of CVDs stemming from low physical activity remains substantial and demonstrates substantial regional disparities. As individuals age, this burden becomes more prominent, particularly among females. Efficacious interventions are imperative to promote physical activity and mitigate the risk of CVDs across diverse populations and regions.

Hyperspectral Compressive Snapshot Reconstruction via Coupled Low-Rank Subspace Representation and Self-Supervised Deep Network.

Coded aperture snapshot spectral imaging (CASSI) is an important technique for capturing three-dimensional (3D) hyperspectral images (HSIs), and involves an inverse problem of reconstructing the 3D HSI from its corresponding coded 2D measurements. Existing model-based and learning-based methods either could not explore the implicit feature of different HSIs or require a large amount of paired data for training, resulting in low reconstruction accuracy or poor generalization performance as well as interpretability. To remedy these deficiencies, this paper proposes a novel HSI reconstruction method, which exploits the global spectral correlation from the HSI itself through a formulation of model-driven low-rank subspace representation and learns the deep prior by a data-driven self-supervised deep learning scheme. Specifically, we firstly develop a model-driven low-rank subspace representation to decompose the HSI as the product of an orthogonal basis and a spatial representation coefficient, then propose a data-driven deep guided spatial-attention network (called DGSAN) to adaptively reconstruct the implicit spatial feature of HSI by learning the deep coefficient prior (DCP), and finally embed these implicit priors into an iterative optimization framework through a self-supervised training way without requiring any training data. Thus, the proposed method shall enhance the reconstruction accuracy, generalization ability, and interpretability. Extensive experiments on several datasets and imaging systems validate the superiority of our method. The source code and data of this article will be made publicly available at https://github.com/ChenYong1993/LRSDN.

Combining Low-Rank and Deep Plug-and-Play Priors for Snapshot Compressive Imaging.

Snapshot compressive imaging (SCI) is a promising technique that captures a 3-D hyperspectral image (HSI) by a 2-D detector in a compressed manner. The ill-posed inverse process of reconstructing the HSI from their corresponding 2-D measurements is challenging. However, current approaches either neglect the underlying characteristics, such as high spectral correlation, or demand abundant training datasets, resulting in an inadequate balance among performance, generalizability, and interpretability. To address these challenges, in this article, we propose a novel approach called LR2DP that integrates the model-driven low-rank prior and data-driven deep priors for SCI reconstruction. This approach not only captures the spectral correlation and deep spatial features of HSI but also takes advantage of both model-based and learning-based methods without requiring any extra training datasets. Specifically, to preserve the strong spectral correlation of the HSI effectively, we propose that the HSI lies in a low-rank subspace, thereby transforming the problem of reconstructing the HSI into estimating the spectral basis and spatial representation coefficient. Inspired by the mutual promotion of unsupervised deep image prior (DIP) and trained deep denoising prior (DDP), we integrate the unsupervised network and pre-trained deep denoiser into the plug-and-play (PnP) regime to estimate the representation coefficient together, aiming to explore the internal target image prior (learned by DIP) and the external training image prior (depicted by pre-trained DDP) of the HSI. An effective half-quadratic splitting (HQS) technique is employed to optimize the proposed HSI reconstruction model. Extensive experiments on both simulated and real datasets demonstrate the superiority of the proposed method over the state-of-the-art approaches.

Exploring Structural Sparsity of Deep Networks Via Inverse Scale Spaces.

The great success of deep neural networks is built upon their over-parameterization, which smooths the optimization landscape without degrading the generalization ability. Despite the benefits of over-parameterization, a huge amount of parameters makes deep networks cumbersome in daily life applications. On the other hand, training neural networks without over-parameterization faces many practical problems, e.g., being trapped in the local optimal. Though techniques such as pruning and distillation are developed, they are expensive in fully training a dense network as backward selection methods; and there is still a void on systematically exploring forward selection methods for learning structural sparsity in deep networks. To fill in this gap, this paper proposes a new approach based on differential inclusions of inverse scale spaces. Specifically, our method can generate a family of models from simple to complex ones along the dynamics via coupling a pair of parameters, such that over-parameterized deep models and their structural sparsity can be explored simultaneously. This kind of differential inclusion scheme has a simple discretization, dubbed Deep structure splitting Linearized Bregman Iteration (DessiLBI), whose global convergence in learning deep networks could be established under the Kurdyka-Lojasiewicz framework. Particularly, we explore several applications of DessiLBI, including finding sparse structures of networks directly via the coupled structure parameter and growing networks from simple to complex ones progressively. Experimental evidence shows that our method achieves comparable and even better performance than the competitive optimizers in exploring the sparse structure of several widely used backbones on the benchmark datasets. Remarkably, with early stopping, our method unveils "winning tickets" in early epochs: the effective sparse network structures with comparable test accuracy to fully trained over-parameterized models, that are further transferable to similar alternative tasks. Furthermore, our method is able to grow networks efficiently with adaptive filter configurations, demonstrating the good performance with much less computational cost. Codes and models can be downloaded at https://github.com/DessiLBI2020/DessiLBI.

A Tale of HodgeRank and Spectral Method: Target Attack Against Rank Aggregation is the Fixed Point of Adversarial Game.

Rank aggregation with pairwise comparisons has shown promising results in elections, sports competitions, recommendations, and information retrieval. However, little attention has been paid to the security issue of such algorithms, in contrast to numerous research work on the computational and statistical characteristics. Driven by huge profit, the potential adversary has strong motivation and incentives to manipulate the ranking list. Meanwhile, the intrinsic vulnerability of the rank aggregation methods is not well studied in the literature. To fully understand the possible risks, we focus on the purposeful adversary who desires to designate the aggregated results by modifying the pairwise data in this paper. From the perspective of the dynamical system, the attack behavior with a target ranking list is a fixed point belonging to the composition of the adversary and the victim. To perform the targeted attack, we formulate the interaction between the adversary and the victim as a game-theoretic framework consisting of two continuous operators while Nash equilibrium is established. Then two procedures against HodgeRank and RankCentrality are constructed to produce the modification of the original data. Furthermore, we prove that the victims will produce the target ranking list once the adversary masters the complete information. It is noteworthy that the proposed methods allow the adversary only to hold incomplete information or imperfect feedback and perform the purposeful attack. The effectiveness of the suggested target attack strategies is demonstrated by a series of toy simulations and several real-world data experiments. These experimental results show that the proposed methods could achieve the attacker's goal in the sense that the leading candidate of the perturbed ranking list is the designated one by the adversary.

Fully corrective gradient boosting with squared hinge: Fast learning rates and early stopping.

In this paper, we propose an efficient boosting method with theoretical guarantees for binary classification. There are three key ingredients of the proposed boosting method: a fully corrective greedy (FCG) update, a differentiable squared hinge (also called truncated quadratic) loss function, and an efficient alternating direction method of multipliers (ADMM) solver. Compared with traditional boosting methods, on one hand, the FCG update accelerates the numerical convergence rate, and on the other hand, the squared hinge loss inherits the robustness of the hinge loss for classification and maintains the theoretical benefits of the square loss in regression. The ADMM solver with guaranteed fast convergence then provides an efficient implementation for the proposed boosting method. We conduct both theoretical analysis and numerical verification to show the outperformance of the proposed method. Theoretically, a fast learning rate of order O((m/logm)-1/2) is proved under certain standard assumptions, where m is the size of sample set. Numerically, a series of toy simulations and real data experiments are carried out to verify the developed theory.

Poisoning Attack Against Estimating From Pairwise Comparisons.

As pairwise ranking becomes broadly employed for elections, sports competitions, recommendation, information retrieval and so on, attackers have strong motivation and incentives to manipulate or disrupt the ranking list. They could inject malicious comparisons into the training data to fool the target ranking algorithm. Such a technique is called "poisoning attack" in regression and classification tasks. In this paper, to the best of our knowledge, we initiate the first systematic investigation of data poisoning attack on the pairwise ranking algorithms, which can be generally formalized as the dynamic and static games between the ranker and the attacker, and can be modeled as certain kinds of integer programming problems mathematically. To break the computational hurdle of the underlying integer programming problems, we reformulate them into the distributionally robust optimization (DRO) problems, which are computational tractable. Based on such DRO formulations, we propose two efficient poisoning attack algorithms and establish the associated theoretical guarantees including the existence of Nash equilibrium and the generalization ability bounds. The effectiveness of the suggested poisoning attack strategies is demonstrated by a series of toy simulations and several real data experiments. These experimental results show that the proposed methods can significantly reduce the performance of the ranker in the sense that the correlation between the true ranking list and the aggregated results with toxic data can be decreased dramatically.

Random Sketching for Neural Networks With ReLU.

Training neural networks is recently a hot topic in machine learning due to its great success in many applications. Since the neural networks' training usually involves a highly nonconvex optimization problem, it is difficult to design optimization algorithms with perfect convergence guarantees to derive a neural network estimator of high quality. In this article, we borrow the well-known random sketching strategy from kernel methods to transform the training of shallow rectified linear unit (ReLU) nets into a linear least-squares problem. Using the localized approximation property of shallow ReLU nets and a recently developed dimensionality-leveraging scheme, we succeed in equipping shallow ReLU nets with a specific random sketching scheme. The efficiency of the suggested random sketching strategy is guaranteed by theoretical analysis and also verified via a series of numerical experiments. Theoretically, we show that the proposed random sketching is almost optimal in terms of both approximation capability and learning performance. This implies that random sketching does not degenerate the performance of shallow ReLU nets. Numerically, we show that random sketching can significantly reduce the computational burden of numerous backpropagation (BP) algorithms while maintaining their learning performance.

Constructive Neural Network Learning.

In this paper, we aim at developing scalable neural network-type learning systems. Motivated by the idea of constructive neural networks in approximation theory, we focus on constructing rather than training feed-forward neural networks (FNNs) for learning, and propose a novel FNNs learning system called the constructive FNN (CFN). Theoretically, we prove that the proposed method not only overcomes the classical saturation problem for constructive FNN approximation, but also reaches the optimal learning rate when the regression function is smooth, while the state-of-the-art learning rates established for traditional FNNs are only near optimal (up to a logarithmic factor). A series of numerical simulations are provided to show the efficiency and feasibility of CFN.

Fast Learning With Polynomial Kernels.

This paper proposes a new learning system of low computational cost, called fast polynomial kernel learning (FPL), based on regularized least squares with polynomial kernel and subsampling. The almost optimal learning rate as well as the feasibility verifications including the subsampling mechanism and solvability of FPL are provided in the framework of learning theory. Our theoretical assertions are verified by numerous toy simulations and real data applications. The studies in this paper show that FPL can reduce the computational burden of kernel methods without sacrificing its generalization ability very much.

Greedy Criterion in Orthogonal Greedy Learning.

Orthogonal greedy learning (OGL) is a stepwise learning scheme that starts with selecting a new atom from a specified dictionary via the steepest gradient descent (SGD) and then builds the estimator through orthogonal projection. In this paper, we found that SGD is not the unique greedy criterion and introduced a new greedy criterion, called as " -greedy threshold" for learning. Based on this new greedy criterion, we derived a straightforward termination rule for OGL. Our theoretical study shows that the new learning scheme can achieve the existing (almost) optimal learning rate of OGL. Numerical experiments are also provided to support that this new scheme can achieve almost optimal generalization performance while requiring less computation than OGL.

Learning Rates for Classification with Gaussian Kernels.

This letter aims at refined error analysis for binary classification using support vector machine (SVM) with gaussian kernel and convex loss. Our first result shows that for some loss functions, such as the truncated quadratic loss and quadratic loss, SVM with gaussian kernel can reach the almost optimal learning rate provided the regression function is smooth. Our second result shows that for a large number of loss functions, under some Tsybakov noise assumption, if the regression function is infinitely smooth, then SVM with gaussian kernel can achieve the learning rate of order [Formula: see text], where [Formula: see text] is the number of samples.

Jackson-type inequalities for spherical neural networks with doubling weights.

Recently, the spherical data processing has emerged in many applications and attracted a lot of attention. Among all the methods for dealing with the spherical data, the spherical neural networks (SNNs) method has been recognized as a very efficient tool due to SNNs possess both good approximation capability and spacial localization property. For better localized approximant, weighted approximation should be considered since different areas of the sphere may play different roles in the approximation process. In this paper, using the minimal Riesz energy points and the spherical cap average operator, we first construct a class of well-localized SNNs with a bounded sigmoidal activation function, and then study their approximation capabilities. More specifically, we establish a Jackson-type error estimate for the weighted SNNs approximation in the metric of L(p) space for the well developed doubling weights.

Learning rates of lq coefficient regularization learning with gaussian kernel.

Regularization is a well-recognized powerful strategy to improve the performance of a learning machine and l(q) regularization schemes with 0 < q < ∞ are central in use. It is known that different q leads to different properties of the deduced estimators, say, l(2) regularization leads to a smooth estimator, while l(1) regularization leads to a sparse estimator. Then how the generalization capability of l(q) regularization learning varies with q is worthy of investigation. In this letter, we study this problem in the framework of statistical learning theory. Our main results show that implementing l(q) coefficient regularization schemes in the sample-dependent hypothesis space associated with a gaussian kernel can attain the same almost optimal learning rates for all 0 < q < ∞. That is, the upper and lower bounds of learning rates for l(q) regularization learning are asymptotically identical for all 0 < q < ∞. Our finding tentatively reveals that in some modeling contexts, the choice of q might not have a strong impact on the generalization capability. From this perspective, q can be arbitrarily specified, or specified merely by other nongeneralization criteria like smoothness, computational complexity or sparsity.