OpenRaiser/Intern-Atlas huggingface dataset:
Energy Efficient Resource Allocation for Hybrid Services with Future Channel Gains
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we propose a framework to maximize energy efficiency (EE) of a system supporting real-time (RT) and non-real-time services by exploiting future average channel gains of mobile users, which change in the timescale of seconds and are reported predictable within a minute-long time window. To demonstrate the potential of improving EE by jointly optimizing resource allocation for both services by harnessing both future average channel gains and current instantaneous channel gains, we optimize a two-timescale policy with perfect prediction, by taking orthogonal frequency division multiple access system serving RT and video-on-demand (VoD) users as an example. Considering that fine-grained prediction for every user is with high cost, we propose a heuristic policy that only needs to predict the median of average channel gains of VoD users. Simulation results show that the optimal policy outperforms relevant counterparts, indicating the necessity of the joint optimization for both services and for two timescales. Besides, the heuristic policy performs closely to the optimal policy with perfect prediction while becomes superior with large prediction errors. This suggests that the EE gain over non-predictive policies can be captured with coarse-grained prediction.
Sampling of the Wiener Process for Remote Estimation over a Channel with Random Delay
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we consider a problem of sampling a Wiener process, with samples forwarded to a remote estimator over a channel that is modeled as a queue. The estimator reconstructs an estimate of the real-time signal value from causally received samples. We study the optimal online sampling strategy that minimizes the mean square estimation error subject to a sampling rate constraint. We prove that the optimal sampling strategy is a threshold policy, and find the optimal threshold. This threshold is determined by how much the Wiener process varies during the random service time and the maximum allowed sampling rate. Further, if the sampling times are independent of the observed Wiener process, the above sampling problem for minimizing the estimation error is equivalent to a sampling problem for minimizing the age of information. This reveals an interesting connection between the age of information and remote estimation error. Our comparisons show that the estimation error achieved by the optimal sampling policy can be much smaller than those of age-optimal sampling, zero-wait sampling, and periodic sampling.
Sensor Calibration for Off-the-Grid Spectral Estimation
Venue: arXiv cs.IT 2019
Year: 2019

This paper studies sensor calibration in spectral estimation where the true frequencies are located on a continuous domain. We consider a uniform array of sensors that collects measurements whose spectrum is composed of a finite number of frequencies, where each sensor has an unknown calibration parameter. Our goal is to recover the spectrum and the calibration parameters simultaneously from multiple snapshots of the measurements. In the noiseless case with an infinite number of snapshots, we prove uniqueness of this problem up to certain trivial, inevitable ambiguities based on an algebraic method, as long as there are more sensors than frequencies. We then analyze the sensitivity of this algebraic technique with respect to the number of snapshots and noise. We next propose an optimization approach that makes full use of the measurements by minimizing a non-convex objective which is non-negative and continuously differentiable over all calibration parameters and Toeplitz matrices. We prove that, in the case of infinite snapshots and noiseless measurements, the objective vanishes only at equivalent solutions to the true calibration parameters and the measurement covariance matrix. The objective is minimized using Wirtinger gradient descent which is proven to converge to a critical point. We show empirically that this critical point provides a good approximation of the true calibration parameters and the underlying frequencies.
Gradient Coding from Cyclic MDS Codes and Expander Graphs
Venue: arXiv cs.IT 2019
Year: 2019

Gradient coding is a technique for straggler mitigation in distributed learning. In this paper we design novel gradient codes using tools from classical coding theory, namely, cyclic MDS codes, which compare favorably with existing solutions, both in the applicable range of parameters and in the complexity of the involved algorithms. Second, we introduce an approximate variant of the gradient coding problem, in which we settle for approximate gradient computation instead of the exact one. This approach enables graceful degradation, i.e., the $\ell_2$ error of the approximate gradient is a decreasing function of the number of stragglers. Our main result is that normalized adjacency matrices of expander graphs yield excellent approximate gradient codes, which enable significantly less computation compared to exact gradient coding, and guarantee faster convergence than trivial solutions under standard assumptions. We experimentally test our approach on Amazon EC2, and show that the generalization error of approximate gradient coding is very close to the full gradient while requiring significantly less computation from the workers.
Satiation in Fisher Markets and Approximation of Nash Social Welfare
Venue: arXiv cs.DS 2019
Year: 2019

