We study decentralized optimization over a network of agents, modeled as an undirected graph and operating without a central server. The objective is to minimize a composite function $f+r$, where $f$ is a (strongly) convex function representing the average of the agents' losses, and $r$ is a convex, extended-value function (regularizer). We introduce DCatalyst, a unified black-box framework that injects Nesterov-type acceleration into decentralized optimization algorithms. At its core, DCatalyst is an inexact, momentum-accelerated proximal scheme (outer loop) that seamlessly wraps around a given decentralized method (inner loop). We show that DCatalyst attains optimal (up to logarithmic factors) communication and computational complexity across a broad family of decentralized algorithms and problem instances. In particular, it delivers accelerated rates for problem classes that previously lacked accelerated decentralized methods, thereby broadening the effectiveness of decentralized methods. On the technical side, our framework introduces inexact estimating sequences--an extension of Nesterov's classical estimating sequences, tailored to decentralized, composite optimization. This construction systematically accommodates consensus errors and inexact solutions of local subproblems, addressing challenges that existing estimating-sequence-based analyses cannot handle while retaining a black-box, plug-and-play character.

We study sparse linear regression over a network of agents, modeled as an undirected graph without a center node. The estimation of the $s$-sparse parameter is formulated as a constrained LASSO problem wherein each agent owns a subset of the $N$ total observations. We analyze the convergence rate and statistical guarantees of a distributed projected gradient tracking-based algorithm under high-dimensional scaling, allowing the ambient dimension $d$ to grow with (and possibly exceed) the sample size $N$. Our theory shows that, under standard notions of restricted strong convexity and smoothness of the average loss functions, suitable conditions on the network connectivity and algorithm tuning, the distributed algorithm converges globally at a linear rate to an estimate that is within the centralized statistical precision of the model, $O(s\log d/N)$. When $s\log d/N=o(1)$, a condition necessary for statistical consistency, an $\varepsilon$-optimal solution is attained after ${O}(\kappa \log (1/\varepsilon))$ gradient computations and $O(\kappa/(1-\rho) \log (1/\varepsilon))$ communication rounds, where $\kappa$ is the restricted condition number of the loss function and $\rho$ measures the network connectivity. The computation cost matches that of the centralized projected gradient algorithm despite having data distributed; whereas the communication rounds reduce as the network connectivity improves. Overall, our study reveals interesting connections between statistical efficiency, network connectivity and topology, and convergence rate in the high dimensional setting.

This paper addresses the minimization of the sum of strongly convex, smooth functions over a network of agents without a centralized server. Existing decentralized algorithms require knowledge of functions and network parameters, such as the Lipschitz constant of the global gradient and/or network connectivity, for hyperparameter tuning. Agents usually cannot access this information, leading to conservative selections and slow convergence or divergence. This paper introduces a decentralized algorithm that eliminates the need for specific parameter tuning. Our approach employs an operator splitting technique with a novel variable metric, enabling a local backtracking line-search to adaptively select the stepsize without global information or extensive communications. This results in favorable convergence guarantees and dependence on optimization and network parameters compared to existing nonadaptive methods. Notably, our method is the first adaptive decentralized algorithm that achieves linear convergence for strongly convex, smooth objectives. Preliminary numerical experiments support our theoretical findings, demonstrating superior performance in convergence speed and scalability.

We explore the matrix sensing problem from near-isotropic linear measurements, distributed across a network of agents modeled as an undirected graph, with no centralized node. We provide the first study of statistical, computational/communication guarantees for a decentralized gradient algorithm that solves the (nonconvex) Burer-Monteiro type decomposition associated to the low-rank matrix estimation. With small random initialization, the algorithm displays an approximate two-phase convergence: (i) a spectral phase that aligns the iterates' column space with the underlying low-rank matrix, mimicking centralized spectral initialization (not directly implementable over networks); and (ii) a local refinement phase that diverts the iterates from certain degenerate saddle points, while ensuring swift convergence to the underlying low-rank matrix. Central to our analysis is a novel "in-network" Restricted Isometry Property which accommodates for the decentralized nature of the optimization, revealing an intriguing interplay between sample complexity and network connectivity, topology, and communication complexity.

We study sparse linear regression over a network of agents, modeled as an undirected graph (with no centralized node). The estimation problem is formulated as the minimization of the sum of the local LASSO loss functions plus a quadratic penalty of the consensus constraint—the latter being instrumental to obtain distributed solution methods. While penalty-based consensus methods have been extensively studied in the optimization literature, their statistical and computational guarantees in the high dimensional setting remain unclear. This work provides an answer to this open problem. Our contribution is two-fold. First, we establish statistical consistency of the estimator: under a suitable choice of the penalty parameter, the optimal solution of the penalized problem achieves near optimal minimax rate $O(s \log d/N)$ in $\ell_2$-loss, where $s$ is the sparsity value, $d$ is the ambient dimension, and $N$ is the total sample size in the network—this matches centralized sample rates. Second, we show that the proximal-gradient algorithm applied to the penalized problem, which naturally leads to distributed implementations, converges linearly up to a tolerance of the order of the centralized statistical error---the rate scales as $O(d)$, revealing an unavoidable speed-accuracy dilemma. Numerical results demonstrate the tightness of the derived sample rate and convergence rate scalings.

We study linear regression from data distributed over a network of agents (with no server node) by means of LASSO estimation, in high-dimension, which allows the ambient dimension to grow faster than the sample size. While there is a vast literature of distributed algorithms applicable to the problem, statistical and computational guarantees of most of them remain unclear in high dimension. This paper provides a first statistical study of the Distributed Gradient Descent (DGD) in the Adapt-Then-Combine (ATC) form. Our theory shows that, under standard notions of restricted strong convexity and smoothness of the loss functions–which hold with high probability for standard data generation models–suitable conditions on the network connectivity and algorithm tuning, DGD-ATC converges globally at a linear rate to an estimate that is within thecentralizedstatistical precision of the model. In the worst-case scenario, the total number of communications to statistical optimality grows logarithmically with the ambient dimension, which improves on the communication complexity of DGD in the Combine-Then-Adapt (CTA) form, scaling linearly with the dimension. This reveals that mixing gradient information among agents, as DGD-ATC does, is critical in high-dimensions to obtain favorable rate scalings.

