Search

We address a large-scale and nonconvex optimization problem, involving an aggregative term. This term can be interpreted as the sum of the contributions of N agents to some common good, with N large. We investigate a relaxation of this problem, obtained by randomization. The relaxation gap is proved to converge to zeros as N goes to infinity, independently of the dimension of the aggregate. We propose a stochastic method to construct an approximate minimizer of the original problem, given an approximate solution of the randomized problem. McDiarmid's concentration inequality is used to quantify the probability of success of the method. We consider the Frank-Wolfe (FW) algorithm for the resolution of the randomized problem. Each iteration of the algorithm requires to solve a subproblem which can be decomposed into N independent optimization problems. A sublinear convergence rate is obtained for the FW algorithm. In order to handle the memory overflow problem possibly caused by the FW algorithm, we propose a stochastic Frank-Wolfe (SFW) algorithm, which ensures the convergence in both expectation and probability senses. Numerical experiments on a mixed-integer quadratic program illustrate the efficiency of the method., Comment: 33 pages, 3 figures

Graph Convolutional Networks (GCNs) have emerged as the state-of-the-art method for graph-based learning tasks. However, training GCNs at scale is still challenging, hindering both the exploration of more sophisticated GCN architectures and their applications to real-world large graphs. While it might be natural to consider graph partition and distributed training for tackling this challenge, this direction has only been slightly scratched the surface in the previous works due to the limitations of existing designs. In this work, we first analyze why distributed GCN training is ineffective and identify the underlying cause to be the excessive number of boundary nodes of each partitioned subgraph, which easily explodes the memory and communication costs for GCN training. Furthermore, we propose a simple yet effective method dubbed BNS-GCN that adopts random Boundary-Node-Sampling to enable efficient and scalable distributed GCN training. Experiments and ablation studies consistently validate the effectiveness of BNS-GCN, e.g., boosting the throughput by up to 16.2x and reducing the memory usage by up to 58%, while maintaining a full-graph accuracy. Furthermore, both theoretical and empirical analysis show that BNS-GCN enjoys a better convergence than existing sampling-based methods. We believe that our BNS-GCN has opened up a new paradigm for enabling GCN training at scale. The code is available at https://github.com/RICE-EIC/BNS-GCN., Comment: MLSys 2022

Graph Convolutional Networks (GCNs) is the state-of-the-art method for learning graph-structured data, and training large-scale GCNs requires distributed training across multiple accelerators such that each accelerator is able to hold a partitioned subgraph. However, distributed GCN training incurs prohibitive overhead of communicating node features and feature gradients among partitions for every GCN layer during each training iteration, limiting the achievable training efficiency and model scalability. To this end, we propose PipeGCN, a simple yet effective scheme that hides the communication overhead by pipelining inter-partition communication with intra-partition computation. It is non-trivial to pipeline for efficient GCN training, as communicated node features/gradients will become stale and thus can harm the convergence, negating the pipeline benefit. Notably, little is known regarding the convergence rate of GCN training with both stale features and stale feature gradients. This work not only provides a theoretical convergence analysis but also finds the convergence rate of PipeGCN to be close to that of the vanilla distributed GCN training without any staleness. Furthermore, we develop a smoothing method to further improve PipeGCN's convergence. Extensive experiments show that PipeGCN can largely boost the training throughput (1.7x~28.5x) while achieving the same accuracy as its vanilla counterpart and existing full-graph training methods. The code is available at https://github.com/RICE-EIC/PipeGCN., Comment: ICLR 2022

Vision transformers (ViTs) have recently set off a new wave in neural architecture design thanks to their record-breaking performance in various vision tasks. In parallel, to fulfill the goal of deploying ViTs into real-world vision applications, their robustness against potential malicious attacks has gained increasing attention. In particular, recent works show that ViTs are more robust against adversarial attacks as compared with convolutional neural networks (CNNs), and conjecture that this is because ViTs focus more on capturing global interactions among different input/feature patches, leading to their improved robustness to local perturbations imposed by adversarial attacks. In this work, we ask an intriguing question: "Under what kinds of perturbations do ViTs become more vulnerable learners compared to CNNs?" Driven by this question, we first conduct a comprehensive experiment regarding the robustness of both ViTs and CNNs under various existing adversarial attacks to understand the underlying reason favoring their robustness. Based on the drawn insights, we then propose a dedicated attack framework, dubbed Patch-Fool, that fools the self-attention mechanism by attacking its basic component (i.e., a single patch) with a series of attention-aware optimization techniques. Interestingly, our Patch-Fool framework shows for the first time that ViTs are not necessarily more robust than CNNs against adversarial perturbations. In particular, we find that ViTs are more vulnerable learners compared with CNNs against our Patch-Fool attack which is consistent across extensive experiments, and the observations from Sparse/Mild Patch-Fool, two variants of Patch-Fool, indicate an intriguing insight that the perturbation density and strength on each patch seem to be the key factors that influence the robustness ranking between ViTs and CNNs., Comment: Accepted at ICLR 2022

