This paper jointly investigates privacy preservation and Byzantine-robustness in decentralized learning. In a decentralized network, honest-but-curious agents faithfully follow the prescribed algorithm, but expect to infer their neighbors' private data from messages received during the learning process, while dishonest-and-Byzantine agents disobey the prescribed algorithm, and deliberately disseminate wrong messages to their neighbors for the sake of biasing the learning process. For this novel setting, we investigate a generic privacy-preserving and Byzantine-robust decentralized stochastic gradient descent (SGD) framework, in which Gaussian noise is injected to preserve privacy and robust aggregation rules are adopted to counteract Byzantine attacks. We analyze its learning error and privacy guarantee, discovering an essential tradeoff between privacy preservation and Byzantine-robustness in decentralized learning – the learning error caused by defending against Byzantine attacks is exacerbated by the Gaussian noise added to preserve privacy. For a class of state-of-the-art robust aggregation rules, we give unified analysis of their “mixing abilities”. Building upon this analysis, we reveal how the “mixing abilities” affect the tradeoff between privacy preservation and Byzantine-robustness. The theoretical results provide guidelines for achieving a favorable tradeoff with proper design of robust aggregation rules. Numerical experiments are conducted and corroborate our theoretical findings.

This paper explores locally differentially private distributed algorithms that solve non-convex empirical risk minimization problems. Traditional approaches often assume uniformly bounded stochastic gradients, which may not hold in practice. To address this issue, we propose differentially \textbf{Pri}vate \textbf{S}tochastic recursive \textbf{M}omentum with gr\textbf{A}dient clipping (PriSMA) that judiciously integrates clipping and momentum to enhance utility while guaranteeing privacy. Without assuming uniformly bounded stochastic gradients, given privacy requirement $(\epsilon,\delta)$, PriSMA achieves a learning error of $\tilde{\mathcal{O}}\big((\frac{\sqrt{d}}{\sqrt{M}N\epsilon})^\frac{2}{5}\big)$, where $M$ is the number of clients, $N$ is the number of data samples on each client and $d$ is the model dimension. This learning error bound is better than the state-of-the-art $\tilde{\mathcal{O}}\big((\frac{\sqrt{d}}{{\sqrt{M}N\epsilon}})^\frac{1}{3}\big)$ in terms of the dependence on $M$ and $N$.

Decentralized learning, which facilitates joint model training across geographically scattered devices, has gained significant attention in the field of signal and information processing in recent years. While the optimization errors of decentralized learning algorithms have been extensively studied, their generalization errors remain relatively under-explored. As the generalization errors reflect the scalability of the trained models on unseen data and are crucial in determining the performance of the trained models in real-world applications, understanding the generalization errors of decentralized learning algorithms is of paramount importance. In this paper, we present the first fine-grained generalization error analysis for decentralized learning with heterogeneous data as well as under mild assumptions, in contrast to prior studies that consider the homogeneous data and/or rely on a stringent bounded stochastic gradient assumption. Our results shed light on the impact of data heterogeneity, model initialization and stochastic gradient noise – factors that have not been previously investigated – on the generalization error of decentralized learning. Numerical experiments are conducted to validate our theoretical findings.

Fairness among different workers and robustness to Byzantine attacks are two critical issues in distributed learning. In this paper, we attempt to answer the following question: Can we simultaneously achieve fairness and robustness under Byzantine attacks? Here we provide a negative answer: It is very difficult to kill two birds with one stone. First, we observe that most of the existing robust distributed learning algorithms rely on robust aggregators to aggregate messages from the workers, and such robust aggregators share a common majority-dominance property. Second, we prove that a class of fair distributed learning algorithms, replacing the mean aggregator by those robust aggregators having the majority-dominance property to enhance robustness to Byzantine attacks, lead to unfair solutions even for a simple distributed linear regression problem. Third, we conduct numerical experiments on distributed linear regression and nonlinear classification, showing these algorithms to be either short of fairness or lack of robustness.

Federated learning addresses the concerns on data privacy by sharing model updates instead of raw data samples; however, the trained model is able to "memorize" some information about the training dataset. With the legislation on the right to be forgotten, it has become crucial for the federated system to remove the impact of undesired (e.g., unshareable or poisoned) data samples from the trained model, leading to the demand of federated unlearning. Existing federated unlearning algorithms often result in degraded model utility on the remaining dataset, and/or overlook the high communication cost during unlearning. To address these issues, in this paper we propose an effective and efficient federated unlearning algorithm that consists of two phases, balanced forgetting and utility refinement. The former ensures sufficient removal of the unlearning dataset but avoids utility degradation on the remaining dataset. The latter further recovers model utility on the remaining dataset. To reduce the communication cost, we also adopt oriented saliency compression that allows the clients to upload only salient parameters to the central server and is tailored to the specific focus of each phase. Extensive experiments are conducted to empirically show the superior performance of our proposed algorithm.

Robustness to malicious attacks is of paramount importance for distributed learning. Existing works usually consider the classical Byzantine attacks model, which assumes that some workers can send arbitrarily malicious messages to the server and disturb the aggregation steps of the distributed learning process. To defend against such worst-case Byzantine attacks, various robust aggregators have been proposed. They are proven to be effective and much superior to the often-used mean aggregator. In this paper, however, we demonstrate that the robust aggregators are too conservative for a class of weak but practical malicious attacks, known as label poisoning attacks, where the sample labels of some workers are poisoned. Surprisingly, we are able to show that the mean aggregator is more robust than the state-of-the-art robust aggregators in theory, given that the distributed data are sufficiently heterogeneous. In fact, the learning error of the mean aggregator is proven to be order-optimal in this case. Experimental results corroborate our theoretical findings, showing the superiority of the mean aggregator under label poisoning attacks.

In this paper, we establish tight lower bounds for Byzantine-robust distributed first-order stochastic methods in both strongly convex and non-convex stochastic optimization. We reveal that when the distributed nodes have heterogeneous data, the convergence error comprises two components: a non-vanishing Byzantine error and a vanishing optimization error. We establish the lower bounds on the Byzantine error and on the minimum number of queries to a stochastic gradient oracle for achieving an arbitrarily small optimization error. Nevertheless, we also identify significant discrepancies between our established lower bounds and the existing upper bounds. To fill this gap, we leverage the techniques of Nesterov's acceleration and variance reduction to develop novel Byzantine-robust distributed stochastic optimization methods that provably match these lower bounds, up to at most logarithmic factors, implying that our established lower bounds are tight.

