 
Last updated on October 10, 2017. This conference program is tentative and subject to change
Technical Program for Wednesday October 4, 2017

WeA1 
Library 
Distributed Storage I 
Invited Session 
Chair: Mohajer, Soheil  Univ. of Minnesota 
CoChair: Duursma, Iwan  Univ. of Illinois 
Organizer: Duursma, Iwan  Univ. of Illinois 
Organizer: Mohajer, Soheil  Univ. of Minnesota 

08:3008:50, Paper WeA1.1  
Efficient Data Access in Hybrid Cloud Storage (I) 
Samy, Islam  Univ. of Arizona 
Koyluoglu, Onur Ozan  Univ. of California Berkeley 
Rawat, Ankit Singh  Massachusetts Inst. of Tech 
Keywords: Data Storage, Coding Techniques and Applications, Coding Theory
Abstract: Hybrid cloud is a widely adopted framework where onpremise storage and/or compute resources are combined with public cloud system. This paper explores the storage aspect of this framework, which requires designing coding schemes that are aware of both local and global components of the available storage space. The coding schemes should provide efficient repair mechanisms for the data stored on the public cloud (global storage space) and utilize the local storage space to facilitate seamless access to the overall information stored on the hybrid cloud storage. This paper presents a mathematical model for hybrid cloud storage which takes all these requirements into account. The paper then extends the information flow graph approach to characterize the fundamental limits on access bandwidth of the system, i.e., the amount of data downloaded from the public cloud during the data reconstruction process. This paper also presents several explicit coding schemes that utilize the available local storage space to attain the fundamental limit on the access bandwidth. The setup where multiple clients with varying local storage spaces are supported by a single global storage space is also addressed.


08:5009:10, Paper WeA1.2  
Correcting Bursty and Localized Deletions Using Guess & Check Codes (I) 
Kas Hanna, Serge  Rutgers Univ 
El Rouayheb, Salim  Rutgers Univ 
Keywords: Coding Theory, Information Theory
Abstract: We consider the problem of constructing binary codes for correcting deletions that are localized within a certain part of the codeword that is unknown a priori. The model that we study is when delta leq w deletions occur in a window of size at most w bits. These delta deletions are not necessarily consecutive, but are restricted to a window of size w. The localized deletions model is a generalization of the bursty model, where all the deleted bits are consecutive. In this work we propose new explicit codes, based on the family of Guess & Check codes~cite{GC,GCisit2017}, that can correct, with high probability, delta leq w deletions that are localized within a window of size at most w=mathcal{O}(log k), where k is the length of the information message. These codes have deterministic polynomial time encoding and decoding schemes. The redundancy of these codes is clog k+w+1, where c is a constant representing a code parameter.


09:1009:30, Paper WeA1.3  
On the Service Capacity Region of Accessing Erasure Coded Content (I) 
Aktas, Mehmet Fatih  Rutgers Univ 
Anderson, Sarah  Univ. of St. Thomas 
Johnston, Ann  Penn State 
Joshi, Gauri  Carnegie Mellon Univ 
Kadhe, Swanand  Texas A&M Univ 
Matthews, Gretchen  Clemson 
Mayer, Carolyn  Univ. of NebraskaLincoln 
Soljanin, Emina  Rutgers Univ 
Keywords: Data Storage, Performance Analysis, Distributed and LargeScale Systems
Abstract: Cloud storage systems generally add redundancy in storing content files such that K files are replicated or erasure coded and stored on N > K nodes. In addition to providing reliability against failures, the redundant copies can be used to serve a larger volume of content access requests. A request for one of the files can be either be sent to a systematic node, or one of the repair groups. In this paper, we seek to maximize the service capacity region, that is, the set of request arrival rates for the K files that can be supported by a coded storage system. We explore two aspects of this problem: 1) for a given erasure code, how to optimally split incoming requests between systematic nodes and repair groups, and 2) choosing an underlying erasure code that maximizes the achievable service capacity region. In particular, we consider MDS and Simplex codes. Our analysis demonstrates that erasure coding makes the system more robust to skews in file popularity than simply replicating a file at multiple servers, and that coding and replication together can make the capacity region larger than either alone.


09:3009:50, Paper WeA1.4  
Universal Weakly Secure Minimum Storage Regenerating Codes for Distributed Storage (I) 
Kadhe, Swanand  Texas A&M Univ. 
Sprintson, Alex  Texas A&M Univ. 

09:5010:10, Paper WeA1.5  
Fundamental Limits of Dynamic Partial Sums: An Information Theoretic Perspective (I) 
Tian, Chao  Texas A&M Univ. 
Liu, Tie  Texas A&M Univ. 
Shen, Cong  Univ. of Science and Tech. of China 

WeA2 
Solarium 
Stochastic Analysis 
Regular Session 
Chair: Wang, Weina  Univ. of Illinois at UrbanaChampaign 

08:3008:50, Paper WeA2.1  
Fundamental Limits of Universal VariableToFixed Length Coding of Parametric Sources 
Iri, Nematollah  Arizona State Univ 
Kosut, Oliver  Arizona State Univ 
Keywords: Information Theory, Information Theory and Statistics
Abstract: Universal variabletofixed (VF) length coding of ddimensional exponential family of distributions is considered. An achievable scheme is proposed, which consists of a dictionary to parse the source output stream. The previouslyintroduced notion of quantized type is employed for the dictionary construction. The quantized type class of a sequence is based on partitioning the space of minimal sufficient statistics into cuboids. The proposed dictionary consists of sequences in the boundaries of transition from low to high quantized type class size. Asymptotics of the epsiloncoding rate of the proposed coding scheme for large enough dictionaries is derived. In particular, we show that the thirdorder coding rate of the proposed scheme is Hfrac{d}{2}frac{loglog M}{log M}, where H is the entropy of the source and M is the dictionary size. We further provide a converse, showing that this rate is optimal up to the thirdorder term.


08:5009:10, Paper WeA2.2  
DataDriven Distributed Optimization Using Wasserstein Ambiguity Sets 
Cherukuri, Ashish  ETH Zurich 
Cortes, Jorge  Univ. of California San Diego 
Keywords: Optimization, Learning and Inference, Distributed and LargeScale Systems
Abstract: This paper considers a general class of stochastic optimization problem for multiagent systems. We assume that the probability distribution of the uncertain parameters is unknown to the agents and instead, each agent gathers a certain number of samples of it. The objective for the agents is to cooperatively find, using the available data, a solution that has performance guarantees for the stochastic problem. To this end, we formulate a datadriven distributionally robust optimization (DRO) problem using Wasserstein ambiguity sets that has the desired performance guarantees. With the aim of solving this optimization in a distributed manner, we identify a convexconcave modified Lagrangian function whose saddle points are in correspondence with the optimizers of the DRO problem. We then design our distributed algorithm as the gradient descent in the convex variable and gradient ascent in the concave variable of this Lagrangian function. Our convergence analysis shows that the trajectories of this dynamics converge asymptotically to an optimizer of the DRO problem. Simulations illustrate our results.


09:1009:30, Paper WeA2.3  
Load Balancing in Hypergraphs 
Delgosha, Payam  Univ. of California, Berkeley 
Anantharam, Venkat  Univ. of California, Berkeley 
Keywords: Information Theory and Statistics, Data Storage, Coding Techniques and Applications
Abstract: We study the load balancing problem in networks. A task is viewed as a hyperedge in a hypergraph having access to the resources represented by its endpoints. For simplicity, we consider the case where each hyperedge represents one unit of load which should be distributed among its endpoints. An allocation is a way of distributing this load. The overall cost of an allocation is evaluated as the separable sum of a convex function of the total load at each resource. It is known that an allocation is optimal if it is balanced in the sense that no demand desires to change its allocation. Further, it is known that the net load faced by each resource is the same in any balanced allocation. We analyze the properties of the empirical distribution of the loads faced by the resources in balanced allocations for a sequence of hypergraphs as their size goes to infinity. In the special case of unimodular hypergraph GaltonWatson processes, we characterize the asymptotic empirical load distribution at a typical resource via a fixed point equation. Moreover, we are able to characterize the asymptotics of the maximum load at a resource under some additional conditions.


09:3009:50, Paper WeA2.4  
The Primal versus the Dual Ising Model 
Molkaraie, Mehdi  ETHZ 
Keywords: Learning and Inference, Information Theory and Statistics
Abstract: We represent the Ising model by normal factor graphs in the primal and in the dual domains. By analogy with Kirchhoff's voltage and current laws, we show that in the primal normal factor graphs, the dependency among the variables is along the cycles, whereas in the dual normal factor graphs, the dependency is on the cutsets. In the primal (resp. dual) domain, dependent variables can be computed via their fundamental cycles (resp. fundamental cutsets). In both domains, we propose a uniform sampling algorithm to estimate the partition function. For the homogeneous Ising model on a twodimensional torus, we use Onsager's closed form solution to illustrate the opposite behavior of the estimator in the primal and in the dual domains.


09:5010:10, Paper WeA2.5  
On the Spectral Norms of PseudoWigner and Related Matrices 
Soloveychik, Ilya  Harvard Univ 
Tarokh, Vahid  Harvard Univ 
Keywords: Information Theory and Statistics
Abstract: We investigate the spectral norms of symmetric N by N matrices from two pseudorandom ensembles. The first is the pseudoWigner ensemble introduced in ``PseudoWigner Matrices'' by Soloveychik, Xiang and Tarokh and the second is its Sample Covariancetype analog defined in this work. Both ensembles are defined through the concept of rindependence by controlling the amount of randomness in the underlying matrices, and can be constructed from dual BCH codes. We show that when the measure of randomness r grows as N^k, where k lies between (0,1] and c > 0, the norm of the matrices is almost surely within o((log^{1+c} N)/(N^{min[k,2/3]})) distance from 1. Numerical simulations verifying the obtained results are provided.


WeA3 
Butternut 
Wireless Communication and Sensor Networks 
Regular Session 
Chair: Magner, Abram  Univ. of Illinois 

08:3008:50, Paper WeA3.1  
IntegerForcing Architectures for Uplink Cloud Radio Access Networks 
El Bakoury, Islam  Boston Univ 
Nazer, Bobak  Boston Univ 
Keywords: Wireless Communication Systems, Information Theoretic Approaches in Wireless Communications, Optimization
Abstract: Consider an uplink cloud radio access network where users are observed simultaneously by several base stations, each with a ratelimited link to a central processor that wishes to decode all transmitted messages. Recent efforts have demonstrated the advantages of compressionbased strategies that send quantized channel observations to the central processor, rather than attempt local decoding. We propose an endtoend integerforcing framework for compressionbased uplink cloud radio access. For the important special case where the users have no channel state information and communicate at symmetric rates, we demonstrate via simulations that our framework is competitive with stateoftheart WynerZivbased strategies. In particular, our framework offers similar performance with lower implementation complexity.


08:5009:10, Paper WeA3.2  
Physical Layer Deep Learning of Encodings for the MIMO Fading Channel 
O'Shea, Timothy  Virginia Tech 
Erpek, Tugba  Virginia Tech 
Clancy, Charles  Virginia Tech 
Keywords: Learning and Inference, Machine Learning and Learning Theory, Wireless Communication Systems
Abstract: We introduce a novel physical layer scheme for Multiple Input Multiple Output (MIMO) communications based on unsupervised deep learning using an autoencoder. This method extends prior work on the joint optimization of physical layer representation and encoding and decoding processes as a single endtoend task by expanding the transmitter and receiver to the multiantenna case. We introduce a domain appropriate wireless channel impairment model (the multiinput multioutput Rayleigh fading channel), into the autoencoder optimization problem in order to directly learn a system which optimizes for it. This approach demonstrates significant potential for learning schemes which achieve and exceed performance of current day methods which are widely used in existing wireless MIMO systems. We discuss how the scheme can be easily adapted for openloop and closedloop operation in spatial multiplexing modes as well as spatial diversity modes. Each of these modes is learned and realized using the same simple and compact approach.


09:1009:30, Paper WeA3.3  
Joint UplinkDownlink Cell Associations for Interference Networks with Local Connectivity 
Singhal, Manik  Purdue Univ 
El Gamal, Aly  Purdue Univ 
Keywords: Information Theoretic Approaches in Wireless Communications, Wireless Communication Systems, Network Information Theory
Abstract: We study information theoretic models of interference networks that consist of K Base Station (BS)  Mobile Terminal (MT) pairs. Each BS is connected to the MT carrying the same index as well as L following MTs, where the connectivity parameter L >= 1. We fix the value of L and study large networks as K goes to infinity. We assume that each MT can be associated with N BSs, and these associations are determined by a cloudbased controller that has a global view of the network. An MT has to be associated with a BS, in order for the BS to transmit its message in the downlink, or decode its message in the uplink. In previous work, the cell associations that maximize the average uplinkdownlink per user degrees of freedom (puDoF) were identified for the case when L=1. Further, when only the downlink is considered, the problem was settled for all values of L when we are restricted to use only zeroforcing interference cancellation schemes. In this work, we first propose puDoF inner bounds for arbitrary values of L when only the uplink is considered, and characterize the uplink puDoF value when only zeroforcing schemes are allowed and N >= L/2. We then introduce new achievable average uplinkdownlink puDoF, and conjecture that the new scheme is optimal for all values of L, when we restrict our attention to zeroforcing schemes.


