More Like this

1. Stability of a Subcritical Fluid Model for Fair Bandwidth Sharing with General File Size Distributions

   https://doi.org/10.1287/stsy.2019.0058  

   Fu, Yingjia ; Williams, Ruth J. ( September 2020 , Stochastic Systems)

   null (Ed.)

   This work concerns the asymptotic behavior of solutions to a (strictly) subcritical fluid model for a data communication network, where file sizes are generally distributed and the network operates under a fair bandwidth-sharing policy. Here we consider fair bandwidth-sharing policies that are a slight generalization of the [Formula: see text]-fair policies introduced by Mo and Walrand [Mo J, Walrand J (2000) Fair end-to-end window-based congestion control. IEEE/ACM Trans. Networks 8(5):556–567.]. Since the year 2000, it has been a standing problem to prove stability of the data communications network model of Massoulié and Roberts [Massoulié L, Roberts J (2000) Bandwidth sharing and admission control for elastic traffic. Telecommunication Systems 15(1):185–201.], with general file sizes and operating under fair bandwidth sharing policies, when the offered load is less than capacity (subcritical conditions). A crucial step in an approach to this problem is to prove stability of subcritical fluid model solutions. In 2012, Paganini et al. [Paganini F, Tang A, Ferragut A, Andrew LLH (2012) Network stability under alpha fair bandwidth allocation with general file size distribution. IEEE Trans. Automatic Control 57(3):579–591.] introduced a Lyapunov function for this purpose and gave an argument, assuming that fluid model solutions are sufficiently smooth in time and space that they are strong solutions of a partial differential equation and assuming that no fluid level on any route touches zero before all route levels reach zero. The aim of the current paper is to prove stability of the subcritical fluid model without these strong assumptions. Starting with a slight generalization of the Lyapunov function proposed by Paganini et al., assuming that each component of the initial state of a measure-valued fluid model solution, as well as the file size distributions, have no atoms and have finite first moments, we prove absolute continuity in time of the composition of the Lyapunov function with any subcritical fluid model solution and describe the associated density. We use this to prove that the Lyapunov function composed with such a subcritical fluid model solution converges to zero as time goes to infinity. This implies that each component of the measure-valued fluid model solution converges vaguely on [Formula: see text] to the zero measure as time goes to infinity. Under the further assumption that the file size distributions have finite pth moments for some p > 1 and that each component of the initial state of the fluid model solution has finite pth moment, it is proved that the fluid model solution reaches the measure with all components equal to the zero measure in finite time and that the time to reach this zero state has a uniform bound for all fluid model solutions having a uniform bound on the initial total mass and the pth moment of each component of the initial state. In contrast to the analysis of Paganini et al., we do not need their strong smoothness assumptions on fluid model solutions and we rigorously treat the realistic, but singular situation, where the fluid level on some routes becomes zero, whereas other route levels remain positive. 

   more » « less
2. Estimating the Region of Attraction Using Polynomial Optimization: A Converse Lyapunov Result

   https://doi.org/978-1-5090-2872-6/17  

   Jones, M. ; Mohammadi, H. ; Peet, M. ( December 2017 , Proceedings of the IEEE Conference on Decision & Control)

   In this paper, we propose an iterative method for using SOS programming to estimate the region of attraction of a polynomial vector field, the conjectured convergence of which necessitates the existence of polynomial Lyapunov functions whose sublevel sets approximate the true region of attraction arbitrarily well. The main technical result of the paper is the proof of existence of such a Lyapunov function. Specifically, we usetheHausdorffdistancemetrictoanalyzeconvergenceandin the main theorem demonstrate that the existence of an n-times continuously differentiable maximal Lyapunov function implies that for any ε >0, there exists a polynomial Lyapunov function and associated sub-level set which together prove stability of a set which is within ε Hausdorff distance of the true region of attraction. The proposed iterative method and probably convergence is illustrated with a numerical example. 

   more » « less
3. Structured Neural-PI Control with End-to-End Stability and Output Tracking Guarantees

   Wenqi Cui, Yan Jiang ( December 2023 , Advances in Neural Information Processing Systems 36 (NeurIPS 2023))

   A. Oh and T. Neumann and A. Globerson and K. Saenko and M. Hardt and S. Levine (Ed.)

   We study the optimal control of multiple-input and multiple-output dynamical systems via the design of neural network-based controllers with stability and output tracking guarantees. While neural network-based nonlinear controllers have shown superior performance in various applications, their lack of provable guarantees has restricted their adoption in high-stake real-world applications. This paper bridges the gap between neural network-based controllers and the need for stabilization guarantees. Using equilibrium-independent passivity, a property present in a wide range of physical systems, we propose neural Proportional-Integral (PI) controllers that have provable guarantees of stability and zero steady-state output tracking error. The key structure is the strict monotonicity on proportional and integral terms, which is parameterized as gradients of strictly convex neural networks (SCNN). We construct SCNN with tunable softplus-β activations, which yields universal approximation capability and is also useful in incorporating communication constraints. In addition, the SCNNs serve as Lyapunov functions, giving us end-to-end performance guarantees. Experiments on traffic and power networks demonstrate that the proposed approach improves both transient and steady-state performances, while unstructured neural networks lead to unstable behaviors. 

   more » « less
4. Approximation of compositional functions with ReLU neural networks

   Gong, Q. ; Kang, W. ; Fahroo, F. ( May 2023 , Systems control letters)

   The power of DNN has been successfully demonstrated on a wide variety of high-dimensional problems that cannot be solved by conventional control design methods. These successes also uncover some fundamental and pressing challenges in understanding the representability of deep neural networks for complex and high dimensional input–output relations. Towards the goal of understanding these fundamental questions, we applied an algebraic framework developed in our previous work to analyze ReLU neural network approximation of compositional functions. We prove that for Lipschitz continuous functions, ReLU neural networks have an approximation error upper bound that is a polynomial of the network’s complexity and the compositional features. If the compositional features do not increase exponentially with dimension, which is the case in many applications, the complexity of DNN has a polynomial growth. In addition to function approximations, we also establish ReLU network approximation results for the trajectories of control systems, and for a Lyapunov function that characterizes the domain of attraction. 

   more » « less
5. GraphCache: Message Passing as Caching for Sentence-Level Relation Extraction

   https://doi.org/10.18653/v1/2022.findings-naacl.128  

   Wang, Yiwei ; Chen, Muhao ; Zhou, Wenxuan ; Cai, Yujun ; Liang, Yuxuan ; Hooi, Bryan ( January 2022 , Findings of the Association for Computational Linguistics: NAACL 2022)

   Entity types and textual context are essential properties for sentence-level relation extraction (RE). Existing work only encodes these properties within individual instances, which limits the performance of RE given the insufficient features in a single sentence. In contrast, we model these properties from the whole dataset and use the dataset-level information to enrich the semantics of every instance. We propose the GraphCache (Graph Neural Network as Caching) module, that propagates the features across sentences to learn better representations for RE. GraphCache aggregates the features from sentences in the whole dataset to learn global representations of properties, and use them to augment the local features within individual sentences. The global property features act as dataset-level prior knowledge for RE, and a complement to the sentence-level features. Inspired by the classical caching technique in computer systems, we develop GraphCache to update the property representations in an online manner. Overall, GraphCache yields significant effectiveness gains on RE and enables efficient message passing across all sentences in the dataset. 

   more » « less