Stochastic approximation (SA) that involves multiple coupled sequences has diverse applications, including but not limited to bilevel optimization, meta learning and reinforcement learning. Unfortunately, the existing multi-timescale analysis of multiple-sequence SA (MSSA) implies a slow convergence rate, whereas the single-timescale analysis relies on assuming smoothness of fixed points. In this paper, we present tighter single-timescale analysis for MSSA, without assuming smoothness of fixed points. Our theoretical results demonstrate that, when all involved operators are strongly monotone, MSSA converges at a rate of $\tilde {\mathcal{O}}\left( {{K^{ - 1}}} \right)$, where K is the total number of iterations. Under a weaker assumption that all involved operators are strongly monotone except for$O\left( {{K^{ - \frac{1}{2}}}} \right)$ the main one, MSSA converges at a rate of . These theoretical results align with those established in single-sequence SA (SSSA). Applying these theoretical results to bilevel optimization offers relaxed assumptions and/or simpler algorithms with performance guarantees, as validated by numerical experiments.

This paper considers the problem of decentralized resource allocation in the presence of Byzantine attacks. Such attacks occur when an unknown number of malicious agents send random or carefully crafted messages to their neighbors, aiming to prevent the honest agents from reaching the optimal resource allocation strategy. We characterize these malicious behaviors with the classical Byzantine attacks model, and propose a class of Byzantine-resilient decentralized resource allocation algorithms augmented with dual-domain defenses. The honest agents receive messages containing the (possibly malicious) dual variables from their neighbors at each iteration, and filter these messages with robust aggregation rules. Theoretically, we prove that the proposed algorithms converge to a neighborhood of the optimal resource allocation strategy, given that the robust aggregation rules are properly designed. Numerical experiments are conducted to corroborate the theoretical results.

Recently, decentralized learning has emerged as a popular peer-to-peer signal and information processing paradigm that enables model training across geographically distributed agents in a scalable manner, without the presence of any central server. When some of the agents are malicious (also termed as Byzantine), Byzantine-resilient decentralized learning algorithms are able to limit the impact of these Byzantine agents, without knowing their number and identities, and have guaranteed optimization errors. However, analysis of the generalization errors, which are critical to implementations of the trained models, is still lacking. In this paper, we provide the first analysis of the generalization errors for a class of Byzantine-resilient decentralized stochastic gradient descent (DSGD) algorithms. Our theoretical results reveal that the generalization errors cannot be entirely eliminated because of the presence of Byzantine agents, even if the number of training samples are infinite. Numerical experiments are conducted to confirm our theoretical results.

This paper jointly considers privacy preservation and Byzantine-robustness in decentralized learning. In a decentralized network, honest-but-curious agents faithfully follow the prescribed algorithm, but expect to infer their neighbors’ private data from messages received during the learning process, while dishonest-and-Byzantine agents disobey the prescribed algorithm, and deliberately disseminate wrong messages to their neighbors so as to bias the learning process. For this novel setting, we investigate a generic privacy-preserving and Byzantine-robust decentralized stochastic gradient descent (SGD) framework, in which Gaussian noise is injected to preserve privacy and robust aggregation rules are adopted to counteract Byzantine attacks. We analyze its learning error and privacy guarantee, discovering an essential tradeoff between privacy preservation and Byzantine-robustness in decentralized learning – the learning error caused by defending against Byzantine attacks is exacerbated by the Gaussian noise added to preserve privacy. Numerical experiments corroborate our theoretical findings.

In this article, we consider centralized training and decentralized execution (CTDE) with diverse and private reward functions in cooperative multiagent reinforcement learning (MARL). The main challenge is that an unknown number of agents, whose identities are also unknown, can deliberately generate malicious messages and transmit them to the central controller. We term these malicious actions as Byzantine attacks. First, without Byzantine attacks, we propose a reward-free deep deterministic policy gradient (RF-DDPG) algorithm, in which gradients of agents' critics rather than rewards are sent to the central controller for preserving privacy. Second, to cope with Byzantine attacks, we develop a robust extension of RF-DDPG termed R2F-DDPG, which replaces the vulnerable average aggregation rule with robust ones. We propose a novel class of RL-specific Byzantine attacks that fail conventional robust aggregation rules, motivating the projection-boosted robust aggregation rules for R2F-DDPG. Numerical experiments show that RF-DDPG successfully trains agents to work cooperatively and that R2F-DDPG demonstrates robustness to Byzantine attacks.

This paper studies distributed online learning under Byzantine attacks. The performance of an online learning algorithm is characterized by (adversarial) regret, and a sublinear bound is preferred. But we prove that, even with a class of state-of-the-art robust aggregation rules, in an adversarial environment and with Byzantine participants, distributed online gradient descent can only achieve a linear adversarial regret bound, which is tight. This is the inevitable consequence of Byzantine attacks, even though we can control the constant of the linear adversarial regret to a reasonable level. Interestingly, when the environment is not fully adversarial so that the losses of the honest participants are i.i.d. (independent and identically distributed), we show that sublinear stochastic regret, in contrast to the aforementioned adversarial regret, is possible. We develop a Byzantine-robust distributed online gradient descent algorithm with momentum to attain such a sublinear stochastic regret bound.

This paper investigates personalized federated learning, in which a group of workers are coordinated by a server to train correlated local models, in addition to a common global model. This distributed statistical learning problem faces two challenges: efficiency of information exchange between the workers and the server, and robustness to potential malicious messages from the so-called Byzantine workers. We propose a projected stochastic block gradient descent method to address the robustness issue. Therein, each regular worker learns in a personalized manner with the aid of the global model, and the server judiciously aggregates the local models via a Huber function-based descent step. To improve communication efficiency, we allow the regular workers to perform multi-steps of local update per communication round. Convergence of the proposed method is established for non-convex personalized federated learning. Numerical experiments on neural network training validate advantages of the proposed method over the existing ones.

Recent studies demonstrate that Graph Neural Networks (GNNs) are vulnerable to slight but adversarially designed perturbations, known asadversarial examples. To address this issue, robust training methods against adversarial examples have received considerable attention in the literature.Adversarial Training (AT)is a successful approach to learning a robust model using adversarially perturbed training samples. Existing AT methods on GNNs typically construct adversarial perturbations in terms of graph structures or node features. However, they are less effective and fraught with challenges on graph data due to the discreteness of graph structure and the relationships between connected examples. In this work, we seek to address these challenges and proposeSpectralAdversarialTraining (SAT), a simple yet effective adversarial training approach for GNNs. SAT first adopts a low-rank approximation of the graph structure based on spectral decomposition, and then constructs adversarial perturbations in the spectral domain rather than directly manipulating the original graph structure. To investigate its effectiveness, we employ SAT on three widely used GNNs. Experimental results on four public graph datasets demonstrate that SAT significantly improves the robustness of GNNs against adversarial attacks without sacrificing classification accuracy and training efficiency.