We study distributed (strongly convex) optimization problems over a network of agents, with no centralized nodes. The loss functions of the agents are assumed to be similar, due to statistical data similarity or otherwise. In order to reduce the number of communications to reach a solution accuracy, we proposed a preconditioned, accelerated distributed method. An $\varepsilon$-solution is achieved in $\tilde{\mathcal{O}}\big(\sqrt{\frac{\beta/\mu}{1-\rho}}\log1/\varepsilon\big)$ number of communications steps, where $\beta/\mu$ is the relative condition number between the global and local loss functions, and $\rho$ characterizes the connectivity of the network. This rate matches (up to poly-log factors) lower complexity communication bounds of distributed gossip-algorithms applied to the class of problems of interest. Numerical results show significant communication savings with respect to existing accelerated distributed schemes, especially when solving ill-conditioned problems.

We study structured convex optimization problems, with additive objective $r:=p + q$, where $r$ is ($\mu$-strongly) convex, $q$ is $L_q$-smooth and convex, and $p$ is $L_p$-smooth, possibly nonconvex. For such a class of problems, we proposed an inexact accelerated gradient sliding method that can skip the gradient computation for one of these components while still achieving optimal complexity of gradient calls of $p$ and $q$, that is, $\mathcal{O}(\sqrt{L_p/\mu})$ and $\mathcal{O}(\sqrt{L_q/\mu})$, respectively. This result is much sharper than the classic black-box complexity $\mathcal{O}(\sqrt{(L_p+L_q)/\mu})$, especially when the difference between $L_p$ and $L_q$ is large. We then apply the proposed method to solve distributed optimization problems over master-worker architectures, under agents' function similarity, due to statistical data similarity or otherwise. The distributed algorithm achieves for the first time lower complexity bounds on both communication and local gradient calls, with the former having being a long-standing open problem. Finally the method is extended to distributed saddle-problems (under function similarity) by means of solving a class of variational inequalities, achieving lower communication and computation complexity bounds.

We study linear regression from data distributed over a network of agents (with no master node) under high-dimensional scaling, which allows the ambient dimension to grow faster than the sample size. We propose a novel decentralization of the projected gradient algorithm whereby agents iteratively update their local estimates by a “double-mixing” mechanism, which suitably combines averages of iterates and gradients of neighbouring nodes. Under standard assumptions on the statistical model and network connectivity, the proposed method enjoys global linear convergence up to the statistical precision of the model. This improves on guarantees of (plain) DGD algorithms, whose iteration complexity grows undesirably with the ambient dimension. Our technical contribution is a novel convergence analysis that resembles (albeit different) algorithmic stability arguments extended to high-dimensions and distributed setting, which is of independent interest.

We study acceleration for distributed sparse regression in {\it high-dimensions}, which allows the parameter size to exceed and grow faster than the sample size. When applicable, existing distributed algorithms employing acceleration perform poorly in this setting, theoretically and numerically. We propose a new accelerated distributed algorithm suitable for high-dimensions. The method couples a suitable instance of accelerated Nesterov's proximal gradient with consensus and gradient-tracking mechanisms, aiming at estimating locally the gradient of the empirical loss while enforcing agreement on the local estimates. Under standard assumptions on the statistical model and tuning parameters, the proposed method is proved to globally converge at {\it linear} rate to an estimate that is within the {\it statistical precision} of the model. The iteration complexity scales as $\mathcal{O}(\sqrt{\kappa})$, while the communications per iteration are at most $\widetilde{\mathcal{O}}(\log m/(1-\rho))$, where $\kappa$ is the restricted condition number of the empirical loss, $m$ is the number of agents, and $\rho\in (0,1)$ measures the network connectivity. As by-product of our design, we also report an accelerated method for high-dimensional estimations over master-worker architectures, which is of independent interest and compares favorably with existing works.

This paper studies distributed algorithms for (strongly convex) composite optimization problems over mesh networks, subject to quantized communications. Instead of focusing on a specific algorithmic design, a black-box model is proposed, casting linearly convergent distributed algorithms in the form of fixed-point iterates. The algorithmic model is equipped with a novel random or deterministic Biased Compression (BC) rule on the quantizer design, and a new Adaptive encoding Non-uniform Quantizer (ANQ) coupled with a communication-efficient encoding scheme, which implements the BC-rule using a finite number of bits (below machine precision). This fills a gap existing in most state-of-the-art quantization schemes, such as those based on the popular compression rule, which rely on communication of some scalar signals with negligible quantization error (in practice quantized at the machine precision). A unified communication complexity analysis is developed for the black-box model, determining the average number of bits required to reach a solution of the optimization problem within a target accuracy. It is shown that the proposed BC-rule preserves linear convergence of the unquantized algorithms, and a trade-off between convergence rate and communication cost under ANQ-based quantization is characterized. Numerical results validate our theoretical findings and show that distributed algorithms equipped with the proposed ANQ have more favorable communication cost than algorithms using state-of-the-art quantization rules.

We propose a distributed cubic regularization of the Newton method for solving (constrained) empirical risk minimization problems over a network of agents, modeled as undirected graph. The algorithm employs an inexact, preconditioned Newton step at each agent’s side: the gradient of the centralized loss is iteratively estimated via a gradient-tracking consensus mechanism and the Hessian is subsampled over the local data sets. No Hessian matrices are exchanged over the network. We derive global complexity bounds for convex and strongly convex losses. Our analysis reveals an interesting interplay between sample and iteration/communication complexity: statistically accurate solutions are achievable in roughly the same number of iterations of the centralized cubic Newton, with a communication cost per iteration of the order of $\widetilde{\mathcal{O}}\big(1/\sqrt{1-\rho}\big)$, where $\rho$ characterizes the connectivity of the network. This represents a significant improvement with respect to existing, statistically oblivious, distributed Newton-based methods over networks.