We study linear Fisher markets with satiation. In these markets, sellers have earning limits and buyers have utility limits. Beyond natural applications in economics, these markets arise in the context of maximizing Nash social welfare when allocating indivisible items to agents. In contrast to markets with either earning or utility limits, markets with both limits have not been studied before. They turn out to have fundamentally different properties. In general, the existence of competitive equilibria is not guaranteed. We identify a natural property of markets (termed money clearing) that implies existence. We show that the set of equilibria is not always convex, answering a question of Cole et al. [EC'17]. We design an FPTAS to compute an approximate equilibrium and prove that the problem of computing an exact equilibrium lies in the intersection of complexity classes PLS and PPAD. For a constant number of buyers or goods, we give a polynomial-time algorithm to compute an exact equilibrium. We show how (approximate) equilibria can be rounded and provide the first constant-factor approximation algorithm (with a factor of 2.404) for maximizing Nash social welfare when agents have budget-additive valuations. Finally, we significantly improve the approximation hardness for additive valuations to \sqrt{8/7} > 1.069 (over 1.00008 by Lee [IPL'17]).
Binary Tomography Reconstructions With Few Projections
Venue: arXiv cs.DM 2019
Year: 2019

Discrete tomography deals with the reconstruction of images from projections collected along a few given directions. Different approaches can be considered, according to different models. In this paper we adopt the grid model, where pixels are lattice points with integer coordinates, X-rays are discrete lattice lines, and projections are obtained by counting the number of lattice points intercepted by X-rays taken in the assigned directions. We move from a theoretical result that allows uniqueness of reconstruction in the grid with just four suitably selected X-ray directions. In this framework, the structure of the allowed ghosts is studied and described. This leads to a new result, stating that the unique binary solution can be explicitly and exactly retrieved from the minimum Euclidean norm solution by means of a rounding method based on some special entries, which are precisely determined. A corresponding iterative algorithm has been implemented, and tested on a few phantoms having different characteristics and structure.
Deep Layer Aggregation
Venue: arXiv cs.CV 2019
Year: 2019

Visual recognition requires rich representations that span levels from low to high, scales from small to large, and resolutions from fine to coarse. Even with the depth of features in a convolutional network, a layer in isolation is not enough: compounding and aggregating these representations improves inference of what and where. Architectural efforts are exploring many dimensions for network backbones, designing deeper or wider architectures, but how to best aggregate layers and blocks across a network deserves further attention. Although skip connections have been incorporated to combine layers, these connections have been "shallow" themselves, and only fuse by simple, one-step operations. We augment standard architectures with deeper aggregation to better fuse information across layers. Our deep layer aggregation structures iteratively and hierarchically merge the feature hierarchy to make networks with better accuracy and fewer parameters. Experiments across architectures and tasks show that deep layer aggregation improves recognition and resolution compared to existing branching and merging schemes. The code is at https://github.com/ucbdrive/dla.
Optimal Secure Multi-Layer IoT Network Design
Venue: arXiv cs.GT 2019
Year: 2019

