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

ThA1 
Library 
Foundations of the Sharing Economy (II) 
Invited Session 
Chair: Varshney, Lav R.  Univ. of Illinois at UrbanaChampaign 
CoChair: Basar, Tamer  Univ. of Illinois 
Organizer: Varshney, Lav R.  Univ. of Illinois at UrbanaChampaign 
Organizer: Basar, Tamer  Univ. of Illinois 
Organizer: Bose, Subhonmesh  Univ. of Illinois at Urbana Champaign 

08:3008:50, Paper ThA1.1  
Matching While Learning (I) 
Johari, Ramesh  Stanford Univ. 
Kamble, Vijay  UC Berkeley 
Kanoria, Yashodhan  Stanford Univ. 

08:5009:10, Paper ThA1.2  
Learning from Reviews (I) 
Acemoglu, Daron  MIT 
Makhdoumi, Ali  MIT 
Malekian, Azarakhsh  Univ. of Toronto 
Ozdaglar, Asu  MIT 

09:1009:30, Paper ThA1.3  
A Game Theoretic Approach to Promotion Design in TwoSided Platforms (I) 
Ajorlou, Amir  Massachusetts Inst. of Tech 
Jadbabaie, Ali  Massachusetts Inst. of Tech 
Keywords: Pricing and Congestion Control, Distributed and LargeScale Systems, Optimization
Abstract: Twosided platforms often face a high degree of uncertainty in the availability of their service providers, which can harm the profit of the platform as it may result in too many or too few providers available for service. We propose a gametheoretic approach to optimal promotion design as a means by which platforms can influence providers' availability. We consider a mass of service providers in a twosided market, each can be either active or not. The price paid for a service is decreasing with the number of active providers and increasing with a known demand. A provider participates only if his expected earning, that is the expected price less a fixed percentage held as the commission by the platform, passes his "reserved price". There are two types of uncertainties in reserved prices. An idiosyncratic uncertainty which models the variation of reserved prices across providers; And a systematic uncertainty, representing the uncertainty in the overall average reserved price, which also accounts for the uncertainty in the number of active providers. We view the decision making of providers as a global game of strategic substitutes. Focusing on the threshold equilibria of the game, we formulate the optimal promotion design as an infinite dimensional convex optimization problem, where we show that the optimal decreasing promotion program is a combination of a "bonus at all prices" and a "lowpriceonly bonus".


09:3009:50, Paper ThA1.4  
Pricing in Dynamic TwoSided Markets (I) 
Banerjee, Siddhartha  Cornell Univ. 

09:5010:10, Paper ThA1.5  
The Impact of Privacy on Free Service Markets (I) 
Huang, Chong  Arizona State Univ. 
Sankar, Lalitha  Arizona State Univ. 

ThA2 
Solarium 
Information Theory and Applications 
Invited Session 
Chair: Viswanath, Pramod  Univ. of Illinois 
Organizer: Viswanath, Pramod  Univ. of Illinois 

08:3008:50, Paper ThA2.1  
On the ZeroError Capacity of Channels with Noisy Feedback (I) 
Asadi, Meysam  Univ. of Illinoice at Chicago 
Devroye, Natasha  Univ. of Illinois at Chicago 
Keywords: Network Information Theory, Information Theory
Abstract: The zeroerror capacity of discrete memoryless channels (DMC) with noiseless feedback when variablelength codes are permitted has been shown to be positive whenever there exists at least one channel output ``disprover'', i.e. a channel output that cannot be reached from at least one of the inputs. Furthermore, whenever there exists a disprover, this variablelength zeroerror capacity attains the Shannon (smallerror) capacity. Here, we study the zeroerror capacity of a DMC when the channel feedback is noisy. We show that the variablelength zeroerror capacity with noisy feedback is lower bounded by the forward channel's zeroundetectederror capacity, and show that under certain conditions this is tight. We survey conditions under which the zeroerror capacity without feedback, with perfect feedback, and with noisy feedback, are positive.


08:5009:10, Paper ThA2.2  
Gaussian Variable PacketError Coding (I) 
Fan, Xiaoqing  Qualcomm 
Wagner, Aaron  Cornell Univ 
Keywords: Network Information Theory, Coding Techniques and Applications
Abstract: We consider the problem of communicating a Gaussian source over several paths in a network, some unknown subset of which are subject to adversarial errors. The aim is to encode the source in such a way that one can provide a meansquare error distortion guarantee at the receiver that improves as the number of patherrors decreases. We show that a natural design based on errorcorrecting and errordetecting codes is not orderoptimal in the rate as the distortion constraint tends to zero, but a hybrid scheme that involves a form of uncoded transmission is.


09:1009:30, Paper ThA2.3  
Porcupine Neural Networks: (Almost) All Local Optima Are Global (I) 
Feizi, Soheil  Stanford Univ. 
Javadi, Hamid  Stanford Univ. 
Jesse, Zhang  Stanford Univ. 
Tse, David  UC Berkeley 

09:3009:50, Paper ThA2.4  
Sparse Group Testing Codes for LowEnergy Massive Random Access (I) 
Inan, Huseyin A.  Stanford Univ 
Kairouz, Peter  Stanford Univ 
Ozgur, Ayfer  Stanford Univ 
Keywords: Information Theoretic Approaches in Wireless Communications
Abstract: We present random access protocols for machinetype communication where a massive number of lowenergy wireless devices want to occasionally transmit short information packets. We focus on the device discovery problem, with extensions to joint discovery and data transmission as well as data transmission without communicating the device identities. We formulate this problem as a combinatorial group testing problem, where the goal is to exactly identify the set of at most d defective items from a pool of n items. We translate the energy constraint at the wireless physical layer to a constraint on the number of tests each item can participate in, and study the resulting ``sparse'' combinatorial group testing problem. The celebrated result for the combinatorial group testing problem is that the number of tests t can be made logarithmic in n when d = O(log n). However, stateoftheart group testing codes require the items to be tested w = Omega(frac{d log n}{log d + log log n} ) times. In our sparse setting, we restrict the number of tests each item can participate in by w_{max}. We show that t decreases suddenly from n to (d+1)sqrt{n} when w_{max} is increased from d to d+1. If w_{max}=ld+1 for any positive integer l such that ld+1 leqsqrt[l+1]{n}, we can achieve t=(ld+1)n^{1/(l+1)}. We also prove a nearly matching lower bound. These results reveal a favorable tradeoff between energy and spectral efficiency for random access.


09:5010:10, Paper ThA2.5  
EnergyEfficiency and RandomAccess (I) 
Polyanskiy, Yury  MIT 

10:1010:30, Paper ThA2.6  
Belief Propagation, Bethe Approximation and Polynomials (I) 
Straszak, Damian  EPFL 
Vishnoi, Nisheeth Kumar  EPFL 
Keywords: Optimization, Learning and Inference
Abstract: Factor graphs are important models for representing probability distributions in machine learning, coding theory, and statistical physics. Several computational problems, such as computing marginals and computing partition functions, arise when working with factor graphs. Bethe approximation is an optimizationbased framework for computing partition functions and is known to be related to belief propagation, as the stationary points of the Bethe approximation coincide with the fixed points of belief propagation. However, the relation between the Bethe approximation and the true partition function is not well understood and has been recently a topic of study. It has been observed that for a few classes of factor graphs, Bethe approximation gives a lower bound on the partition function. This observation has been rigorously proved for permanents and for attractive models. Here we show that if the local constraints satisfy a certain geometric property, then Bethe approximation is a lower bound to the partition function. We arrive at our result by viewing factor graphs through the lens of polynomials. We reformulate the Bethe approximation as a polynomial optimization problem and state a sufficient condition for the lower bound to hold inspired by recent developments in the theory of real stable polynomials. We believe that this new way of viewing factor graphs might lead to a better understanding of the belief propagation algorithm and factor graphs in general.


ThA3 
Butternut 
LDPC Codes 
Regular Session 
Chair: Heidarzadeh, Anoosheh  Texas A&M Univ 

08:3008:50, Paper ThA3.1  
A Generalized Algebraic Approach to Optimizing SCLDPC Codes 
Beemer, Allison  Univ. of Nebraska  Lincoln 
Habib, Salman  New Jersey Inst. of Tech 
Kelley, Christine  Univ. of Nebraska  Lincoln 
Kliewer, Joerg  New Jersey Inst. of Tech 
Keywords: Coding Theory, Coding Techniques and Applications, Performance Analysis
Abstract: Spatially coupled lowdensity paritycheck (SCLDPC) codes are sparse graph codes that have recently become of interest due to their capacityapproaching performance on memoryless binary input channels. In this paper, we unify all existing SCLDPC code construction methods under a new generalized description of SCLDPC codes based on algebraic lifts of graphs. We present an improved lowcomplexity counting method for the special case of (3,3)absorbing sets for arraybased SCLDPC codes, which we then use to optimize permutation assignments in SCLDPC code construction. We show that codes constructed in this way are able to outperform previously published constructions, in terms of the number of dominant absorbing sets and with respect to both standard and windowed decoding.


08:5009:10, Paper ThA3.2  
On LDPC Decoding with Natural Redundancy 
Upadhyaya, Pulakesh  Texas A&M Univ. Coll. Station 
Jiang, Anxiao (Andrew)  Texas a M Univ 
Keywords: Coding Techniques and Applications, Data Storage
Abstract: Bigdata storage has substantial challenges due to accumulative noise in storage media. To ensure its longterm reliability, new techniques for error correction are being explored.This paper studies how to discover natural redundancy in data and use it for error correction. It explores the combination of natural redundancy decoding with lowdensity paritycheck (LDPC) codes for enhanced errorcorrection performance. It derives analytical equations for the density evolution of LDPC decoding given information from naturalredundancy decoders. It proposes a theoretical model for compressed languages, and studies the performance of iterative decoding between the LDPC decoder and the naturalredundancy decoder. It also presents an upper bound to the code sizes of errorcorrecting codes given the assistance from naturalredundancy decoders.


09:1009:30, Paper ThA3.3  
Serial Concatenation of Reed Muller and LDPC Codes with Low Error Floor 
Xiao, Xin  Univ. of Arizona 
Nasseri, Mona  Univ. of California, Davis 
Vasic, Bane  Univ. of Arizona 
Lin, Shu  Univ. of California, Davis 
Keywords: Coding Techniques and Applications, Data Storage, Wireless Communication Systems
Abstract: In this paper, we propose a concatenated coding scheme involving an outer ReedMuller (RM) code and an inner Finite Field lowdensity parity check (LDPC) code of medium length and high rate. It lowers the error floor of inner Finite Field LDPC code. This concatenation scheme offers flexibility in design and it is easy to implement. In addition, the decoding works in a serial turbo manner and has no harmful trapping sets of size smaller than the minimum distance of the outer code. The simulation results indicate that the proposed serial concatenation can eliminate the dominant trapping sets of the inner Finite Field LDPC code.


09:3009:50, Paper ThA3.4  
Lower Bounds for Quantized LDPC MinSum Decoders Based on Absorbing Sets 
Hatami, Homayoon  Univ. of Notre Dame, Indiana, USA 
G. M. Mitchell, David  Klipsch School of Electrical and Computer Engineering, New Mexic 
Costello, Daniel  Univ. of Notre Dame 
Fuja, Thomas E.  Univ. of Notre Dame 
Keywords: Coding Theory
Abstract: Previously published lower bounds on the error floor performance of lowdensity paritycheck (LDPC) codes with quantized sumproduct algorithm (SPA) decoders need modification to apply to minsum algorithm (MSA) decoders. In this paper we show that, due to the suboptimality of MSA decoders, certain assumptions that apply to SPA decoders are not valid for MSA decoders. Based on appropriately modified assumptions, an improved technique is then proposed to evaluate lower bounds on the error floor performance of LDPC codes for an additive white Gaussian noise channel and a quantized MSA decoder. This new technique not only results in error floor bounds for MSA decoders, but also for SPA decoders. The obtained bound is based on an absorbing set, and a good error floor approximation can be obtained when the multiplicity of the absorbing set is known.