Federated learning (FL) enables multiple clients to collaborate on a common learning task via only exchanging model updates. With the progressive improvements in deep learning models, communication is becoming a primary bottleneck of FL. Quantization of model updates before transmitting is an effective technique to reduce communication overhead. Most prior literature assumes lossless transmission, but in practice, quantized model updates are distorted by wireless channels due to the variation of client locations. Therefore, this paper focuses on analysis and design of personalized model update quantization with explicitly incorporating channel diversity in wireless FL. We present a novel convergence analysis of quantized FL, which encompasses full and partial client participation, single and multiple local training iterations, and convex and non-convex loss functions. This analysis explicitly embodies the impact of personalized quantization error, channel diversity and model aggregation in FL, and also elucidates their tradeoff on tightening a convergence rate upper bound. An optimization framework, which seeks an optimal allocation scheme given a total budget of quantization bits, is proposed by minimizing an upper bound with respect to channel quality. A nearly optimal solution is derived for this non-convex integer programming problem via analytically solving Karush–Kuhn–Tucker (KKT) optimality conditions and linear search. From a perspective of outlier detection, this channel-aware allocation scheme is also extended to robust model aggregation against client dropouts. Comprehensive numerical evaluation demonstrates the performance enhancement of the proposed scheme over the vanilla allocation scheme with equal quantization bits, particularly in terms of training stability, test accuracy, and robustness.

Motivated by the emerging federated learning applications, we jointly consider the problems of Byzantine-robustness and communication efficiency in distributed non-convex learning over non-IID data. We propose a compressed robust stochastic model aggregation (CRSA) method, which applies the idea of robust stochastic model aggregation to achieve Byzantine-robustness over non-IID data, while compresses the transmitted messages so as to achieve communication efficiency. Utilizing the tools of Moreau envelope and proximal point projection, we establish the convergence of C-RSA for distributed non-convex learning problems. Numerical experiments on training a large-scale neural network demonstrate the effectiveness of the proposed C-RSA method.

We consider the Byzantine-robust decentralized stochastic optimization problem, where every agent periodically communicates with its neighbors to exchange the local models, and then updates its own local model by stochastic gradient descent. However, an unknown number of the agents are Byzantine, and perform adversarially during the optimization process. Few works have considered this challenging scenario, and an existing method termed DECEMBER is unable to simultaneously achieve linear convergence speed and small learning error due to the stochastic noise. To eliminate the negative effect of the stochastic noise, we introduce two variance reduction methods, stochastic average gradient algorithm (SAGA) and loopless stochastic variance-reduced gradient (LSVRG), to Byzantine-robust decentralized stochastic optimization. The two resulting methods, DECEMBER-SAGA and DECEMBER-LSVRG, enjoy both linear convergence speeds and small learning errors. Numerical experiments demonstrate their effectiveness.

This paper considers the resource allocation problem in a decentralized multi-agent network at presence of Byzantine agents. Compared with its centralized counterpart, a decentralized algorithm enjoys better scalability when the network is large-scale, but is more vulnerable when some of the agents are malicious and send wrong messages during the optimization process. We use the Byzantine attack model to describe these malicious actions, and propose a novel Byzantine-resilient decentralized resource allocation algorithm, abbreviated as BREDA. At each iteration of BREDA, each honest agent receives messages from its neighbors, uses coordinate-wise trimmed mean (CTM) to aggregate these messages, and then updates its local primal and dual variables with gradient descent and ascent, respectively. Numerical experiments demonstrate the resilience of BREDA to various Byzantine attacks.

Federated learning (FL) raises new challenges on security risks, especially when the FL system involves Byzantine clients that send corrupted or adversarial messages to the central server for deteriorating the training paradigm. While there is an extensive research on robust algorithms for horizontal or data-partitioned FL problems, the exploration in Byzantine-resilient vertical or feature-partitioned FL is quite limited. In this paper, we provide a problem formulation of vertical FL in the presence of Byzantine attacks, and propose a Byzantine-resilient dual subgradient method. Convergence analysis is established, and the influence of the Byzantine clients is also clarified. Numerical experiments show the proposed algorithm is robust to various Byzantine attacks on vertical FL.

We investigate the problem of Byzantine-robust compressed federated learning, where the transmissions from the workers to the master node are compressed, and subject to malicious attacks from an unknown number of Byzantine workers. We show that the vanilla combination of the distributed compressed stochastic gradient descent (SGD) with geometric median-based robust aggregation suffers from the compression noise under Byzantine attacks. In light of this observation, we propose to reduce the compression noise with gradient difference compression to improve the Byzantine-robustness. We also observe the impact of the intrinsic stochastic noise from selecting random samples, and adopt the stochastic average gradient algorithm (SAGA) to gradually eliminate the inner variations of regular workers. We prove that the proposed algorithm reaches a neighborhood of the optimal solution at a linear convergence rate, and the asymptotic learning error is in the same order as that of the state-of-the-art uncompressed method. Finally, numerical experiments demonstrate the effectiveness of the proposed method.

This paper aims at jointly addressing two seemly conflicting issues in federated learning: differential privacy (DP) and Byzantine-robustness, which are particularly challenging when the distributed data are non-i.i.d. (independent and identically distributed). The standard DP mechanisms add noise to the transmitted messages, and entangles with robust stochastic gradient aggregation to defend against Byzantine attacks. In this paper, we decouple the two issues via robust stochastic model aggregation, in the sense that our proposed DP mechanisms and the defense against Byzantine attacks have separated influence on the learning performance. Leveraging robust stochastic model aggregation, at each iteration, each worker calculates the difference between the local model and the global one, followed by sending the element-wise signs to the master node, which enables robustness to Byzantine attacks. Further, we design two DP mechanisms to perturb the uploaded signs for the purpose of privacy preservation, and prove that they are (epsilon,0)-DP by exploiting the properties of noise distributions. With the tools of Moreau envelop and proximal point projection, we establish the convergence of the proposed algorithm when the cost function is nonconvex. We analyze the trade-off between privacy preservation and learning performance, and show that the influence of our proposed DP mechanisms is decoupled with that of robust stochastic model aggregation. Numerical experiments demonstrate the effectiveness of the proposed algorithm.