With the remarkable growth of the Internet and communication technologies over the past few decades, Internet of Things (IoTs) is enabling the ubiquitous connectivity of heterogeneous physical devices with software, sensors, and actuators. IoT networks are naturally two-layer with the cloud and cellular networks coexisting with the underlaid device-to-device (D2D) communications. The connectivity of IoTs plays an important role in information dissemination for mission-critical and civilian applications. However, IoT communication networks are vulnerable to cyber attacks including the denial-of-service (DoS) and jamming attacks, resulting in link removals in IoT network. In this work, we develop a heterogeneous IoT network design framework in which a network designer can add links to provide additional communication paths between two nodes or secure links against attacks by investing resources. By anticipating the strategic cyber attacks, we characterize the optimal design of secure IoT network by first providing a lower bound on the number of links a secure network requires for a given budget of protected links, and then developing a method to construct networks that satisfy the heterogeneous network design specifications. Therefore, each layer of the designed heterogeneous IoT network is resistant to a predefined level of malicious attacks with minimum resources. Finally, we provide case studies on the Internet of Battlefield Things (IoBT) to corroborate and illustrate our obtained results.
Optimal Timing in Dynamic and Robust Attacker Engagement During Advanced Persistent Threats
Venue: arXiv cs.CR 2019
Year: 2019

Advanced persistent threats (APTs) are stealthy attacks which make use of social engineering and deception to give adversaries insider access to networked systems. Against APTs, active defense technologies aim to create and exploit information asymmetry for defenders. In this paper, we study a scenario in which a powerful defender uses honeynets for active defense in order to observe an attacker who has penetrated the network. Rather than immediately eject the attacker, the defender may elect to gather information. We introduce an undiscounted, infinite-horizon Markov decision process on a continuous state space in order to model the defender's problem. We find a threshold of information that the defender should gather about the attacker before ejecting him. Then we study the robustness of this policy using a Stackelberg game. Finally, we simulate the policy for a conceptual network. Our results provide a quantitative foundation for studying optimal timing for attacker engagement in network defense.
Generic second-order macroscopic traffic node model for general multi-input multi-output road junctions via a dynamic system approach
Venue: arXiv cs.SY 2019
Year: 2019

This paper addresses an open problem in traffic modeling: the second-order macroscopic node problem. A second-order macroscopic traffic model, in contrast to a first-order model, allows for variation of driving behavior across subpopulations of vehicles in the flow. The second-order models are thus more descriptive (e.g., they have been used to model variable mixtures of behaviorally-different traffic, like car/truck traffic, autonomous/human-driven traffic, etc.), but are much more complex. The second-order node problem is a particularly complex problem, as it requires the resolution of discontinuities in traffic density and mixture characteristics, and solving of throughflows for arbitrary numbers of input and output roads to a node (in other words, this is an arbitrary-dimensional Riemann problem with two conserved quantities). In this paper, we extend the well-known "Generic Class of Node Model" constraints to the second order and present a simple solution algorithm to the second-order node problem. Our solution makes use of a recently-introduced dynamic system characterization of the first-order node model problem, which gives insight and intuition as to the continuous-time dynamics implicit in node models. We further argue that the common "supply and demand" construction of node models that decouples them from link models is not suitable to the second-order node problem. Our second-order node model and solution method have immediate applications in allowing modeling of behaviorally-complex traffic flows of contemporary interest (like partially-autonomous-vehicle flows) in arbitrary road networks.
Query expansion techniques for information retrieval: A survey
Venue: arXiv cs.IR 2019
Year: 2019

With the ever increasing size of the web, relevant information extraction on the Internet with a query formed by a few keywords has become a big challenge. Query Expansion (QE) plays a crucial role in improving searches on the Internet. Here, the user's initial query is reformulated by adding additional meaningful terms with similar significance. QE -- as part of information retrieval (IR) -- has long attracted researchers' attention. It has become very influential in the field of personalized social document, question answering, cross-language IR, information filtering and multimedia IR. Research in QE has gained further prominence because of IR dedicated conferences such as TREC (Text Information Retrieval Conference) and CLEF (Conference and Labs of the Evaluation Forum). This paper surveys QE techniques in IR from 1960 to 2017 with respect to core techniques, data sources used, weighting and ranking methodologies, user participation and applications -- bringing out similarities and differences.
Abstract Hidden Markov Models: a monadic account of quantitative information flow
Venue: arXiv cs.LO 2019
Year: 2019