We study solution methods for (strongly-)convex-(strongly)-concave Saddle-Point Problems (SPPs) over networks of two type--master/workers (thus centralized) architectures and mesh (thus decentralized) networks. The local functions at each node are assumed to be \textit{similar}, due to statistical data similarity or otherwise. We establish lower complexity bounds for a fairly general class of algorithms solving the SPP. We show that a given suboptimality $\epsilon>0$ is achieved over master/workers networks in $\Omega\big(\Delta\cdot \delta/\mu\cdot \log (1/\varepsilon)\big)$ rounds of communications, where $\delta>0$ measures the degree of similarity of the local functions, $\mu$ is their strong convexity constant, and $\Delta$ is the diameter of the network. The lower communication complexity bound over mesh networks reads $\Omega\big(1/{\sqrt{\rho}} \cdot {\delta}/{\mu}\cdot\log (1/\varepsilon)\big)$, where $\rho$ is the (normalized) eigengap of the gossip matrix used for the communication between neighbouring nodes. We then propose algorithms matching the lower bounds over either types of networks (up to log-factors). We assess the effectiveness of the proposed algorithms on a robust regression problem.

This paper proposes a novel family of primal-dual-based distributed algorithms for smooth, convex, multi-agent optimization over networks that uses only gradient information and gossip communications. The algorithms can also employ acceleration on the computation and communications. We provide a unified analysis of their convergence rate, measured in terms of the Bregman distance associated to the saddle point reformation of the distributed optimization problem. When acceleration is employed, the rate is shown to be optimal, in the sense that it matches (under the proposed metric) existing complexity lower bounds of distributed algorithms applicable to such a class of problem and using only gradient information and gossip communications. Preliminary numerical results on distributed least-square regression problems show that the proposed algorithm compares favorably on existing distributed schemes.

This paper puts forth a novel bi-linear modeling framework for data recovery via manifold-learning and sparse-approximation arguments and considers its application to dynamic magnetic-resonance imaging (dMRI). Each temporal-domain MR image is viewed as a point that lies onto or close to a smooth manifold, and landmark points are identified to describe the point cloud concisely. To facilitate computations, a dimensionality reduction module generates low-dimensional/compressed renditions of the landmark points. Recovery of high-fidelity MRI data is realized by solving a non-convex minimization task for the linear decompression operator and affine combinations of landmark points which locally approximate the latent manifold geometry. An algorithm with guaranteed convergence to stationary solutions of the non-convex minimization task is also provided. The aforementioned framework exploits the underlying spatio-temporal patterns and geometry of the acquired data without any prior training on external data or information. Extensive numerical results on simulated as well as real cardiac-cine MRI data illustrate noteworthy improvements of the advocated machine-learning framework over state-of-the-art reconstruction techniques.

This paper studies Dictionary Learning problems wherein the learning task is distributed over a multi-agent network, modeled as a time-varying directed graph. This formulation is relevant, for instance, in Big Data scenarios where massive amounts of data are collected/stored in different locations (e.g., sensors, clouds) and aggregating and/or processing all data in a fusion center might be inefficient or unfeasible, due to resource limitations, communication overheads or privacy issues. We develop a unified decentralized algorithmic framework for this class of nonconvex problems, which is proved to converge to stationary solutions at a sublinear rate. The new method hinges on Successive Convex Approximation techniques, coupled with a decentralized tracking mechanism aiming at locally estimating the gradient of the smooth part of the sum-utility. To the best of our knowledge, this is the first provably convergent decentralized algorithm for Dictionary Learning and, more generally, bi-convex problems over (time-varying) (di)graphs.

We propose a novel parallel asynchronous algorithmic framework for the minimization of the sum of a smooth (nonconvex) function and a convex (nonsmooth) regularizer. The framework hinges on Successive Convex Approximation (SCA) techniques and on a novel probabilistic model which describes in a unified way a variety of asynchronous settings in a more faithful and exhaustive way with respect to state-of-the-art models. Key features of our framework are: i) it accommodates inconsistent read, meaning that components of the variables may be written by some cores while being simultaneously read by others; ii) it covers in a unified way several existing methods; and iii) it accommodates a variety of parallel computing architectures. Almost sure convergence to stationary solutions is proved for the general case, and iteration complexity analysis is given for a specific version of our model. Numerical results show that our scheme outperforms existing asynchronous ones.

The paper studies a general class of distributed dictionary learning (DL) problems where the learning task is distributed over a multi-agent network with (possibly) time-varying (non-symmetric) connectivity. This setting is relevant, for instance, in scenarios where massive amounts of data are not collocated but collected/stored in different spatial locations. We develop a unified distributed algorithmic framework for this class of non-convex problems and establish its asymptotic convergence. The new method hinges on Successive Convex Approximation (SCA) techniques while leveraging a novel broadcast protocol to disseminate information and distribute the computation over the network, which neither requires the double-stochasticity of the consensus matrices nor the knowledge of the graph sequence to implement. To the best of our knowledge, this is the first distributed scheme with provable convergence for DL (and more generally bi-convex) problems, over (time-varying) digraphs.

We consider supervised learning problems over training sets in which both the number of training examples and the dimension of the feature vectors are large. We focus on the case where the loss function defining the quality of the parameter we wish to estimate may be non-convex, but also has a convex regularization. We propose a Doubly Stochastic Successive Convex approximation scheme (DSSC) able to handle non-convex regularized expected risk minimization. The method operates by decomposing the decision variable into blocks and operating on random subsets of blocks at each step. The algorithm belongs to the family of successive convex approximation methods since we replace the original non-convex stochastic objective by a strongly convex sample surrogate function, and solve the resulting convex program, for each randomly selected block in parallel. The method operates on subsets of features (block coordinate methods) and training examples (stochastic approximation) at each step. In contrast to many stochastic convex methods whose almost sure behavior is not guaranteed in non-convex settings, DSSC attains almost sure convergence to a stationary solution of the problem. Numerical experiments on a non-convex variant of a lasso regression problem show that DSSC performs favorably in this setting.