Computation offloading is envisioned as a promising technique for prolonging the battery lives and enhancing the computation capability of mobile devices. In this paper, we study the task offloading and resource purchasing problems in an edge-cloud collaborative system. The purpose of this system is to minimize the cost of task offloading while ensuring that the tasks can be served before their maximum acceptable delays. Due to the uncertainty of both the task arrival rates and the prices of the computing resources, it is impossible to make an optimal decision online for a long-running time. Therefore, we propose a two-timescale Lyapunov optimization algorithm to overcome the uncertainty of the system’s future information and make the optimal decisions only based on the system’s current states. By purchasing computation resources in different timescales from the public cloud and making online decisions on where and how many requests should be offloaded, we can achieve an efficient outcome such that the system performance can approach the offline optimum without requiring a priori knowledge of system statistics. Rigorous theoretical analysis confirms the effectiveness of the proposed two-timescale Lyapunov optimization algorithm and extensive trace-driven experimental results show that the algorithm achieves outstanding performance gains over existing benchmarks.

This article develops a communication-efficient algorithm to solve the stochastic optimization problem defined over a distributed network, aiming at reducing the burdensome communication in applications, such as distributed machine learning. Different from the existing works based on quantization and sparsification, we introduce a communication-censoring technique to reduce the transmissions of variables, which leads to our communication-censored distributed stochastic gradient descent (CSGD) algorithm. Specifically, in CSGD, the latest minibatch stochastic gradient at a worker will be transmitted to the server if and only if it is sufficiently informative. When the latest gradient is not available, the stale one will be reused at the server. To implement this communication-censoring strategy, the batch size is increasing in order to alleviate the effect of stochastic gradient noise. Theoretically, CSGD enjoys the same order of convergence rate as that of SGD but effectively reduces communication. Numerical experiments demonstrate the sizable communication saving of CSGD.

In distributed learning and optimization, a network of multiple computing units coordinates to solve a large-scale problem. This article focuses on dynamic optimization over a decentralized network. We develop a communication-efficient algorithm based on the alternating direction method of multipliers (ADMM) with quantized and censored communications, termed DQC-ADMM. At each time of the algorithm, the nodes collaborate to minimize the summation of their time-varying, local objective functions. Through local iterative computation and communication, DQC-ADMM is able to track the time-varying optimal solution. Different from traditional approaches requiring transmissions of the exact local iterates among the neighbors at every time, we propose to quantize the transmitted information, as well as adopt a communication-censoring strategy for the sake of reducing the communication cost in the optimization process. To be specific, a node transmits the quantized version of the local information to its neighbors, if and only if the value sufficiently deviates from the one previously transmitted. We theoretically justify that the proposed DQC-ADMM is capable of tracking the time-varying optimal solution, subject to a bounded error caused by the quantized and censored communications, as well as the system dynamics. Through numerical experiments, we evaluate the tracking performance and communication savings of the proposed DQC-ADMM.

This paper considers the policy evaluation problem in reinforcement learning with agents of a decentralized and directed network. The focus is on decentralized temporal-difference (TD) learning with linear function approximation in the presence of unreliable or even malicious agents, termed as Byzantine agents. In order to evaluate the quality of a fixed policy in a common environment, agents usually run decentralized TD(λ) collaboratively. However, when some Byzantine agents behave adversarially, decentralized TD(λ) is unable to learn an accurate linear approximation for the true value function. We propose a trimmed-mean based decentralized TD(λ) algorithm to perform policy evaluation in this setting. We establish the finite-time convergence rate, as well as the asymptotic learning error that depends on the number of Byzantine agents. Numerical experiments corroborate the robustness of the proposed algorithm.

In this letter, we consider the policy evaluation problem with linear function approximation in the context of decentralized multi-agent reinforcement learning (MARL), where the agents with a fixed joint policy cooperate to estimate the global expected accumulative reward through a decentralized communication network. In the existing algorithms, every agent updates its local parameter by combining its neighboring local parameters and then running a local stochastic temporal-difference(0) (TD(0)) gradient step. However, due to the diversity of reward functions across the agents, the local stochastic TD(0) gradients can be very different, which hinders the agents from reaching the consensual and optimal parameter. Motivated by the gradient tracking strategy in decentralized optimization, we combine gradient tracking with decentralized TD(0) to accelerate the process of reaching consensus. We also propose two other acceleration strategies, one is gradient consensus while another jointly uses gradient tracking and gradient consensus. Numerical experiments demonstrate that the proposed algorithms attain faster convergence than the popular decentralized TD(0) method.

Deep learning has revolutionized the performance of classification and object detection, but meanwhile demands sufficient labeled data for training. Given insufficient data, while many techniques have been developed to help combat overfitting, the challenge remains if one tries to train deep networks, especially in the ill-posedextremely low data regimes: only a small set of labeled data are available, and nothing – including unlabeled data – else. Such regimes arise from practical situations where not only data labeling but also data collection itself is expensive. We propose a deep adversarial data augmentation (DADA) technique to address the problem, in which we elaborately formulate data augmentation as a problem of training a class-conditional and supervised generative adversarial network (GAN). Specifically, a new discriminator loss is proposed to fit the goal of data augmentation, through which both real and augmented samples are enforced to contribute to and be consistent in finding the decision boundaries. Tailored training techniques are developed accordingly. To quantitatively validate its effectiveness, we first perform extensive simulations to show that DADA substantially outperforms both traditional data augmentation and a few GAN-based options. We then extend experiments to three real-world small labeled classification datasets where existing data augmentation and/or transfer learning strategies are either less effective or infeasible. We also demonstrate that DADA to can be extended to the detection task. We improve the pedestrian synthesis work by substitute for our discriminator and training scheme. Validation experiment shows that DADA can improve the detection mean average precision (mAP) compared with some traditional data augmentation techniques in object detection. Source code is available athttps://github.com/SchafferZhang/DADA.

