Mobile edge computing (MEC) is a promising solution for enhancing user experience, minimizing content delivery expenses, and reducing backhaul traffic. This paper presents a game-theoretic framework to address the edge resource crowdsourcing problem, where mobile edge devices (MEDs) provide idle storage for content caching in exchange for rewards from a content provider (CP). We model the interaction between the CP and MEDs as a Stackelberg game, with the CP as the leader setting the reward structure and the MEDs as followers competing in a non-cooperative game for these rewards. We propose a novel privacy-preserving method to derive the Stackelberg equilibrium of the game. Notably, our algorithm is designed to operate effectively in time-varying communication networks, addressing the high mobility inherent in MEC environments. This contrasts with state-of-the-art algorithms, which assume a static communication network among MEDs–an impractical condition that does not account for the mobility of MEDs during algorithm execution. Specifically, our approach employs consensus-based algorithms to compute the Nash equilibrium (NE) for MEDs, with MEDs exchanging NE profile estimates with neighbors via row-stochastic mixing matrices and performing gradient steps to optimize their utility in a fully decentralized manner. Based on the computed NE strategies, we propose a zeroth-order reward search algorithm for the CP to determine the optimal strategy for profit maximization. Our comprehensive analysis details the properties of the equilibrium and establishes the geometric convergence of the proposed algorithms to the NE. We also derive explicit bounds for the stepsizes based on the game's properties and the graphs' connectivity structure. Extensive numerical results validate the efficacy of our proposed approach.

In this correspondence, we correct the following points in the above paper.

We study gradient methods for optimizing $(L_0, L_1)$-smooth functions, a class that generalizes Lipschitz-smooth functions and has gained attention for its relevance in machine learning. We provide new insights into the structure of this function class and develop a principled framework for analyzing optimization methods in this setting. While our convergence rate estimates recover existing results for minimizing the gradient norm in nonconvex problems, our approach significantly improves the best-known complexity bounds for convex objectives. Moreover, we show that the gradient method with Polyak stepsizes and the normalized gradient method achieve nearly the same complexity guarantees as methods that rely on explicit knowledge of $(L_0, L_1)$. Finally, we demonstrate that a carefully designed accelerated gradient method can be applied to $(L_0, L_1)$-smooth functions, further improving all previous results.

Cyber–physical multiagent systems are driving rapid technological advancements that automate a wide range of critical functions, thereby enabling safer, more accessible, and more efficient autonomous operations across diverse sectors. We refer to the capability of such systems to self-organize and coordinate toward accomplishing shared objectives as autonomy. The unique characteristics of these systems prompt a reevaluation of their security concepts, including their vulnerabilities, and mechanisms to mitigate these vulnerabilities. This survey article examines how advancements in wireless networking, coupled with sensing and computing capabilities, can foster novel security concepts for autonomous cyber–physical systems (CPSs). It delves into three main themes related to securing multiagent CPSs. First, we discuss the threats that are particularly relevant to multiagent CPSs, given the potential lack of trustworthiness between agents. Second, we present prospects for sensing, contextual awareness, and authentication, enabling the inference and measurement of a form of interagent “quantitative trust” or “cy-trust” for these systems. Third, we elaborate on the application of quantifiable trust notions to enable “resilient coordination,” where “resilient” signifies sustained functionality amid attacks on multiagent CPSs. This survey unveils the cyber–physical character of future interconnected systems as a pivotal catalyst for realizing robust autonomy.

Variational Inequality (VI) problems have attracted great interest in the machine learning (ML) community due to their application in adversarial and multi-agent training. Despite its relevance in ML, the oft-used strong-monotonicity and Lipschitz continuity assumptions on VI problems are restrictive and do not hold in many machine learning problems. To address this, we relax smoothness and monotonicity assumptions and study structured non-monotone generalized smoothness. The key idea of our results is in adaptive stepsizes. We prove the first-known convergence results for solving generalized smooth VIs for the three popular methods, namely, projection, Korpelevich, and Popov methods. Our convergence rate results for generalized smooth VIs match or improve existing results on smooth VIs. We present numerical experiments that support our theoretical guarantees and highlight the efficiency of proposed adaptive stepsizes.