09:5010:10, Paper ThA3.5  
Stopping Set Elimination for LDPC Codes 
Jiang, Anxiao (Andrew)  Texas a M Univ 
Upadhyaya, Pulakesh  Texas A&M Univ. Coll. Station 
Wang, Ying  Texas A&M Univ 
Narayanan, Krishna  Texas A&M Univ 
Zhou, Hongchao  California Inst. of Tech 
Sima, Jin  California Inst. of Tech 
Bruck, Jehoshua  Caltech 
Keywords: Coding Techniques and Applications, Data Storage
Abstract: This work studies the StoppingSet Elimination Problem, namely, given a stopping set, how to remove the fewest erasures so that the remaining erasures can be decoded by belief propagation in k iterations (including k = ∞). The NPhardness of the problem is proven. An approximation algorithm is presented for k = 1. And efficient exact algorithms are presented for general k when the stopping sets form trees.


ThA4 
Pine 
Game Theory 
Regular Session 
Chair: Silva, Alonso  Nokia Bell Labs 

08:3008:50, Paper ThA4.1  
Economic Inefficiency in Resource Allocation Games 
Tota, Praneeth  Illinois Inst. of Tech 
Kapoor, Sanjiv  Illinois Inst. of Tech 
Grimmer, Benjamin  Illinois Inst. of Tech 
Keywords: Network Games and Algorithms, Pricing and Congestion Control
Abstract: In this paper we consider the economic efficiency of multitiered resource allocation bidding systems where allocations are based on monetary bids leading to a competitive congestion game model. We consider resources that are priced and proportionally divided among the users. This paper focuses on two aspects: (i) the impact of wealth and (ii) the inefficiency of Nash equilibrium. Motivated by the recent debate on NetNeutrality we consider the impact of two distinct categories of players, one with higher endowment than the other. We define Wealth impact factor (WIF) as the measure of disparity of payoffs between the rich and the poor when the game is at NE. Surprisingly, improving WIF requires quadratic effort by the poor players. which shows the disparity between the rich and the poor when considering multiple tiers of service. We also consider the inefficiency of Nash equilibrium that arises in resource allocation. The inefficiency of utilities achieved in Nash equilibrium, measured by the price of anarchy, has been shown to be at least 3/4 by Johari and Tsitsiklis. Since the effective utilities of the players depends on the payments, we define the social objective as a function of payoffs and express the price of anarchy in terms of a measure that we term as the economic efficiency factor (ECF). We show show that this inefficiency can be as large as n, the number of players for linear utilities. Interestingly, for strictly concave utilities the ECF


08:5009:10, Paper ThA4.2  
Evolution of Social Power for Opinion Dynamics Networks 
Iglesias Rey, Susana  Nokia Bell Labs 
Reyes, Patricio  Tech. Inst. for Industrial Mathematics (ITMATI) 
Silva, Alonso  Nokia Bell Labs 
Keywords: Network Games and Algorithms, Dynamic Games
Abstract: This article studies the evolution of opinions and interpersonal influence structures in a group of agents as they discuss a sequence of issues, each of which follows an opinion dynamics model. In this work, we propose a general opinion dynamics model and an evolution of interpersonal influence structures based on the model of reflected appraisals proposed by Friedkin. Our contributions can be summarized as follows: (i) we introduce a model of opinion dynamics and evolution of interpersonal influence structures between issues viewed as a best response cost minimization response to the neighbors actions, (ii) we show that DeGroot's and FriedkinJohnsen's models of opinion dynamics and their evolution of interpersonal influence structures are particular cases of our proposed model, and (iii) we prove the existence of an equilibrium. This work is a step towards providing a solid formulation of the evolution of opinions and interpersonal influence structures over a sequence of issues.


09:1009:30, Paper ThA4.3  
On the Geometry of Nash and Correlated Equilibria with Cumulative Prospect Theoretic Preferences 
Phade, Soham  Univ. of California, Berkeley 
Anantharam, Venkat  Univ. of California, Berkeley 
Keywords: Dynamic Games
Abstract: It is known that the set of all correlated equilibria of an nplayer cooperative game is a convex polytope and includes all the Nash equilibria. Further, the Nash equilibria all lie on the boundary of this polytope. We study the geometry of both these equilibrium notions when the players have cumulative prospect theoretic (CPT) preferences. The set of CPT correlated equilibria includes all the CPT Nash equilibria but it need not be a convex polytope. We show that it can, in fact, be disconnected. However, all the CPT Nash equilibria continue to lie on its boundary. We also characterize the sets of CPT correlated equilibria and CPT Nash equilibria for all 2x2 games.


09:3009:50, Paper ThA4.4  
A Distributed, Dynamical System View of Finite, Static Games 
Li, Yuke  Yale Univ 
Liu, Fengjiao  Yale Univ 
Morse, Stephen  Yale Univ 
Keywords: Optimization, Distributed and LargeScale Systems
Abstract: This paper contains a reformulation of any nplayer finite, static game into a framework of distributed, dynamical system based on agents' payoffbased deviations. The reformulation generalizes the method employed in the second part of the study of countries' relation formation problem in cite{system} to the case of any finite, static game. In the paper two deviation rules are provided and possible applications of this framework are discussed.


09:5010:10, Paper ThA4.5  
Optimal Pricing Policy of Network Goods 
Makhdoumi, Ali  MIT 
Malekian, Azarakhsh  Univ. of Toronto 
Ozdaglar, Asu  MIT 
Keywords: Network Games and Algorithms, Dynamic Games, Pricing and Congestion Control
Abstract: We study the optimal pricing policy of a strategic monopolist selling durable goods in a dynamic pricing game with multiple rounds. Customers are forwardlooking and experience a (positive) network externality, i.e., each customer’s utility depends not only on her valuation of the item and the offered price, but also the weighted sum of the number of other customers who have purchased the item. The monopolist announces and commits to a price sequence and strategic buyers decide on when (if ever) to buy the good in a perfect Bayesian equilibrium. We fully characterize the optimal pricing policy and show that it is linearly increasing in time, where the slope of the price path is described by a single network measure: sum of the entries of the inverse of network externality matrix, termed network effect. Our result shows that increasing the number of rounds and network effect increases both revenue and social welfare. We also establish that increasing network asymmetry, increases the network effect which in turn increases the revenue.


ThA5 
Lower Level 
Deep Learning 
Invited Session 
Chair: Schwing, Alexander  Univ. of Illinois UrbanaChampaign 
Organizer: Schwing, Alexander  Univ. of Illinois UrbanaChampaign 
Organizer: Do, Minh  Univ. of Illinois 

08:3008:50, Paper ThA5.1  
Learning with Little Data (I) 
Zemel, Richard  Univ. of Toronto 

08:5009:10, Paper ThA5.2  
Learning Representations for Active Vision (I) 
Olshausen, Bruno  UC Berkeley 

09:1009:30, Paper ThA5.3  
DeepCodec: Adaptive Sensing and Recovery Via Deep Convolutional Neural Networks (I) 
Mousavi, Ali  Rice Univ 
Dasarathy, Gautam  Univ. of Wisconsin  Madison 
Baraniuk, Richard  Rice Univ 
Keywords: Learning and Inference, Computational Models and Representations, Signal Acquisition, Coding, and Retrieval
Abstract: We develop a novel computational sensing framework for sensing and recovering structured signals. When trained on a set of representative signals, our framework learns to take undersampled measurements and recover signals from these measurements using a deep convolutional neural network. In other words, it learns a transformation from the original signals to a nearoptimal number of undersampled measurements and the inverse transformation from measurements to signals. This is in contrast to conventional compressive sensing (CS) systems that use random linear measurements and convex optimization or iterative algorithms for signal recovery.


09:3009:50, Paper ThA5.4  
Statistics, Computation and Learning with Graph Neural Networks (I) 
Bruna, Joan  New York Univ. 

09:5010:10, Paper ThA5.5  
Neural Map: Structured Memory for Deep Reinforcement Learning (I) 
Salakhutdinov, Ruslan  Carnegie Mellon Univ. 

ThB1 
Library 
Networks Learning and Algorithms I 
Invited Session 
Chair: Vaidya, Nitin  Univ. of Illinois 
Organizer: Hajek, Bruce  Univ. of Illinois 
Organizer: Srikant, R  Univ. of Illinois 

10:3010:50, Paper ThB1.1  
Order Detection under Pairwise Measurements (I) 
Bagaria, Vivek Kumar  Stanford 
Tse, David  UC Berkeley 
Wu, Yihong  Univ. of Illinois 
Xu, Jiaming  PURDUE Univ. 

10:5011:10, Paper ThB1.2  
Community Detection and Invariance to Distribution (I) 
Brennan, Matthew  MIT 
Bresler, Guy  MIT 
Huleihel, Wasim  MIT 

11:1011:30, Paper ThB1.3  
Diffusion Source Localization in the ErdosRenyi Random Graph (I) 
Ying, Lei  Arizona State Univ. 
Zhu, Kai  Arizona State Univ. 

11:3011:50, Paper ThB1.4  
Towards InstanceOptimal Regret in Online Learning (I) 
Gupta, Varun  Univ. of Chicago 

11:5012:10, Paper ThB1.5  
SelfProgramming Networks: Architecture and Algorithms (I) 
Geng, Yilong  Stanford Univ. 
Liu, Shiyu  Stanford Univ. 
Wang, Feiran  Stanford Univ. 
Yin, Zi  Stanford Univ. 
Prabhakar, Balaji  Stanford Univ. 
Rosenblum, Mendel  Stanford Univ. 

12:1012:30, Paper ThB1.6  
Adaptive Matching for Expert Systems with Uncertain Task Types (I) 
Shah, Virag  Microsoft Res.  Inria Joint Center 
Gulikers, Lennart  MSRInria Joint Centre, Inria 
Massoulie, Laurent  MSRInria Joint Centre, Inria 
Vojnovic, Milan  London School of Ec 
Keywords: Adaptive Control and Automation, Machine Learning and Learning Theory
Abstract: Online twosided matching markets such as Q&A forums (e.g. StackOverflow, Quora) and online labour platforms (e.g. Upwork) critically rely on the ability to propose adequate matches based on imperfect knowledge of the two parties to be matched. This prompts the following question: Which matching recommendation algorithms can, in the presence of such uncertainty, lead to efficient platform operation? To answer this question, we develop a model of a task / server matching system. For this model, we give a necessary and sufficient condition for an incoming stream of tasks to be manageable by the system. We further identify a socalled backpressure policy under which the throughput that the system can handle is optimized. We show that this policy achieves strictly larger throughput than a natural greedy policy. Finally, we validate our model and confirm our theoretical findings with experiments based on logs of Math.StackExchange, a StackOverflow forum dedicated to mathematics.


ThB2 
Solarium 
Foundations of the Sharing Economy (I) 
Invited Session 
Chair: Bose, Subhonmesh  Univ. of Illinois at Urbana Champaign 
CoChair: Basar, Tamer  Univ. of Illinois 
Organizer: Varshney, Lav R.  Univ. of Illinois at UrbanaChampaign 
Organizer: Basar, Tamer  Univ. of Illinois 
Organizer: Bose, Subhonmesh  Univ. of Illinois at Urbana Champaign 

10:3010:50, Paper ThB2.1  
Coordinating Shared Experimentation in Dynamic Environments (I) (withdrawn from program) 
Mani, Ankur  Univ. of Minnesota 

10:5011:10, Paper ThB2.2  
Network Cournot Competition in Platform Markets (I) 
Lin, Weixuan  Cornell Univ 
Pang, John  California Inst. of Tech 
Bitar, Eilyan  Cornell Univ 
Wierman, Adam  California Inst. of Tech 
Keywords: Network Games and Algorithms, Optimization
Abstract: This paper studies network design and efficiency loss in online platforms using the model of networked Cournot competition. We consider two styles of platforms: open access platforms and discriminatory access platforms. In open access platforms, every firm can connect to every market, while discriminatory access platforms limit connections between firms and markets in order to improve upon social welfare. Our results provide tight bounds on the efficiency loss of both open access and discriminatory access platforms. In the case of open access platforms, we show that the efficiency loss at a Nash equilibrium is upper bounded by 3/2. In the case of discriminatory access platforms, we prove that under an assumption on the linearity of cost functions, a greedy algorithm for optimizing network connections can guarantee the efficiency loss at a Nash equilibrium is upper bounded by 4/3.