09:3009:50, Paper WeA3.4  
HalfDuplex Routing Is NPHard 
Ezzeldin, Yahya  Univ. of California, Los Angeles (UCLA) 
Cardone, Martina  Univ. of California, Los Angeles (UCLA) 
Fragouli, Christina  UCLA 
Tuninetti, Daniela  Univ. of Illinois at Chicago 
Keywords: Wireless Communication Systems, Network Information Theory, Information Theoretic Approaches in Wireless Communications
Abstract: Routing is a widespread approach to transfer information from a source node to a destination node in many deployed wireless adhoc networks. Today’s implemented routing algorithms seek to efficiently find the path/route with the largest FullDuplex (FD) capacity, which is given by the minimum among the pointtopoint link capacities in the path. Such an approach may be suboptimal if then the nodes in the selected path are operated in HalfDuplex (HD) mode. Recently, the capacity (up to a constant gap that only depends on the number of nodes in the path) of an HD line network (i.e., a path) has been shown to be equal to half of the minimum of the harmonic means of the capacities of two consecutive links in the path. This paper asks the question of whether it is possible to design a polynomialtime algorithm that efficiently finds the path with the largest HD capacity in a relay network. The problem of finding such a path is shown to be NPhard in general. However, if the number of cycles in the network is polynomial in the number of nodes, then a polynomialtime algorithm can indeed be designed.


09:5010:10, Paper WeA3.5  
The MultipleAccess Collision Channel without Feedback: Capacity Region and a Mutual Information Game 
Vasconcelos, Marcos  Univ. of Southern California 
Mitra, Urbashi  Univ. of Southern California 
Keywords: Wireless Communication Systems, Optimization, Information Theoretic Approaches in Wireless Communications
Abstract: This paper revisits the collision channel without feedback by reformulating it as a deterministic multipleaccess channel. The capacity region of this channel is computed for different cardinalities of the input alphabets, and it is shown that: for alphabets with small cardinalities, the users exploit the action of transmitting vs. not transmitting to communicate at rates on the boundary of the capacity region; and as the alphabet cardinalities increase, the timesharing lower bound approaches the boundary of the capacity region. A noncooperative mutual information game is also considered and the existence of a unique Nashequilibrium solution is established.


WeA4 
Pine 
Information Theory and Networks 
Regular Session 
Chair: Perlaza, Samir  Princeton Univ 

08:3008:50, Paper WeA4.1  
TwoTransmitter TwoReceiver Channel with Confidential Messages 
ZivariFard, Hassan  Univ. of Texas at Dallas 
Bloch, Matthieu  Georgia Inst. of Tech 
Nosratinia, Aria  Univ. of Texas at Dallas 
Keywords: Network Information Theory, Information Theory, Reliability, Security and Trust
Abstract: We study the twotransmitter tworeceiver channel with confidential messages channel under a secrecy constraint, exploring the effect of a single eavesdropper on the secure communication rate. A general achievable secrecy rate region and an outer bound are derived for the degraded version of this channel. An example is provided in which the inner and outer bound meet. For the general nondegraded channel, another outer bound is derived and a special case is highlighted in which the inner and outer bound meet. Our inner bound recovers the known inner bounds for the multipleaccess wiretap channel, broadcast channel with confidential messages, and the compound MAC channel.


08:5009:10, Paper WeA4.2  
Simultaneous Information and Energy Transmission in Gaussian Interference Channels with Feedback 
Khalfet, Nizar  INRIA 
Perlaza, Samir  INRIA and Princeton Univ 
Keywords: Network Information Theory
Abstract: In this paper, the fundamental limits of simultaneous information and energy transmission in the twouser Gaussian interference channel with feedback are fully characterized. More specifically, an achievable and converse region in terms of information and energy transmission rates (in bits per channel use and energyunits per channel use, respectively) are presented. The achievable region is obtained using a combination of rate splitting, common randomness, superposition coding, powersplitting, and block Markov decoding. Finally, the converse region is obtained using some of the existing outer bounds on the information transmission rates, as well as a new outer bound on the energy transmission rate.


09:1009:30, Paper WeA4.3  
On AlphaDecodability and AlphaLikelihood Decoder 
Liu, Jingbo  Princeton Univ 
Cuff, Paul  Princeton Univ 
Verdú, Sergio  Princeton Univ 
Keywords: Information Theory, Information Theory and Statistics, Coding Techniques and Applications
Abstract: Generalizing the maximum and the average error criteria for channel coding, we introduce the alphadecodability, defined as the alphanorm of the probabilities of correctly decoding the messages. Several aspects, such as the exponent, the existence of a strong Fano’s inequality, and the achievability of the channel capacity by random coding are investigated, and it is revealed that alpha=0 (corresponding to the geometric average of the probabilities) emerges as the critical value for several properties. In the same vein of interpolating the maximum and the average, we also revisit the alphalikelihood decoder, which outputs a message with probability proportional to the its likelihood to the power alpha. For any code, up to a factor of 2, we show that the average error probability of the 1likelihood decoder is optimal, and that the error probability of the 0likelihood decoder coincides with the zero undetected error probability. This provides a unified approach to the (conventional) channel coding and the zero undetected error coding, and strengthens previous results on the error exponents of the likelihood decoder with simpler proofs. We also establish a connection between the parameter alpha in the likelihood decoder and the parameter rho in Gallager’s random coding exponent.


09:3009:50, Paper WeA4.4  
Capacity of a TwoWay Function Multicast Channel 
Shin, Seiyun  ETRI 
Suh, Changho  KAIST 
Keywords: Network Information Theory, Network Coding, Information Theoretic Approaches in Wireless Communications
Abstract: We explore the role of interaction for the problem of reliable computation over twoway multicast networks. Specifically we consider a fournode network in which two nodes wish to compute a modulosum of two independent Bernoulli sources generated from the other two, and a similar task is done in the other direction. The main contribution of this work lies in the characterization of the computation capacity region for a deterministic model of the network via a novel transmission scheme. One consequence of this result is that not only we can get an interaction gain over the oneway nonfeedback computation capacities, we can sometime get all the way to perfectfeedback computation capacities simultaneously in both directions. This result draws a parallel with the recent result developed in the context of twoway interference channels.


09:5010:10, Paper WeA4.5  
The Effect of Removing a Network Communication Edge: Group Network Codes 
Wei, Fei  SUNY at Buffalo 
Langberg, Michael  SUNY at Buffalo 
Keywords: Network Information Theory, Information Theory, Coding Theory
Abstract: The edge removal problem quantifies the loss in rate when removing an edge from a given network. In this work, we study the edge removal problem on network coding instances that are solvable using group network codes. We show that removing any edge of capacity R_e from a given network reduces the rate vector achievable by abelian group network codes by at most an additive R_e. Our work extends previous results of similar nature on linear network codes which are a special case of group network codes. The extent to which the achievable rate is affected by removing an R_e capacity edge, in the presence of general network coding functions, is yet to be quantified.


WeA5 
Lower Level 
Mathematical Challenges in Electric Power System 
Invited Session 
Chair: Bose, Subhonmesh  Univ. of Illinois at Urbana Champaign 
CoChair: DominguezGarcia, Alejandro  Univ. of Illinois at UrbanaChampaign 
Organizer: DominguezGarcia, Alejandro  Univ. of Illinois at UrbanaChampaign 
Organizer: Bose, Subhonmesh  Univ. of Illinois at Urbana Champaign 

08:3008:50, Paper WeA5.1  
Calculating and Calibrating a Persistence Measure for Use in Monitoring Power System Vulnerability (I) 
Lesieutre, Bernard  Univ. of Wisconsin 
Roy, Sandip  Washington State Univ 
Keywords: Complex Networked Systems, Data Analytics
Abstract: Widearea monitoring using phasor measurement units (PMUs) offers the possibility of detecting conditions during which the power system may be vulnerable to destabilizing events. Such events are often characterized by undamped oscillations and are preceded by conditions of very low damping. Current techniques for estimating damping from low SNR ambient data are less accurate than desired, although fairly accurate for estimating frequencies of oscillation. We introduce a robust “persistence measure” that can be used in lieu of damping estimates to assess conditions for vulnerability to dynamic instability. The measure relies on the calculation of the energies of normalized sample autocorrelations of select signals. In this paper we focus on the technical details associated with spectral smoothing and temporal isolation in the calculation of the normalized autocorrelations, to permit effective calibration of the metric for both stable and unstable systems. An example is provided using measurements from the field.


08:5009:10, Paper WeA5.2  
The Impact of Load Models in an Algorithm for Improving Voltage Stability Via Demand Response (I) 
Yao, Mengqi  Univ. of Michigan 
Molzahn, Daniel K.  Argonne National Lab 
Mathieu, Johanna L.  Univ. of Michigan 
Keywords: Optimization
Abstract: Increasing communication and control capabilities will allow future power system operators to exploit large quantities of responsive demand. This paper discusses ongoing work that employs demand response to improve voltage stability via virtual spatial shifting of loads (i.e., altering the locational distribution of power consumption in one time period with an energy payback in a following time period). In this paper, we study the impact of load models on a previously proposed iterative linearization algorithm to determine loading patterns that maximize a voltage stability margin, namely, the smallest singular value (SSV) of the power flow Jacobian matrix. Specifically, we extend the algorithm to enable inclusion of composite load models consisting of both "ZIP" components and a steadystate squirrelcage induction machine (IM) model. We then investigate the impact of different load models on both the stability margin and the loading pattern. Using the IEEE 14bus system as an illustrative example, the results show that the type of load model affects the nominal system's SSV, the optimal SSV, and the optimal loading pattern. The maximumachievable percent change in SSV is larger using IM models than using ZIP models. We also discuss the difficulty in interpreting the stability margin when the system undergoes structural changes resulting from the use of different voltagedependent load models.


09:1009:30, Paper WeA5.3  
NetworkCognizant Model Reduction of GridTied ThreePhase Inverters (I) 
Purba, Victor  Univ. of Minnesota  Twin Cities 
Jafarpour, Saber  Univ. of California Santa Barbara 
Johnson, Brian B.  National Renewable Energy Lab 
Bullo, Francesco  UCSB 
Dhople, Sairaj  Univ. of Minnesota 
Keywords: Complex Networked Systems, Robust and Nonlinear Control, Distributed and LargeScale Systems
Abstract: Powerelectronics inverters are expected to satisfy a significant fraction of system load in nextgeneration power networks with the growing integration of renewable resources and flexible loads. Typical dynamical models for gridtied inverters are nonlinear and composed of a large number of states; therefore it is impractical to study systems with many inverters when their full dynamics are retained. In our previous work, we have shown that a system of parallelconnected gridtied threephase inverters can be modeled as one aggregated inverter unit with the same structure and statespace dimension as any individual inverter in the system. Here, we extend this result to networks with arbitrary topologies by leveraging a classical aggregation method for coherent synchronous generators in transmission networks, and a linear approximation of the AC powerflow equations to ease computational burden. Numerical simulation results for a prototypical distribution feeder demonstrate the accuracy and computational benefits of the approach.


09:3009:50, Paper WeA5.4  
Dynamic Matching for Distributed Energy Resources (I) 
Qin, Junjie  Stanford Univ. 
Mather, Jonathan  UC Berkeley 
Rajagopal, Ram  Stanford 
Poolla, Kameshwar  UC Berkeley 
Varaiya, Varaiya  Univ. of California, Berkeley 

09:5010:10, Paper WeA5.5  
Distributed Flow Balancing Over Unreliable Communication Links (I) 
Rikos, Apostolos I.  Univ. of Cyprus 
Hadjicostis, Christoforos  Univ. of Cyprus 
Keywords: Distributed and LargeScale Systems
Abstract: We consider the distributed flowbalancing problem in networks of nodes that are interconnected via directed edges, each of which admits a positive flow within a certain interval, captured by lower and upper limits. A digraph with positive flows on its (directed) edges is flowbalanced if, for each node, the sum of the flows of the incoming edges equals the sum of the flows of the outgoing edges. We develop a distributed flow balancing algorithm in which each node is in charge of updating the flows on its outgoing edges based on certain values it maintains and updates, using corresponding information available from its immediate in and outneighbors. We assume that communication between neighboring nodes is bidirectional, but unreliable in that it may result in possible packet drops, independently between different communication links and link directions. We show that, even when communication links drop packets occasionally (but not always), the proposed algorithm allows nodes to reach flow balancing, with probability one, in an asymptotic fashion, as long as the necessary and sufficient circulation conditions on the lower and upper edge flow limits are satisfied. We also provide examples to illustrate the operation and performance of the proposed algorithm.