This paper addresses an optimal control problem for a large population of identical plug-in electric vehicles (PEVs). The number of PEVs being large, the mean field assumption is formulated to describe the evolution of the PEVs population and its interaction with the central planner. The resulting problem of optimal control of partial differential equations (PDEs) is discretized. Using convex analysis tools, we show the existence of an optimal solution and the convergence of the Chambolle-Pock algorithm to a solution. The implementation of this optimal control to the finite population of PEVs is detailed and we illustrate our approach with two numerical examples.

An important issue in today's electricity markets is the management of flexibilities offered by new practices, such as smart home appliances or electric vehicles. By inducing changes in the behavior of residential electric utilities, demand response (DR) seeks to adjust the demand of power to the supply for increased grid stability and better integration of renewable energies. A key role in DR is played by emergent independent entities called load aggregators (LAs). We develop a new decentralized algorithm to solve a convex relaxation of the classical Alternative Current Optimal Power Flow (ACOPF) problem, which relies on local information only. Each computational step can be performed in an entirely privacy-preserving manner, and system-wide coordination is achieved via node-specific distribution locational marginal prices (DLMPs). We demonstrate the efficiency of our approach on a 15-bus radial distribution network., Comment: 8 pages, 3 figures; submitted for publication

Chemical bonding in 2D layered materials and van der Waals solids is central to understanding and harnessing their unique electronic, magnetic, optical, thermal and superconducting properties. Here we report the discovery of spontaneous, bidirectional, bilayer twisting (twist angle ~ 4.5{\deg}) in the metallic kagom\'e MgCo6Ge6 at T = 100(2) K via X-ray diffraction measure-ments, enabled by the preparation of single crystals by the Laser Bridgman method. Despite the appearance of static twisting on cooling from T ~ 300 K to 100 K, no evidence for a phase transition was found in physical properties measurements. Combined with the presence of an Einstein phonon mode contribution in the specific heat, this implies that the twisting exists at all temperatures but is thermally fluctuating at room temperature. Crystal Orbital Hamilton Population analysis demonstrates that the cooperative twisting between layers stabilizes the Co-kagom\'e network when coupled to strongly bonded and rigid (Ge2) dimers that connect adjacent layers. Further modelling of the displacive disorder in the crystal structure shows the presence of second, Mg-deficient, stacking sequence. This alternative stacking sequence also exhibits inter-layer twisting, but with a different pattern, consistent with the change in electron count due to removal of Mg. Magnetization, resistivity, and low-temperature specific heat measurements are all consistent with a Pauli paramagnetic, strongly correlated metal. Our results provide crucial insight into how chemical concepts lead to interesting electronic structures and behaviors in layered materials.

This paper shows the existence of $\mathcal{O}(\frac{1}{n^\gamma})$-Nash equilibria in $n$-player noncooperative sum-aggregative games in which the players' cost functions, depending only on their own action and the average of all players' actions, are lower semicontinuous in the former while $\gamma$-H\"{o}lder continuous in the latter. Neither the action sets nor the cost functions need to be convex. For an important class of sum-aggregative games, which includes congestion games with $\gamma$ equal to 1, a gradient-proximal algorithm is used to construct $\mathcal{O}(\frac{1}{n})$-Nash equilibria with at most $\mathcal{O}(n^3)$ iterations. These results are applied to a numerical example concerning the demand-side management of an electricity system. The asymptotic performance of the algorithm when $n$ tends to infinity is illustrated., Comment: 28 pages,2 figures