11:1011:30, Paper ThB2.3  
Congestion Control and Pricing in a Network of Electric Vehicle Public Charging Stations (I) 
Wong, Philip  Univ. of California Santa Barbara 
Alizadeh, Mahnoosh  Univ. of California Santa Barbara 
Keywords: Pricing and Congestion Control, Distributed and LargeScale Systems, Optimization
Abstract: In this work, we employ stochastic queueing models to design charging fees for a network of public electric vehicle charging stations operated by a Charging Network Operator (CNO). We assume that the CNO has access to statistics of electric vehicle (EV) users' mobility patterns that determine the demand for charging stations. We model geographically distributed charging stations as a network of unobservable queues with heterogeneous operational costs due to their geographical location and variations in the locational marginal price of electricity. Individual EV users are modeled as selfish agents that minimize their own expected cost of traveling and charging. To eliminate the inefficiencies of selfish routing in the queueing network and reduce aggregate electricity costs, the CNO designs charging fees to control the equilibrium travel and charging patterns on the charging station network. We consider the socially optimal solution to this charging fee design problem and analyze its performance. We also provide bounds on the Price of Anarchy in the charging network (including congestion and electricity costs).


11:3011:50, Paper ThB2.4  
A Structural Characterization of Market Power in Power Markets (I) 
Lin, Weixuan  Cornell Univ. 
Bitar, Eilyan  Cornell Univ. 

11:5012:10, Paper ThB2.5  
A Dynamic RideSourcing Game with Many Drivers 
Salhab, Rabih  Ec. Pol. De Montreal 
Le Ny, Jerome  Ec. Pol. De Montreal 
Malhame, Roland  École Pol. De Montréal 
Keywords: Dynamic Games, Decentralized Control Systems
Abstract: We consider a dynamic game model of ridesourcing, where a large number of private car owners provide rides to randomly appearing customers. Free drivers can travel around the city to improve their chance of being hired. They have access to the origindestination statistics, to the current customer requests and to information about traffic congestion and the timevarying connectivity of the road network. We show how each driver can compute a bestresponse strategy to the anticipated behavior of the other drivers, which leads to an approximate Nash equilibrium in the limit of an infinite number of players. The outputs of our discretetime model are the cars’ individual paths and the distribution of the free and busy drivers at each period. Finally, a numerical example illustrates three scenarios where a road closure in a city makes the cars desert an area. It shows how a financial incentive, namely increasing the ride fare in the deserted area, helps reestablish the ride service in that region.


12:1012:30, Paper ThB2.6  
The Merits of Sharing a Ride 
Ehsani, Pooyan  Concordia Univ 
Yu, Jia Yuan  Concordia Univ 
Keywords: Machine Learning and Learning Theory, Optimization
Abstract: The culture of sharing instead of ownership is sharply increasing in individuals behaviors. Particularly in transportation, concepts of sharing a ride in either carpooling or ridesharing have been recently adopted. Effective optimization approach to match passengers in realtime is the core of any ridesharing system. In this paper, we model ridesharing as an online matching problem on general graphs such that passengers do not drive private cars and use shared taxis. We propose an optimization algorithm to solve it. The outlined algorithm calculates the optimal waiting time when a passenger arrives. This leads to a matching with minimal overall overheads while maximizing the number of partnerships. To evaluate the behavior of our algorithm, we used NYC taxi reallife data set. Results represent substantial reduction in overall overheads.


ThB3 
Butternut 
Inverse Problems 
Invited Session 
Chair: Dokmanic, Ivan  Univ. of Illinois at UrbanaChampaign 
CoChair: Zhao, Zhizhen  Univ. of Illinois at UrbanaChampaign 
Organizer: Zhao, Zhizhen  Univ. of Illinois at UrbanaChampaign 
Organizer: Dokmanic, Ivan  Univ. of Illinois at UrbanaChampaign 

10:3010:50, Paper ThB3.1  
A Sampling Theorem for Deconvolution (I) 
Bernstein, Brett  New York Univ. 
FernandezGranda, Carlos  New York Univ. 

10:5011:10, Paper ThB3.2  
Multireference Alignment with Nonperiodic Distribution Is Easier (I) 
Sharon, Nir  Princeton Univ. 

11:1011:30, Paper ThB3.3  
Multireference Alignment, Invariant Features and CryoEM (I) 
Bendory, Tamir  Princeton Univ. 

11:3011:50, Paper ThB3.4  
Finite Sample Guarantees for PCA in NonIsotropic and DataDependent Noise (I) 
Vaswani, Namrata  Iowa State Univ 
Narayanamurthy, Praneeth  Iowa State Univ 
Keywords: Machine Learning and Learning Theory
Abstract: This work obtains finite sample guarantees for Principal Component Analysis (PCA) that hold even when the corrupting noise is nonisotropic, and a part (or all of it) is datadependent. Because of the latter, in general, the noise and the true data are correlated. The results in this work are a significant improvement over those given in our earlier work where this ``correlatedPCA" problem was first studied. In fact, in certain regimes, these imply that the sample complexity required to achieve subspace recovery error that is a constant fraction of the noise level is nearoptimal. Useful corollaries of our result include guarantees for PCA in sparse datadependent noise and for PCA with missing data. An important application of the former is in proving correctness of the subspace update step of a popular online algorithm for dynamic robust PCA.


11:5012:10, Paper ThB3.5  
Algebraic Variety Models for HighRank Matrix Completion (I) 
PimentelAlarcon, Daniel  Georgia State Univ 
Ongie, Greg  Univ. of Michigan 
Balzano, Laura  Univ. of Michigan 
Willett, Rebecca  Univ. of WisconsinMadison 
Nowak, Robert  Univ. of Wisconsin, Madison 
Keywords: Computational Models and Representations, Machine Learning and Learning Theory, Optimization
Abstract: Low rank matrix completion (LRMC) has received tremendous attention in recent years. The low rank assumption means that the columns (or rows) of the matrix to be completed are points on a lowdimensional linear variety. This paper extends this thinking to cases where the columns are points on lowdimensional nonlinear algebraic varieties. While others have recently studied matrix completion in such settings, existing results focus mainly on algorithms and experiments, without supporting theory. This paper proposes a new approach to what we call Low AlgebraicDimension Matrix Completion (LADM). We present a provablycorrect algorithm for completion of LAD matrices and a more practical algorithm that leverages existing LRMC methods on a tensorized representation of the data. In particular, the new algorithm can succeed in many cases where traditional LRMC is guaranteed to fail. We also provide experimental results showing that the new approach significantly outperforms existing stateoftheart methods for standard matrix completion in many situations.


12:1012:30, Paper ThB3.6  
Inverse Problems with Multiscale Scattering Transforms (I) 
Bruna, Joan  New York Univ. 
Dokmanic, Ivan  Univ. of Illinois at UrbanaChampaign 
Cosse, Augustin  New York Univ. 

ThB4 
Pine 
Learning Theory 
Regular Session 
Chair: Honorio, Jean  Purdue Univ 

10:3010:50, Paper ThB4.1  
Relations among Different Privacy Notions 
Zhao, Jun  Carnegie Mellon Univ. & Nanyang Tech. Univ 
Keywords: Information Theory, Data Analytics, Performance Analysis
Abstract: We present a comprehensive view of the relations among several privacy notions: differential privacy (DP), Bayesian differential privacy (BDP), semantic privacy (SP), and membership privacy (MP). The results are organized into two parts. In part one, we extend the notion of semantic privacy (SP) to Bayesian semantic privacy (BSP) and show its essential equivalence with Bayesian differential privacy (BDP) in the quantitative sense. We prove the relations between BDP and BSP as follows: epsilonBDP is implied by [1/21/(exp(epsilon)+1)]BSP, and epsilonBDP implies (exp(2*epsilon)1)BSP. In addition, we obtain a minor result of epsilonDP being implied by [1/21/(exp(epsilon)+1)]SP, which improves the result of Kasiviswanathan and Smith in Journal of Privacy and Confidentiality 2014 stating that epsilonDP is implied by epsilon/6SP for epsilon at most 1.35. In part two, we establish the relations between BDP and MP. First, epsilonBDP implies epsilonMP. Second, for a family of distributions that are downward scalable in the sense of Li et al. in ACM CCS 2013, it is shown that epsilonBDP is implied by epsilonMP.


10:5011:10, Paper ThB4.2  
Improved Algorithms for Distributed Boosting 
Cooper, Jeff  Google, Inc 
Reyzin, Lev  Univ. of Illinois at Chicago 
Keywords: Machine Learning and Learning Theory, Distributed and LargeScale Systems, Data Analytics
Abstract: We introduce two distributed boosting algorithms. Our first algorithm uses the entire dataset to train a classifier and requires a significant amount of communication among the distributed sites. Our second algorithm requires very little communication but uses a subsample of the dataset to train the final classifier. Both of our algorithms improve upon existing practical distributed boosting algorithms. Further, both are competitive with AdaBoost when it is run with the entire dataset.


11:1011:30, Paper ThB4.3  
Composition Properties of Inferential Privacy for TimeSeries Data 
Song, Shuang  Univ. of California, San Diego 
Chaudhuri, Kamalika  Univ. of California, San Diego 
Keywords: Machine Learning and Learning Theory, Reliability, Security and Trust, Data Analytics
Abstract: With the proliferation of mobile devices and the internet of things, developing principled solutions for privacy in time series applications has become increasingly important. While differential privacy is the gold standard for database privacy, many time series applications require a different kind of guarantee, and a number of recent works have used some form of inferential privacy to address these situations. However, a major barrier to using inferential privacy in practice is its lack of graceful composition  even if the same or related sensitive data is used in multiple releases that are safe individually, the combined release may have poor privacy properties. In this paper, we study composition properties of a form of inferential privacy called Pufferfish when applied to timeseries data. We show that while general Pufferfish mechanisms may not compose gracefully, a specific Pufferfish mechanism, called the Markov Quilt Mechanism, which was recently introduced, has strong composition properties comparable to that of pure differential privacy when applied to time series data.


11:3011:50, Paper ThB4.4  
Exact Recovery in the Binary Stochastic Block Model with Binary Side Information 
Saad, Hussein  Univ. of Texas at Dallas 
Abotabl, Ahmed  Univ. of Texas at Dallas 
Nosratinia, Aria  Univ. of Texas at Dallas 
Keywords: Learning and Inference, Information Theory, Machine Learning and Learning Theory
Abstract: We consider a generalization of the community detection problem, where for inference we have access to an additional observation that carries information (side information) about the label of each node. We study the effect of the quality of side information on the exact recovery phase transition of the binary symmetric stochastic block model by passing the true label through a binary symmetric channel (BSC) with crossover probability alpha. We show that when alpha is constant or approaching zero such that log(frac{1alpha}{alpha}) = o(log(n)), side information does not help exact recovery and the phase transition does not change. On the other hand, when log(frac{1alpha}{alpha}) = O(log(n)), we show that side information helps exact recovery. We provide necessary and sufficient conditions that are tight for different asymptotic regimes of alpha. An efficient algorithm that incorporates the effect of side information is proposed that uses a partial recovery algorithm combined with a local improvement procedure. Sufficient conditions are derived for exact recovery under this efficient algorithm.


11:5012:10, Paper ThB4.5  
Regret Bounds and Regimes of Optimality for ItemItem and UserUser Recommendation Systems 
Bresler, Guy  MIT 
Karzand, Mina  MIT 