10:1010:30, Paper WeA5.6  
Killing Death Spiral Softly with a Small Connection Charge (I) 
Sun, Tao  Shanghai Jiao Tong Univ 
Tong, Lang  Cornell Univ 
Keywords: Complex Networked Systems, Decentralized Control Systems, Optimization
Abstract: The death spiral hypothesis points to the possibility that, with increasing integration of behindthemeter renewables, the revenue of a regulated utility declines, which forces the utility to increase the price of electricity to maintain revenue adequacy. This in turn drives more consumers to adopt renewable technology, which further erodes the financial standing of the utility. We analyze the interactions between a regulated utility who sets the retail tariff and its priceelastic customers whose decisions to adopt renewable technology are influenced by the retail tariff and the cost of the technology. We establish conditions for the existence of death spiral and the stable diffusion of renewable technologies. We show in particular that linear tariffs always induce death spiral when the fixed operating cost of the utility rises beyond a certain threshold. For twopart tariffs with connection and volumetric charges, the Ramsey pricing that optimizes myopically social welfare subject to the revenue adequacy constraint induces a stable equilibrium. The Ramsey pricing, however, inhibits renewable adoption with a high connection charge. In contrast, a twopart tariff with a small connection charge results in a stable adoption process with a higher level of renewable adoption and greater longterm social welfare. Market data are used to illustrate various solar adoption scenarios.


WeB1 
Library 
Density Estimation and Property Testing 
Invited Session 
Chair: Oh, Sewoong  UIUC 
CoChair: Viswanath, Pramod  Univ. of Illinois 
Organizer: Oh, Sewoong  UIUC 
Organizer: Viswanath, Pramod  Univ. of Illinois 

10:3010:50, Paper WeB1.1  
Estimating Density Functionals (I) 
Poczos, Barnabas  Carnegie Mellon Univ. 

10:5011:10, Paper WeB1.2  
Three Approaches for Optimal Property Estimation (I) 
Jiao, Jiantao  Stanford Univ. 
Han, Yanjun  Stanford Univ. 
Weissman, Tsachy  Stanford 

11:1011:30, Paper WeB1.3  
Ensemble Estimation of Distributional Functionals Via KNearest Neighbors (I) 
Moon, Kevin Randall  Yale Univ. 
Sricharan, Kumar  Palo Alto Res. Center 
Hero, Alfred  Univ. of Michigan 

11:3011:50, Paper WeB1.4  
Disentangled Representations Via Synergy Minimization (I) 
Ver Steeg, Greg  Univ. of Southern California 
Brekelmans, Rob  Univ. of Southern California 
Harutyunyan, Hrayr  Yerevan State Univ 
Galstyan, Aram  Univ. of Southern California 
Keywords: Machine Learning and Learning Theory, Computational Models and Representations
Abstract: Scientists often seek simplified representations of complex systems to facilitate prediction and understanding. If the factors comprising a representation allow us to make accurate predictions about our system, but obscuring any subset of the factors destroys our ability to make predictions, we say that the representation exhibits informational synergy. We argue that synergy is an undesirable feature in learned representations and that explicitly minimizing synergy can help disentangle the true factors of variation underlying data. We explore different ways of quantifying synergy, deriving new closedform expressions in some cases, and then show how to modify learning to produce representations that are minimally synergistic. We introduce a benchmark task to disentangle separate characters from images of words. We demonstrate that Minimally Synergistic (MinSyn) representations correctly disentangle characters while methods relying on statistical independence fail.


11:5012:10, Paper WeB1.5  
A Unified Estimator for (all?) Symmetric Distribution Properties (I) 
Acharya, Jayadev  Cornell Univ. 
Das, Hirakendu  Univ. of CaliforniaSan Diego 
Orlitsky, Alon  UCSD 
Suresh, Ananda Theertha  Univ. of CaliforniaSan Diego 

12:1012:30, Paper WeB1.6  
Optimal Distribution Testing Via Reductions (I) 
Diakonikolas, Ilias  Univ. of Southern California 

WeB2 
Solarium 
Networks Learning and Algorithms II 
Invited Session 
Chair: Stolyar, Alexander  Univ. of Illinois 
Organizer: Hajek, Bruce  Univ. of Illinois 
Organizer: Srikant, R  Univ. of Illinois 

10:3010:50, Paper WeB2.1  
An Improved Bound for Coflow Scheduling in Datacenter Networks (I) 
Ghaderi, Javad  Columbia Univ. 
Shafiee, Mehrnoosh  Columbia Univ. 

10:5011:10, Paper WeB2.2  
Optimal Convergence and Adaptation for Utility Optimal Opportunistic Scheduling (I) 
Neely, Michael  Univ. of Southern California 
Keywords: Optimization, Wireless Communication Systems
Abstract: This paper considers the fundamental convergence time for opportunistic scheduling over timevarying channels. The channel state probabilities are unknown and algorithms must perform some type of estimation and learning while they make decisions to optimize network utility. Existing schemes can achieve a utility within epsilon of optimality, for any desired epsilon>0, with convergence and adaptation times of O(1/epsilon^2). This paper shows that if the utility function is concave and smooth, then O(log(1/epsilon)/epsilon) convergence time is possible via an existing stochastic variation on the FrankWolfe algorithm, called the RUN algorithm. Next, a converse result is proven to show it is impossible for any algorithm to have convergence time better than O(1/epsilon), provided the algorithm has no apriori knowledge of channel state probabilities. Hence, RUN is within a logarithmic factor of convergence time optimality. However, RUN has a vanishing stepsize and hence has an infinite adaptation time. Using stochastic FrankWolfe with a fixed stepsize yields improved O(1/epsilon^2) adaptation time, but convergence time increases to O(1/epsilon^2), similar to existing driftpluspenalty based algorithms. This raises important open questions regarding optimal adaptation.


11:1011:30, Paper WeB2.3  
Learning from Randomly Arriving Agents (I) 
Le, Tho  Northwestern Univ 
Subramanian, Vijay  Univ. of Michigan 
Berry, Randall  Northwestern Univ 
Keywords: Network Games and Algorithms, Dynamic Games, Learning and Inference
Abstract: We add to a line of work considering the impact of observation imperfections in models of Bayesian observational learning. In particular, we study a discretetime model in which in each timeslot, an agent may randomly arrive. Agents who arrive have the opportunity to buy a given item. If an agent chooses to buy, this action is recorded for subsequent agents. However, the decisions of agents who do not choose to buy are not recorded. Hence, if no one buys in a given slot, agents are unaware if this was due to no agent arriving or an agent choosing not to buy. We study the impact of this uncertainty on the emergence of information cascades. Using a Markov chain based analysis, we show that incorrect cascades may occur and that the probability of such cascades is not monotonic in the arrival probability of a user. Moreover, if the agents’ private signals are weak, wrong cascades are more likely to happen than correct cascades.


11:3011:50, Paper WeB2.4  
Throughput Maximizing Control of Parallel Server Systems with Learning (I) 
Walrand, Jean  Univ. of California, Berkeley 
Zhong, Yuan  Univ. of Chicago 

11:5012:10, Paper WeB2.5  
On Stochastic ProximalPoint Method for ConvexComposite Optimization (I) 
Nedich, Angelia  Arizona State Univ 
Tatarenko, Tatiana  Arizona State Univ 
Keywords: Optimization, Learning and Inference, Machine Learning and Learning Theory
Abstract: We study stochastic proximalpoint method applied to a convexcomposite optimization problem, where the objective function is given as the sum of two convex functions, one of which is smooth while the other is not necessarily smooth but has a simple structure for evaluating the proximal operator. The main goal is to investigate a tradeoff between the choice of a constant stepsize value and the speed at which the algorithm approaches the optimal points. We consider the case of a strongly convex objective function and make the most standard assumptions on the smooth component function and its stochastic gradient estimates. First of all, we analyze the basic properties of the stochastic proximalpoint mapping associated with the procedure under consideration. Based on these properties, we formulate the main result, which provides the explicit condition on the constant stepsize for which the stochastic proximalpoint method approaches a neighborhood of the optimal point in expectation, where the parameter > 0 is related to the variance of the stochastic gradient estimates. Moreover, the rate at which the neighborhood attracts the iterates is geometric, which allows us to estimate the number of iterations the procedure needs to enter this region (in expectation).


12:1012:30, Paper WeB2.6  
On Differential Pricing and Net Neutrality (I) 
Misra, Vishal  Columbia Univ. 

WeB3 
Butternut 
Detection and Estimation 
Regular Session 
Chair: Sinopoli, Bruno  Carnegie Mellon Univ 

10:3010:50, Paper WeB3.1  
Supermajority Sentiment Detection with External Influence in Large Social Networks 
Tong, Tian  Carnegie Mellon Univ 
Negi, Rohit  Carnegie Mellon Univ 
Keywords: Detection and Estimation, Sensor Networks, Performance Analysis
Abstract: In a large social network whose members harbor binary sentiments towards an issue, we investigate the asymptotic accuracy of sentiment detection. We model the user sentiments by an Ising Markov random field model and allow the user sentiments to be biased by an external influence. We consider a general supermajority sentiment detection problem and show that the detection accuracy is affected by the network structure, its parameters, as well as the external influence level.


10:5011:10, Paper WeB3.2  
Testing for Directed Information Graphs 
Molavipour, Sina  KTH Royal Inst. of Tech 
Bassi, German  KTH Royal Inst. of Tech 
Skoglund, Mikael  Royal Inst. of Tech. (KTH) 
Keywords: Detection and Estimation, Learning and Inference, Information Theory and Statistics
Abstract: In this paper, we study a hypothesis test to determine the underlying directed graph structure of nodes in a network, where the nodes represent random processes and the direction of the links indicate a causal relationship between said processes. Specifically, a kth order Markov structure is considered for them, and the chosen metric to determine a connection between nodes is the directed information. The hypothesis test is based on the empirically calculated transition probabilities which are used to estimate the directed information. For a single edge, it is proven that the detection probability can be chosen arbitrarily close to one, while the false alarm probability remains negligible. When the test is performed on the whole graph, we derive bounds for the false alarm and detection probabilities, which show that the test is asymptotically optimal by properly setting the threshold test and using a large number of samples. Furthermore, we study how the convergence of the measures relies on the existence of links in the true graph.


11:1011:30, Paper WeB3.3  
Inferring Link Changes in Dynamic Networks through Power Spectral Density Variations 
Costanzo, John A.W.B.  Carnegie Mellon Univ 
Materassi, Donatello  Univ. of Minnesota 
Sinopoli, Bruno  Carnegie Mellon Univ 
Keywords: Detection and Estimation, Intrusion/Anomaly Detection and Diagnosis, Sensor Networks
Abstract: In this paper, we present a computationally efficient method of detecting and localizing changes in the dynamics of links in networks of LTI systems, represented as a collection of interdependent time series. We define “link” to mean a dependence of one node process on another. Our method uses only passively obtained secondorder statistics. The dynamics of the network are not required to be known. As such, we do not require a leastsquares step to find system parameters, nor do we risk using possibly corrupted data to update what we believe is the original system model. As a passive method, it does not require injecting control signals or manipulating the network. The corrupted link is only partially identified, but the scope of the problem is narrowed significantly. We detect a link change by tracking the cross power spectral density between each pair of node processes in the network. When a link changes, many pairs of nodes will experience a change in their power spectral density; we call these “changed pairs”. We characterize which pairs of nodes in the network will change depending on which link changes. We use this characterization to uniquely find the strongly connected component containing the head of the changed link. We also provide a characterization of when the tail of the changed link can be uniquely identified.


11:3011:50, Paper WeB3.4  
Nonlinear Sequential Accepts and Rejects for Identification of Top Arms in Stochastic Bandits 
Shahrampour, Shahin  Harvard Univ 
Tarokh, Vahid  Harvard Univ 
Keywords: Detection and Estimation, Learning and Inference, Machine Learning and Learning Theory
Abstract: We address the Mbestarm identification problem in multiarmed bandits. A player has a limited budget to explore K arms, and once pulled, each arm yields a reward drawn (independently) from a fixed, unknown distribution. The goal is to find the top M arms in the sense of expected reward. We develop an algorithm which proceeds in rounds to deactivate arms iteratively. At each round, the budget is divided by a nonlinear function of remaining arms, and the arms are pulled correspondingly. Based on a decision rule, the deactivated arm at each round may be accepted or rejected. The algorithm outputs the accepted arms that should ideally be the top M arms. We characterize the decay rate of the misidentification probability and establish that the nonlinear budget allocation proves to be useful for different problem environments (described by the number of competitive arms). We provide comprehensive numerical experiments showing that our algorithm outperforms the stateoftheart using suitable nonlinearity.


