Electrical and Electronic Engineering - Research Publications
Permanent URI for this collection
Search Results
1 - 7 of 7
-
ItemAn Information Analysis of Iterative Algorithms for Network Utility Maximization and Strategic Games(IEEE, 2019)A variety of resource allocation problems on networked systems, for example, those in cyber-physical systems or Internet-of-things applications, require distributed solution methods. Modern distributed algorithms usually require bandwidth-limited digital communication between the system and its users, who are often modeled as independent decision makers with individual preferences. This paper presents a quantitative information flow and knowledge gain analysis of decentralized iterative algorithms with bounded trajectories in the context of convex network utility maximization problems and strategic games with a unique Nash equilibrium solution. First, a novel generic framework is introduced to quantify knowledge gain in network resource allocation problems using entropy by taking into account priors in the solution space. Second, a general result is presented on the interplay between quantization of information and distributed algorithm performance both for linear and sublinear convergence. Third, information flow in distributed algorithms is studied and a lower bound is derived on the total amount of information exchanged for convergence under uniform quantization. The well-known primal-dual decomposition algorithm is used as an example to illustrate the results. Finally, convergence guarantees for distributed algorithms with estimation are investigated. This paper establishes specific links between information concepts and iterative algorithms in addition to building a foundation for integrating learning schemes into distributed optimization.
-
ItemLower Bounds on the Best-Case Complexity of Solving a Class of Non-cooperative Games(Elsevier, 2016)This paper studies the complexity of solving the class G of all N-player non-cooperative games with continuous action spaces that admit at least one Nash equilibrium (NE). We consider a distributed Nash seeking setting where agents communicate with a set of system nodes (SNs), over noisy communication channels, to obtain the required information for updating their actions. The complexity of solving games in the class G is defined as the minimum number of iterations required to find a NE of any game in G with ε accuracy. Using information-theoretic inequalities, we derive a lower bound on the complexity of solving the game class G that depends on the Kolmogorov 2ε-capacity of the constraint set and the total capacity of the communication channels. We also derive a lower bound on the complexity of solving games in G which depends on the volume and surface area of the constraint set.
-
ItemSample Complexity of Solving Non-Cooperative Games(Institute of Electrical and Electronics Engineers, 2020-02-01)This paper studies the complexity of solving two classes of non-cooperative games in a distributed manner, in which the players communicate with a set of system nodes over noisy communication channels. The complexity of solving each game class is defined as the minimum number of iterations required to find a Nash equilibrium (NE) of any game in that class with ∈ accuracy. First, we consider the class G of all N-player non-cooperative games with a continuous action space that admit at least one NE. Using information-theoretic inequalities, a lower bound on the complexity of solving G is derived which depends on the Kolmogorov 2∈-capacity of the constraint set and the total capacity of the communication channels. Our results indicate that the game class G can be solved at most exponentially fast. We next consider the class of all N-player non-cooperative games with at least one NE such that the players' utility functions satisfy a certain (differential) constraint. We derive lower bounds on the complexity of solving this game class under both Gaussian and non-Gaussian noise models. Finally, we derive upper and lower bounds on the sample complexity of a class of quadratic games. It is shown that the complexity of solving this game class scales according to Θ (1/∈ 2 ) where € is the accuracy parameter.
-
ItemOPTIMAL INFINITE HORIZON CONTROL UNDER A LOW DATA RATE 2(Elsevier BV, 2006)
-
ItemA DATA-RATE LIMITED VIEW OF ADAPTIVE CONTROL(Elsevier BV, 2006)
-
ItemFinite horizon LQ optimal control and computation with data rate constraints(IEEE - Institute of Electrical and Electronic Engineers, 2005)
-
ItemFeedback control under data rate constraints: An overview(INSTITUTE OF ELECTRICAL ELECTRONICS ENGINEERS (IEEE), 2007)The emerging area of control with limited data rates incorporates ideas from both control and information theory. The data rate constraint introduces quantization into the feedback loop and gives the interconnected system a two-fold nature, continuous and symbolic. In this paper, we review the results available in the literature on data-rate-limited control. For linear systems, we show how fundamental tradeoffs between the data rate and control goals, such as stability, mean entry times, and asymptotic state norms, emerge naturally. While many classical tools from both control and information theory can still be used in this context, it turns out that the deepest results necessitate a novel, integrated view of both disciplines.