12:1012:30, Paper ThB4.6  
On the Sample Complexity of Learning Graphical Games 
Honorio, Jean  Purdue Univ 
Keywords: Machine Learning and Learning Theory
Abstract: We analyze the sample complexity of learning graphical games from purely behavioral data. We assume that we can only observe the players' joint actions and not their payoffs. We analyze the sufficient and necessary number of samples for the correct recovery of the set of purestrategy Nash equilibria (PSNE) of the true game. Our analysis focuses on directed graphs with n nodes and at most k parents per node. Sparse graphs correspond to k in O(1) with respect to n, while dense graphs correspond to k in O(n). By using VC dimension arguments, we show that if the number of samples is greater than O(k n log^2{n}) for sparse graphs or O(n^2 log{n}) for dense graphs, then maximum likelihood estimation correctly recovers the PSNE with high probability. By using informationtheoretic arguments, we show that if the number of samples is less than Omega(k n log^2{n}) for sparse graphs or Omega(n^2 log{n}) for dense graphs, then any conceivable method fails to recover the PSNE with arbitrary probability.


ThB5 
Lower Level 
Information Theory 
Regular Session 
Chair: Ozgur, Ayfer  Stanford Univ 

10:3010:50, Paper ThB5.1  
Communications Over a State Dependent Channel, When the Channel State and Message Are Dependent 
Graves, Eric  Army Res. Lab 
Keywords: Information Theory
Abstract: This paper studies communication over a discrete channel with state, where the (possibly nonergodic) state of the channel is arbitrarily correlated with the message, and this state is provided causally to both encoder and decoder. Matching necessary and sufficient conditions for reliable variable lengthchannel codes are found. In particular, it is shown that in order to transmit a given message, the empirical capacity of the channel must be greater than the marginal entropy of the message conditioned on the total observed channel states.


10:5011:10, Paper ThB5.2  
A Solution to Cover's Problem for the Binary Symmetric Relay Channel: Geometry of Sets on the Hamming Sphere 
Pate Barnes, Leighton  Stanford Univ 
Wu, Xiugang  Stanford Univ 
Ozgur, Ayfer  Stanford Univ 
Keywords: Information Theory, Network Information Theory
Abstract: We solve a longstanding open problem posed by Cover and named ``The Capacity of the Relay Channel,'' emph{Open Problems in Communication and Computation, SpringerVerlag, 1987}, in the case when the channels from the source to the relay and the destination are binary symmetric channels. Similar to our recent solution of this problem in the Gaussian case, we solve this problem by connecting it to highdimensional geometry. However, our geometric approach in the binary case significantly deviates from the Gaussian case, since our treatment of the Gaussian case relied on an extension of the classical isoperimetric inequality on the Euclidean sphere, the counterpart of which does not exist on the Hamming sphere. Instead, we prove a Riesz rearrangement type inequality on the Hamming sphere, which allows us to develop a new upper bound on the capacity of the binary symmetric relay channel. Our argument (and consequently our upper bound) for the binary case is weaker than the one we obtained in the Gaussian case, but nevertheless strong enough to resolve Cover's problem.


11:1011:30, Paper ThB5.3  
On Very Noisy Channels with Feedback 
Shende, Nirmal  Cornell Univ 
Wagner, Aaron  Cornell Univ 
Keywords: Information Theory
Abstract: We show that even perfect feedback does not improve the error exponent, normal approximation, or moderate deviations performance of fixedblocklength codes over very noisy channels.


11:3011:50, Paper ThB5.4  
Capacity Achieving Input Distribution to the Generalized Inverse Gaussian Neuron Model 
Sungkar, Mustafa  Univ. of Virginia 
Berger, Toby  Univ. of Virginia, Charlottesville 
Levy, William B  Univ. of Virginia 
Keywords: Information Theory, Biological Information Systems
Abstract: The buildup of a cortical neuron's excitation, called the postsynaptic potential (PSP), is well modeled by the generalized inverse Gaussian (First) Hitting Time (GIGHT) diffusion. Such a model is called the generalized inverse Gaussian (GIG) neuron model. It is also believed that a neuron's purpose is to send information about the state of its input to the neuron's targets. We use Shannon's mutual information as a measure of this neural information in the GIG neuron model. The remarkable energy efficiency of neurons suggests that the neuron maximizes the transmitted mutual information subject to an energy constraint. Thus, we are interested in the information capacity of the GIG neuron model as a function of energy expended. This paper improves our work with Jie Xing (Xing et al., 2015), wherein the upper bound of the capacitycost curve for the GIG neuron model was obtained. Here, we numerically computed the capacitycost curve for such a model and found that for certain parameters, the upper bound and actual curve almost coincide. More interestingly, we found that the maximizing input distribution is discrete for certain parameters. This has implications on how the neural network should operate in order to optimally transmit information.


11:5012:10, Paper ThB5.5  
Interactive Coding for Markovian Protocols 
BenYishai, Assaf  Tel Aviv Univ 
Shayevitz, Ofer  Tel Aviv Univ 
Kim, YoungHan  UCSD 
Keywords: Information Theory
Abstract: We address the problem of simulating an arbitrary Markovian interactive protocol over binary symmetric channels with crossover probability varepsilon. We are interested in the achievable rates of reliable simulation, i.e., in characterizing the smallest possible blowup in communications such that a vanishing error probability (in the protocol length) can be attained. Whereas for general interactive protocols the output of each party may depend on all previous outputs of its counterpart, in a (first order) Markovian protocol this dependence is limited to the last observed output only. In the special case where there is no dependence on previous outputs (no interaction), the maximal achievable rate is given by the (oneway) Shannon capacity 1h(varepsilon). For Markovian protocols, we first show that a rate of frac{2}{3}(1h(varepsilon)) can be trivially achieved. We then describe a more involved coding scheme and provide a closedform lower bound for its rate at any noise level varepsilon. Specifically, we show that this scheme outperforms the trivial one for any varepsilon<0.044, and achieves a rate higher than frac{1h(varepsilon)}{1+h(varepsilon)+hleft( right)}=1Theta(h(varepsilon)) as varepsilonto 0, which is orderwise the best possible. This should be juxtaposed with a result of Kol and Raz that shows the capacity for interactive protocols with alternating rounds is lower bounded by 1O(sqrt{h(varepsilon)})


12:1012:30, Paper ThB5.6  
Towards the Exact RateMemory TradeOff for Uncoded Caching with Secure Delivery 
Bahrami, Mohsen  Univ. of Arizona 
Attia, Mohamed A.  Univ. of Arizona 
Tandon, Ravi  Univ. of Arizona 
Vasic, Bane  Univ. of Arizona 
Keywords: Information Theory, Coding Techniques and Applications
Abstract: We consider the problem of secure delivery in a singlehop caching network with a central server connected to multiple endusers via an insecure multicast link. The server has a database of a set of files (content) and each user, which is equipped with a local cache memory, requests access one of the files. In addition to delivering users' requests, the server needs to keep the files (informationtheoretically) secure from an external eavesdropper observing the underlying communications between the server and users. We focus on an important class of content placement strategies where the prefetching is required to be uncoded and caches are filled with uncoded fragments of files. In this paper, we establish the exact characterization of secure ratememory tradeoff for the worstcase communication rate through a matching converse under the constraint of uncoded cache placement where the number of users is no larger than the number of files in the database.


ThB6 
Visitor Center 
Reliability, Security & Trust 
Regular Session 
Chair: Calmon, Flavio  Harvard 

10:3010:50, Paper ThB6.1  
An EstimationTheoretic View of Privacy 
Wang, Hao  Harvard Univ 
Calmon, Flavio  Harvard Univ 
Keywords: Reliability, Security and Trust, Detection and Estimation, Information Theory
Abstract: We study the central problem in data privacy: how to share data with an analyst while providing both privacy and utility guarantees to the user that owns the data. We present an estimationtheoretic analysis of the privacyutility tradeoff (PUT) in this setting. Here, an analyst is allowed to reconstruct (in a meansquared error sense) certain functions of the data (utility), while other private functions should not be reconstructed with distortion below a certain threshold (privacy). We demonstrate how a chi^2based information measure captures the fundamental PUT, and characterize several properties of this function. In particular, we give a sharp bound for the PUT. We then propose a convex program to compute privacyassuring mappings when the functions to be disclosed and hidden are known a priori. Finally, we evaluate the robustness of our approach to finite samples.


10:5011:10, Paper ThB6.2  
Achieving the Secrecy Capacity of the AWGN Wiretap Channel Via Multilevel Coding 
Abotabl, Ahmed  Univ. of Texas at Dallas 
Nosratinia, Aria  Univ. of Texas at Dallas 
Keywords: Reliability, Security and Trust, Coding Theory, Information Theory
Abstract: In this paper we study coded modulation for the AWGN wiretap channel. We propose multilevel coding in which the encoding of the message and the randomness is performed through distinct levels. Modulation dependent conditions under which the proposed multilevel coding achieves the secrecy capacity are studied. It is shown that it is always possible to achieve the secrecy capacity via this approach as the number of levels increases. While assuming maximum likelihood decoding at the eavesdropper, the proposed multilevel coding is studied under maximum likelihood decoding and multistage decoding at the legitimate receiver. The labeling effect on the achievable secrecy rates is also investigated. Achieving other points on the rateequivocation region is also studied, showing that multilevel coding can approach any point on the rateequivocation region. One of the advantages of the proposed method is to allow the use of existing BIAWGN codes, e.g., LDPC codes, to approach the secrecy capacity. Simulations support our findings.


11:1011:30, Paper ThB6.3  
Towards a Theory of FreeLunch Privacy in CyberPhysical Systems 
Jia, Ruoxi  Univ. of California at Berkeley 
Dong, Roy  Univ. of California  Berkeley 
Ganesh, Prashanth  Univ. of California at Berkeley 
Sastry, Shankar  UC Berkeley 
Spanos, Costas  Univ. of California, Berkeley 
Keywords: Optimization, Data Analytics, Learning and Inference
Abstract: Emerging cyberphysical systems (CPS) often require collecting end users' data to support datainformed decision making processes. There has been a longstanding argument as to the tradeoff between privacy and data utility. In this paper, we adopt a multiparametric programming approach to rigorously study conditions under which data utility has to be sacrificed to protect privacy and situations where freelunch privacy can be achieved, i.e., data can be concealed without hurting the optimality of the decision making underlying the CPS. We formalize the concept of freelunch privacy, and establish various results on its existence, geometry, as well as efficient computation methods. We propose the freelunch privacy mechanism, which is a pragmatic mechanism that exploits freelunch privacy if it exists with the constant guarantee of optimal usage of data. We study the resilience of this mechanism against attacks that attempt to infer the parameter of a user's data generating process. We close the paper by a case study on occupancyadaptive smart home temperature control to demonstrate the efficacy of the mechanism.


11:3011:50, Paper ThB6.4  
The Securable Subspace of a Linear Stochastic System with Malicious Sensors and Actuators 
Satchidanandan, Bharadwaj  Texas A&M Univ 
Kumar, P. R.  Texas A&M Univ 
Keywords: Reliability, Security and Trust
Abstract: Analogous to the notions of controllable and unobservable subspaces, the recently introduced notions of securable and unsecurable subspaces for linear dynamical systems have important operational meaning in the context of secure control of deterministic linear dynamical systems. Specifically, given a multiple input, multiple output linear dynamical system, an arbitrary subset of whose sensors and actuators are malicious, the unsecurable subspace has the operational meaning as the set of states that the malicious actuators can steer the system to, without detection of the visit to such a state by the honest sensors in the system. In this paper, we examine these subspaces from the standpoint of a fullyobserved stochastic linear dynamical system, and establish operational meanings for them in this context.


11:5012:10, Paper ThB6.5  
Monotonicity Properties and Spectral Characterization of Power Redistribution in Cascading Failures 
Guo, Linqi  California Inst. of Tech 
Liang, Chen  California Inst. of Tech 
Low, Steven  California Inst. of Tech 
Keywords: Reliability, Security and Trust, Complex Networked Systems, Computational Models and Representations
Abstract: In this work, we apply spectral graph theory methods to study the monotonicity and structural properties of power redistribution in a cascading failure process. We demonstrate that in contrast to the lack of monotonicity in physical domain, there is a rich collection of monotonicity one can explore in the spectral domain, leading to a systematic way to define topological metrics that are monotonic. It is further shown that many useful quantities in cascading failure analysis can be unified into a spectral inner product, which itself is related to graphical properties of the transmission network. Such graphical interpretations precisely capture the Kirchhoff's law expressed in terms of graph structural properties and gauge the impact of a line when it is tripped. We illustrate that our characterization leads to a treepartition of the network so that failure cascading can be localized.