Hidden Markov Models, HMM's, are mathematical models of Markov processes with state that is hidden, but from which information can leak. They are typically represented as 3-way joint-probability distributions. We use HMM's as denotations of probabilistic hidden-state sequential programs: for that, we recast them as `abstract' HMM's, computations in the Giry monad $\mathbb{D}$, and we equip them with a partial order of increasing security. However to encode the monadic type with hiding over some state $\mathcal{X}$ we use $\mathbb{D}\mathcal{X}\to \mathbb{D}^2\mathcal{X}$ rather than the conventional $\mathcal{X}{\to}\mathbb{D}\mathcal{X}$ that suffices for Markov models whose state is not hidden. We illustrate the $\mathbb{D}\mathcal{X}\to \mathbb{D}^2\mathcal{X}$ construction with a small Haskell prototype. We then present uncertainty measures as a generalisation of the extant diversity of probabilistic entropies, with characteristic analytic properties for them, and show how the new entropies interact with the order of increasing security. Furthermore, we give a `backwards' uncertainty-transformer semantics for HMM's that is dual to the `forwards' abstract HMM's - it is an analogue of the duality between forwards, relational semantics and backwards, predicate-transformer semantics for imperative programs with demonic choice. Finally, we argue that, from this new denotational-semantic viewpoint, one can see that the Dalenius desideratum for statistical databases is actually an issue in compositionality. We propose a means for taking it into account.
Transparency: Motivations and Challenges
Venue: arXiv cs.CY 2019
Year: 2019

Transparency is often deemed critical to enable effective real-world deployment of intelligent systems. Yet the motivations for and benefits of different types of transparency can vary significantly depending on context, and objective measurement criteria are difficult to identify. We provide a brief survey, suggesting challenges and related concerns. We highlight and review settings where transparency may cause harm, discussing connections across privacy, multi-agent game theory, economics, fairness and trust.
ISS-MULT: Intelligent Sample Selection for Multi-Task Learning in Question Answering
Venue: arXiv cs.CL 2019
Year: 2019

Transferring knowledge from a source domain to another domain is useful, especially when gathering new data is very expensive and time-consuming. Deep networks have been well-studied for question answering tasks in recent years; however, no prominent research for transfer learning through deep neural networks exists in the question answering field. In this paper, two main methods (INIT and MULT) in this field are examined. Then, a new method named Intelligent sample selection (ISS-MULT) is proposed to improve the MULT method for question answering tasks. Different datasets, specificay SQuAD, SelQA, WikiQA, NewWikiQA and InforBoxQA, are used for evaluation. Moreover, two different tasks of question answering - answer selection and answer triggering - are evaluated to examine the effectiveness of transfer learning. The results show that using transfer learning generally improves the performance if the corpora are related and are based on the same policy. In addition, using ISS-MULT could finely improve the MULT method for question answering tasks, and these improvements prove more significant in the answer triggering task.
Statistics of Deep Generated Images
Venue: arXiv cs.CV 2019
Year: 2019

Here, we explore the low-level statistics of images generated by state-of-the-art deep generative models. First, Variational auto-encoder (VAE~\cite{kingma2013auto}), Wasserstein generative adversarial network (WGAN~\cite{arjovsky2017wasserstein}) and deep convolutional generative adversarial network (DCGAN~\cite{radford2015unsupervised}) are trained on the ImageNet dataset and a large set of cartoon frames from animations. Then, for images generated by these models as well as natural scenes and cartoons, statistics including mean power spectrum, the number of connected components in a given image area, distribution of random filter responses, and contrast distribution are computed. Our analyses on training images support current findings on scale invariance, non-Gaussianity, and Weibull contrast distribution of natural scenes. We find that although similar results hold over cartoon images, there is still a significant difference between statistics of natural scenes and images generated by VAE, DCGAN and WGAN models. In particular, generated images do not have scale invariant mean power spectrum magnitude, which indicates existence of extra structures in these images. Inspecting how well the statistics of deep generated images match the known statistical properties of natural images, such as scale invariance, non-Gaussianity, and Weibull contrast distribution, can a) reveal the degree to which deep learning models capture the essence of the natural scenes, b) provide a new dimension to evaluate models, and c) allow possible improvement of image generative models (e.g., via defining new loss functions).
Kripke Completeness of Strictly Positive Modal Logics over Meet-semilattices with Operators
Venue: arXiv cs.LO 2019
Year: 2019

Our concern is the completeness problem for spi-logics, that is, sets of implications between strictly positive formulas built from propositional variables, conjunction and modal diamond operators. Originated in logic, algebra and computer science, spi-logics have two natural semantics: meet-semilattices with monotone operators providing Birkhoff-style calculi, and first-order relational structures (aka Kripke frames) often used as the intended structures in applications. Here we lay foundations for a completeness theory that aims to answer the question whether the two semantics define the same consequence relations for a given spi-logic.
Optimal Offline Dynamic $2,3$-Edge/Vertex Connectivity
Venue: arXiv cs.DS 2019
Year: 2019

We give offline algorithms for processing a sequence of $2$ and $3$ edge and vertex connectivity queries in a fully-dynamic undirected graph. While the current best fully-dynamic online data structures for $3$-edge and $3$-vertex connectivity require $O(n^{2/3})$ and $O(n)$ time per update, respectively, our per-operation cost is only $O(\log n)$, optimal due to the dynamic connectivity lower bound of Patrascu and Demaine. Our approach utilizes a divide and conquer scheme that transforms a graph into smaller equivalents that preserve connectivity information. This construction of equivalents is closely-related to the development of vertex sparsifiers, and shares important connections to several upcoming results in dynamic graph data structures, outside of just the offline model.
Key and Message Semantic-Security over State-Dependent Channels
Venue: arXiv cs.IT 2019
Year: 2019

We study the trade-off between secret message (SM) and secret key (SK) rates, simultaneously achievable over a state-dependent (SD) wiretap channel (WTC) with non-causal channel state information (CSI) at the encoder. This model subsumes other instances of CSI availability as special cases, and calls for efficient utilization of the state sequence for both reliability and security purposes. An inner bound on the semantic-security (SS) SM-SK capacity region is derived based on a superposition coding scheme inspired by a past work of the authors. The region is shown to attain capacity for a certain class of SD-WTCs. SS is established by virtue of two versions of the strong soft-covering lemma. The derived region yields an improvement upon the previously best known SM-SK trade-off result reported by Prabhakaran et al., and, to the best of our knowledge, upon all other existing lower bounds for either SM or SK for this setup, even if the semantic security requirement is relaxed to weak secrecy. It is demonstrated that our region can be strictly larger than those reported in the preceding works.
Harnessing Correlations in Distributed Erasure-Coded Key-Value Stores
Venue: arXiv cs.IT 2019
Year: 2019

Motivated by applications of distributed storage systems to key-value stores, the multi-version coding problem was formulated to efficiently store frequently updated data in asynchronous decentralized storage systems. Inspired by consistency requirements in distributed systems, the main goal in the multi-version coding problem is to ensure that the latest possible version of the data is decodable, even if the data updates have not reached some servers in the system. In this paper, we study the storage cost of ensuring consistency for the case where the data versions are correlated, in contrast to previous work where data versions were treated as being independent. We provide multi-version code constructions that show that the storage cost can be significantly smaller than the previous constructions depending on the degree of correlation, despite the asynchrony and the decentralized nature. Our achievability results are based on Reed-Solomon codes and random binning. Through an information-theoretic converse, we show that our multi-version codes are nearly-optimal, within a factor of $2$, in certain interesting regimes.