We consider a non-convex constrained Lagrangian formulation of a fundamental bi-criteria optimization problem for variable selection in statistical learning; the two criteria are a smooth (possibly) non-convex loss function, measuring the fitness of the model to data, and the latter function is a difference-of-convex (DC) regularization, employed to promote some extra structure on the solution, like sparsity. This general class of nonconvex problems arises in many big-data applications, from statistical machine learning to physical sciences and engineering. We develop the first unified distributed algorithmic framework for these problems and establish its asymptotic convergence to d-stationary solutions. Two key features of the method are: i) it can be implemented on arbitrary networks (digraphs) with (possibly) time-varying connectivity; and ii) it does not require the restrictive assumption that the (sub)gradient of the objective function is bounded, which enlarges significantly the class of statistical learning problems that can be solved with convergence guarantees.

In this paper we introduce a novel algorithmic framework for non-convex distributed optimization in multi-agent networks with time-varying (nonsymmetric) topology. The proposed method hinges on successive convex approximation (SCA) techniques while leveraging dynamic consensus as a mechanism to diffuse information: each agent first solves (possibly inexactly) a local convex approximation of the nonconvex original problem, and then performs local averaging operations. Asymptotic convergence to (stationary) solutions of the nonconvex problem is established. Finally, the framework is applied to a distributed nonlinear regression problem.

The paper studies the max-min fair multicast multigroup beamforming problem in a multi-cell environment, with perfect (instantaneous or statistical) Channel State Information (CSI). We propose a new general distributed algorithmic framework based on INner Convex Approximations (INCA): the nonsmooth NP-hard problem is replaced by a sequence of smooth strongly convex subproblems, which can be solved in a distributed fashion across the cells, with limited communication overhead. Differently from renowned semidefinite-relaxation-based schemes, the INCA algorithm is proved to always converge to a d-stationary solution of the aforementioned class of problems. Numerical results show that it compares favorably with state-of-the-art algorithms.

We study distributed queueing games in interference-limited wireless networks. We formulate the throughput maximization problem via distributed selection of users' transmission thresholds as a Nash Equilibrium Problem (NEP). We first focus on the solution analysis of the NEP and derive sufficient conditions for the existence and uniqueness of a Nash Equilibrium (NE). Then, we develop a general best-response-based algorithmic framework wherein the users can explicitly choose the degree of desired cooperation and signaling, converging to different types of solutions, namely: 1) a NE of the NEP when there is no cooperation among users and 2) a stationary point of the Network Utility Maximization (NUM) problem associated with the NEP, when some cooperation among the users in the form of (pricing) message passing is allowed. Finally, as a benchmark, we design a globally optimal but centralized solution method for the nonconvex NUM problem. Our experiments show that in many scenarios the sum-throughput at the NE of the NEP is very close to the global optimum of the NUM problem, which validates our noncooperative and distributed approach. When the gap of the NE from the global optimality is non negligible (e.g., in the presence of “high” coupling among users), exploiting cooperation among the users in the form of pricing enhances the system performance.

We propose a decomposition framework for the parallel optimization of the sum of a differentiable function and a (block) separable nonsmooth, convex one. The latter term is typically used to enforce structure in the solution as, for example, in LASSO problems. Our framework is very flexible and includes both fully parallel Jacobi schemes and Gauss-Seidel (Southwell-type) ones, as well as virtually all possibilities in between (e.g., gradient- or Newton-type methods) with only a subset of variables updated at each iteration. Our theoretical convergence results improve on existing ones, and numerical results show that the new method compares favorably to existing algorithms.

It is widely recognized that one of the factors that are going to yield the most significant capacity increase in wireless networks is spatial reuse of radio resources through dense deployment of radio access points. This leads to the development of small cell networks where different size cells, e.g. macro cells, picocells, femtocells, relays, coexist under the same standard. Of course, dense deployment is able to unravel its potential benefits only provided that interference is properly managed. In this paper, we propose an algorithm able to perform cell association and radio resource allocation jointly, in order to maximize the sum rate in a MIMO (interference) network. Cell selection is inherently a combinatorial problem. To deal with the nonconvexity, we introduce a suitably chosen convex relaxation of the objective function and develop a fast algorithm converging to a locally optimal solution of the nonconvex problem.

We propose a general algorithmic framework for the minimization of a nonconvex smooth function subject to nonconvex smooth constraints. The algorithm solves a sequence of (separable) strongly convex problems. Convergence to a stationary solution of the original nonconvex optimization is established. Our framework is very general and flexible; it unifies several existing Successive Convex Approximation (SCA)-based algorithms such as (proximal) gradient or Newton type methods, block coordinate (parallel) descent schemes, difference of convex functions methods, and improves on their convergence properties. More importantly, and differently from current SCA schemes, it naturally leads to distributed and parallelizable schemes for a large class of nonconvex problems. The new method is applied to the solution of a new rate profile optimization problem over Interference Broadcast Channels (IBCs); numerical results show that it outperforms existing ad-hoc algorithms.

Noncooperative game-theoretic tools have been increasingly used to study many important resource allocation problems in communications, networking, smart grids, and portfolio optimization. In this paper, we consider a general class of convex Nash equilibrium problems (NEPs), where each player aims at solving an arbitrary smooth convex optimization problem. Differently from most of current works, we do not assume any specific structure for the players' problems, and we allow the optimization variables of the players to be matrices in the complex domain. Our main contribution is the design of a novel class of distributed (asynchronous) best-response-algorithms suitable for solving the proposed NEPs, even in the presence of multiple solutions. The new methods, whose convergence analysis is based on variational inequality (VI) techniques, can select, among all the equilibria of a game, those that optimize a given performance criterion, at the cost of limited signaling among the players. This is a major departure from existing best-response algorithms, whose convergence conditions imply the uniqueness of the NE. Some of our results hinge on the use of VI problems directly in the complex domain; the study of these new kind of VIs also represents a noteworthy innovative contribution. We then apply the developed methods to solve some new generalizations of Single Input Single Output (SISO) and Multiple Input Multiple Output (MIMO) games in cognitive radio systems, showing a considerable performance improvement over classical pure noncooperative schemes.