Aggregative games have many industrial applications, and computing an equilibrium in those games is challenging when the number of players is large. In the framework of atomic aggregative games with coupling constraints, we show that variational Nash equilibria of a large aggregative game can be approximated by a Wardrop equilibrium of an auxiliary population game of smaller dimension. Each population of this auxiliary game corresponds to a group of atomic players of the initial large game. This approach enables an efficient computation of an approximated equilibrium, as the variational inequality characterizing the Wardrop equilibrium is of smaller dimension than the initial one. This is illustrated on an example in the smart grid context., Comment: arXiv admin note: substantial text overlap with arXiv:1810.01436

Circadian rhythms influence multiple essential biological activities including sleep, performance, and mood. The dim light melatonin onset (DLMO) is the gold standard for measuring human circadian phase (i.e., timing). The collection of DLMO is expensive and time-consuming since multiple saliva or blood samples are required overnight in special conditions, and the samples must then be assayed for melatonin. Recently, several computational approaches have been designed for estimating DLMO. These methods collect daily sampled data (e.g., sleep onset/offset times) or frequently sampled data (e.g., light exposure/skin temperature/physical activity collected every minute) to train learning models for estimating DLMO. One limitation of these studies is that they only leverage one time-scale data. We propose a two-step framework for estimating DLMO using data from both time scales. The first step summarizes data from before the current day, while the second step combines this summary with frequently sampled data of the current day. We evaluate three moving average models that input sleep timing data as the first step and use recurrent neural network models as the second step. The results using data from 207 undergraduates show that our two-step model with two time-scale features has statistically significantly lower root-mean-square errors than models that use either daily sampled data or frequently sampled data., Comment: 16 pages, 6 figures, 4 tables, ACM Transactions on Computing for Healthcare

We define and analyze the notion of variational Wardrop equilibrium for nonatomic aggregative games with an infinity of players types. These equilibria are characterized through an infinite-dimensional variational inequality. We show, under monotonicity conditions, a convergence theorem enables to approximate such an equilibrium with arbitrary precision. To this end, we introduce a sequence of nonatomic games with a finite number of players types, which approximates the initial game. We show the existence of a symmetric Wardrop equilibrium in each of these games. We prove that those symmetric equilibria converge to an equilibrium of the infinite game, and that they can be computed as solutions of finite-dimensional variational inequalities. The model is illustrated through an example from smart grids: the description of a large population of electricity consumers by a parametric distribution gives a nonatomic game with an infinity of different players types, with actions subject to coupling constraints., Comment: arXiv admin note: substantial text overlap with arXiv:1806.06230

We consider a network of prosumers involved in peer-to-peer energy exchanges, with differentiation price preferences on the trades with their neighbors, and we analyze two market designs: (i) a centralized market, used as a benchmark, where a global market operator optimizes the flows (trades) between the nodes, local demand and flexibility activation to maximize the system overall social welfare; (ii) a distributed peer-to-peer market design where prosumers in local energy communities optimize selfishly their trades, demand, and flexibility activation. We first characterizethe solution of the peer-to-peer market as a Variational Equilibrium and prove that the set of Variational Equilibria coincides with the set of social welfare optimal solutions of market design (i). We give several results that help understanding the structure of the trades at an equilibriumor at the optimum. We characterize the impact of preferences on the network line congestion and renewable energy waste under both designs. We provide a reduced example for which we give the set of all possible generalized equilibria, which enables to give an approximation of the price ofanarchy. We provide a more realistic example which relies on the IEEE 14-bus network, for which we can simulate the trades under different preference prices. Our analysis shows in particular that the preferences have a large impact on the structure of the trades, but that one equilibrium(variational) is optimal.

Computing an equilibrium in congestion games can be challenging when the number of players is large. Yet, it is a problem to be addressed in practice, for instance to forecast the state of the system and be able to control it. In this work, we analyze the case of generalized atomic congestion games, with coupling constraints, and with players that are heterogeneous through their action sets and their utility functions. We obtain an approximation of the variational Nash equilibria---a notion generalizing Nash equilibria in the presence of coupling constraints---of a large atomic congestion game by an equilibrium of an auxiliary population game, where each population corresponds to a group of atomic players of the initial game. Because the variational inequalities characterizing the equilibrium of the auxiliary game have smaller dimension than the original problem, this approach enables the fast computation of an estimation of equilibria in a large congestion game with thousands of heterogeneous players., Comment: 12 pages, 3 figures