In this paper, we aim at solving a distributed machine learning problem under Byzantine attacks. In the distributed system, a number of workers (termed as Byzantine workers) could send arbitrary messages to the master and bias the learning process, due to data corruptions, computation errors or malicious attacks. Prior work has considered a total variation (TV) norm-penalized approximation formulation to handle Byzantine attacks, where the TV norm penalty forces the regular workers' local variables to be close, and meanwhile, tolerates the outliers sent by the Byzantine workers. The stochastic subgradient method, which does not consider the problem structure, is shown to be able to solve the TV norm-penalized approximation formulation. In this paper, we propose a stochastic alternating direction method of multipliers (ADMM) that utilizes the special structure of the TV norm penalty. The stochastic ADMM iterates are further simplified, such that the iteration-wise communication and computation costs are the same as those of the stochastic subgradient method. Numerical experiments on the COVERTYPE and MNIST dataset demonstrate the resilience of the proposed stochastic ADMM to various Byzantine attacks.

In this paper, we consider the Byzantine-robust stochastic optimization problem defined over a decentralized network, where the agents collaboratively minimize the summation of expectations of stochastic local cost functions, but some of the agents are unreliable. Due to data corruptions, equipment failures or cyber-attacks, these Byzantine agents can send faulty values to their neighbors and bias the optimization process. Our key idea to handle the Byzantine attacks is to formulate a total variation (TV) norm-penalized approximation of the Byzantine-free problem, where the penalty term forces the local models of regular agents to be close, but also allows the existence of outliers from the Byzantine agents. A stochastic subgra-dient method is applied to solve the penalized problem. We prove that the proposed method converges to a near-optimal solution of the Byzantine-free problem under mild assumptions, and the gap is determined by the number of Byzantine agents and the network topology. Numerical experiments corroborate the theoretical analysis, as well as demonstrate the robustness of proposed method to Byzantine attacks and its superior performance over existing methods.

This contribution deals with distributed finite-sum optimization for learning over networks in the presence of malicious Byzantine attacks. To cope with such attacks, resilient approaches so far combine stochastic gradient descent (SGD) with different robust aggregation rules. However, the sizeable SGD-induced gradient noise makes it challenging to distinguish malicious messages sent by the Byzantine attackers from noisy stochastic gradients sent by the friendly workers. This motivates gradient noise reduction as a means of robustifying SGD in the presence of Byzantine attacks. To this end, the present work puts forth a Byzantine attack resilient distributed (Byrd-) SAGA approach for learning tasks involving finite-sum optimization over networks. Rather than the mean employed by distributed SAGA, the novel Byrd-SAGA relies on the geometric median to aggregate the corrected stochastic gradients sent by the workers. When less than half of the workers are Byzantine attackers, the robustness of geometric median to outliers enables Byrd-SAGA to achieve provable linear convergence to a neighborhood of the optimal solution, where the size of neighborhood is determined by the number of Byzantine workers. Numerical tests demonstrate the robustness of Byrd-SAGA to various Byzantine attacks, as well as the merits of Byrd-SAGA over Byzantine-resilient SGD.

In this paper, we propose a class of robust stochastic subgradient methods for distributed learning from heterogeneous datasets at presence of an unknown number of Byzantine workers. The Byzantine workers, during the learning process, may send arbitrary incorrect messages to the master due to data corruptions, communication failures or malicious attacks, and consequently bias the learned model. The key to the proposed methods is a regularization term incorporated with the objective function so as to robustify the learning task and mitigate the negative effects of Byzantine attacks. The resultant subgradient-based algorithms are termed Byzantine-Robust Stochastic Aggregation methods, justifying our acronym RSA used henceforth. In contrast to most of the existing algorithms, RSA does not rely on the assumption that the data are independent and identically distributed (i.i.d.) on the workers, and hence fits for a wider class of applications. Theoretically, we show that: i) RSA converges to a near-optimal solution with the learning error dependent on the number of Byzantine workers; ii) the convergence rate of RSA under Byzantine attacks is the same as that of the stochastic gradient descent method, which is free of Byzantine attacks. Numerically, experiments on real dataset corroborate the competitive performance of RSA and a complexity reduction compared to the state-of-the-art alternatives.

This paper proposes a communication- and computation-efficient algorithm to solve a convex consensus optimization problem defined over a decentralized network. A remarkable existing algorithm to solve this problem is the alternating direction method of multipliers (ADMM), in which at every iteration every node updates its local variable through combining neighboring variables and solving an optimization subproblem. The proposed algorithm, called as communication-censored linearized ADMM (COLA), leverages a linearization technique to reduce the iteration-wise computation cost of ADMM and uses a communication-censoring strategy to alleviate the communication cost. To be specific, COLA introduces successive linearization approximations to the local cost functions such that the resultant computation is first-order and light-weight. Since the linearization technique slows down the convergence speed, COLA further adopts the communication-censoring strategy to avoid transmissions of less informative messages. A node is allowed to transmit only if the distance between the current local variable and its previously transmitted one is larger than a censoring threshold. We establish convergence as well as sublinear and linear rates of convergence of COLA, and demonstrate its satisfactory communication-computation tradeoff with numerical experiments.

In this paper, we aim at completing a large-scale low-rank matrix over a distributed network, which is subject to Byzantine attacks. We consider solving a nonconvex matrix factorization model with the distributed successive over-relaxation (SOR) method, where the distributed workers compute their private matrices using their own training data and the public matrix sent by the master, while the master updates the public matrix through aggregating the private matrices sent by the workers. However, the Byzantine workers could deliberately send faulty messages to the master so as to bias the optimization process. To address this issue, we propose to replace the aggregation step in the distributed SOR method by several state-of-the-art robust ones: geometric median, median, Krum and h-Krum. We conduct numerical experiments on the Netflix dataset and demonstrate the effectiveness of the proposed robust aggregation strategies in handling Byzantine attacks.

Deep learning has revolutionized the performance of classification, but meanwhile demands sufficient labeled data for training. Given insufficient data, while many techniques have been developed to help combat overfitting, the challenge remains if one tries to train deep networks, especially in the ill-posed extremely low data regimes: only a small set of labeled data are available, and nothing - including unlabeled data - else. Such regimes arise from practical situations where not only data labeling but also data collection itself is expensive. We propose a deep adversarial data augmentation (DADA) technique to address the problem, in which we elaborately formulate data augmentation as a problem of training a class-conditional and supervised generative adversarial network (GAN). Specifically, a new discriminator loss is proposed to fit the goal of data augmentation, through which both real and augmented samples are enforced to contribute to and be consistent in finding the decision boundaries. Tailored training techniques are developed accordingly. Source code is available at https://github.com/SchafferZhang/DADA.