12:1012:30, Paper ThB6.6  
Embracing Risk Dependency in Designing CyberInsurance Contracts 
Khalili, Mohammad Mahdi  Univ. of Michigan  Ann Arbor 
Naghizadeh Ardabili, Parinaz  Purdue Univ 
Liu, Mingyan  Univ. of Michigan 
Keywords: Reliability, Security and Trust, Network Games and Algorithms
Abstract: We study the problem of designing cyber insurance policies in an interdependent network, where the loss of one agent (a primary party) depends not only on his own effort, but also on the investments and efforts of others (third parties) in the same ecosystem (i.e., externalities). In designing cyber insurance policies, the conventional wisdom is to avoid insuring dependent parties for two reasons. First, simultaneous loss incidents threaten the insurer's business and capital. Second, when a loss incident can be attributed to a third party, the insurer of the primary party can get compensation from the insurer of the third party in order to reduce its own risk exposure. In this work, we analyze an interdependent network model in order to understand whether an insurer should avoid or embrace risks interdependencies. We focus on two interdependent agents, where the risk of one agent (primary party) depends on the other agent (third party), but not the other way around. We consider two potential scenarios: one in which an insurer only signs a primary party, and another one in which the insurer of the primary party further insures the third party agent. We show that that there is in fact profitable for the primary party's insurer to insure both interdependent agents. Further, we show that insuring both agents not only provides higher profit for the insurer, but also reduces the collective risk.


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

13:3013:50, Paper ThC1.1  
ExactRepair TradeOff for (n, K = D − 1, D) Regenerating Codes (I) 
Elyasi, Mehran  Univ. of Minnesota 
Mohajer, Soheil  Univ. of Minnesota 
Keywords: Data Storage
Abstract: A class of exactrepair regenerating codes is introduced for a distributed storage systems with parameters (n,k=d1,d). The proposed construction uses determinant codes as building blocks. The proposed codes can be generated for k different operating points (alpha,beta) on the tradeoff, including the MBR and the MSR points. The tradeoff achievable by the proposed code is strictly below the stateoftheart codes, and more importantly, does not depend on n, the total number of nodes in the system. The field size required for the construction is only Theta(n).


13:5014:10, Paper ThC1.2  
A Tradeoff between the SubPacketization Size and the Repair Bandwidth for ReedSolomon Code (I) 
Li, Weiqi  Univ. of California, Irvine 
Wang, Zhiying  Univ. of California, Irvine 
Jafarkhani, Hamid  Univ. of California Irvine 
Keywords: Network Coding, Data Storage, Coding Techniques and Applications
Abstract: ReedSolomon (RS) codes are widely used in practical storage systems but their repair bandwidth characterization is still an open problem. RS codes can be viewed as the evaluations of a polynomial over a finite field. Recently, Guruswami and Wootters proposed a repair method for RS codes when the evaluation points are the entire field. Tamo, Ye and Barg achieved the minimum storage regenerating (MSR) bound when the subpacketization size grows faster than the exponential function of the size of the evaluation points. In this work, we extend these results to accommodate different sizes of the evaluation points. Our schemes provide a flexible tradeoff between the subpacketization size and the repair bandwidth. In addition, we improve the subpacketization bound for scalar MSR codes.


14:1014:30, Paper ThC1.3  
Recent Results on Codes for Distributed Storage (I) 
Kumar, P. Vijay  Indian Inst. of Science 

14:3014:50, Paper ThC1.4  
Approximating Index Coding Rates for Useful Classes of Graphs (I) 
Mazumdar, Arya  Univ. of Massachusetts Amherst 

14:5015:10, Paper ThC1.5  
Improved Schemes for Asymptotically Optimal Repair of MDS Codes 
Chowdhury, Ameera  Univ. of California San Diego 
Vardy, Alexander  Univ. of California San Diego 
Keywords: Data Storage, Coding Theory
Abstract: An (n,k,l) MDS code of length n, dimension k, and subpacketization l over a finite field F is a set of n symbol vectors of length l over F with the property that any k vectors can recover the entire data of kl symbols. When a node fails, we can recover it by downloading symbols from the surviving nodes, and the total number of symbols downloaded in the worse case is the repair bandwidth of the code. By the cutset bound, the repair bandwidth of an (n,k,l) MDS code is at least (n1)l/(nk). There are several constructions of (n,k,l) MDS codes whose repair bandwidths meet or asymptotically meet the cutset bound. Letting r=nk denote the number of parities, Ye and Barg constructed (n,k,r^{n}) ReedSolomon codes that asymptotically meet the cutset bound. Ye and Barg also constructed optimal bandwidth and optimal update (n,k,r^{n}) MDS codes. A key idea in these constructions is to expand integers in base r. We show that, when r is an integral power, we can significantly reduce the subpacketization of Ye's and Barg's constructions while achieving asymptotically optimal repair bandwidth. Specifically, when r=s^{m}, we obtain an (n,k,s^{m+n1}) ReedSolomon code and an optimal update (n,k,s^{m+n1}) MDS code, which both have asymptotically optimal repair bandwidth.


ThC2 
Solarium 
Inference/Causality 
Invited Session 
Chair: Quinn, Christopher  Purdue Univ 
CoChair: Kiyavash, Negar  Univ. of Illinois 
Organizer: Quinn, Christopher  Purdue Univ 
Organizer: Kiyavash, Negar  Univ. of Illinois 

13:3013:50, Paper ThC2.1  
Joint Causal Inference from Observational and Experimental Data (I) 
Mooij, Joris M.  Univ. of Amsterdam 

13:5014:10, Paper ThC2.2  
Dictionary Learning Based on Sparse Distribution Tomography (I) 
Pad, Pedram  CSEM/EPFL 
Salehi, Farnood  EPFL 
Celis, L. Elisa  EPFL 
Thiran, Patrick  EPFL 
Unser, Michael  EPFL 

14:1014:30, Paper ThC2.3  
Cheshire: An Online Algorithm for Activity Maximization in Social Networks (I) 
Zarezade, Ali  Sharif Univ. of Tech 
De, Abir  IIT Kharagpur 
Rabiee, Hamid R.  Sharif Univ. of Tech 
Gomez Rodriguez, Manuel  MPISWS 
Keywords: Machine Learning and Learning Theory, Complex Networked Systems, Adaptive Control and Automation
Abstract: User engagement in social networks depends critically on the number of online actions their users take in the network. Can we design an algorithm that finds when to incentivize users to take actions to maximize the overall activity in a social network? In this paper, we model the number of online actions over time using multidimensional Hawkes processes, derive an alternate representation of these processes based on stochastic differential equations (SDEs) with jumps and, exploiting this alternate representation, address the above question from the perspective of stochastic optimal control of SDEs with jumps. We find that the optimal level of incentivized actions depends linearly on the current level of overall actions. Moreover, the coefficients of this linear relationship can be found by solving a matrix Riccati differential equation, which can be solved efficiently, and a first order differential equation, which has a closed form solution. As a result, we are able to design an efficient online algorithm, Cheshire, to sample the optimal times of the users' incentivized actions. Experiments on both synthetic and real data gathered from Twitter show that our algorithm is able to consistently maximize the number of online actions more effectively than the state of the art.


14:3014:50, Paper ThC2.4  
The Asymptotic Performance of Complex LASSO (I) 
Abbasi, Ehsan  California Inst. of Tech. 
Hassibi, Babak  California Inst. of Tech. 

ThC3 
Butternut 
Control Theory 
Regular Session 
Chair: Paccagnan, Dario  ETH Zurich 

13:3013:50, Paper ThC3.1  
The Risks and Rewards of Conditioning Noncooperative Designs to Additional Information 
Paccagnan, Dario  ETH Zurich 
Marden, Jason R.  Univ. of California, Santa Barbara 
Keywords: Decentralized Control Systems, Distributed and LargeScale Systems, Network Games and Algorithms
Abstract: A fundamental challenge in multiagent systems is to design local control algorithms to ensure a desirable collective behaviour. The information available to the agents, gathered either through communication or sensing, defines the structure of the admissible control laws and naturally restricts the achievable performance. Hence, it is fundamental to identify what piece of information can be used to produce a significant performance enhancement. This paper studies, within a class of resource allocation problems, the case when such information is uncertain or inaccessible and pinpoints a fundamental riskreward tradeoff faced by the system designer.


13:5014:10, Paper ThC3.2  
A BernoulliGaussian Physical Watermark for Detecting Integrity Attacks in Control Systems 
Weerakkody, Sean  Carnegie Mellon Univ 
Ozel, Omur  Carnegie Mellon Univ 
Sinopoli, Bruno  Carnegie Mellon Univ 
Keywords: Detection and Estimation, Adaptive Control and Automation, Optimization
Abstract: We examine the merit of Bernoulli packet drops in actively detecting integrity attacks on control systems. The aim is to detect an adversary who delivers fake sensor measurements to a system operator in order to conceal their effect on the plant. Physical watermarks, or noisy additive Gaussian inputs, have been previously used to detect several classes of integrity attacks in control systems. In this paper, we consider the analysis and design of Gaussian physical watermarks in the presence of packet drops at the control input. On one hand, this enables analysis in a more general network setting. On the other hand, we observe that in certain cases, Bernoulli packet drops can improve detection performance relative to a purely Gaussian watermark. This motivates the joint design of a BernoulliGaussian watermark which incorporates both an additive Gaussian input and a Bernoulli drop process. We characterize the effect of such a watermark on system performance as well as attack detectability in two separate design scenarios. Here, we consider a correlation detector for attack recognition. We then propose efficiently solvable optimization problems to intelligently select parameters of the Gaussian input and the Bernoulli drop process while addressing security and performance tradeoffs. Finally, we provide numerical results which illustrate that a watermark with packet drops can indeed outperform a Gaussian watermark.


14:1014:30, Paper ThC3.3  
TransitionBased versus StateBased Reward Functions for MDPs with ValueAtRisk 
Ma, Shuai  Concordia Univ 
Yu, Jia Yuan  Concordia Univ 
Keywords: Adaptive Control and Automation, Reliability, Security and Trust, Machine Learning and Learning Theory
Abstract: In reinforcement learning, the reward function on current state and action is widely used. When the objective is about the expectation of the (discounted) total reward only, it works perfectly. However, if the objective involves the total reward distribution, the result will be wrong. This paper studies ValueatRisk (VaR) problems in short and longhorizon Markov decision processes (MDPs) with two reward functions, which share the same expectations. Firstly we show that with VaR objective, when the real reward function is transitionbased (with respect to action and both current and next states), the simplified (statebased, with respect to action and current state only) reward function will change the VaR. Secondly, for longhorizon MDPs, we estimate the VaR function with the aid of spectral theory and the central limit theorem. Thirdly, since the estimation method is for a Markov reward process with the reward function on current state only, we present a transformation algorithm for the Markov reward process with the reward function on current and next states, in order to estimate the VaR function with an intact total reward distribution.


14:3014:50, Paper ThC3.4  
Structured State Space Realizations for SLS Distributed Controllers 
Anderson, James  California Inst. of Tech 
Matni, Nikolai  California Inst. of Tech 
Keywords: Decentralized Control Systems, Distributed and LargeScale Systems, Complex Networked Systems
Abstract: In recent work the system level synthesis (SLS) paradigm has been shown to provide a truly scalable method for synthesizing distributed feedback controllers. Moreover, the resulting synthesis problem is convex. In this paper we provide minimal state space realizations for both the state and output feedback controllers. It is also shown that (for fixed n) the state dimension of the controllers grows linearly with FIR filter horizon length  in both cases, we show that if the underlying transfer matrices are structured, so is the corresponding statespace realization. For the H2 state feedback case a simple decomposition technique reduces the synthesis problem to solving a set of lower dimensional LQR problems that can be solved in parallel.