11:5012:10, Paper WeB3.5  
A Semidefinite Programming Relaxation under False Data Injection Attacks against Power Grid AC State Estimation 
Jin, Ming  Univ. of California, Berkeley 
Lavaei, Javad  Univ. of California, Berkeley 
Johansson, Karl Henrik  Royal Inst. of Tech 
Keywords: Detection and Estimation, Optimization, Complex Networked Systems
Abstract: The integration of sensing and information technology renders the power grid susceptible to cyberattacks. To understand how vulnerable the state estimator is, we study its behavior under the worst attacks possible. A general false data injection attack (FDIA) based on the AC model is formulated, where the attacker manipulates sensor measurements to mislead the system operator to make decisions based on a falsified state. To stage such an attack, the optimization problem incorporates constraints of limited resources (allowing only a limited number of measurements to be altered), and stealth operation (ensuring the cyber hack cannot be identified by the bad data detection algorithm). Due to the nonlinear AC power flow model and combinatorial selection of compromised sensors, the problem is nonconvex and cannot be solved in polynomial time; however, it is shown that convexification of the original problem based on a semidefinite programming (SDP) relaxation and a sparsity penalty is able to recover a nearoptimal solution. This represents the first study to solve the ACbased FDIA. Simulations on a 30bus system illustrate that the proposed attack requires only sparse sensor manipulation and remains stealthy from the residualbased bad data detection mechanism. In light of the analysis, this study raises new challenges on grid defense mechanism and attack detection strategy.


12:1012:30, Paper WeB3.6  
Reconstruction of Gene Regulatory Networks Using an Error Filtering Learning Scheme 
Tzortzis, Ioannis  Univ. of Cyprus 
Hadjicostis, Christoforos  Univ. of Cyprus 
Mombaerts, Laurent  Univ. of Luxembourg 
Keywords: Complex Networked Systems, Biological Information Systems
Abstract: One of the fundamental and most challenging problems in system biology is the reconstruction of gene regulatory networks from inputoutput data based on nonlinear differential equations. This paper presents an approach to estimate the unknown nonlinearities and to identify the true network that generated the data, based on an error filtering learning scheme and a Lyapunov synthesis method. The unknown nonlinearities are modelled by networks using radial basis functions and the model validation is performed by taking advantage of the socalled persistency of excitation of input signals, a condition that turnsout to play a significant role in the problem of uncovering the true network structure. The proposed methodology and the theoretical results are validated through an illustrative example.


WeB4 
Pine 
Network Game Theory 
Regular Session 
Chair: Atia, George  Univ. of Central Florida 

10:3010:50, Paper WeB4.1  
Dynamic GameTheoretic Defense Approach against Stealthy Jamming Attacks in Wireless Networks 
Anwar, Ahmed  Univ. of Central Florida 
Atia, George  Univ. of Central Florida 
Guirguis, Mina  Texas State Univ 
Keywords: Network Games and Algorithms, Dynamic Games
Abstract: This paper develops a gametheoretic defense approach against jamming attacks targeting access points in a wireless network. We formulate a twoplayer zerosum stochastic game between a network administrator (the defender) and a jammer (the attacker) in which the defender adapts the RF footprints of the nodes to counteract the jamming attack aimed at creating excessive interference in the network. Our formulation captures inherent tradeoffs between the ability of the attack to inflict damage and the attack exposure, and between reducing the interference level and maintaining network coverage. We obtain optimal policies for both players at Nash Equilibrium using a valueiteration based algorithm. To handle the statespace complexity for this class of games, we develop approximate policies by judiciously extracting features that are wellrepresentative of the different states. Through numerical results, we show convergence of the used algorithm to stationary policies and demonstrate the effectiveness of the defense mechanism and the approximate policies against such attacks.


10:5011:10, Paper WeB4.2  
Learning Dynamics in Stochastic Routing Games 
Meigs, Emily  MIT 
Parise, Francesca  MIT 
Ozdaglar, Asu  MIT 
Keywords: Network Games and Algorithms, Learning and Inference
Abstract: We consider a repeated nonatomic network routing game where a large number of riskneutral users are unsure about the edge latency functions and learn about them using past travel experience. We assume that the network has affine stochastic edge latency functions with unknown slope. We consider a simple process of learning where agents share common observations of travel times, estimate the unknown edge slope parameters via ordinary least squares and, at every step, dispatch their traffic demand over the network according to the Wardrop equilibrium computed using mean latency functions with most recent estimates. We prove that under this learning dynamics, the flow vector in the network converges almost surely to the full information Wardrop equilibrium. Moreover, the slope parameters of all the edges used in the full information Wardrop equilibrium are learned almost surely in the limit.


11:1011:30, Paper WeB4.3  
A Stochastic Flow Network Model with AlmostFractional Routing 
Xue, Mengran  Washington State Univ 
Roy, Sandip  Washington State Univ 
Keywords: Complex Networked Systems, Network Games and Algorithms
Abstract: A discretetime fractionalrouting model is defined for the flow of quantal items in a closed network. In contrast to models with independent probabilistic routing of items, the fractional routing model almost exactly dictates the proportions of items at each network node that are transmitted to neighbors. Although the model has a nonlinear structure, the expectations of nodal item counts are shown to be governed by a linear dynamical system, and in fact to be identical to the expected item counts for a probabilistic routing model defined on the same network graph. Further, the fractional routing model is shown to exhibit lower variability as compared to a probabilistic routing model. Finally, statistical analysis of items' locations in the network is briefly discussed, and an example is developed which illustrates the dynamics of the model.


11:3011:50, Paper WeB4.4  
On the Exponential Rate of Convergence of Fictitious Play in Potential Games 
Swenson, Brian  Carnegie Mellon Univ 
Kar, Soummya  Carnegie Mellon Univ 
Keywords: Decentralized Control Systems, Distributed and LargeScale Systems, Network Games and Algorithms
Abstract: The paper studies fictitious play (FP) learning dynamics in continuous time. It is shown that in almost every potential game, and for almost every initial condition, the rate of convergence of FP is exponential. In particular, the paper focuses on studying the behavior of FP in potential games in which all equilibria of the game are regular, as introduced by Harsanyi. Such games are referred to as regular potential games. Recently it has been shown that almost all potential games (in the sense of the Lebesgue measure) are regular. In this paper it is shown that in any regular potential game (and hence, in almost every potential game), FP converges to the set of Nash equilibria at an exponential rate from almost every initial condition.


11:5012:10, Paper WeB4.5  
On the Uniqueness and Stability of Equilibria of Network Games 
Naghizadeh Ardabili, Parinaz  Purdue Univ 
Liu, Mingyan  Univ. of Michigan 
Keywords: Network Games and Algorithms, Optimization
Abstract: We study a class of games played on networks with general (nonlinear) bestresponse functions. Specifically, we let each agent's payoff depend on a linearly weighted sum of her neighbors' actions through a nonlinear interaction function. We identify conditions on the network structure of the underlying game under which (i) the Nash equilibrium of the game is unique, and (ii) the Nash equilibria are stable under perturbations in the underlying model's parameters. We find that both the uniqueness and stability of the Nash equilibria are related to the lowest eigenvalue of suitably defined matrices, which are determined by the network's adjacency matrix, as well as the slopes of the interaction functions. We show that our uniqueness result generalizes an existing uniqueness condition for games of linear bestresponses to games with general bestresponse functions. We further identify the classes of agents that are instrumental in the spread of shocks over the network. In particular, for small shocks, we show that agents that are strictly inactive at a given equilibrium can be precluded from the equilibrium's stability analysis, irrespective of their network position or links.


12:1012:30, Paper WeB4.6  
A Dynamic Colonel Blotto Game Model for Spectrum Sharing in Wireless Networks 
Hajimirsadeghi, Mohammad  WINLAB, Rutgers Univ 
Mandayam, Narayan  WINLAB, Rutgers Univ 
Keywords: Network Games and Algorithms, Dynamic Games, Wireless Communication Systems
Abstract: Motivated by many real world examples such as communication of mobile devices, localized Internet of Things (IoT) devices, or even autonomous vehicles, and aiming to capture the influence of spectral allocation in a competitive environment on the performance of communication devices. We introduce and study the problem of dynamic competitive spectrum allocation. A scenario of two network service providers (NSPs) who are competing over a period of time to provide wireless connectivity to a set of users is considered. The NSPs compete with one another to gain access to the users by strategically offering the limited available resources to maximize their total payoff. The users accept the best offer made by NSPs which is the bandwidth that maximizes their utility functions. Under such an architecture, this paper focuses on the optimal policy bandwidth allocation strategies for the NSPs over a period of time. Under the condition of dynamically varying spectrum availability at each NSP, we show that the dynamic process of spectrum allocation can be described as a two level game in which the upper level is modeled as an optimal control problem and the lower level is modeled using a classical problem in game theory called the Colonel Blotto gamea multidimensional strategic resource allocation game. We adopt a dynamic noncooperative repeated game as the decentralized approach for the NSPs to determine their optimal strategies for the next time slot. We also provide the o


WeB5 
Lower Level 
Power and Energy Systems 
Invited Session 
Chair: DominguezGarcia, Alejandro  Univ. of Illinois at UrbanaChampaign 
CoChair: Bose, Subhonmesh  Univ. of Illinois at Urbana Champaign 
Organizer: DominguezGarcia, Alejandro  Univ. of Illinois at UrbanaChampaign 
Organizer: Bose, Subhonmesh  Univ. of Illinois at Urbana Champaign 

10:3010:50, Paper WeB5.1  
Identifying Security Vulnerabilities of Weakly Detectable Network Parameters (I) 
Lin, Yuzhang  Northeastern Univ 
Abur, Ali  NORTHEASTERN Univ 
Keywords: Detection and Estimation, Optimization, Distributed and LargeScale Systems
Abstract: This paper is concerned about the security vulnerabilities in the implementation of the Congestion Revenue Rights (CRR) markets. Such problems may be due to the weakly detectable network model parameter errors which are commonly found in power systems. CRRs are financial tools for hedging the risk of congestion charges in power markets. The reimbursements received by CRR holders are determined by the congestion patterns and Locational Marginal Prices (LMPs) in the dayahead markets, which heavily rely on the parameters in the network model. It is recently shown that detection of errors in certain network model parameters may be very difficult. This paper’s primary goal is to illustrate the lack of market security due to such vulnerabilities, i.e. CRR market calculations can be manipulated by injecting parameter errors which are not likely to be detected. A case study using the IEEE 14bus system will illustrate the feasibility of such undetectable manipulations. Several suggestions for preventing such cyber security issues are provided at the end of the paper.


10:5011:10, Paper WeB5.2  
TimeVarying Injection Shift Factors to Predict PostContingency Dynamic Line Flows (I) 
AlDigs, Abdullah  Univ. of British Columbia 
Dhople, Sairaj  Univ. of Minnesota 
Chen, Yu Christine  Univ. of British Columbia 
Keywords: Complex Networked Systems, Distributed and LargeScale Systems
Abstract: In this paper, we derive analytical closedform expressions for timevarying generator participation factors that are valid throughout the postcontingency transient period. Combining these with conventional injection shift factors (ISFs) computed at the predisturbance steadystate operating point, postcontingency dynamic transmissionline flows after the outage of any one particular asset, such as a generator or load, can be accurately predicted. This is advantageous over conventional ISFbased contingency analysis, which is applicable only for the postdisturbance steadystate operating point. As such, operators can determine whether or not any transmission lines exceed their operational limits during the transient without repeated timedomain simulations for each credible contingency. We validate the proposed methodology via numerical case studies conducted on standard IEEE test systems.


11:1011:30, Paper WeB5.3  
Convex Relaxation for MixedInteger Optimal Power Flow Problems (I) 
Chang, ChinYao  Univ. of California, San Diego 
Martinez, Sonia  Univ. of California, San Diego 
Cortes, Jorge  Univ. of California San Diego 
Keywords: Optimization, Distributed and LargeScale Systems, Decentralized Control Systems
Abstract: Recent years have witnessed the success of employing convex relaxations of the AC optimal power flow (OPF) problem to find global or nearglobal optimal solutions. The majority of the effort has focused on solving problem formulations where variables live in continuous spaces. Our focus here is in the extension of these results to the cooptimization of network topology and the OPF problem. We employ binary variables to model topology reconfiguration in the standard semidefinite programming (SDP) formulation of the OPF problem. This makes the problem nonconvex, not only because the variables are binary, but also because of the presence of bilinear products between the binary and other continuous variables. Our proposed convex relaxation to this problem incorporates the bilinear terms in a novel way that improves over the commonly used McCormick approximation. We also address the exponential complexity associated with the discrete variables by partitioning the network graph in a way that minimizes the impact on the optimal value of the relaxation. As a result, the problem is broken down into several parallel mixedinteger problems, reducing the overall computational complexity. Simulations in the IEEE 118bus test case demonstrate that our approach converges to solutions which are very close to the lower bound of the mixedinteger OPF problem.


11:3011:50, Paper WeB5.4  
Sparse Tableau Relaxation for the Optimal Power Flow Problem (I) 
Park, Byungkwon  Univ. of WisconsinMadison 
DeMarco, Christopher L.  Univ. of WisconsinMadison 
Keywords: Network Information Theory
Abstract: This work will begin from a critique the “Ybus” formulation longutilized for representation of network constraints in the Optimal Power Flow problem. This representation inherently restricts allowable network elements to be voltagecontrolled only, and uses strict nodal analysis to eliminate variables from KVL and KCL constraints. The approach here argues for the advantages of generalized multiport representation of network elements, and retention of unreduced KVL and KCL equations in a Sparse Tableau Formulation (STF) of network constraints. In the STF, one is better able to exploit the fact that the vast majority of power grid network elements (e.g., transmission lines, transformers) have voltagecurrent behavior that is wellmodeled as linear. Therefore, the sources of nonlinearity and nonconvexity in the network constraints appear only in equations associate with each bus, and for the STF, each constraint involves only variables local to that bus. This open the door to simple, engineeringbased relaxations of these STF constraint equations at each bus. This work will examine two such relaxations. The first introduces a variable admittance at each bus, with the admittance values relaxed to lie within bounds that guarantee all power injections feasible for the original problem are achievable by a feasible admittance value. The second introduces a variable current injection at each bus, with the current values relaxed to lie within bounds that guarantee all power in