A pure or nearly pure quantum state can be described as a low-rank density matrix, which is a positive semidefinite and unit-trace Hermitian. We consider the problem of recovering such a low-rank density matrix contaminated by sparse components, from a small set of linear measurements. This quantum state estimation task can be formulated as a robust principal component analysis (RPCA) problem subject to positive semidefinite and unit-trace Hermitian constraints. We propose an efficient and fast inexact alternating direction method of multipliers (I-ADMM), in which the subproblems are solved inexactly and hence have closed-form solutions. We prove global convergence of the proposed I-ADMM, and the theoretical result provides a guideline for parameter setting. Numerical experiments show that the proposed I-ADMM can recover state density matrices of 5 qubits on a laptop in 0.69 s, with 6 × 10-4accuracy (99.38% fidelity) using 30% compressive sensing measurements, which outperforms existing algorithms.

This paper considers the problem of tracking a network-wide solution that dynamically minimizes the summation of time-varying local cost functions of agents, when some of the agents are malfunctioning. The malfunctioning agents broadcast faulty values to their neighbors, and lead the optimization process to a wrong direction. To mitigate the influence of the malfunctioning agents, we propose a total variation (TV) norm regularized formulation that drives the local variables of the regular agents to be close, while allows them to be different with the faulty values broadcast by the malfunctioning agents. We give a sufficient condition under which consensus of the regular agents is guaranteed, and bound the gap between the consensual solution and the optimal solution we pursue as if the malfunctioning agents do not exist. A fully decentralized subgradient algorithm is proposed to solve the TV norm regularized problem in a dynamic manner. At every time, every regular agent only needs one subgradient evaluation of its current local cost function, in addition to combining messages received from neighboring regular and malfunctioning agents. The tracking error is proved to be bounded, given that the variation of the optimal solution is bounded. Numerical experiments demonstrate the robust tracking performance of the proposed algorithm at presence of the malfunctioning agents.

Light field, a promising representation to describe the scene appearance, is susceptible to various noise due to the current sensor design. This paper proposes a novel tensor-based denoising method for the 4D light field that consists of two main steps. First, we generalize the intrinsic tensor sparsity measure to light field images by exploiting the nonlocal similarity across the spatial and angular dimensions. Second, we further exploit the spatial-angular correlation by integrating light field super-resolution into the denoising process to eliminate the sub-pixel misalignment of different views. After a back-projection from the refined high-resolution central view under an intensity consistency criteria, the denoising performance for the light field can be boosted. Experimental results validate the superior performance of the proposed method in terms of both PSNR and visual quality on the HCI light field dataset.

Internet of Things (IoT) is featured with its seamless connectivity of billions of smart devices, which offer different functionalities and serve various personalized tasks. To meet the task-specific requirements such as latency and privacy, the fog computing emerges to extend cloud computing services to the edge of the Internet backbone. This paper deals withonline fog computingemerging in IoT, where the goal is to balance computation and communication at fog networks on-the-fly to minimize service latency. Due to heterogeneous devices and human participation in IoT, the online decisions here need to flexibly adapt to the temporally unpredictable user demands and availability of fog resources. By generalizing the classic online convex optimization (OCO) framework, the low-latency fog computing task is first formulated as an OCO problem involving both time-varying loss functions and time-varying constraints. These constraints are revealed after making decisions, and allow instantaneous violations yet they must be satisfied in the long term. Tailored for heterogeneous tasks in IoT, a “thing-adaptive” online saddle-point (TAOSP) scheme is developed, which automatically adjusts the stepsize to offer desirabletask-specificlearning rates. It is established that without prior knowledge of the time-varying parameters, TAOSP simultaneously yields near-optimality and feasibility, provided that the best dynamic solutions vary slowly over time. Numerical tests corroborate that our novel approach outperforms the state-of-the-art in minimizing network latency.

Inter-datacenter (inter-DC) networks are essential for large enterprises to deliver high-quality services to end-users. Since DCs are vulnerable to natural disasters, an inter-DC network operator needs an effective emergency backup plan to evacuate the endangered data out in case of a progressive disaster whose status can be predicted by an early warning system. In this paper, we try to solve the problem of emergency backup in inter-DC networks with progressive disasters. We first utilize the time-expanded network (TEN) approach to model the time-variant inter-DC network during a progressive disaster as a variant TEN (VTEN) and convert the dynamic flow scheduling for emergency backup to a static one. Then, with the VTEN, we formulate an optimization model to maximize the profit from the emergency backup in consideration of data values and resource costs. Although this large-scale optimization can be solved in a distributed way by leveraging the alternation direction method of multipliers (ADMM), we find that one of its subproblems is nontrivial in the distributed setting. We propose a novel inexact ADMM approach to resolve the issue induced by the subproblem, and prove that the proposed algorithm can converge to the optimal solution. The results from extensive simulations confirm that our algorithm is robust and time-efficient, and outperforms several benchmarks in terms of backup profit and running time.

The deluge of networked big data motivates the development of computation- and communication-efficient network information processing algorithms. In this paper, we propose two data-adaptive censoring strategies that significantly reduce the computation and communication costs of the distributed recursive least-squares (D-RLS) algorithm. Through introducing a cost function that underrates the importance of those observations with small innovations, we develop the first censoring strategy based on the alternating minimization algorithm and the stochastic Newton method. It saves computation when a datum is censored. The computation and communication costs are further reduced by the second censoring strategy, which prohibits a node updating and transmitting its local estimate to neighbors when its current innovation is less than a threshold. For both strategies, a simple criterion for selecting the threshold of innovation is given so as to reach a target ratio of data reduction. The proposed censored D-RLS algorithms guarantee convergence to the optimal argument in the mean-square deviation sense. Numerical experiments validate the effectiveness of the proposed algorithms.

This paper considers the emergency backup in an inter-datacenter (inter-DC) network whose topology is time-variant due to the progress of a disaster. We first transform the dynamic backup into a static flow problem through building a variable time-expanded network (V-TEN). Then, by considering both data utility and resource cost, we formulate an optimization to maximize the backup profit and leverage the alternating direction method of multipliers (ADMM) to design a time-efficient and distributed algorithm. Simulation results show that our ADMM-based algorithm outperforms several existing ones.

Despite its nonconvex nature, ℓ0 sparse approximation is desirable in many theoretical and application cases. We study the ℓ0 sparse approximation problem with the tool of deep learning, by proposing Deep ℓ0 Encoders. Two typical forms, the ℓ0 regularized problem and the M-sparse problem, are investigated. Based on solid iterative algorithms, we model them as feed-forward neural networks, through introducing novel neurons and pooling functions. Enforcing such structural priors acts as an effective network regularization. The deep encoders also enjoy faster inference, larger learning capacity, and better scalability compared to conventional sparse coding solutions. Furthermore, under task-driven losses, the models can be conveniently optimized from end to end. Numerical results demonstrate the impressive performances of the proposed encoders.