14:5015:10, Paper ThC3.5  
A Model Predictive Control Approach to Flow Pacing for TCP 
FridovichKeil, David  Univ. of California, Berkeley 
Hanford, Nathan  Univ. of California, Davis 
Chapman, Margaret  Univ. of California, Berkeley 
Tomlin, Claire  Univ. of California, Berkeley 
Farrens, Matthew  Univ. of California, Davis 
Ghosal, Dipak  Univ. of California, Davis 
Keywords: Pricing and Congestion Control, Adaptive Control and Automation
Abstract: A key challenge in the management of Internet traffic is the design of algorithms that complement wellestablished protocols, such as the Transmission Control Protocol (TCP), and simultaneously address their limitations. The challenge becomes greater in the context of large socalled "elephant" flows over long paths that often transition from higher to lower bandwidth connections. At these transition points either persistent queues are formed when buffers are overprovisioned or packet loss occurs when buffers are underprovisioned; both cases lead to degraded and/or highly variable endtoend performance. Ideally, for such scenarios, the source should "learn" and set a pacing rate that matches the lower bandwidth connection. In this paper, we adopt a modelbased receding horizon control strategy to design a pacing control method. Each new roundtrip time (RTT) measurement is first incorporated into a linear timevarying (LTV) predictive model. Subsequently, we solve a onestep lookahead optimization problem which finds the pacing rate which optimally trades off RTT, variance in RTT, and throughput according to the most uptodate model. We implemented our proofofconcept control strategy on the Linux operating system alongside the existing CoDel queuing discipline (qdisc) and HTCP congestioncontrol algorithm. Our preliminary results indicate significant reduction in the variances of the RTT and the throughput, resulting in more predictable performance overall.


15:1015:30, Paper ThC3.6  
Controllability of Stochastic Differential Equations with Markovian Switching 
Zhao, Guangliang  GE Global Res 
Yang, Zhixin  Ball State Univ 
Yuan, Quan  Ball State Univ 
Wang, Le Yi  Wayne State Univ 
Keywords: Robust and Nonlinear Control
Abstract: For systems of switching diffusions, a concept of controllability is proposed by using the finite expected value of the first reaching time(or mean reaching time) to an arbitrarily small open set of the terminal point. A necessary and sufficient condition is obtained utilizing positive recurrent. A verification criterion is provided by using Liapnov functions, and a matrix form criterion if the system is linear. Finally, a simulation example is provided to show that when coupled with regime switching, the hybrid system of uncontrollable ODEs could be controllable.


ThC4 
Pine 
Statistical Learning I 
Invited Session 
Chair: Viswanath, Pramod  Univ. of Illinois 
CoChair: Oh, Sewoong  UIUC 
Organizer: Oh, Sewoong  UIUC 
Organizer: Viswanath, Pramod  Univ. of Illinois 

13:3013:50, Paper ThC4.1  
Greed Is Good: NearOptimal Submodular Maximization Via Greedy Optimization (I) 
Karbasi, Amin  Yale Univ. 

13:5014:10, Paper ThC4.2  
Optimal Rates for Community Estimation in the Weighted Stochastic Block Model (I) 
Jog, Varun  Univ. of WisconsinMadison 
Loh, PoLing  Univ. of Wisconsin  Madison 
Xu, Min  Univ. of Pennsylvania 

14:1014:30, Paper ThC4.3  
Permutation Tests for Infection Graphs (I) 
Khim, Justin  Univ. of Pennsylvania 
Loh, PoLing  Univ. of Wisconsin  Madison 

14:3014:50, Paper ThC4.4  
Mean Estimation from Adaptive OneBit Measurements (I) 
Kipnis, Alon  Stanford Univ 
Duchi, John  Stanford Univ 
Keywords: Detection and Estimation, Signal Acquisition, Coding, and Retrieval, Learning and Inference
Abstract: We consider the problem of estimating the mean of a normal distribution under the following constraint: the estimator can access only a single bit of each sample from this distribution. We study the squared error risk in this estimation as a function of the number of samples and onebit measurements n. We consider an adaptive estimation setting where the singlebit sent at step n is a function of both the new sample and the previous n1 acquired bits. For this setting, we show that no estimator can attain asymptotic mean squared error smaller than π/(2n)+o(n^{1}) times the variance.


14:5015:10, Paper ThC4.5  
Efficiently Choosing the Best Intervention under Experimental Budget Constraints (I) 
Shanmugam, Karthikeyan  IBM Res. NY 
Sen, Rajat  UT Austin 
Shakkottai, Sanjay  The Univ. of Texas at Austin 
Dimakis, Alex  UT Austin 

ThC5 
Lower Level 
Information Theory & Statistics 
Regular Session 
Chair: Beirami, Ahmad  MIT 

13:3013:50, Paper ThC5.1  
Guesswork Subject to a Total Entropy Budget 
Rezaee, Arman  MIT 
Beirami, Ahmad  MIT 
Makhdoumi, Ali  MIT 
Médard, Muriel  MIT 
Duffy, Ken  Hamilton Inst. National Univ. of Ireland, Maynooth 

13:5014:10, Paper ThC5.2  
Lower Bounds for TwoSample Structural Change Detection in Ising and Gaussian Models 
Gangrade, Aditya  Boston Univ 
Nazer, Bobak  Boston Univ 
Saligrama, Venkatesh  Boston Univ 
Keywords: Information Theory and Statistics, Detection and Estimation, Machine Learning and Learning Theory
Abstract: The change detection problem is to determine if the Markov network structures of two Markov random fields differ from one another given two sets of samples drawn from the respective underlying distributions. We study the tradeoff between the sample sizes and the reliability of change detection, measured as a minimax risk, for the important cases of the Ising models and the Gaussian Markov random fields restricted to the models which have network structures with p nodes and degree at most d, and obtain informationtheoretic lower bounds for reliable change detection over these models. We show that for the Ising model, Omegaleft(frac{d^2}{(log d)^2}log pright) samples are required from each dataset to detect even the sparsest possible changes, and that for the Gaussian, Omegaleft( gamma^{2} log(p)right) samples are required from each dataset to detect change, where gamma is the smallest ratio of offdiagonal to diagonal terms in the precision matrices of the distributions. These bounds are compared to the corresponding results in structure learning, and closely match them under mild conditions on the model parameters. Thus, our change detection bounds inherit partial tightness from the structure learning schemes in previous literature, demonstrating that in certain parameter regimes, the naive structure learning based approach to change detection is minimax optimal up to constant factors.


14:1014:30, Paper ThC5.3  
On Composite Binary Hypothesis Testing with Training Data 
Bell, Michael  Hebrew Univ. of Jerusalem 
Kochman, Yuval  Hebrew Univ. of Jerusalem 
Keywords: Information Theory and Statistics
Abstract: Motivated by an outlier detection problem, we con sider the problem of testing between a known i.i.d. distribution over a finite alphabet, and a composite hypothesis consisting of all other i.i.d. distributions over the same alphabet. We wish to quantify the loss with respect to simple hypothesis testing, and further to find how much of it can be regained using a training sequence that is known to come from the unknown distribution. To that end, we present new optimality criteria, universal minimax with and without a training sequence. We show that under our criteria, the acceptance region of the optimal tests takes the simple form of a “sphere of types”, where the center is shifted to be “antipodal” to the type of the training sequence (if such a sequence is present). Further, noting that universality has no cost in the exponential sense, we turn to the secondorder regime of fixed error probabilities, where we define a figure of merit that we call resolution tradeoff. In this regime we solve Gaussian hypothesis testing problems, that are asymptotically equivalent to the original ones, in order to derive the resolution tradeoffs with and without training sequence.


14:3014:50, Paper ThC5.4  
On the Equality Condition for the IMMSE Proof of the Entropy Power Inequality 
Dytso, Alex  Princeton 
Bustin, Ronit  Tech 
Poor, H. Vincent  Princeton Univ 
Shamai, Shlomo  Tech 
Keywords: Information Theory, Information Theory and Statistics, Detection and Estimation
Abstract: The paper establishes the equality condition in the IMMSE proof of the entropy power inequality (EPI). This is done by establishing an exact expression for the deficit between the two sides of the EPI. Interestingly, a necessary condition for the equality is established by making a connection to the famous Cauchy functional equation.


14:5015:10, Paper ThC5.5  
Algebraic Properties of Solutions to Common Information of Gaussian Vectors under Sparse Graphical Constraints 
Moharrer, Ali  Louisiana State Univ 
Wei, Shuangqing  Louisiana State Univ 
Keywords: Information Theory and Statistics, Learning and Inference
Abstract: We formulate Wyner’s common information for random vectors x ∈ Rn with joint Gaussian density. We show that finding the common information of Gaussian vectors is equivalent to maximizing a logdeterminant of the additive Gaussian noise covariance matrix. We coin such optimization problem as a constrained minimum determinant factor analysis (CMDFA) problem. The convexity of such problem with necessary and sufficient conditions on CMDFA solution is shown. We study the algebraic properties of CMDFA solution space, through which we study two sparse Gaussian graphical models, namely, latent Gaussian stars, and explicit Gaussian chains. Interestingly, we show that depending on pairwise covariance values in a Gaussian graphical structure, one may not always end up with the same parameters and structure for CMDFA solution as those found via graphical learning algorithms. In addition, our results suggest that Gaussian chains have little room left for dimension reduction in terms of the number of latent variables required in their CMDFA solutions.


ThD1 
Library 
Statistical Physics and Inference 
Invited Session 
Chair: Oh, Sewoong  UIUC 
Organizer: Oh, Sewoong  UIUC 

15:3015:50, Paper ThD1.1  
Streaming Bayesian Inference: Theoretical Limits and MiniBatch Approximate MessagePassing (I) 
Manoel, Andre  Neurospin, CEA, Univ. ParisSaclay 
Krzakala, Florent  Lab. De Physique Statistique, ENS Paris 
Tramel, Eric  OWKIN 
Zdeborová, Lenka  IPhT, CNRS, CEA, Univ. ParisSaclay 
Keywords: Learning and Inference, Computational Models and Representations, Detection and Estimation
Abstract: In statistical learning for realworld largescale data problems, one must often resort to “streaming” algorithms which operate sequentially on small batches of data. In this work, we present an analysis of the informationtheoretic limits of minibatch inference in the context of generalized linear models and lowrank matrix factorization. In a controlled Bayesoptimal setting, we characterize the optimal performance and phase transitions as a function of minibatch size. We base part of our results on a detailed analysis of a minibatch version of the approximate messagepassing algorithm (MiniAMP), which we introduce. Additionally, we show that this theoretical optimality carries over into realdata problems by illustrating that MiniAMP is competitive with standard streaming algorithms for clustering.


15:5016:10, Paper ThD1.2  
The Layered Structure of Tensor Estimation and Its Mutual Information (I) 
Barbier, Jean  EPFL 
Macris, Nicolas  EPFL 
Miolane, Leo  INRIA 
Keywords: Machine Learning and Learning Theory, Learning and Inference, Information Theory and Statistics
Abstract: We consider rankone nonsymmetric tensor esti mation and derive simple formulas for the mutual information. We start by the order 2 problem, namely matrix factorization. We treat it completely in a simpler fashion than previous proofs using a new type of interpolation method developed in [1]. We then show how to harness the structure in “layers” of tensor estimation in order to obtain a formula for the mutual information for the order 3 problem from the knowledge of the formula for the order 2 problem, still using the same kind of interpolation. Our proof technique straightforwardly general izes and allows to rigorously obtain the mutual information at any order in a recursive way.