The envisioned smart grid aims to improve the interaction between the supply- and the demand-side of the electricity network, resulting in a great optimization potential. In this paper, we propose a holistic-based, distributed day-ahead demand-side management method that is suitable for energy markets subject to an external regulation. Here, active subscribers solve the nonconvex problem of deriving the bidding strategies that minimize their overall expected monetary expense and simultaneously optimize eventual dispatchable energy generation and storage strategies. We show that, when such users collaborate, they achieve greater saving with respect to the corresponding user-oriented, selfish optimization. In this setting, we propose a cooperative, distributed, and iterative algorithm providing the optimal bidding, production, and storage strategies of the users, along with its convergence properties.

We propose a decomposition framework for the distributed optimization of general nonconvex sum-utility functions arising in the design of wireless multi-user interfering systems. Our main contributions are: the development of the first provably convergent Jacobi best-response algorithm, where all users simultaneously solve a suitably convexified version of the original sum-utility optimization problem; the derivation of a general dynamic pricing mechanism that provides a unified view of existing pricing schemes that are based, instead, on heuristics; and a framework that can be easily particularized to well-known applications, giving rise to practical algorithms that outperform all existing ad-hoc methods proposed for very specific problems. Our framework contains as special cases well-known gradient algorithms for nonconvex sum-utility problems, and many block-coordinate descents schemes for convex functions.

In cognitive radio (CR) systems, the primary users (PU) are protected by temperature interference constraints imposed on secondary users (SU). However, such limitations may be easily violated by SUs if perfect SU-to-PU channel state information (CSI) is not available at the secondary transmitters. In this paper, we propose a novel and distributed design of MIMO CR networks that is robust against imperfect SU-to-PU CSI. Specifically, we formulate the system design as a noncooperative game and robust global interference constraints are enforced via pricing; the prices are thus additional variables to be optimized. Building on the advanced and new theory of finite-dimensional variational inequalities (VI) in the complex domain, we analyze the proposed NE problem and devise alternative distributed algorithms along with their convergence properties.

We study distributed queueing games in interference-limited ad-hoc wireless networks. We formulate system design as a Nash Equilibrium (NE) problem, where the users aim at maximizing their own throughput by choosing the optimal transmission threshold. We first derive conditions for the existence and uniqueness of the NE; then we propose a distributed best-response algorithm solving the game along with its convergence properties. A second contribution of the paper is to develop a Branch and Bound-based (centralized) algorithm solving the associated (nonconvex) social problem, which one can use as benchmark to evaluate the performance of the proposed game theoretical formulation. Interestingly, our numerical results show that the sum-throughput achievable at the NE of the proposed game are very close to that of the social problem, which validates our game theoretical formulation. The performance loss is not negligible only in high interference scenarios. For such cases, we proposed a pricing-based algorithm yielding sum-throughput solutions very close to the globally optimal ones, at the cost of very limited signaling among the users.

Cognitive Radio (CR) systems are built on the coexistence of primary users (PUs) and secondary users (SUs), the latter being allowed to share spectral resources with the PUs but under strict interference limitations. However, such limitations may easily be violated by SUs if perfect SU-to-PU channel state information (CSI) is not available at the secondary transmitters, which always happens in practice. In this paper, we propose a distributed design of MIMO CR networks under global interference temperature constraints that is robust (in the worst-case sense) against SU-to-PU channel uncertainties. More specifically, we consider two alternative formulations that are complementary to each other in terms of signaling and system performance, namely: a game-theoretical design and a social-oriented optimization. To study and solve the proposed formulations we hinge on the new theory of finite-dimensional variational inequalities (VI) in the complex domain and a novel parallel decomposition technique for nonconvex sum-utility problems with coupling constraints, respectively. A major contribution of this paper is to devise a new class of distributed best-response algorithms with provable convergence. The algorithms differ in computational complexity, convergence speed, communication overhead, and achievable performance; they are thus applicable to a variety of CR scenarios, either cooperative or non-cooperative, which allow the SUs to explore the trade-off between signaling and performance.

In this paper, we propose a novel class of Nash problems for cognitive radio (CR) networks, modeled as Gaussian frequency-selective interference channels, wherein each secondary user (SU) competes against the others to maximize his own opportunistic throughput by choosing jointly the sensing duration, the detection thresholds, and the vector power allocation. The proposed general formulation allows us to accommodate several (transmit) power and (deterministic/probabilistic) interference constraints, such as constraints on the maximum individual and/or aggregate (probabilistic) interference tolerable at the primary receivers. To keep the optimization as decentralized as possible, global (coupling) interference constraints are imposed by penalizing each SU with a set of time-varying prices based upon his contribution to the total interference; the prices are thus additional variable to optimize. The resulting players' optimization problems are nonconvex; moreover, there are possibly price clearing conditions associated with the global constraints to be satisfied by the solution. All this makes the analysis of the proposed games a challenging task; none of classical results in the game theory literature can be successfully applied. The main contribution of this paper is to develop a novel optimization-based theory for studying the proposed nonconvex games; we provide a comprehensive analysis of the existence and uniqueness of a standard Nash equilibrium, devise alternative best-response based algorithms, and establish their convergence. Some of the proposed algorithms are totally distributed and asynchronous, whereas some others require limited signaling among the SUs (in the form of consensus algorithms) in favor of better performance; overall, they are thus applicable to a variety of CR scenarios, either cooperative or noncooperative, which allows the SUs to explore the existing tradeoff between signaling and performance.