In this paper, we design a Deep Dual-Domain (D3) based fast restoration model to remove artifacts of JPEG compressed images. It leverages the large learning capacity of deep networks, as well as the problem-specific expertise that was hardly incorporated in the past design of deep architectures. For the latter, we take into consideration both the prior knowledge of the JPEG compression scheme, and the successful practice of the sparsity-based dual-domain approach. We further design the One-Step Sparse Inference (1-SI) module, as an efficient and lightweighted feed-forward approximation of sparse coding. Extensive experiments verify the superiority of the proposed D3 model over several state-of-the-art methods. Specifically, our best model is capable of outperforming the latest deep model for around 1 dB in PSNR, and is 30 times faster.

In this paper, we propose a weighted alternating direction method of multipliers (ADMM) to solve the consensus optimization problem over a decentralized network. Compared with the conventional ADMM that is popular in decentralized network optimization, the weighted ADMM is able to tune its weight matrices for the purpose of reducing the communication cost spent in the optimization process. We first prove convergence and establish linear convergence rate of the weighted ADMM. Second, we maximize the derived convergence speed and obtain the best weight matrices on a given topology. Third, observing that exchanging information with all the neighbors is expensive, we maximize the convergence speed while limit the number of communication arcs. This strategy finds a subgraph within the underlying topology to fulfill the optimization task and leads to a favorable tradeoff between the number of iterations and the communication cost per iteration. Numerical experiments demonstrate advantages of the weighted ADMM over its conventional counterpart in expediting the convergence speed and reducing the communication cost.

Agents of a network have access to strongly convex local functions fiand attempt to minimize the aggregate function f(x) = Σi=1nfi(x) while relying on variable exchanges with neighboring nodes. Various methods to solve this distributed optimization problem exist but they all rely on first order information. This paper introduces Network Newton, a method that incorporates second order information via distributed evaluation of approximations to Newton steps. The method is shown to converge linearly and to do so while exhibiting a quadratic phase. Numerical analyses show substantial reductions in convergence times relative to existing (first order) alternatives.

In this paper, we focus on solving the decentralized consensus optimization problem defined over a networked multi-agent system. All the agents shall cooperatively find a common minimizer of the overall objective while each agent holds its own local objective and can only communicate with its neighbors. Motivated by many applications in which the local objective is the sum of a differentiable part and a nondifferentiable part, this paper proposes a proximal gradient exact first-order algorithm (PG-EXTRA) that utilizes the separable problem structure. Here, “exact” means this decentralized algorithm yields an exact consensus minimizer using a fixed step size. When the nondifferentiable part vanishes, PG-EXTRA reduces to EXTRA, an existing decentralized optimization algorithm. When the differentiable part vanishes, PG-EXTRA finds its special case P-EXTRA, a proximal algorithm. We prove convergence and rate of convergence for PG-EXTRA. Numerical experiments on a decentralized compressive sensing problem validates the theoretical results.