16:1016:30, Paper ThD1.3  
Additivity of Information in Multilayer Networks Via Additive Gaussian Noise Transforms (I) 
Reeves, Galen  Duke Univ 
Keywords: Learning and Inference, Information Theory and Statistics, Detection and Estimation
Abstract: Multilayer (or deep) networks are powerful probabilistic models based on multiple stages of a linear transform followed by a nonlinear (possibly random) function. In general, the linear transforms are defined by matrices and the nonlinear functions are defined by information channels. These models have gained great popularity due to their ability to characterize complex probabilistic relationships arising in a wide variety of inference problems. The contribution of this paper is a new method for analyzing the fundamental limits of statistical inference in settings where the model is known. The validity of our method can be established in a number of settings and is conjectured to hold more generally. A key assumption made throughout is that the linear transforms are drawn randomly from orthogonally invariant distributions over matrices. Our method yields explicit formulas for 1) the mutual information; 2) the minimum meansquared error (MMSE); 3) the existence and locations of certain phasetransitions with respect to the problem parameters; and 4) the stationary points for the state evolution of approximate message passing algorithms. When applied to the special case of models with multivariate Gaussian channels our method is rigorous and has close connections to free probability theory for random matrices. When applied to the general case of nonGaussian channels, our method provides a simple alternative to the replica method from statistical physics.


16:3016:50, Paper ThD1.4  
Phase Retrieval Via Linear Programming: Fundamental Limits and Algorithmic Improvements (I) 
Dhifallah, Oussama  Harvard Univ 
Thrampoulidis, Christos  MIT 
Lu, Yue M.  Harvard Univ 

16:5017:10, Paper ThD1.5  
The Lovasz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime (I) 
Banks, Jess  Univ. of CaliforniaBerkeley 
Kleinberg, Robert  Cornell Univ. 
Moore, Cristopher  Santa Fe Inst. 

17:1017:30, Paper ThD1.6  
Gauging Variational Inference (I) 
Ahn, Sungsoo  KAIST 
Chertkov, Michael  Los Alamos National Lab. 
Shin, Jinwoo  KAIST 

ThD2 
Solarium 
Information Retrieval/Power Networks 
Regular Session 
Chair: Sprintson, Alex  Texas A&M Univ 

15:3015:50, Paper ThD2.1  
The Capacity of Cache Aided Private Information Retrieval 
Tandon, Ravi  Univ. of Arizona 
Keywords: Data Storage, Network Information Theory, Reliability, Security and Trust
Abstract: The problem of cache enabled private information retrieval (PIR) is considered in which a user wishes to privately retrieve one out of K messages, each of size L bits from N distributed databases. The user has a local cache of storage SL bits which can be used to store any function of the K messages. The main contribution of this work is the exact characterization of the capacity of cache enabled PIR as a function of the storage parameter S. In particular, for a given cache storage parameter S, the informationtheoretically optimal download cost D^{*}(S)/L (or the inverse of capacity) is shown to be equal to (1 frac{S}{K})left(1+ frac{1}{N}+ ldots + frac{1}{N^{K1}}right). Special cases of this result correspond to the settings when S=0, for which the optimal download cost was shown by Sun and Jafar to be left(1+ frac{1}{N}+ ldots + frac{1}{N^{K1}}right), and the case when S=K, i.e., cache size is large enough to store all messages locally, for which the optimal download cost is 0. The intermediate points 0<= S<= K can be readily achieved through a simple memorysharing based PIR scheme. The key technical contribution of this work is the converse, i.e., a lower bound on the download cost as a function of storage S which shows that memory sharing is informationtheoretically optimal.


15:5016:10, Paper ThD2.2  
Secure Symmetric Private Information Retrieval from Colluding Databases with Adversaries 
Wang, Qiwen  KTH Royal Inst. of Tech 
Skoglund, Mikael  Royal Inst. of Tech. (KTH) 
Keywords: Coding Techniques and Applications, Reliability, Security and Trust, Information Theory
Abstract: The problem of symmetric private information retrieval (SPIR) from replicated databases with colluding servers and adversaries is studied. Specifically, the database comprises K files, which are replicatively stored among N servers. A user wants to retrieve one file from the database by communicating with the N servers, without revealing the identity of the desired file to any server. Furthermore, the user shall learn nothing about the other K1 files in the database. Any T out of N servers may collude, that is, they may communicate their interactions with the user to guess the identity of the requested file. An adversary in the system can tap in on or even try to corrupt the communication. Three types of adversaries are considered: a Byzantine adversary who can overwrite the transmission of any B servers to the user; a passive eavesdropper who can tap in on the incoming and outgoing transmissions of any E servers; and a combination of both  an adversary who can tap in on a set of any E nodes, and overwrite the transmission of a set of any B nodes. The problems of SPIR with colluding servers and the three types of adversaries are named TBSPIR, TESPIR and TBESPIR respectively. The capacity of the problem is defined as the maximum number of information bits of the desired file retrieved per downloaded bit. We show that the informationtheoretical capacity of the TBSPIR problem equals 1(2B+T)/N, if the servers share common randomness (unavailable at the user) with amount


16:1016:30, Paper ThD2.3  
Private Information Retrieval from Byzantine and Colluding Databases 
Banawan, Karim  Univ. of Maryland 
Ulukus, Sennur  Univ. of Maryland 
Keywords: Information Theory, Data Storage, Coding Techniques and Applications
Abstract: We consider the problem of singleround private information retrieval (PIR) from N replicated databases. We consider the case when B databases are outdated (unsynchronized), or even worse, adversarial (Byzantine), and therefore, can return incorrect answers. In the PIR problem with Byzantine databases (BPIR), a user wishes to retrieve a specific message from a set of M messages with zeroerror, irrespective of the actions performed by the Byzantine databases. We consider the Tprivacy constraint in this paper, where any T databases can collude, and exchange the queries submitted by the user. We determine the informationtheoretic capacity of this problem, which is the maximum number of emph{correct symbols} that can be retrieved privately for every symbol of the downloaded data to be C=frac{N2B}{N}cdotfrac{1frac{T}{N2B}}{1(frac{T}{N2B})^M}, if 2B+T < N. Our achievable scheme extends the optimal achievable scheme for the robust PIR (RPIR) problem to correct the emph{errors} introduced by the Byzantine databases. Our converse proof uses the idea of the cutset bound in the network coding problem against adversarial nodes.


16:3016:50, Paper ThD2.4  
Private Information Retrieval with Side Information: The Single Server Case 
Kadhe, Swanand  Texas A&M Univ 
Garcia, Brenden  Texas A&M Univ 
Heidarzadeh, Anoosheh  Texas A&M Univ 
El Rouayheb, Salim  Rutgers Uiversity 
Sprintson, Alex  Texas A&M Univ 
Keywords: Reliability, Security and Trust, Network Coding, Coding Techniques and Applications
Abstract: We study the problem of Private Information Retrieval (PIR) in the presence of prior side information. The problem setup includes a database of K independent messages possibly replicated on several servers, and a user that needs to retrieve one of these messages. In addition, the user has some prior side information in the form of a subset of M messages, not containing the desired message and unknown to the servers. This problem is motivated by practical settings in which the user can obtain side information opportunistically from other users or has previously downloaded some messages using classical PIR schemes. The objective of the user is to retrieve the required message without revealing its identity while minimizing the amount of data downloaded from the server. We focus on achieving informationtheoretic privacy for single server in two scenarios: (i) the user wants to protect jointly its demand and side information; (ii) the user wants to protect only the information about its demand, but not the side information. We prove that, in the first scenario, the minimum download cost is KM messages, and in the second scenario, it is K/(M+1) messages. This is a significant improvement compared to the minimum cost of K messages in the setting where the user has no side information. Our proof techniques use a reduction from PIR with side information to an index coding problem. We leverage this reduction to prove converse results, as well as to design achievability schemes.


16:5017:10, Paper ThD2.5  
Efficiently Finding All Power Flow Solutions to Tree Networks 
Zachariah, Alisha  Univ. of Wisconsin  Madison 
Charles, Zachary  Univ. of Wisconsin  Madison 
Keywords: Complex Networked Systems, Distributed and LargeScale Systems
Abstract: In this paper we present an algorithm which provably finds all voltage solutions to the power flow equations on tree networks. Our algorithm uses elimination theory to reduce the equations to univariate polynomials whose roots govern the voltages of the entire tree. The algorithm utilizes the sparse structure of the tree to decrease its computational cost. We show that the runtime of the algorithm depends on the degrees of the vertices in the tree. This implies that in physically motivated distribution networks, our algorithm runs much faster than in the worstcase scenario, scaling more like the number of real solutions as opposed to the number of complex solutions. Finally, we compare our algorithm to common approaches to finding all voltage solutions, including homotopy continuation methods and Grobner basis methods. We show that our algorithm outperforms these other methods in the low, medium, and highdegree settings and scales better with the number of buses.


ThD3 
Butternut 
Coding Theory 
Regular Session 
Chair: Wootters, Mary  Stanford Univ 