In recent years, game-theoretic tools have been increasingly used to study many important resource allocation problems in communications and networking. One common feature shared by all these approaches is that, when it comes to (distributed) computation of equilibria, assumptions are always made that imply uniqueness of the Nash Equilibrium. This simplifies considerably the analysis of the games under investigation and permits to design distributed solution methods with convergence guarantee. However, requiring the uniqueness of the solution may be too demanding in many practical situations, thus strongly limiting the applicability of current game theoretical methodologies. In this paper, we overcome this limitation and propose novel distributed algorithms for noncooperative games having multiple solutions. The new methods, whose convergence analysis is based on variational inequality techniques, are able to select, among all the equilibria of a game, those which optimize a given performance criterion. We apply the developed methods to a power control problem over parallel Gaussian interference channels and show that they yield a considerable performance improvement over classical power control schemes.

The concept of cognitive radio has recently received great attention from the research community as a promising paradigm to achieve efficient use of the frequency resource by allowing the coexistence of primary and secondary users in the same bandwidth. In this paper, we propose a novel Nash equilibrium (NE) problem to model concurrent communications of cognitive secondary users who compete with each other to maximize their information rate, subject to constraints on the transmit power (and possibly spectral masks) as well as on per-carrier and total aggregate interference tolerable at the primary users' receivers. The coupling among the strategies of the players due to the interference constraints presents a new challenge for the analysis of this class of Nash games that cannot be addressed using the game theoretical models proposed in the literature. For this purpose, we need the framework given by the more advanced theory of finite-dimensional Variational Inequalities. This provides us with all the mathematical tools necessary to analyze the proposed NE problem (e.g., existence and uniqueness of the solution) and to devise alternative distributed algorithms along with their convergence properties.

Using imperfect channel state information (CSI) may cause severe violations of the interference restriction in cognitive radio (CR). We consider designing a robust CR system, over either SISO frequency-selective or MIMO channels, with multiple primary users (PUs) and multiple noncooperative secondary users (SUs), who form an ad-hoc network that is naturally modeled as a noncooperative game. The imperfectness of PU CSI is taken into account through the worst-case robustness philosophy. We study the existence and uniqueness properties of the Nash equilibria (NE) of the robust games, and devise distributed algorithms with their convergency properties to achieve the competitive optimality for the SU network. As special cases, our framework also provides, through convex optimization, the robust power allocation and precoding for each SU.

The observations gathered by the individual nodes of a sensor network may be unreliable due to malfunctioning, observation noise or low battery level. Global reliability is typically recovered by collecting all the measurements in a fusion center which takes proper decisions. However, centralized networks are more vulnerable and prone to congestion around the sink nodes. To relax the congestion problem, decrease the network vulnerability and improve the network efficiency, it is appropriate to bring the decisions at the lowest possible level. In this paper, we propose a distributed algorithm allowing each node to improve the reliability of its own reading thanks to the interaction with the other nodes, assuming that the field monitored by the network is a smooth function. In mathematical terms, this only requires that the useful field belongs to a subspace of dimension smaller than the number of nodes. Although fully decentralized, the proposed algorithm is globally optimal, in the sense that it performs the projection of the overall set of observations onto the signal subspace through an iterative decentralized algorithms, that requires minimum convergence time, for any given node coverage.

Achieving consensus on common global parameters through totally decentralized algorithms is a topic that has attracted considerable attention in the last few years, in view of its potential application in sensor networks. Several algorithms, along with their convergence properties, have been studied in the literature, among which the most popular are the (weighted) average consensus based schemes. One of the most critical aspects of these algorithms is that they suffer from catastrophic noise propagation. We show that the noise affecting the system state variables has a variance that grows linearly with the time index. In addition, we prove that encoding the information on the first forward difference of the state variables rather than on the state itself improves noise resilience, since it guarantees that the asymptotic value of the consensus is affected by noise with bounded variance. The results of our in-depth analysis of the effect of additive noise on consensus algorithms are valid regardless of the noise statistics and for arbitrary network topologies, i.e., arbitrary Laplacian matrices, and contain as special cases previously known results.

In this paper we focus on the maximization of the information rates subject to transmit power constraints for noncooperative multiple-input multiple-output (MIMO) systems, using the same physical resources, i.e., time, bandwidth and space. To derive decentralized solutions that do not require any cooperation among the systems, the optimization problem is formulated as a static noncooperative game. The analysis of the game for arbitrary MIMO interference channels is quite involved, since it requires the study of a set of nonlinear nondifferentiable matrix-valued equations, based on the MIMO waterfilling solution. To overcome this difficulty, we provide a new interpretation of the waterfilling operator, for the general MIMO multiuser case, as a matrix projection. This key result allows us to simplify the study of the game and to obtain sufficient conditions for both uniqueness of the Nash equilibrium (NE) and convergence of the proposed totally asynchronous distributed algorithms. The proposed approach provides a general framework that encompasses all previous works, mostly concerned with the particular case of SISO Gaussian frequency-selective interference channel.

This paper considers the noncooperative maximization of mutual information in the Gaussian interference channel in a fully distributed fashion via game theory. This problem has been studied in a number of papers during the past decade for the case of frequency-selective channels. A variety of conditions guaranteeing the uniqueness of the Nash Equilibrium (NE) and convergence of many different distributed algorithms have been derived. In this paper we provide a unified view of the state-of- the-art results, showing that most of the techniques proposed in the literature to study the game, even though apparently different, can be unified using our recent interpretation of the waterfilling operator as a projection onto a proper polyhedral set. Based on this interpretation, we then provide a mathematical framework, useful to derive a unified set of sufficient conditions guaranteeing the uniqueness of the NE and the global convergence of waterfilling based asynchronous distributed algorithms. The proposed mathematical framework is also instrumental to study the extension of the game to the more general MIMO case, for which only few results are available in the current literature. The resulting algorithm is, similarly to the frequency-selective case, an iterative asynchronous MIMO waterfilling algorithm. The proof of convergence hinges again on the interpretation of the MIMO waterfilling as a matrix projection, which is the natural generalization of our results obtained for the waterfilling mapping in the frequency-selective case.