Mobile edge computing (MEC) is a promising solution for enhancing the user experience, minimizing content delivery expenses, and reducing backhaul traffic. In this paper, we propose a novel privacy-preserving decentralized game-theoretic framework for resource crowdsourcing in MEC. Our framework models the interactions between a content provider (CP) and multiple mobile edge device users (MEDs) as a non-cooperative game, in which MEDs offer idle storage resources for content caching in exchange for rewards. We introduce efficient decentralized gradient play algorithms for Nash equilibrium (NE) computation by exchanging local information among neighboring MEDs only, thus preventing attackers from learning users' private information. The key challenge in designing such algorithms is that communication among MEDs is not fixed and is facilitated by a sequence of undirected time-varying graphs. Our approach achieves linear convergence to the NE without imposing any assumptions on the values of parameters in the local objective functions, such as requiring strong monotonicity to be stronger than its dependence on other MEDs' actions, which is commonly required in existing literature when the graph is directed time-varying. Extensive simulations demonstrate the effectiveness of our approach in achieving efficient resource outsourcing decisions while preserving the privacy of the edge devices.

This work considers the problem of resilient consensus, where stochastic values of trust between agents are available. Specifically, we derive a unified mathematical framework to characterize convergence, deviation of the consensus from the true consensus value, and expected convergence rate, when there exists additional information of trust between agents. We show that under certain conditions on the stochastic trust values and consensus protocol: First, almost sure convergence to a common limit value is possible even when malicious agents constitute more than half of the network connectivity; second, the deviation of the converged limit, from the case where there is no attack, i.e., the true consensus value, can be bounded with probability that approaches 1 exponentially; and third correct classification of malicious and legitimate agents can be attained in finite time almost surely. Furthermore, the expected convergence rate decays exponentially as a function of the quality of the trust observations between agents.

The problem of estimating the support of a distribution is of great importance in many areas of machine learning, computer science and molecular biology. Almost all of the existing work in this area has used perfectly accurate sampling assumptions, which is seldom true in practice. Here we introduce the first known theoretical approach to support estimation in the presence of sampling artifacts, where each sample is assumed to be observed through a Poisson channel that simultaneously captures repetitions and deletions. The proposed estimator is based on regularized weighted Chebyshev approximations, with weights governed by evaluations of Touchard (Bell) polynomials. The supports in the presence of sampling artifacts are calculated via discretized semi-infinite programming methods. The newly proposed estimation approach is tested on synthetic and textual data, as well as on GISAID data for the purpose of estimating the mutational diversity of genes in the SARS-Cov-2 viral genome. For all experiments performed, we observed significant improvements of our integrated method compared to adequately modified known noiseless support estimation methods. A full version of this paper is accessible at: https://arxiv.org/pdf/2006.07999.pdf

We consider the problem of recovering a complex vector x ∈ ℂnfrom m quadratic measurements {〈Aix, x〉}i=1m. This problem, known as quadratic feasibility, encompasses the well known phase retrieval problem and has applications in a wide range of important areas including power system state estimation and x-ray crystallography. In general, not only is the the quadratic feasibility problem NP-hard to solve, but it may in fact be unidentifiable. In this paper, we establish conditions under which this problem becomes identifiable, and further prove isometry properties in the case when the matrices {Ai}i=1mare Hermitian matrices sampled from a complex Gaussian distribution. Moreover, we explore a nonconvex optimization formulation of this problem, and establish salient features of the associated optimization landscape that enables gradient algorithms with an arbitrary initialization to converge to a globally optimal point with a high probability. Our results also reveal sample complexity requirements for successfully identifying a feasible solution in these contexts.

This special issue provides a comprehensive overview of modern optimization tools and methods for the purposes of data-driven learning and control.

Decentralized optimization to minimize a finite sum of functions, distributed over a network of nodes, has been a significant area within control and signal-processing research due to its natural relevance to optimal control and signal estimation problems. More recently, the emergence of sophisticated computing and large-scale data science needs have led to a resurgence of activity in this area. In this article, we discuss decentralized first-order gradient methods, which have found tremendous success in control, signal processing, and machine learning problems, where such methods, due to their simplicity, serve as the first method of choice for many complex inference and training tasks. In particular, we provide a general framework of decentralized first-order methods that is applicable to directed and undirected communication networks alike and show that much of the existing work on optimization and consensus can be related explicitly to this framework. We further extend the discussion to decentralized stochastic first-order methods that rely on stochastic gradients at each node and describe how local variance reduction schemes, previously shown to have promise in the centralized settings, are able to improve the performance of decentralized methods when combined with what is known as gradient tracking. We motivate and demonstrate the effectiveness of the corresponding methods in the context of machine learning and signal-processing problems that arise in decentralized environments.