15:3015:50, Paper ThD3.1  
Maximally Recoverable Codes: The Bounded Case 
Gandikota, Venkata  Purdue Univ 
Grigorescu, Elena  Purdue Univ 
Thomas, Clayton  Purdue Univ 
Zhu, Minshen  Purdue Univ 
Keywords: Coding Theory, Data Storage
Abstract: Modern distributed storage systems employ Maximally Recoverable codes that aim to balance failure recovery capabilities with encoding/decoding efficiency tradeoffs. Recent works of Gopalan et al [SODA 2017] and Kane et al [ECCC TR17033] show that the alphabet size of basic gridlike topologies of practical interest must be large, a feature that hampers decoding efficiency. To bypass such shortcomings, in this work we initiate the study of a weaker version of recoverability, where instead of being able to correct all correctable erasure patterns (as is the case for maximal recoverability), we only require to correct all nontrivial (i.e., `irreducible') erasure patterns of bounded size. The study of this notion reduces to a variant of a combinatorial problem studied in the literature, which we believe is also interesting in its own right. We provide some upper and lower bounds for the alphabet size of {em Weakly Recoverable} codes withstanding all irreducible erasure patterns of small (constant) size. While our results may be contrived, we believe the questions we propose are relevant both to real storage systems and to combinatorial analysis, and merit further study.


15:5016:10, Paper ThD3.2  
MultiErasure Locally Recoverable Codes Over Small Fields 
Huang, Pengfei  Univ. of California, San Diego 
Yaakobi, Eitan  Tech.  Israel Inst. of Tech 
Siegel, Paul H.  UCSD 
Keywords: Coding Techniques and Applications, Coding Theory, Data Storage
Abstract: Erasure codes play an important role in storage systems to prevent data loss. In this work, we study a class of erasure codes called MultiErasure Locally Recoverable Codes (MELRCs) for storage arrays. Compared to previous related works, we focus on the construction of MELRCs over small fields. We first develop upper and lower bounds on the minimum distance of MELRCs. Our main contribution is to propose a general construction of MELRCs based on generalized tensor product codes, and study their erasurecorrecting properties. A decoding algorithm tailored for erasure recovery is given, and correctable erasure patterns are identified. We then prove that our construction yields optimal MELRCs with a wide range of code parameters, and present some explicit MELRCs over small fields. Finally, we show that generalized integrated interleaving (GII) codes can be treated as a subclass of generalized tensor product codes, thus defining the exact relation between these codes.


16:1016:30, Paper ThD3.3  
Limitations of Piggybacking Codes with Low Substriping 
Hulett, Reyna  Stanford Univ 
Wootters, Mary  Stanford Univ 
Keywords: Coding Theory, Data Storage
Abstract: The piggybacking framework for designing erasure codes for distributed storage has empirically proven to be very useful, and has been used to design codes with desirable properties, such as low repair bandwidth and complexity. However, the theoretical properties of this framework remain largely unexplored. We address this by adapting a general characterization of repair schemes (previously used for ReedSolomon codes) to analyze piggybacking codes with low substriping. With this characterization, we establish a separation between piggybacking and general erasure codes, and several impossibility results for subcategories of piggybacking codes; for certain parameters, we also present explicit, optimal constructions of piggybacking codes.


16:3016:50, Paper ThD3.4  
Reconciling Similar Sets 
Gabrys, Ryan  SPAWAR Systems Center Pacific 
Farnoud (Hassanzadeh), Farzad  Univ. of Virginia 
Keywords: Coding Theory, Distributed and LargeScale Systems, Data Storage
Abstract: In this work, we study the problem of synchronizing two sets of data where the size of the symmetric difference between the sets is small and, in addition, the elements in the symmetric difference are related through the Hamming distance metric. In our initial work, we provided communicationefficient methods for this problem when the elements in the symmetric difference were within a given Hamming distance. We now extend that work by considering sets whose symmetric difference consists of many blocks, each composed of elements that are within a given Hamming distance. We develop new encoding and decoding algorithms to address the complexities arising from allowing multiple difference blocks.


16:5017:10, Paper ThD3.5  
Repairing Multiple Failures for Scalar MDS Codes 
Bartan, Burak  Stanford Univ 
Wootters, Mary  Stanford Univ 
Keywords: Coding Theory, Data Storage
Abstract: In distributed storage, erasure codes  like ReedSolomon Codes  are often employed to provide reliability. In this setting, it is desirable to be able to repair one or more failed nodes while minimizing the repair bandwidth. In this work, motivated by ReedSolomon codes, we study the problem of repairing multiple failed nodes in a scalar MDS code. We extend the framework of (Guruswami and Wootters, 2017) to give a framework for constructing repair schemes for multiple failures in general scalar MDS codes, in the centralized repair model. We then specialize our framework to ReedSolomon codes, and extend and improve upon recent results of (Dau et al., 2017).


ThD4 
Pine 
Optimization 
Regular Session 
Chair: Molkaraie, Mehdi  ETHZ 

15:3015:50, Paper ThD4.1  
Efficient Rank Minimization to Tighten Semidefinite Programming for Unconstrained Binary Quadratic Optimization 
Pogodin, Roman  Skolkovo Inst. of Science and Tech. 
Krechetov, Mikhail  Skoltech 
Maximov, Yury  Los Alamos National Lab. 

15:5016:10, Paper ThD4.2  
Distributed Stochastic Optimization in Networks with Low Informational Exchange 
Li, Wenjie  L2S 
Assaad, Mohamad  CentraleSupélec 
Duhamel, Pierre  Lab. Des Signaux Et Systèmes (L2S)Supélec 
Keywords: Optimization, Wireless Communication Systems
Abstract: We consider the problem of distributed stochastic optimization in networks. Each node adjusts its action in order to optimize the global utility of the network, which is defined as the sum of local utilities of all nodes. Since the computation of the gradient may require much information exchange, we consider here that each node only has a noisy numerical observation of its local utility. This assumption is quite realistic, especially when the system is too complicated or constantly changing. At each time, nodes may exchange the observation of their numerical local utilities to estimate the global utility. Under the assumptions whether each node has collected the local utilities of all the other nodes or only part of these utilities, we propose two stochastic perturbation based distributed algorithms. We use tools from stochastic approximation to prove that both algorithms converge to the optimum. We then apply our algorithm to a power control problem in wireless networks and present numerical results that corroborate our claim.


16:1016:30, Paper ThD4.3  
Privacy Preserving CloudBased Quadratic Optimization 
Alexandru, Andreea  Univ. of Pennsylvania 
Gatsis, Konstantinos  Univ. of Pennsylvania 
Pappas, George  Univ. of Pennsylvania 
Keywords: Reliability, Security and Trust, Optimization
Abstract: This work proposes a protocol for privately solving constrained quadratic optimization problems with sensitive data. The problem encompasses the private data of multiple agents and is outsourced to an untrusted server. We describe the desired security goals and investigate the information leakage from duality theory. We present an interactive protocol that achieves the solution of a strictly quadratic convex optimization problem with private linear cost and private linear inequality constraints, by making use of partially homomorphic cryptosystems to securely effectuate computations. Then, we provide extensions to the protocol in order to also consider equality constraints and to obtain a speedup of the performance.


16:3016:50, Paper ThD4.4  
Sequential Smoothing Framework for Convex Concave Saddle Point Problems with Application to LargeScale Constrained Optimization 
Le, Hien  National Univ. of Singapore 
Haskell, William  National Univ. of Singapore 
Keywords: Optimization, Machine Learning and Learning Theory
Abstract: In this paper, we propose a sequential smoothing algorithm for solving large scale convex concave saddle point problems. We prove that this class of algorithms can achieve the convergence rate O(frac{1}{sqrt{varepsilon}}) in the deterministic setting and O(frac{1}{sqrt{varepsilon}}) with probability at least 1delta, where delta>0, in the stochastic setting, to obtain an varepsilonoptimal solution. We then apply our general algorithm to the specific problem of largescale convex constrained optimization.


16:5017:10, Paper ThD4.5  
Inexact Iteration of Averaged Operators for NonStrongly Convex Stochastic Optimization 
Haskell, William  National Univ. of Singapore 
Jain, Rahul  Univ. of Southern California 
Keywords: Optimization, Machine Learning and Learning Theory, Learning and Inference
Abstract: We present a framework for analysis of iteration of inexact averaged operators with stochstic errors. Many algorithms for nonstrongly convex stochastic optimization problems can be seen as iteration of such operators. Under certain conditions, we show that iteration of such operators has a sublinear O(1/K) convergence rate to its fixed point. This is accomoplished via a stochastic dominance argument. We then show that the general development gives convergence rate analysis for samplingbased algorithms for nonstrongly convex stochastic optimization including minimization, saddle point problems, and constrained optimization.


17:1017:30, Paper ThD4.6  
Asynchronous Primal Updates in Dual Subgradient Methods Via Approximate Lagrange Multipliers 
Valls, Víctor  Trinity Coll. Dublin 
Leith, Douglas  Trinity Coll. Dublin 
Keywords: Optimization, Decentralized Control Systems, Distributed and LargeScale Systems
Abstract: In this paper, we show that it is possible to make asynchronous primal updates in dual subgradient methods by the use of approximate Lagrange multipliers or Lagrange multipliers with 'errors'. An important difference with previous works is that we allow agents to select the Lagrange multiplier they prefer when computing a primal variable or partial subgradient. That is, agents are not constrained to use the 'freshest' dual variable available in the system. This allows us not only to obtain asynchronous primal updates, but also to have flexibility as to how to select control actions and therefore model problems. We illustrate the results with a networking example where agents make asynchronous packet transmissions.


ThD5 
Lower Level 
Learning, Optimization, and Control 
Invited Session 
Chair: Raginsky, Maxim  Univ. of Illinois at UrbanaChampaign 
CoChair: Belabbas, MohamedAli  Univ. of Illinois, UrbanaChampaign 
Organizer: Belabbas, MohamedAli  Univ. of Illinois, UrbanaChampaign 
Organizer: Raginsky, Maxim  Univ. of Illinois at UrbanaChampaign 

15:3015:50, Paper ThD5.1  
Control of Unknown Linear Systems with Thompson Sampling (I) 
Ouyang, Yi  Univ. of Southern California 
Gagrani, Mukul  Univ. of Southern California 
Jain, Rahul  Univ. of Southern California 
Keywords: Adaptive Control and Automation, Machine Learning and Learning Theory, Learning and Inference
Abstract: We propose a Thompson sampling based learning algorithm for the Linear Quadratic (LQ) control problem with unknown system parameters. The algorithm is called Thompson sampling with dynamic episodes (TSDE) where two stopping criteria determine the lengths of the dynamic episodes in Thompson sampling. The first stopping criterion controls the growth rate of episode length. The second stopping criterion is triggered when the determinant of the sample covariance matrix is less than half of the previous value. We show under some conditions on the prior distribution that the expected (Bayesian) regret of TSDE accumulated up to time T is bounded by O~(sqrt(T)). Here O~(·) hides constants and logarithmic factors. This is the first O ̃~(sqrt(T) ) bound on expected regret of learning in LQ control. Numerical simulations are provided to illustrate the performance of TSDE.


15:5016:10, Paper ThD5.2  
Simulation Optimization Via GradientBased Stochastic Search (I) 
Zhou, Enlu  Georgia Inst. of Tech. 
Bhatnagar, Shalabh  Indian Inst. of Science 

16:1016:30, Paper ThD5.3  
Robust Convergence Analysis of Distributed Optimization Algorithms (I) 
Sundararajan, Akhil  Univ. of WisconsinMadison 
Hu, Bin  Univ. of WisconsinMadison 
Lessard, Laurent  Univ. of WisconsinMadison 
Keywords: Optimization, Distributed and LargeScale Systems, Robust and Nonlinear Control
Abstract: We present a unified framework for analyzing the convergence of distributed optimization algorithms by formulating a semidefinite program (SDP) which can be efficiently solved to bound the linear rate of convergence. Two different SDP formulations are considered. First, we formulate an SDP that depends explicitly on the gossip matrix of the network graph. This result provides bounds that depend explicitly on the graph topology, but the SDP dimension scales with the size of the graph. Second, we formulate an SDP that depends implicitly on the gossip matrix via its spectral gap. This result provides coarser bounds, but yields a small SDP that is independent of graph size. Our approach improves upon existing bounds for the algorithms we analyzed, and numerical simulations reveal that our bounds are likely tight. The efficient and automated nature of our analysis makes it a powerful tool for algorithm selection and tuning, and for the discovery of new algorithms as well.


16:3016:50, Paper ThD5.4  
On Exploiting Spectral Properties for Solving MDP with Large State Space 
Liu, Libin  Univ. of Southern California 
Chattopadhyay, Arpan  Univ. of Southern California 
Mitra, Urbashi  Univ. of Southern California 
Keywords: Machine Learning and Learning Theory, Computational Models and Representations, Learning and Inference
Abstract: A large number of systems are wellmodeled by Markov Decision Processes (MDPs). In particular, certain wireless communication networks and biological networks admit such models. Herein, moderate complexity strategies are proposed for computing the optimal policy for a large state space with long run discounted cost MDP, by exploiting spectral properties of the probability transition matrices (PTM). Methods such as value iteration and policy iteration for such problems are computationally prohibitive for large state spaces. Reduced dimensional policy iteration can be achieved by projecting the value function on a proper subspace. However there is no clear method for determining the optimal subspace. To this end, Graph signal processing methods have the potential to provide a solution. In order to use spectral techniques, an appropriate positive semidefinite (PSD) matrix is generated from the PTM and the single stage cost vector. Low complexity computation of the value function is enabled by the bases of this dominant subspace. The proposed projections are combined with policy iteration to find the optimal policy. Finally, numerical results on a wireless system are provided to highlight the performances and tradeoffs of these various algorithms, and we found that direct spectral decomposition of outer product of PTM gives us best performance in general.


16:5017:10, Paper ThD5.5  
Vaidya Walk: A Sampling Algorithm Based on VolumetricLogarithmic Barrier 
Chen, Yuansi  Univ. of California, Berkeley 
Dwivedi, Raaz  Univ. of California Berkeley 
Wainwright, Martin  UC Berkeley 
Yu, Bin  UC Berkeley 
Keywords: Machine Learning and Learning Theory, Learning and Inference, Optimization
Abstract: We propose a new random walk known as Vaidya walk, to generate samples from the uniform distribution on the interior of a polytope. The random walk is an instance of sampling algorithm derived from an interior point method and is based on the volumetric logarithmic barrier introduced by Vaidya. We show that Vaidya walk mixes in significantly fewer steps compared to Dikin walk, a random walk introduced by Kannan and Narayanan which was based on the logarithmic barrier method. In particular, we prove that for a polytope in R^n defined by m constraints, the new random walk mixes in O(sqrt{m/n}) fewer steps compared to Dikin walk. The per iteration cost for our method is at most twice that of Dikin walk, and hence the speed up is significant for polytopes with m>>n. Furthermore, the algorithm is also faster than Ball walk and HitandRun for a large family of polytopes. We illustrate the speedup compared to Dikin walk via several numerical examples and discuss possible new and faster algorithms for sampling from polytopes.


17:1017:30, Paper ThD5.6  
Stability of Learning Algorithms That Converge to Local Minima (I) 
Charles, Zachary  Univ. of Wisconsin  Madison 
Papailiopoulos, Dimitris  Univ. of WisconsinMadison 

17:3017:50, Paper ThD5.7  
Differentiable Imitation Learning for Sequential Prediction (I) 
Boots, Byron  Georgia Inst. of Tech. 
 