In this paper, we consider monitoring multiple events in a sensing field using a large-scale wireless sensor network (WSN). The goal is to develop communication-efficient algorithms that are scalable to the network size. Exploiting the sparse nature of the events, we formulate the event monitoring task as an `1 regularized nonnegative least squares problem where the optimization variable is a sparse vector representing the locations and magnitudes of events. Traditionally the problem can be reformulated by letting each sensor hold a local copy of the event vector and imposing consensus constraints on the local copies, and solved by decentralized algorithms such as the alternating direction method of multipliers (ADMM). This technique requires each sensor to exchange their estimates of the entire sparse vector and hence leads to high communication cost. Motivated by the observation that an event usually has limited influence range, we develop two communication-efficient decentralized algorithms, one is the partial consensus algorithm and the other is the Jacobi approach. In the partial consensus algorithm that is based on the ADMM, each sensor is responsible for recovering those events relevant to itself, and hence only consent with neighboring nodes on a part of the sparse vector. This strategy greatly reduces the amount of information exchanged among sensors. The Jacobi approach addresses the case that each sensor cares about the event occurring at its own position. Jacobi-like iterates are shown to be much faster than other algorithms, and incur minimal communication cost per iteration. Simulation results validate the effectiveness of the proposed algorithms and demonstrate the importance of proper modelling in designing communication-efficient decentralized algorithms.

This paper develops a decentralized linearized alternating direction method of multipliers (LADMM) that minimizes the sum of local cost functions in a multi-agent network. Through linearizing the local cost functions agents can obtain their local solutions with simple algebraic operations and gradient descent steps. We prove that the algorithm linearly converges to the optimal solution given that the local cost functions are strongly convex and have Lipschitz gradients. The decentralized LADMM has similar computations as the distributed (sub)gradient method but outperforms the latter, which is unable to achieve linear rate of convergence and convergence to the exact optimal solution simultaneously. Compared to its non-linearized counterpart that suffers from high computation burden, the decentralized LADMM has a comparable rate of convergence according to both theoretical analysis and numerical experiments.

This paper considers the problem of covariance matrix estimation from the viewpoint of statistical signal processing for high-dimensional or wideband random processes. Due to limited sensing resources, it is often desired to accurately estimate the covariance matrix from a small number of sample observations. To make up for the lack of observations, this paper leverages the structural characteristics of the random processes by considering the interplay of three widely-available signal structures: stationarity, sparsity and the underlying probability distribution of the observed random signal. New problem formulations are developed that incorporate both compressive sampling and sparse covariance estimation strategies. Tradeoff study is provided to illustrate the design choices when estimating the covariance matrices using a handful of sample observations.

In the decentralized consensus optimization problem, a network of agents minimizes the summation of their local objective functions on a common set of variables, allowing only information exchange among neighbors. The alternating direction method of multipliers (ADMM) has been shown to be a powerful tool for solving the problem with empirically fast convergence. This paper establishes the linear convergence rate of the ADMM in decentralized consensus optimization. The theoretical convergence rate is a function of the network topology, properties of the local objective functions, and the algorithm parameter. This result not only gives a performance guarantee for the ADMM but also provides a guideline to accelerate its convergence rate for the decentralized consensus optimization problems.

In old video restoration, automatic detection of common defects, e.g., scratches and blotches, has always been emphasized. While prior thoughts mainly focus on detecting blotches and linear, vertical scratches separately, this paper contributes to a more generalized and challenging issue: simultaneous detection of blotches and complex scratches in video, with much less knowledge of them. We investigate the characteristics of blotches and scratches in space and time domain, and propose a novel detection method based on two main steps: cartoon-texture decomposition in the space domain and content-defect separation in the time domain. We then formulate it into convex optimization problems and develop corresponding algorithms. The experiment results demonstrate that the proposed method is of high detection accuracy, verifying the effectiveness of our detection via a video decomposition method.

In this paper, we propose a robust temporal-spatial decomposition (RTSD) model and discuss its applications in video processing. A video sequence usually possesses high correlations among and within its frames. Fully exploiting the temporal and spatial correlations enables efficient processing and better understanding of the video sequence. Considering that the video sequence typically contains slowly changing background and rapidly changing foreground as well as noise, we propose to decompose the video frames into three parts: the temporal-spatially correlated part, the feature compensation part, and the sparse noise part. Accordingly, the decomposition problem can be formulated as the minimization of a convex function, which consists of a nuclear norm, a total variation (TV)-like norm, and anl1norm. Since the minimization is nontrivial to handle, we develop a two-stage strategy to solve this decomposition problem, and discuss different alternatives to fulfil each stage of decomposition. The RTSD model treats video frames as a unity from both the temporal and spatial point of view, and demonstrates robustness to noise and certain background variations. Experiments on video denoising and scratch detection applications verify the effectiveness of the proposed RTSD model and the developed algorithms.

This paper introduces algorithms for the decentralized low-rank matrix completion problem. Assume a low-rank matrix W = [W1,W2, ...,WL]. In a network, each agent ℓ observes some entries of Wℓ. In order to recover the unobserved entries of W via decentralized computation, we factorize the unknown matrix W as the product of a public matrix X, common to all agents, and a private matrix Y = [Y1,Y2, ...,YL], where Yℓis held by agent ℓ. Each agent ℓ alternatively updates Yℓand its local estimate of X while communicating with its neighbors toward a consensus on the estimate. Once this consensus is (nearly) reached throughout the network, each agent ℓ recovers Wℓ= XYℓ, and thus W is recovered. The communication cost is scalable to the number of agents, and Wℓand Yℓare kept private to agent ℓ to a certain extent. The algorithm is accelerated by extrapolation and compares favorably to the centralized code in terms of recovery quality and robustness to rank over-estimate.

A new video frame interpolation technique is proposed in this paper.We first use the classical motion compensation interpolation (MCI), but only for motion vectors (MVs) marked as reliable in our classification procedure. To fill in the regions where no such MV is available, we proposed a novel 3-D total variation regularized completion model, which exploits both temporal and spatial smoothness among video frames. Experiments demonstrate its superior performance compared to several classical methods, both in visual quality and PSNR values, while the typical artifacts are significantly reduced.

In this paper, we propose a novel video error concealment method to restore the visual degradation, caused by packet loss in video delivery over unreliable channels. For a video sequence, we exploit its inherent temporal-spatially correlated property, i.e., temporal continuity and spatial smoothness, from a global view point. We then formulate it into a total variation regularized matrix completion model. Compared with the error concealment methods implemented in the H.264 reference software, our algorithm is able to achieve significantly higher PSNR as well as better visual quality.

This paper presents a novel denoising scheme for video sequences corrupted by mixed Gaussian-impulse noise. From a global viewpoint, such a video sequence contains three parts: temporal-spatially correlated video content, uncorrelated dense Gaussian noise, and uncorrelated sparse impulse noise. This fact motivates us to formulate the mixed Gaussian-impulse noise removal task as a temporal-spatial decomposition problem, which amounts to a convex program. A two-stage algorithm is developed to solve this problem efficiently. Effectiveness of the proposed algorithm on mixed Gaussian-impulse noise removal is validated through experiments. The results are satisfactory in both visual quality and PSNR values, while very few prior knowledge of noise statistic is required compared to most state-of-the-art methods.

This paper considers the problem of finding sparse solutions from multiple measurement vectors (MMVs) with joint sparsity. The solutions share the same sparsity structure, and the locations of the common nonzero support contain important information of signal features. When the measurement vectors are collected from spatially distributed users, the issue of decentralized support detection arises. This paper develops a decentralized row-based Lasso (DR-Lasso) algorithm for the distributed MMV problem. A penalty term on row-based total energy is introduced to enforce joint sparsity for the MMVs, and consensus constraints are formulated such that users can consent on the total energy, and hence the common nonzero support, in a decentralized manner. As an illustrative example, the problem of cooperative spectrum occupancy detection is solved in the context of wideband cognitive radio networks.

This paper addresses the problem of decentralized event detection in large-scale wireless sensor networks (WSNs). Compared with centralized or hierarchical solutions, decentralized algorithms are superior in terms of scalability and robustness. However, traditional decentralized optimization tools, such as consensus optimization, entail intensive information exchange of high-dimensional decision vectors and multipliers. This paper exploits the phenomenon of limited influence, namely, the influence of one event only affects its neighboring area. For this scenario, we let each sensor make decisions for its local area rather than for the entire network, and individual decisions seek to collaboratively reach the global optimum through iterative local communications at low network costs. An optimal solution based on the alternating direction method of multipliers (ADMM) is developed. To further reduce the network communication load, we also propose a heuristic decentralized linear programming (DLP) algorithm, which is shown to be efficient via simulations.

In a homogeneous wireless multihop network, the transmission range of nodes is an essential design parameter that critically affects the global design of the network. This paper investigates the relationship between the transmission range and two fundamental characteristics of wireless multihop networks: minimum node degree and k-connectivity. Conventional analysis assumes boundless network deployment area, which suffers from undesired border effects in practical applications based on bounded areas. To circumvent the border effect, this paper provides new analysis to accurately assess the network characteristics, including the upper bound and lower bound of both the minimum node degree and the k-connectivity. The analytical expressions hold for any arbitrary two-dimensional deployment area, when the nodes are densely deployed in a large and regular area. Simulation results corroborate with the derived analytical expressions.

Interest in multimodal function optimization is expanding rapidly since real-world optimization problems often require location of multiple optima in searching space. The concept of restricted evolution is introduced to provide multiple optima. Combined with a simple evolution strategy, restricted evolution method can provide multiple solutions with low time consumption. Consequent local search based on the found solutions improves accuracy of optimization. The proposed method is applied to practical design of varied-line-spacing holographic gratings. Optimization results show the efficiency and usefulness of this method.