We describe a distributed framework for resource sharing problems that arise in communications, micro-economics, and various networking applications. In particular, we consider a hierarchical multi-layer decomposition for network utility maximization (ML-NUM), where functionalities are assigned to different layers. The proposed methodology creates solutions with central management and distributed computations to the resource allocation problems. In non-stationary environments, the technique aims to respond quickly to the dynamics of the network by decreasing delay by partially shifting the communication and computational burden to the network edges. Our main contribution is a detailed analysis under the assumption that the network changes are on the same time-scale as the convergence time of the algorithms used for local computations. Moreover, assuming strong concavity and smoothness of the users' objective functions, and under some stability conditions for each layer, we present convergence rates and optimality bounds for the ML-NUM framework. In addition, the main benefits of the proposed method are demonstrated with numerical examples.

In this paper, we consider the problem of solving a distributed (consensus-based) optimization problem in a network that contains regular and malicious nodes (agents). The regular nodes are performing a distributed iterative algorithm to solve their associated optimization problem, while the malicious nodes inject false data with a goal to steer the iterates to a point that serves their own interest. The problem consists of detecting and isolating the malicious agents, thus allowing the regular nodes to solve their optimization problem. We propose a method to dwarf data injection attacks on distributed optimization algorithms, which is based on the idea that the malicious nodes (individually or in collaboration) tend to give themselves away when broadcasting messages with the intention to drive the consensus value away from the optimal point for the regular nodes in the network. In particular, we provide a new gradient-based metric to detect the neighbors that are likely to be malicious. We also provide some simulation results demonstrating the performance of the proposed approach.

This paper studies the security aspect of gossip-based decentralized optimization algorithms for multi agent systems against data injection attacks. Our contributions are two-fold. First, we show that the popular distributed projected gradient method (by Nedić et al.) can be attacked bycoordinated insiderattacks, in which the attackers are able to steer the final state to a point of their choosing. Second, we propose a metric that can be computed locally by the trustworthy agents processing their own iterates and those of their neighboring agents. This metric can be used by the trustworthy agents to detect and localize the attackers. We conclude the paper by supporting our findings with numerical experiments.

We study the decentralized distributed computation of discrete approximations for the regularized Wasserstein barycenter of a finite set of continuous probability measures distributedly stored over a network. We assume there is a network of agents/machines/computers, and each agent holds a private continuous probability measure and seeks to compute the barycenter of all the measures in the network by getting samples from its local measure and exchanging information with its neighbors. Motivated by this problem, we develop, and analyze, a novel accelerated primal-dual stochastic gradient method for general stochastic convex optimization problems with linear equality constraints. Then, we apply this method to the decen- tralized distributed optimization setting to obtain a new algorithm for the distributed semi-discrete regularized Wasserstein barycenter problem. Moreover, we show explicit non-asymptotic complexity for the proposed algorithm. Finally, we show the effectiveness of our method on the distributed computation of the regularized Wasserstein barycenter of univariate Gaussian and von Mises distributions, as well as some applications to image aggregation.

In decentralized optimization, nodes cooperate to minimize an overall objective function that is the sum (or average) of per-node private objective functions. Algorithms interleave local computations with communication among all or a subset of the nodes. Motivated by a variety of applications..decentralized estimation in sensor networks, fitting models to massive data sets, and decentralized control of multirobot systems, to name a few..significant advances have been made toward the development of robust, practical algorithms with theoretical performance guarantees. This paper presents an overview of recent work in this area. In general, rates of convergence depend not only on the number of nodes involved and the desired level of accuracy, but also on the structure and nature of the network over which nodes communicate (e.g., whether links are directed or undirected, static or time varying). We survey the state-of-theart algorithms and their analyses tailored to these different scenarios, highlighting the role of the network topology.