11:5012:10, Paper WeB5.5  
Global Performance Metrics for Synchronization of Heterogeneously Rated Power Systems: The Role of Machine Models and Inertia (I) 
Paganini, Fernando  Univ. ORT Uruguay 
Mallada, Enrique  Johns Hopkins Univ 
Keywords: Coding Theory, Complex Networked Systems
Abstract: A recent trend in control of power systems has sought to quantify the synchronization dynamics in terms of a global performance metric, compute it under very simplified assumptions, and use it to gain insight on the role of system parameters, in particular, inertia. In this paper, we wish to extend this approach to more realistic scenarios, by incorporating the heterogeneity of machine ratings, more complete machine models, and also to more closely map it to classical power engineering notions such as Nadir, Rate of Change of Frequency (RoCoF), and interarea oscillations. We consider the system response to a step change in power excitation, and define the system frequency as a weighted average of generator frequencies (with weights proportional to each machine's rating); we characterize Nadir and RoCoF by the L_infty norm of the system frequency and its derivative, respectively, and interareas oscillations by the L_2 norm of the error of the vector of bus frequencies w.r.t. the system frequency. For machine models where the dynamic parameters (inertia, damping, etc.) are proportional to rating, we analytically compute these norms and use them to show that the role of inertia is more nuanced than in the conventional wisdom. With the classical swing dynamics, inertia constant plays a secondary role in performance. It is only when the turbine dynamics are introduced that the benefits of inertia become more prominent.


12:1012:30, Paper WeB5.6  
Energy Function Analysis of LowInertia Power Systems (I) 
Hiskens, Ian  Univ. of Michigan 

WeC1 
Library 
Big Data in Signal Processing 
Invited Session 
Chair: Varshney, Lav R.  Univ. of Illinois at UrbanaChampaign 
CoChair: Veeravalli, Venu  Univ. of Illinois 
Organizer: Veeravalli, Venu  Univ. of Illinois 
Organizer: Varshney, Lav R.  Univ. of Illinois at UrbanaChampaign 

13:3013:50, Paper WeC1.1  
Landscape Properties of Deep Linear and Residual Neural Networks (I) 
Liang, Yingbin  The Ohio State Univ. 

13:5014:10, Paper WeC1.2  
Robust PCA with Concurrent Column and ElementWise Outliers (I) 
Rahmani, Mostafa  Univ. of Central Florida 
Atia, George  Univ. of Central Florida 
Keywords: Data Analytics, Learning and Inference
Abstract: To date, existing robust PCA algorithms have only considered settings where the data is corrupted with one type of outliers at a time, but a mechanism to handle simultaneous types of outliers has been lacking. This paper proposes a low rank matrix recovery algorithm that is robust to concurrent presence of columnwise and sparse elementwise outliers. The underpinning of our approach is a sparse approximation of a sparsely corrupted column whereby we set apart an inlier column with sparse corruption from an outlying data point. The core idea of sparse approximation is analyzed analytically where we show that the underlying ell_1norm minimization can obtain the representation of an inlier in presence of sparse corruptions.


14:1014:30, Paper WeC1.3  
Nonparametric Network Comparison (I) 
Wolfe, Patrick  Univ. Coll. London 

14:3014:50, Paper WeC1.4  
Decentralized Exact Coupled Optimization 
Alghunaim, Sulaiman A.  Univ. of California Los Angeles 
Yuan, Kun  Univ. of California Los Angeles 
Sayed, Ali H.  Ec. Pol. Federale De Lausanne (EPFL) 
Keywords: Optimization, Distributed and LargeScale Systems
Abstract: This work develops an exact converging algorithm for the solution of a distributed optimization problem with partiallycoupled parameters across agents in a multiagent scenario. In this formulation, while the network performance is dependent on a collection of parameters, each individual agent may be influenced by only a subset of the parameters. Problems of this type arise in several applications, most notably in distributed control formulations and in power system monitoring. The resulting coupled exact diffusion strategy is shown to converge to the true optimizer at a linear rate for stronglyconvex cost functions.


14:5015:10, Paper WeC1.5  
NonParametric Active Target Localization: Exploiting Unimodality and Separability (I) 
Mokhasunavisu, Dhruva  Univ. of Southern California 
Mitra, Urbashi  Univ. of Southern California 
Keywords: Detection and Estimation, Information Theory and Statistics, Sensor Networks in Communications
Abstract: The problem of localizing the peak of a unimodal signal from noisy measurements is examined. A nonBayesian framework is used to identify feasible peak locations based on collected measurements in the absence of prior information regarding the signal. An active sensing algorithm is designed to reduce the number of measurements without compromising the localization accuracy. The sensing algorithm exploits the unimodality of the signal using a group testing strategy to iteratively reduce the ambiguity associated with the location of the target while adaptively excluding sample locations that are irrelevant for localization. While it can be numerically demonstrated that the greedy approach is not always optimal; we can bound this probability and it is found to be small. Analysis and experiments suggest that the greedy step is optimal with high probability in most cases. Furthermore, it can be shown that using a greedy approach achieves better localization performance than using all the available samples.


WeC2 
Solarium 
Algorithms 
Regular Session 
Chair: Baron, Dror  North Carolina State Univ 

13:3013:50, Paper WeC2.1  
A Dynamical Systems Perspective to Convergence Rate Analysis of Proximal Algorithms 
Fazlyab, Mahyar  Univ. of Pennsylvania 
Ribeiro, Alejandro  Univ. of Pennsylvania 
Morari, Manfred  Univ. of Pennsylvania 
Preciado, Victor M.  Univ. of Pennsylvania 
Keywords: Optimization, Robust and Nonlinear Control, Performance Analysis
Abstract: In this paper, we develop a semidefinite programming (SDP) framework for convergence rate analysis of proximal algorithms designed to solve convex composite optimization problems. We first represent these algorithms as linear dynamical systems interconnected with a nonlinear component. We then propose a family of timevarying nonquadratic Lyapunov functions that are particularly useful for establishing arbitrary (exponential or subexponential) convergence rates. Using Integral Quadratic Constraints (IQCs) to describe the class of allowable nonlinearities in the interconnection, we derive sufficient conditions for Lyapunov stability of proximal algorithms in terms of Linear Matrix Inequalities (LMIs). We show how the developed LMIbased framework can be used to establish convergence rates by specializing it to the proximal gradient method and its accelerated variant for both convex and strongly convex problems.


13:5014:10, Paper WeC2.2  
Novel Inner Bounds with Uncoded Cache Placement for Combination Networks with EndUserCaches 
Wan, Kai  L2SCentraleSupelecUniv. ParisSud 
Ji, Mingyue  Univ. of Southern California 
Piantanida, Pablo  SUPELEC 
Tuninetti, Daniela  Univ. of Illinois at Chicago 
Keywords: Information Theory, Data Storage, Network Coding
Abstract: This paper considers combination networks with endusercaches, where a server with N files communicates through H relays (without caches) to K=binom{H}{r} users equipped with caches of size M files. In this setting, each user is connected to a different subset of r relays. The tradeoff between the cache size and the worstcase download time is studied.Several novel caching schemes are proposed, which leverage the symmetries of combination networks and interference elimination at the endusers.The proposed schemes are proved: (i) to be optimal for some choices of the parameters (N,M,H,r) under the constraint of uncoded cache placement, and (ii) to outperform the stateoftheart schemes in numerical evaluations.


14:1014:30, Paper WeC2.3  
A Fast SinglePass Algorithm for Compressive Sensing Based on Binary Measurement Matrices 
Lotfi, Mahsa  Univ. of Texas at Dallas 
Vidyasagar, Mathukumalli  Univ. of Texas at Dallas 
Keywords: Signal Acquisition, Coding, and Retrieval, Machine Learning and Learning Theory, Information Theory
Abstract: In this paper we present a new algorithm for compressive sensing that makes use of binary measurement matrices and achieves exact recovery of sparse vectors, in a single pass, without any iterations. Our algorithm is hundreds of times faster than methods based on expander graphs (which require multiple iterations). Moreover, our method requires the fewest measurements amongst all methods that use binary measurement matrices. The algorithm can accommodate "nearly" sparse vectors, in which case it recovers the largest components, and can also accommodate noisy measurements. Our algorithm has parallels with ell_1norm minimization, but runs about a hundred times faster.


14:3014:50, Paper WeC2.4  
On the Reconstruction Risk of Convolutional Sparse Dictionary Learning 
Singh, Shashank  Carnegie Mellon Univ. 
Poczos, Barnabas  Carnegie Mellon Univ. 
Ma, Jian  Carnegie Mellon Univ. 

14:5015:10, Paper WeC2.5  
Generalized Geometric Programming for Rate Allocation in Consensus 
Pilgrim, Ryan  North Carolina State Univ 
Zhu, Junan  North Carolina State Univ 
Baron, Dror  North Carolina State Univ 
Bajwa, Waheed U.  Rutgers Univ 
Keywords: Sensor Networks, Statistical Signal Processing, Sensor Networks in Communications
Abstract: Distributed averaging, or distributed average consensus, is a common method for computing the sample mean of the data dispersed among the nodes of a network in a decentralized manner. By iteratively exchanging messages with neighbors, the nodes of the network can converge to an agreement on the sample mean of their initial states. In realworld scenarios, these messages are subject to bandwidth and power constraints, which motivates the design of a lossy compression strategy. Few prior works consider the rate allocation problem from the perspective of constrained optimization, which provides a principled method for the design of lossy compression schemes, allows for the relaxation of certain assumptions, and offers performance guarantees. We show for Gaussiandistributed initial states with entropycoded scalar quantization and vector quantization that the coding rates for distributed averaging can be optimized through generalized geometric programming. In the absence of side information from past states, this approach finds a rate allocation over nodes and iterations that minimizes the aggregate coding rate required to achieve a target mean square error within a finite run time. Our rate allocation is compared to some of the prior art through numerical simulations. The results motivate the incorporation of side information through differential or predictive coding to improve ratedistortion performance.


WeC3 
Butternut 
Delay, Deletions & Synchronization 
Regular Session 
Chair: Baccelli, François  UT Austin 

13:3013:50, Paper WeC3.1  
Bounded Phase Synchronization of Multirate Kuramoto Networks through Decentralised or Distributed Control 
Wu, Liang  UNSW@ADFA 
Pota, Hemanshu R  UNSW@ADFA 
Petersen, Ian R.  Australian National Univ 
Keywords: Complex Networked Systems, Decentralized Control Systems
Abstract: This paper studies the bounded phase synchronization of a general multirate Kuramoto oscillator network by using decentralised or distributed control. The proposed control laws consists of the feedback information of oscillators' phases. We present two methods to design the control gains for both control types such that the phases of oscillators ultimately converge into any given region. These two control gain design methods are related to the eigenvalues of a graph Laplacian matrix or a graph path set, which increases the flexibility in the gain design process. Using an energy function method, we estimate a positively invariant set for the Kuramoto network to achieve transient boundedness on the network's dynamics. The estimate of the positively invariant set is further improved if the network's parameters satisfy a certain condition, based on an extended energy function. The effectiveness and conservativeness of the two control methods are demonstrated and compared on simulation studies.


13:5014:10, Paper WeC3.2  
TwoParty Function Computation on the Reconciled Data 
Kubjas, Ivo  Univ. of Tartu 
Skachek, Vitaly  Univ. of Tartu 
Keywords: Data Storage, Network Games and Algorithms, Distributed and LargeScale Systems
Abstract: In this paper, we initiate a study of a new problem termed function computation on the reconciled data, which generalizes a set reconciliation problem in the literature. Assume a distributed data storage system with two users A and B. The users possess a collection of binary vectors S_{A} and S_{B}, respectively. They are interested in computing a function phi of the reconciled data S_{A} cup S_{B}. It is shown that any deterministic protocol, which computes a sum and a product of reconciled sets of binary vectors represented as nonnegative integers, has to communicate at least 2^n + n  1 and 2^n + n  2 bits in the worstcase scenario, respectively, where n is the length of the binary vectors. Connections to other problems in computer science, such as set disjointness and finding the intersection, are established, yielding a variety of additional upper and lower bounds on the communication complexity. A protocol for computation of a sum function, which is based on use of a family of hash functions, is presented, and its characteristics are analyzed.


14:1014:30, Paper WeC3.3  
Delay Comparison of Delivery and Coding Policies in Data Clusters 
Shah, Virag  Microsoft Res.  Inria Joint Center 
Bouillard, Anne  Nokia Bell Labs 
Baccelli, François  UT Austin 
Keywords: Performance Analysis, Distributed and LargeScale Systems
Abstract: A key function of cloud infrastructure is to store and deliver diverse files, eg, scientific datasets, social network information, videos, etc. In such systems, for the purpose of fast and reliable delivery, files are divided into chunks, replicated or erasurecoded, and disseminated across servers. It is neither known in general how delays scale with the size of a request nor how delays compare under different policies for coding, data dissemination, and delivery. Motivated by these questions, we develop and explore a set of evolution equations as a unified model which captures the above features. These equations allow for both efficient simulation and mathematical analysis of several delivery policies under general statistical assumptions. In particular, we quantify in what sense a workload aware delivery policy performs better than a workload agnostic policy. Under a dynamic or stochastic setting, the sample path comparison of these policies does not hold in general. The comparison is shown to hold under the weaker increasing convex stochastic ordering, still stronger than the comparison of averages. This result further allows us to obtain insightful computable performance bounds. For example, we show that in a system where files are divided into chunks of equal size, replicated or erasurecoded, and disseminated across servers at random, the job delays increase sublogarithmically in the request size for small and mediumsized files but linearly for large files.


14:3014:50, Paper WeC3.4  
Longest Alignment with Edits in Data Streams 
Grigorescu, Elena  Purdue Univ 
Sadeqi Azer, Erfan  Indiana Univ.  Bloomington 
Zhou, Samson  Purdue Univ 
Keywords: Data Storage, Biological Information Systems
Abstract: Analyzing patterns in streamed data generated by network traffic, sensor networks, or satellite feeds is a challenge for systems in which the available storage is limited. In addition, real data is noisy, which makes designing data stream algorithms even more challenging. Motivated by such challenges, we study algorithms for detecting the similarity of two data streams that can be read in sync. Two strings S, Tin Sigma^n form a dnearalignment if the distance between them in some given metric is at most d. We study the problem of identifying a longest substring of S and T that forms a {em dnearalignment} under the {em edit} distance, in the {em simultaneous streaming model}. In this model, symbols of strings S and T are streamed at the same time, and the amount of available processing space is sublinear in the length of the strings. We give several algorithms, including an exact onepass algorithm that uses O{d^2+dlog n} bits of space. We couple these results with comparable lower bounds.


14:5015:10, Paper WeC3.5  
Distributed Leader Selection in Switching Networks of HighOrder Integrators 
Tsiamis, Anastasios  Univ. of Pennsylvania 
Pequito, Sergio  Univ. of Pennsylvania 
Pappas, George  Univ. of Pennsylvania 
Keywords: Distributed and LargeScale Systems, Decentralized Control Systems, Robotics
Abstract: We consider the problem of leader selection in a team of interconnected agents, modeled as higherorder integrators. The leader selection problem aims to determine the minimum number of agents, i.e., the leaders, that are required to receive an external input to ensure a controltheoretical property. The remaining agents, i.e., the followers, update their states based only on local information gathered from the other agents they interact with. In this paper, given the communication topology, our goal is to design distributed protocols that determine the minimum number of leaders and the communication protocol to ensure a desirable property, without any knowledge about the global structure of the network. The main contributions consist of determining the solution to this problem when the controllability and stabilizability are sought. In addition, we extend these results to the case where the communication topology switches over time. Finally, we illustrate the main results by providing a simulation example.


WeC4 
Pine 
Coding Techniques 
Regular Session 
Chair: Li, Qing  ScaleFlux Inc 

13:3013:50, Paper WeC4.1  
Cooperative Data Exchange with Weighted Cost Based on DBasis Construction 
Li, Su  EPFL 
Shah, Abhin  EPFL 
Gastpar, Michael  EPFL 
Keywords: Coding Techniques and Applications, Network Information Theory, Data Storage
Abstract: We consider the cooperative data exchange problem, in which nodes are fully connected with each other. Each node initially only has a subset of the K packets making up a file and wants to recover the whole file. Node i can make a broadcast transmission, which incurs cost w_i and is received by all other nodes. The goal is to minimize the total cost of transmissions that all nodes have to send, which is also called weighted cost. Following the same idea of our previous work (ISIT 2017) which provided a method based on dBasis construction to solve cooperative data exchange problem without weighted cost, we present a modified method to solve cooperative data exchange problem with weighted cost. We present a polynomialtime deterministic algorithm to compute the minimum weighted cost and determine the rate vector and the packets that should be used to generate each transmission. By leveraging the connection to Maximum Distance Separable codes, the coefficients of linear combinations of the optimal coding scheme can be efficiently generated. Our algorithm has significantly lower complexity than the state of the art. In particular, we prove that the minimum weighted cost function is a convex function of the total number of transmissions for integer rate cases.


13:5014:10, Paper WeC4.2  
Joint Decoding of RAIDECC Solutions for SSDs 
Li, Qing  ScaleFlux Inc 
Zheng, Ning  ScaleFlux 
Keywords: Data Storage, Coding Theory, Coding Techniques and Applications
Abstract: There are two independent layers of error correction mechanisms, i.e., errorcorrection codes (ECC) and redundant array of independent disks (RAID), to protect NANDbased Solid State Drives (SSDs) from serious noise/disturb. However, bit error rates of modern SSDs have increased to the point that more powerful ECCs or Maximal Distance Separate codes are only regarded as sufficient solutions. The theme of this work is to show that instead of designing new error correction mechanisms, it is possible to improve the NANDbased SSD reliability by designing a joint decoder exploring the inherent information between ECCs and RAIDs. We first show that it is possible to recover twopage failures using the inherent information with RAID 4/5; we then show that these ideas can be extended to RAID 6; finally, we conduct information theoretic study to explore how much information can be reliably stored with the help of RAID system in NANDbased SSD.


14:1014:30, Paper WeC4.3  
Coded Caching with Multiple File Requests 
Wei, YiPeng  Univ. of Maryland 
Ulukus, Sennur  Univ. of Maryland 
Keywords: Coding Techniques and Applications, Data Storage, Information Theoretic Approaches in Wireless Communications
Abstract: We study a twophase caching network consisting of one server with N files connected to K users through an errorfree shared link. Each user has a cache memory which can store M files in the placement phase. In the delivery phase, each user requests L files, and the server transmits the messages accordingly. Using the message sent by the server combined with the cache memory, each user reconstructs the L files they requested. In this work, we focus on the case L>1, i.e., the case of multiple file requests. We adopt the symmetric batch caching scheme and propose a general delivery scheme. To prove the optimality of the proposed general delivery scheme, we apply two converse techniques. The first converse technique is for general coding schemes and is obtained through virtual user construction. The second converse technique is for vector linear coding schemes and is obtained using an interference alignment point of view. With these two converse techniques, we characterize either the unconstrained optimal coding rate, or optimum linear coding rate, with symmetric batch caching for certain cases.


14:3014:50, Paper WeC4.4  
On ErrorCorrection Performance and Implementation of Polar Code List Decoders for 5G 
Ercan, Furkan  McGill Univ 
Condo, Carlo  McGill Univ 
Hashemi, Seyyed Ali  McGill Univ 
Gross, Warren  McGill Univ 
Keywords: Coding Techniques and Applications, Performance Analysis, Wireless Communication Systems
Abstract: Polar codes are a class of capacity achieving error correcting codes that has been recently selected for the next generation of wireless communication standards (5G). Polar code decoding algorithms have evolved in various directions, striking different balances between errorcorrection performance, speed and complexity. Successivecancellation list (SCL) and its incarnations constitute a powerful, wellstudied set of algorithms, in constant improvement. At the same time, different implementation approaches provide a wide range of area occupations and latency results. 5G puts a focus on improved errorcorrection performance, high throughput and low power consumption: a comprehensive study considering all these metrics is currently lacking in literature. In this work, we evaluate SCLbased decoding algorithms in terms of errorcorrection performance and compare them to lowdensity paritycheck (LDPC) codes. Moreover, we consider various decoder implementations, for both polar and LDPC codes, and compare their area occupation and power and energy consumption when targeting short code lengths and rates. Our work shows that among SCLbased decoders, the partitioned SCL (PSCL) provides the lowest area occupation and power consumption, whereas fast simplified SCL (FastSSCL) yields the lowest energy consumption. Compared to LDPC decoder architectures, different SCL implementations occupy up to 17.1x less area, dissipate up to 7.35x less power, and up to 26x less energy.


14:5015:10, Paper WeC4.5  
Transcoding: A New Strategy for Relay Channels 
Wang, ChihChun  Purdue Univ 
Love, David J.  Purdue Univ 
Ogbe, Dennis  Purdue Univ 
Keywords: Coding Theory, Information Theory
Abstract: The relay channel is a traditional informationtheoretic problem which has important applications in the Internet of Things (IoT) and other future communication networks. In this work, we focus on the simplest possible relaying model: the socalled separated (or twohop) relay channel where there is no direct link between the source and the destination. Previous work has shown that for this channel, the decodeandforward (DF) relaying strategy is capacityachieving under the assumption of asymptotic block lengths. In this paper, however, we are interested in the finitedelay regime where simpler suboptimal techniques like amplifyandforward (AF) can be used to avoid the need for buffering at the relay. We present a new strategy called transcoding which presents a tradeoff between the lowlatency advantages of amplifyandforward and the highrate, highlatency decodeandforward scheme. Our results indicate that our simple, intuitive transcoding schemes outperform traditional relaying schemes in the finitedelay regime.


WeC5 
Lower Level 
Network Analysis 
Regular Session 
Chair: Garg, Siddharth  Univ. of Waterloo 

13:3013:50, Paper WeC5.1  
CloudBased Resource Allocation and Cooperative Transmission in Large Cellular Networks 
Li, Jing  Northwestern Univ 
Guo, Dongning  Northwestern Univ 
Keywords: Wireless Communication Systems, Optimization, Information Theoretic Approaches in Wireless Communications
Abstract: In a large cellular network where access points can transmit cooperatively, how to successfully identify cooperative opportunities and allocate physical resources are two challenging topics. This work considers cloudbased slowtimescale centralized resource and cooperation management for the downlink of large cellular networks. We propose several scalable convex optimization formulations. We then propose a cooperation and resource management scheme. In particular, the proposed scheme dynamically identifies pairs of access points to cooperate to optimize the overall network utility.


13:5014:10, Paper WeC5.2  
Status Updates through Multicast Networks 
Zhong, Jing  Rutgers Univ 
Soljanin, Emina  Rutgers Univ 
Yates, Roy  Rutgers Univ 
Keywords: Performance Analysis, Wireless Communication Systems, Distributed and LargeScale Systems
Abstract: Using age of information as the freshness metric, we examine a multicast network in which realtime status updates are generated by the source and sent to a group of n interested receivers. We show that in order to keep the information freshness at each receiver, the source should terminate the transmission of the current update and start sending a new update packet as soon as it receives the acknowledgements back from any k out of n nodes. As the source stopping threshold k increases, a node is more likely to get the latest generated update, but the age of the most recent update is more likely to become outdated. We derive the age minimized stopping threshold k that balances the likelihood of getting the latest update and the freshness of the latest update for shifted exponential link delay. Through numerical evaluations for different stopping strategies, we find that waiting for the acknowledgements from the earliest k out of n nodes leads to lower average age than waiting for a preselected group of k nodes. We also observe that a properly chosen threshold k can prevent information staleness for increasing number of nodes n in the multicast network.


14:1014:30, Paper WeC5.3  
An Information Theoretic Framework for Active DeAnonymization in Social Networks Based on Group Memberships 
Shirani, Farhad  Tandon School of Engineering, New York Univ 
Garg, Siddharth  Tandon School of Engineering, New York Univ 
Erkip, Elza  Tandon School of Engineering, New York Univ 
Keywords: Reliability, Security and Trust, Information Theory and Statistics, Information Theory
Abstract: In this paper, a new mathematical formulation for the problem of deanonymizing social network users by actively querying their membership in social network groups is introduced. In this formulation, the attacker has access to a noisy observation of the group membership of each user in the social network. When an unidentified victim visits a malicious website, the attacker uses browser history sniffing to make queries regarding the victim's social media activity. Particularly, it can make polar queries regarding the victim's group memberships and the victim's identity. The attacker receives noisy responses to her queries. The goal is to deanonymize the victim with the minimum number of queries. Starting with a rigorous mathematical model for this active deanonymization problem, an upper bound on the attacker's expected query cost is derived, and new attack algorithms are proposed which achieve this bound. These algorithms vary in computational cost and performance. The results suggest that prior heuristic approaches to this problem provide suboptimal solutions.


14:3014:50, Paper WeC5.4  
Stability and Fracture of Social Groups 
Eshghi, Soheil  Yale Univ 
Williams, GraceRose  Dstl 
Colombo, Gualtiero B.  Cardiff Univ 
Turner, Liam D  Cardiff Univ 
Rand, David G.  Yale Univ 
Whitaker, Roger M  Cardiff Univ 
Tassiulas, Leandros  Yale Univ 
Keywords: Computational Models and Representations, Complex Networked Systems
Abstract: In this paper, we present a mathematical model for the mutation of social groups. Group mutability has been studied in multiple domains, with insights generated on significant factors at differing scales. Mathematical modeling enables the simultaneous study of such phenomena, understanding interactions and generating hypotheses for experiments. In particular, we focus on group fracture, where individuals leave groups of which they are members. For example, this can be due to perceived differences with other group members due to norm related conflict (such as extreme actions by some members). Our aim is to consider simple mathematical models incorporating a selection of social and psychological theory which describes these phenomena as a way to understand their interplay, and describe the tradeoffs and challenges.


14:5015:10, Paper WeC5.5  
Energy Savings for Virtual MISO in Fractal Sensor Networks 
Bradonjic, Milan  Rutgers Univ. 
Jacquet, Philippe  INRIA 
Popescu, Dalia  Nokia Bell Labs 

WeD1 
Library 
Networks Learning and Algorithms III 
Invited Session 
Chair: Sowers, Richard  Univ. of Illinois 
Organizer: Hajek, Bruce  Univ. of Illinois 
Organizer: Srikant, R  Univ. of Illinois 

15:3015:50, Paper WeD1.1  
A Fresh Look at an Old Problem: Network Utility Maximization — Convergence, Delay, and Complexity (I) 
Wang, Sinong  The Ohio State Univ. 
Shroff, Ness  The Ohio State Univ. 

15:5016:10, Paper WeD1.2  
Minimizing AgeOfInformation in MultiHop Wireless Networks (I) 
Talak, Rajat  MIT 
Karaman, Sertac  MIT 
Modiano, Eytan  MIT 
Keywords: Network Information Theory
Abstract: Timely exchange of information over multihop wireless networks is gaining increasing relevance with growing interests in applications such as internet of things (IoT) and autonomous vehicular networks. Ageofinformation (AoI) is a recently proposed performance metric that measures information freshness at the destination node. AoI at a destination node is the time since last update was received. We study AoI for multihop networks with general interference constraints with multiple sourcedestination pairs, and derive simple stationary policies in which links are activated according to a stationary probability distribution. We first consider a line network with a single source destination pair, and characterize AoI as a convex function of link activation rates. We then use this result to obtain the optimal policy, in the class of stationary policies, for multihop network, with several sourcedestination pairs. We prove an important separation principle, which says that the optimal scheduling policy for the multihop problem can be obtained by solving an equivalent problem in which all sourcedestination pairs are singlehop away.


16:1016:30, Paper WeD1.3  
Optimal Decentralized Scheduling of MultiHop Wireless Networks with EndToEnd Deadline Constraints (I) 
Singh, Rahul  Texas A&M Univ. 
Kumar, P. R.  Texas A&M Univ. 

16:3016:50, Paper WeD1.4  
Coded Fourier Transform (I) 
Yu, Qian  USC 
Maddahali, Mohammad Ali  Bell Labs AlcatelLucent 
Avestimehr, Salman  USC 
Keywords: Computational Models and Representations, Coding Theory, Information Theory
Abstract: We consider the problem of computing the Fourier transform of highdimensional vectors, distributedly over a cluster of machines consisting of a master node and multiple worker nodes, where the worker nodes can only store and process a fraction of the inputs. We show that by exploiting the algebraic structure of the Fourier transform operation and leveraging concepts from coding theory, one can efficiently deal with the straggler effects. In particular, we propose a computation strategy, named as "coded FFT", which achieves the optimal recovery threshold, defined as the minimum number of workers that the master node needs to wait for in order to compute the output. This is the first code that achieves the optimum robustness in terms of tolerating stragglers or failures for computing Fourier transforms. Furthermore, the reconstruction process for coded FFT can be mapped to MDS decoding, which can be solved efficiently. Moreover, we extend coded FFT to settings including computing general ndimensional Fourier transforms, and provide the optimal computing strategy for those settings.


16:5017:10, Paper WeD1.5  
MeasureValued MeanField Limits for Spatial CSMA Networks (I) 
Whiting, Philip  Macquarie Univ 
Borst, Sem  Bell Lab. Lucent Tech 
van Leeuwaarden, Johan  Eindhoven Univ. of Tech 
Cecchi, Fabio  Eindhoven Univ. of Tech 


17:1017:30, Paper WeD1.6  
Community Detection on Euclidean Random Graphs (I) 
Sankararaman, Abishek  UT Austin 
Baccelli, Francois  The Univ. of Texas at Austin 

17:3017:50, Paper WeD1.7  
DiscountedRate Utility Maximization (DRUM) Framework for ShortTermFair Rate Allocation Over Wireless Networks (I) 
Eryilmaz, Atilla  Ohio State Univ. 
Koprulu, Irem  Ohio State Univ. 

WeD2 
Solarium 
LargeScale Optimization 
Invited Session 
Chair: Raginsky, Maxim  Univ. of Illinois at UrbanaChampaign 
CoChair: He, Niao  UIUC 
Organizer: Nedich, Angelia  Arizona State Univ 
Organizer: Raginsky, Maxim  Univ. of Illinois at UrbanaChampaign 

15:3015:50, Paper WeD2.1  
MultiAgent Constrained Optimization of a Strongly Convex Function Over TimeVarying Directed Networks (I) 
Yazdandoost Hamedani, Erfan  Penn State Univ 
Aybat, Necdet Serhat  Penn State Univ 
Keywords: Optimization, Distributed and LargeScale Systems
Abstract: We consider cooperative multiagent consensus optimization problems over undirected and directed timevarying communication networks, where only local communications are allowed. The objective is to minimize the sum of agentspecific possibly nonsmooth composite convex functions over agentspecific private conic constraint sets; hence, the optimal consensus decision should lie in the intersection of these private sets. Assuming the sum function is strongly convex, we provide convergence rates in suboptimality, infeasibility and consensus violation; examine the effect of underlying network topology on the convergence rates of the proposed decentralized algorithm.


15:5016:10, Paper WeD2.2  
When Cyclic Coordinate Descent Beats Randomized Coordinate Descent (I) 
Gurbuzbalaban, Mert  Rutgers Univ. 

16:1016:30, Paper WeD2.3  
Distributed Optimization Algorithms for Networked Systems (I) 
Zavlanos, Michael  Duke Univ. 

16:3016:50, Paper WeD2.4  
CurvatureAided Incremental Aggregated Gradient Method (I) 
Wai, HoiTo  Arizona State Univ 
Shi, Wei  Univ. of Illinois at Urbana Champaign 
Nedich, Angelia  Arizona State Univ 
Scaglione, Anna  UC Davis 
Keywords: Distributed and LargeScale Systems, Optimization, Machine Learning and Learning Theory
Abstract: We propose a new algorithm for finite sum optimization which we call the curvatureaided incremental aggregated gradient (CIAG) method. Motivated by the problem of training a classifier for a ddimensional problem, where the number of training data is m and m gg d gg 1, the CIAG method seeks to accelerate incremental aggregated gradient (IAG) methods using aids from the curvature (or Hessian) information, while avoiding the evaluation of matrix inverses required by the incremental Newton (IN) method. Specifically, our idea is to exploit the incrementally aggregated Hessian matrix to trace the full gradient vector at every incremental step, therefore achieving an improved linear convergence rate over the stateoftheart IAG method. For strongly convex problems, the fast linear convergence rate requires the objective function to be close to quadratic, or the initial point to be close to optimal solution. Importantly, we show that running one iteration of the CIAG method yields the same improvement to the optimality gap as running one iteration of the full gradient method, while the complexity is O(d^2) for CIAG and O(md) for the full gradient. Overall, the CIAG method strikes a balance between the high computation complexity incremental Newtontype methods and the slow IAG method. Our numerical results support the theoretical findings and show that the CIAG method often converges with much fewer iterations than IN when the problem dimension is high.


16:5017:10, Paper WeD2.5  
Bayesian Function Optimization with Adaptive Discretization (I) 
Shekhar, Shubhanshu  Univ. of California, San Diego 
Javidi, Tara  Univ. of California, San Diego 

17:1017:30, Paper WeD2.6  
Learning Deep ResNet Blocks Sequentially Using Boosting Theory (I) 
Huang, Furong  Univ. of Maryland Coll. Park 
Ash, Jordan  Princeton Univ. 
Langford, John  Microsoft Res. 
Schapire, Robert  Microsoft Res. 

WeD3 
Butternut 
Polar Codes & Applications 
Regular Session 
Chair: Kliewer, Joerg  New Jersey Inst. of Tech 

15:3015:50, Paper WeD3.1  
Generalized Partial Orders for Polar Code BitChannels 
Wu, Wei  Univ. of California, San Diego 
Fan, Bing  Univ. of California, San Diego 
Siegel, Paul H.  Univ. of California, San Diego 
Keywords: Coding Theory, Coding Techniques and Applications, Information Theory
Abstract: We study partial orders (POs) for the synthesized bitchannels of polar codes. First, we consider complementary bitchannel pairs whose Bhattacharyya parameters over the binary erasure channel (BEC) exhibit a symmetry property and provide insight into the alignment of polarized sets of bitchannels for the BEC and general binaryinput memoryless symmetric (BMS) channels. Next, we give an alternative proof of a recently presented PO for bitchannels and use the underlying idea to extend the bitchannel ordering to some additional cases. In particular, the bitchannel ordering for a given code blocklength is used to generate additional bitchannel ordering relationships for larger blocklengths, generalizing previously known POs. Examples are provided to illustrate the new POs.


15:5016:10, Paper WeD3.2  
On the Construction of Polar Codes for Achieving the Capacity of Marginal Channels 
Torfi, Amirsina  West Virginia Univ 
Soleymani, Sobhan  West Virginia Univ 
Aram, Siamak  Univ. of Maryland, Baltimore County 
T. Vakili, Vahid  Iran Univ. of Science and Tech 
Keywords: Reliability, Security and Trust, Coding Theory, Information Theoretic Approaches in Wireless Communications
Abstract: Achieving security against adversaries with unlimited computational power is of great interest in a communication scenario. Since polar codes are capacity achieving codes with low encodingdecoding complexity and they can approach perfect secrecy rates for binaryinput degraded wiretap channels in symmetric settings, they are investigated extensively in the literature recently. In this paper, a polar coding scheme to achieve secrecy capacity in nonsymmetric binary input channels is proposed. The proposed scheme satisfies security and reliability conditions. The wiretap channel is assumed to be stochastically degraded with respect to the legitimate channel and message distribution is uniform. The information set is sent over channels that are good for Bob and bad for Eve. Random bits are sent over channels that are good for both Bob and Eve. A frozen vector is chosen randomly and is sent over channels bad for both. We prove that there exists a frozen vector for which the coding scheme satisfies reliability and security conditions and approaches the secrecy capacity. We further empirically show that in the proposed scheme for nonsymmetric binaryinput discrete memoryless channels, the equivocation rate achieves its upper bound in the whole capacityequivocation region.


16:1016:30, Paper WeD3.3  
On Iterative Decoding of Polar Codes: ScheduleDependent Performance and Constructions 
Schnelling, Christopher  RWTH Aachen Univ 
Amraue, Yassine  RWTH Aachen Univ 
Schmeink, Anke  RWTH Aachen Univ 
Keywords: Coding Techniques and Applications, Coding Theory, Information Theory
Abstract: Polar codes asymptotically achieve the symmetric capacity of any binaryinput discrete memoryless channel under sequential decoding algorithms such as successive cancellation decoding. However, for applications with high throughput requirements, other decoding approaches may be a better fit, as sequential decoders are inherently difficult to parallelize in order to increase their throughput. Iterative beliefpropagation decoding may pose a valid approach for such parallel decoders. In this work, we present an extensive study of polar codes under both sequential and parallel message schedules in iterative decoding, and reveal a strong dependency of the code performance on the schedule used for decoding. To overcome performance impairments observed when using polar codes optimized for sequential scheduling under parallel schedules, we present a method to optimize codes for iterative decoders working with parallel scheduling.


16:3016:50, Paper WeD3.4  
Polar Coding for Multiple Descriptions Using Monotone Chain Rules 
Bhatt, Alankrita  UCSD 
Ghaddar, Nadim  UCSD 
Wang, Lele  Stanford Univ 
Keywords: Coding Techniques and Applications, Coding Theory, Network Information Theory
Abstract: In this paper, we present a polar coding scheme for the multiple description coding problem. The proposed scheme improves upon the existing joint polarization based scheme by Shi, Song, Tian, Chen, and Dumitrescu and achieves the entire El GamalCover inner bound for this problem.


16:5017:10, Paper WeD3.5  
Polar Codes for Channels with Deletions 
Tian, Kuangda  Beihang Univ 
Fazeli, Arman  Univ. of California, San Diego 
Vardy, Alexander  Univ. of California, San Diego 
Liu, Rongke  Beihang Univ 
Keywords: Coding Theory, Coding Techniques and Applications, Information Theory
Abstract: A polar coding scheme for channels with deletions has been proposed recently, in which the information bits are precoded with CRC that helps to detect the location of deletions with high precision. Successive Cancellation (SC) decoding then treats these symbols as simple erasures. Given d as the number of deleted symbols, the decoding algorithm requires to check all binom{ N}{d} combinations of the deleted locations to find one that agrees with the CRC. This escalates the overall decoding complexity to mathcal{O}(N^{d+1}log N), which is not practical even when d is a small number. In this paper, we propose an alternative decoding method for polar codes in presence of deletion errors. This method can be regarded as an extension of SC decoding to the deletion channel. The proposed algorithm is based on the recursive structure of polar codes and it directly adopts the outputs of deletion channel to perform decoding without any preprocessing. In other words, it is no longer required to check all binom{N}{d} possible locations of the deletions. Instead, each node in the proposed polar decoder propagates its uncertainty about deletion pattern to the nodes in the next decoding layer. Eventually, with high probability, the correct deletion pattern becomes visible when the last polar bitchannel is decoded. The resulting decoding complexity is only mathcal{O}(d^2Nlog N), which scales polynomially rather than exponentially with the number of deletions.


17:1017:30, Paper WeD3.6  
Joint CoordinationChannel Coding for Strong Coordination Over Noisy Channels Based on Polar Codes 
Obead, Sarah  New Jersey Inst. of Tech 
Kliewer, Joerg  New Jersey Inst. of Tech 
Vellambi, Badri  Australian National Univ 
Keywords: Information Theory, Information Theoretic Approaches in Wireless Communications, Decentralized Control Systems
Abstract: We construct a joint coordinationchannel polar coding scheme for strong coordination of actions between two agents mathsf X and mathsf Y, which communicate over a discrete memoryless channel (DMC) such that the joint distribution of actions follows a prescribed probability distribution. We show that polar codes are able to achieve our previously established inner bound to the strong noisy coordination capacity region and thus provide a constructive alternative to a random coding proof. Our polar coding scheme also offers a constructive solution to a channel simulation problem where a DMC and shared randomness are together employed to simulate another DMC. In particular, our proposed solution is able to utilize the randomness of the DMC to reduce the amount of local randomness required to generate the sequence of actions at agent mathsf Y. By leveraging our earlier random coding results for this problem, we conclude that the proposed joint coordinationchannel coding scheme strictly outperforms a separate scheme in terms of achievable communication rate for the same amount of injected randomness into both systems.


WeD4 
Pine 
Machine Learning & Data Analysis 
Regular Session 
Chair: Huang, Shuai  UIUC 

15:3015:50, Paper WeD4.1  
Streaming Principal Component Analysis in Noisy Settings (withdrawn from program) 
Mianjy, Poorya  Johns Hopkins Univ. 
Marinov, Teodor Vanislavov  Johns Hopkins Univ. 
Arora, Raman  Johns Hopkins Univ. 

15:5016:10, Paper WeD4.2  
Learning Mixtures of Sparse Linear Regressions Using Sparse Graph Codes 
Yin, Dong  UC Berkeley 
Pedarsani, Ramtin  UC Santa Barbara 
Chen, Yudong  Cornell Univ 
Ramchandran, Kannan  UC Berkeley 
Keywords: Learning and Inference, Coding Theory, Signal Acquisition, Coding, and Retrieval
Abstract: In this paper, we consider the mixture of sparse linear regressions model. Let beta^(1), . . . , beta^(L) in C^n be L unknown sparse parameter vectors with a total of K nonzero coefficients. Noisy linear measurements are obtained in the form y_i = x^H_i beta^{l_i} + w_i, each of which is generated randomly from one of the sparse vectors with the label l_i unknown. The goal is to estimate the parameter vectors efficiently with low sample and computational costs. This problem presents significant challenges as one needs to simultaneously solve the demixing problem of recovering the labels l_i as well as the estimation problem of recovering the sparse vectors beta^(l). Our solution to the problem leverages the connection between modern coding theory and statistical inference. We introduce a new algorithm, MixedColoring, which samples the mixture strategically using query vectors x_i constructed based on ideas from sparse graph codes. Our novel code design allows for both efficient demixing and parameter estimation. The algorithm achieves the orderoptimal sample and time complexities of Theta(K) in the noiseless setting, and nearoptimal Theta(K polylog(n)) complexities in the noisy setting. In one of our experiments, to recover a mixture of two regressions with dimension n = 500 and sparsity K = 50, our algorithm is more than 300 times faster than EM algorithm, with about 1/3 of its sample cost.


16:1016:30, Paper WeD4.3  
Scalable KernelBased Learning Via LowRank Approximation of Lifted Data 
Sheikholeslami, Fatemeh  Univ. of Minnesota 
Giannakis, Georgios  Univ. of Minnesota 
Keywords: Learning and Inference, Statistical Signal Processing, Optimization
Abstract: Despite their welldocumented capability in modeling nonlinear functions, kernel methods fall short in largescale learning tasks due to their excess memory and computational requirements. The present work introduces a novel kernel approximation approach from a dimensionality reduction point of view on virtual lifted data. The proposed framework accommodates feature extraction while considering limited storage and computational availability, and subsequently provides kernel approximation by a linear innerproduct over the extracted features. Probabilistic guarantees on the generalization of the proposed task is provided, and efficient solvers with provable convergence guarantees are developed. By introducing a sampling step which precedes the dimensionality reduction task, the framework is further broadened to accommodate learning over large datasets. The connection between the novel method and Nystr¨om kernel approximation algorithm with its modifications is also presented. Empirical tests validate the effectiveness of the proposed approach.


16:3016:50, Paper WeD4.4  
An Approximation of the CPRank of a Partially Sampled Tensor 
Ashraphijuo, Morteza  Columbia Univ 
Wang, Xiaodong  Columbia Univ 
Aggarwal, Vaneet  Purdue Univ 
Keywords: Machine Learning and Learning Theory, Learning and Inference, Optimization
Abstract: We exploit the recent algebraic geometry analyses that study the fundamental conditions on the locations of the sampled entries for finite completability of lowrank sampled tensor to treat the problem of CPrank approximation for a partially sampled tensor. Particularly, the goal is to approximate the unknown rank based on the locations of the sampled entries, i.e., the sampling pattern, and the rank of an arbitrary given completion. First we provide an upper bound on the unknown CPrank with probability one assuming that the sampling pattern satisfies the proposed combinatorial properties. However, the proposed combinatorial properties may be hard to verify. Hence, we also provide probabilistic versions of such bounds that hold with high probability assuming that the sampling probability is above a threshold, i.e., we provide the sampling probability that results the sampling pattern satisfies the proposed combinatorial properties with high probability. In addition, these upper bounds can be exactly equal to the unknown CPrank given the lowestrank completion. To illustrate how tight our proposed upper bounds are, we have provided some numerical results for the case of twoway tensor, i.e., matrix, in which we applied the nuclear norm minimization to find a lowrank completion of the sampled data and observe that the proposed upper bound is almost equal to the true unknown rank.


16:5017:10, Paper WeD4.5  
If It Ain't Broke, Don't Fix It: Sparse Metric Repair 
Gilbert, Anna  Univ. of Michigan 
Jain, Lalit  Univ. of Michigan 
Keywords: Data Analytics, Optimization, Machine Learning and Learning Theory
Abstract: Many modern dataintensive computational problems either require, or benefit from distance or similarity data that adhere to a metric. The algorithms run faster or have better performance guarantees. Unfortunately, in real applications, the data are messy and values are noisy. The distances between the data points are far from satisfying a metric. Indeed, there are a number of different algorithms for finding the closest set of distances to the given ones that also satisfy a metric (sometimes with the extra condition of being Euclidean). These algorithms can have unintended consequences; they can change a large number of the original data points, and alter many other features of the data. The goal of sparse metric repair is to make as few changes as possible to the original data set or underlying distances so as to ensure the resulting distances satisfy the properties of a metric. In other words, we seek to minimize the sparsity (or the ell_0 ``norm'') of the changes we make to the distances subject to the new distances satisfying a metric. We give three different combinatorial algorithms to repair a metric sparsely and discuss their performance. In one setting the algorithm is guaranteed to return the sparsest solution and in the other settings, the algorithms repair the metric. Without prior information, the algorithms run in time proportional to the cube of the number of input data points and, with prior information we can reduce the running time considerably.


17:1017:30, Paper WeD4.6  
Restless Streaming Bandits: Scheduling Scalable Video in Wireless Networks 
Hosseini, Amir  NYU Tandon School of Engineering 
Panwar, Shivendra  Pol. Inst. of NYU 
Keywords: Wireless Communication Systems, Optimization, Network Games and Algorithms
Abstract: In this paper, we consider the problem of optimal scalable video delivery to mobile users in wireless networks given arbitrary Quality Adaptation (QA) mechanisms. In current practical systems, QA and wireless channel scheduling are performed independently by the content provider and network operator, respectively. While most research has been focused on jointly optimizing these two tasks, the high complexity that comes with a joint approach makes the implementation impractical. Therefore, we present a scheduling mechanism that takes the QA logic of each user as input and optimizes the scheduling accordingly. Hence, there is no need for centralized QA and crosslayer interactions are minimized. We model the QAadaptive scheduling and the jointly optimal problem as a Restless Bandit and a Multiuser Semi Markov Decision Process, respectively in order to compare the loss incurred by not employing a jointly optimal scheme. We then present heuristic algorithms in order to achieve the optimal outcome of the Restless Bandit solution, assuming the base station has knowledge of, but no control over, the underlying quality adaptation of each user (QAAware). We also present a simplified heuristic without the need for any higher layer knowledge at the base station (QABlind). We show that our QAAware strategy can achieve up to two times improvement in network utilization compared to popular baseline algorithms such as Proportional Fairness.


WeD5 
Lower Level 
Sequential Methods 
Invited Session 
Chair: Fellouris, Georgios  Univ. of Illinois 
CoChair: Veeravalli, Venu  Univ. of Illinois 
Organizer: Fellouris, Georgios  Univ. of Illinois 
Organizer: Veeravalli, Venu  Univ. of Illinois 

15:3015:50, Paper WeD5.1  
An FDROriented Approach to Multiple Sequential Fault Detection and Isolation (I) 
Chen, Jie  Univ. of Science and Tech. of China 
Zhang, Wenyi  Univ. of Science and Tech. of China 
Poor, H. Vincent  Princeton Univ 
Keywords: Statistical Signal Processing, Detection and Estimation
Abstract: The problem of sequential fault detection and isolation in multiple data streams is considered. In this work, it is assumed that many independent parallel data streams, each of which has a (possibly infinite) change point, are sequentially observed with a maximum sampling constraint. The prechange data follow a known distribution, and the postchange data follow one of J possible distributions. A sequential procedure is proposed to detect the changes for all data streams, and to isolate the types of changes upon their detection. The sequential procedure is shown to control the false discovery rate. An asymptotic upper bound on the average detection delay over the parallel data streams is also derived. A simulation study is presented to illustrate the proposed procedure and to corroborate the analysis.


15:5016:10, Paper WeD5.2  
Detecting ChangePoints in Markov Processes for Blood Pressure Monitoring (I) 
Bonifonte, Anthony  Georgia Inst. of Tech. 
Xie, Yao  Georgia Inst. of Tech. 
Ayer, Turgay  Georgia Inst. of Tech. 

16:1016:30, Paper WeD5.3  
Nonparametric Sequential Change Detection for HighDimensional Problems (I) 
Yilmaz, Yasin  Univ. of South Florida 

16:3016:50, Paper WeD5.4  
Sequential Estimation of a Binomial Probability (I) 
Yaacoub, Tony  Georgia Inst. of Tech. 
Moustakides, George  Univ. of Patras, Greece and Rutgers Univ. USA 
Mei, Yajun  Georgia Inst. of Tech. 

16:5017:10, Paper WeD5.5  
Quickest Search for a Transient Changes in a Time Series (I) 
Tajer, Ali  Rensselaer Pol. Inst. 

17:1017:30, Paper WeD5.6  
Anomaly Detection under a Nonlinear System Cost Objective Function (I) 
Gurevich, Andrey  BenGurion Univ. of the Negev 
Cohen, Kobi  BenGurion Univ. of the Negev 
Zhao, Qing  Cornell Univ 
Keywords: Intrusion/Anomaly Detection and Diagnosis, Detection and Estimation, Learning and Inference
Abstract: We consider the problem of anomaly detection among K heterogeneous processes. At each given time, a single observation (or a fixed batch of observations) is collected from a chosen process. The observations from each chosen process follow two different distributions, depending on whether the process is normal or abnormal. Each anomalous process incurs a cost until its anomaly is identified and fixed, and the cost is nonlinear (specifically, polynomial with degree d) with the duration of the anomalous state. The objective is a sequential search strategy that minimizes the total expected cost incurred by all the processes during the detection process under reliability constraints. We propose a search algorithm that consists of exploration, exploitation, and sequential testing phases.We analyze the approximation ratio and the regret of the algorithm for d 1, and establish its asymptotic optimality for d = 1.


17:3017:50, Paper WeD5.7  
Decentralized Sequential Composite Hypothesis Test Based on OneBit Communication (I) 
Liu, Jingchen  Columbia Univ 
Li, Xiaoou  Univ. of Minnesota 
Li, Shang  Columbia Univ 
Wang, Xiaodong  Columbia Univ 
 