This paper considers the minimization of transmit power in Gaussian parallel interference channels, subject to a rate constraint for each user. To derive decentralized solutions that do not require any cooperation among the users, we formulate this power control problem as a (generalized) Nash equilibrium (NE) game. We obtain sufficient conditions that guarantee the existence and nonemptiness of the solution set to our problem. Then, to compute the solutions of the game, we propose two distributed algorithms based on the single user water-filling solution: Thesequentialand thesimultaneousiterative water-filling algorithms, wherein the users update their own strategies sequentially and simultaneously, respectively. We derive a unified set of sufficient conditions that guarantee the uniqueness of the solution and global convergence of both algorithms. Our results are applicable to all practical distributed multipoint-to-multipoint interference systems, either wired or wireless, where a quality of service in (QoS) terms of information rate must be guaranteed for each link.

This paper considers the maximization of information rates for the Gaussian frequency-selective interference channel, subject to power and spectral mask constraints on each link. To derive decentralized solutions that do not require any cooperation among the users, the optimization problem is formulated as a static noncooperative game of complete information. To achieve the so-called Nash equilibria of the game, we propose a new distributed algorithm called asynchronous iterative water-filling algorithm. In this algorithm, the users update their power spectral density (PSD) in a completely distributed and asynchronous way: some users may update their power allocation more frequently than others and they may even use outdated measurements of the received interference. The proposed algorithm represents a unified framework that encompasses and generalizes all known iterative water-filling algorithms, e.g., sequential and simultaneous versions. The main result of the paper consists of a unified set of conditions that guarantee the global converge of the proposed algorithm to the (unique) Nash equilibrium of the game.

Achieving consensus on common global parameters through totally decentralized algorithms is a topic that has attracted considerable attention in the last few years. Several algorithms have been developed, among which the most popular is the average consensus method. The main advantage of these approaches is that they do not require a fusion center. But, on the other hand, they are typically based on iterative algorithms, whose energy consumption is proportional to the time necessary to achieve consensus. This time depends on the network topology, as well as on the transmit power of each node. In this paper, we show that there exists an optimal transmit power that minimizes the overall energy consumption necessary to achieve the global estimate within a given accuracy and that this power depends on the network topology.

This paper considers the competitive maximization of information rates in the Gaussian frequency-selective interference channel, subject to global power and spectral mask constraints. We focus on the practical case in which the transmission by the different users contains time and frequency synchronization offsets. We propose a unified framework based on a distributed algorithm called asynchronous iterative waterfilling algorithm. In this algorithm, the users update their power spectral density in a completely distributed and asynchronous way: some users may update their power allocation more frequently than others and they may even use outdated measurements of the received interference. Moreover the users are not required to know time and frequency offsets. Our main contribution is to provide a unified set of convergence conditions for the whole class of algorithms obtained from the asynchronous iterative waterfilling algorithm.

The mathematical models of populations of mutually coupled oscillators having self-synchronization capabilities are a powerful tool for designing sensor networks with high energy efficiency, fault tolerance and scalability. In this work, we derive the conditions for the existence the asymptotic stability of the equilibrium of a system capable to provide maximum likelihood estimates through only local coupling and without the need for a fusion center, provided that the whole network observes the same phenomenon. Interestingly, we show that the network global consensus capability is strictly related to the network topology. Finally we test the performance taking into account propagation delays and possible parameter fluctuations among the network nodes

The detection and localization of an event through a sensor network is a topic that has attracted considerable attention recently because of many potential applications. Typically, these decisions are taken by conveying the sensor measurements to a sink node that processes the data and provides an estimate. However, the presence of a sink node creates a bottleneck that is the cause of potential congestions and it poses problems of scalability. In this work, we propose a decentralized decision scheme that is capable to achieve optimal decisions without requiring a fusion center. The network is composed of a set of mutually coupled oscillators, where each node is coupled only to the nearest nodes. We show how to achieve optimal detection for both deterministic and random signals by properly selecting the parameters of the coupling mechanism. Furthermore, if the nodes know their own positions and the network is connected, we show how to make each node able to perform a totally distributed energy-based source localization

In this paper we propose a unified framework, based on the emergent potential games to deal with a variety of network resource allocation problems. We generalize the existing results on potential games to the cases where there exists coupling among the (possibly vector) strategies of all players. We derive sufficient conditions for the existence and uniqueness of the Nash equilibrium, and provide different distributed algorithms along their convergence properties. Using this new framework, we then show that many power control problems (standard and non-standard) with coupled constraints among the users, can be naturally formulated as potential games and, hence, efficiently solved. Finally, we point out an interesting interplay existing between potential games, classical optimization theory, and Lyapunov stability theory

The sequential iterative water-filling algorithm (IWFA) proposed by Yu et al. is by now a popular low-complexity algorithm to compute the Nash equilibrium point of the power allocation game in a Gaussian frequency-selective multiuser interference channel. The algorithm is based on a distributed sequential updating where, at each iteration, the users choose their power allocation, one after the other. However, this sequential updating strategy may slow down its convergence time excessively when the number of users is high. In this paper, we propose an alternative distributed algorithm, called simultaneous iterative water-filling algorithm (SIWFA), where at each iteration, all the users update their power allocations simultaneously, rather than sequentially. This reduces the convergence time considerably, specially when the number of users is large. Our main contribution is to provide a unified set of sufficient conditions for the convergence of both IWFA and SIWFA, that are less stringent than those known in the literature for IWFA. These conditions guarantee the convergence of both algorithms also in the presence of spectral mask constraints imposed on the power allocations of the users