The problem of least squares regression of a d-dimensional unknown parameter is considered. A stochastic gradient descent based algorithm with weighted iterate-averaging that uses a single pass over the data is studied and its convergence rate is analyzed. We first consider a bounded constraint set of the unknown parameter. Under some standard regularity assumptions, we provide an explicit O(1/k) upper bound on the convergence rate, depending on the variance (due to the additive noise in the measurements) and the size of the constraint set. We show that the variance term dominates the error and decreases with rate 1 /k, while the constraint set term decreases with rate log k/k2. We then compare the asymptotic ratio ρ between the convergence rate of the proposed scheme and the empirical risk minimizer (ERM) as the number of iterations approaches infinity. We show that ρ ≤ 4 under some mild conditions for all d ≥ 1. We further improve the upper bound by showing that ρ ≤ 4/3 for the case of d =1 and unbounded parameter set. Simulation results demonstrate strong performance of the algorithm as compared to existing methods, and coincide with ρ ≤ 4/3 even for large d in practice.

We consider distributed optimization over orthogonal collision channels in spatial multi-channel ALOHA networks. Users are spatially distributed and each user is in the interference range of a few other users. Each user is allowed to transmit over a subset of the shared channels with a certain attempt probability. We study both the non-cooperative and cooperative settings. In the former, the goal of each user is to maximize its own rate irrespective of the utilities of other users. In the latter, the goal is to achieve proportionally fair rates among users. We develop simple distributed learning algorithms to solve these problems. The efficiencies of the proposed algorithms are demonstrated via both theoretical analysis and simulation results.

LP relaxations of Maximum Weighted Independent Set (MWIS) problems have been widely studied. A key motivation for this prior work comes from the central role that MWIS plays in designing throughput-optimal algorithms for wireless networks. However, to the best of our knowledge, the actual packet delay performance of these algorithms has not been studied in the context of wireless networks. In this paper, we first present an algorithm for solving the LP relaxation of MWIS which exhibits faster convergence to an optimal solution. Further, we show that one does not have to wait for infinite time for convergence to occur, but a simple rounding technique can be used to identify the ON/OFF states of the wireless links in finite time. As in prior work, such an approach only identifies the optimal MWIS states of some of the links in the network. Therefore, we present a scheme to combine this solution with Q-CSMA. Simulations indicate that the proposed scheme significantly improves the performance of Q-CSMA. Further, the proposed algorithm is shown to perform much better than previously suggested LP relaxation schemes due to its superior convergence properties.

We describe a novel extension of subspace codes for noncoherent networks, suitable for use when the network is viewed as a communication system that introduces both dimension and symbol errors. We show that when symbol erasures occur in a significantly large number of different basis vectors transmitted through the network and when the min-cut of the network is much smaller than the length of the transmitted codewords, the new family of codes outperforms their subspace code counterparts. For the proposed coding scheme, termed hybrid network coding, we derive two upper bounds on the size of the codes. These bounds represent a variation of the Singleton and of the sphere-packing bound. We show that a simple concatenated scheme that consists of subspace codes and Reed-Solomon codes is asymptotically optimal with respect to the Singleton bound. Finally, we describe two efficient decoding algorithms for concatenated subspace codes that in certain cases have smaller complexity than their subspace decoder counterparts.

We consider constrained minimization of a sum of convex functions over a convex and compact set, when each component function is known only to a specific agent in a time-varying peer to peer network. We study an iterative optimization algorithm in which each agent obtains a weighted average of its own iterate with the iterates of its neighbors, updates the average using the subgradient of its local function and then projects onto the constraint set to generate the new iterate. We obtain error bounds on the limit of the function value when a constant stepsize is used.

We consider the uplink power control problem where mobile users in different cells are communicating with their base stations. We formulate the power control problem as the minimization of a sum of convex functions. Each component function depends on the channel coefficients from all the mobile users to a specific base station and is assumed to be known only to that base station (only CSIR). We then view the power control problem as a distributed optimization problem that is to be solved by the base stations and propose convergent, distributed and iterative power control algorithms. These algorithms require each base station to communicate with the base stations in its neighboring cells in each iteration and are hence non-autonomous. Since the base stations are connected through a wired backbone the communication overhead is not an issue. The convergence of the algorithms is shown theoretically and also verified through numerical simulations.

All opportunistic scheduling algorithms solve simpler optimization problems at each scheduling instance in order to achieve good long-term performance. The analysis of these algorithms assumes that the simpler optimization problems are solved exactly. However, in contrast, real-life implementations only approximately solve these problems but still yield close to optimal performance. We formalize this observation by explicitly bounding the longterm performance in terms of the error in the approximation made at every stage.