Cooperation among mobile users (MUs) in a wireless network can be very useful to reduce the total radiated power necessary to insure the delivery of the information with the desired quality of service. A systematic framework for achieving such a gain consists in making the cooperating nodes act as the antennas of a virtual transmit array, operating according to a distributed space-time coding (DSTC) strategy. However, cooperation implies the allocation of dedicated resources, typically power and time slots, for the exchange of data between source and intermediate nodes (relays). It is then necessary to design the system properly to make possible a final net gain, taking into account all resources involved in the communication. In this paper, we consider regenerative relays and we analyze the effect of intermediate decision errors at the relay nodes. We derive the optimal maximum-likelihood (ML) detector, at the final destination, in case of binary phase-shift keying (BPSK) transmission, and a suboptimal scalar detector, whose bit-error rate (BER) is expressed in (approximate) closed form. Since with DSTC the transmit antennas are not colocated, we show how to allocate the power among source and relay terminals in order to minimize the average BER at the final destination. Finally, we compare alternative cooperation and decoding strategies.

Distributed space-time coding (DSTC) is a rather novel paradigm that merges ideas from space-time coding (STC) and multihop networks (MHN) to design a wireless network capable of improving the performance considerably with respect to single hop networks (SHN). The basic advantage of DSTC comes from allowing multiple nodes to share their antennas to create a virtual transmit array and then implement a distributed space-time coding technique over the virtual array. The major differences between DSTC and conventional STC are: (i) detection errors at the relay nodes; and (ii) possible lack of synchronization between source and relay nodes. In this work, we study these problems and compare different DSTC techniques based on decode and forward and amplify and forward strategies. Finally, we show the trade-off curves between rate and diversity gain for DSTC systems.

In this work we provide the optimal coding strategy for meshed wireless networks, where more links are active simultaneously, assuming as optimality criterion the rates of all the links. We formulate the rate maximization problem as a multi-objective optimization problem (MOP). Assuming a multi-carrier modulation for each user, we show how to allocate the power of each user optimally according to a centralized power distribution algorithm. We also propose a decentralized (suboptimal) but simpler algorithm, based on the idea of Nash equilibrium (NE). Finally, we compare the two strategies showing that the loss, in terms of information rate, of the decentralized strategy based on the iterative water-filling algorithm can be very small with respect to the optimal centralized solution, as the distance between the interfering links is just a few times the distance of each link, thus making the decentralized approach a viable solution.

Cooperation among mobile users in a wireless network can be exploited to induce diversity and/or rate gain, using distributed space-time coding. In this work we consider a distributed block Alamouti scheme, valid for frequency selective channels, where we take explicitly into account the errors in the source-relay link and we derive a closed form expression for the bit error rate in the simple case of BPSK transmission. Building on such derivations, we show how to allocate the power among source and relay terminals in order to minimize the average bit error rate. Since cooperation inevitably requires a proper allocation of resources between source and relay nodes, we show the final balance in terms of rate and diversity gain, incorporating the rate loss due to the exchange of information between source and relays.

We propose a multihop cellular network architecture which takes advantage of cooperation among users to induce a diversity gain. First, mobile terminals (MT), willing to cooperate, share their data during a time slot reserved to MT-to-MT links, and then, in a successive time slot, they send their data to the base station (BS) through a virtual array of antennas, constituted by the antennas of the cooperating users. We derive the coding strategy, for such a virtual array, that maximizes the sum of the rates from the MTs to the BS, under the constraint of a given total available power. We assume at the beginning that the channels from the MT to the BS are perfectly known. This allows us to derive, for each MT, a closed form expression for the optimal power allocation, as a function of frequency. Then, we remove this assumption and we use a first order perturbation analysis to compute the loss resulting from imperfect channel knowledge.

We propose a flexible method for designing space-time block codes capable of achieving the desired trade-off between diversity and coding gain. The proposed system is valid for frequency selective, block fading channels and refers to a block coding scheme capable of achieving full rate transmission, for any number of transmit antennas. We derive a closed form expression for the pairwise error probability and the maximum diversity and coding gain. These expressions are instrumental in designing a coding strategy able to yield the required trade-off between coding and diversity gain, in order to reach the desired average BER with the smallest SNR. Finally, we check our theoretical derivations with simulations and compare our approach with alternative ones.

In this work, we propose a concatenated space-time block coding scheme for transmissions of over block fading frequency selective channels, which guarantees maximum diversity gain and high coding gain, with affordable receiver complexity. We derive a closed form expression for the bound of the pairwise error probability, which is instrumental to devise the optimal coding strategy, and then we check out theoretical derivations with simulations and compare our approach with alternative ones.

It is well known that the optimal coding strategy, maximizing the mutual information under an average transmit power constraint and additive Gaussian noise, for single-input/single-output (SISO) transmission over a time-invariant, dispersive channel is water-filling. The extension to a multiple-input/single-output (MISO) channel can also be derived in a straightforward manner using a numerical approach. The aim of this work is to provide a closed form expression for the optimal coding and power/bit allocation for MISO channel, which has a direct interesting physical interpretation and it establishes a direct link between water-filling, beamforming and maximal ratio combining. We test then our theoretical findings with numerical results.

In this paper we consider a CDMA system equipped with multiple antenna transceivers to implement space-time block coding (STBC). The codes incorporate a cyclic prefix (CP), to facilitate channel equalization and simplify the rejection of multiuser interference (MUI) in broadband transmissions over frequency-selective channels. The only price paid for the introduction of CP is a rate reduction, depending on the relative length of the CP with respect to the code length. To limit, and possibly avoid, this loss, we propose a CDMA/STBC scheme using CP of length smaller than the channel. To prevent interblock interference which would require a sophisticated decoding procedure, we equip the receiver with a MIMO channel shortening filterbank. We derive the conditions under which we can achieve perfect shortening using an FIR filterbank. Finally, we show that the choice of a CP length represents a trade-off between the rate reduction factor and the SNR loss resulting from the insertion of the channel shortening filter.