OpenRaiser/Intern-Atlas huggingface dataset:
Sample Complexity Bounds on Differentially Private Learning via Communication Complexity
Venue: arXiv cs.DS 2015
Year: 2015

In this work we analyze the sample complexity of classification by differentially private algorithms. Differential privacy is a strong and well-studied notion of privacy introduced by Dwork et al. (2006) that ensures that the output of an algorithm leaks little information about the data point provided by any of the participating individuals. Sample complexity of private PAC and agnostic learning was studied in a number of prior works starting with (Kasiviswanathan et al., 2008) but a number of basic questions still remain open, most notably whether learning with privacy requires more samples than learning without privacy. We show that the sample complexity of learning with (pure) differential privacy can be arbitrarily higher than the sample complexity of learning without the privacy constraint or the sample complexity of learning with approximate differential privacy. Our second contribution and the main tool is an equivalence between the sample complexity of (pure) differentially private learning of a concept class $C$ (or $SCDP(C)$) and the randomized one-way communication complexity of the evaluation problem for concepts from $C$. Using this equivalence we prove the following bounds: 1. $SCDP(C) = Ω(LDim(C))$, where $LDim(C)$ is the Littlestone's (1987) dimension characterizing the number of mistakes in the online-mistake-bound learning model. Known bounds on $LDim(C)$ then imply that $SCDP(C)$ can be much higher than the VC-dimension of $C$. 2. For any $t$, there exists a class $C$ such that $LDim(C)=2$ but $SCDP(C) \geq t$. 3. For any $t$, there exists a class $C$ such that the sample complexity of (pure) $α$-differentially private PAC learning is $Ω(t/α)$ but the sample complexity of the relaxed $(α,β)$-differentially private PAC learning is $O(\log(1/β)/α)$. This resolves an open problem of Beimel et al. (2013b).
About Adaptive Coding on Countable Alphabets: Max-Stable Envelope Classes
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we study the problem of lossless universal source coding for stationary memoryless sources on countably infinite alphabets. This task is generally not achievable without restricting the class of sources over which universality is desired. Building on our prior work, we propose natural families of sources characterized by a common dominating envelope. We particularly emphasize the notion of adaptivity, which is the ability to perform as well as an oracle knowing the envelope, without actually knowing it. This is closely related to the notion of hierarchical universal source coding, but with the important difference that families of envelope classes are not discretely indexed and not necessarily nested. Our contribution is to extend the classes of envelopes over which adaptive universal source coding is possible, namely by including max-stable (heavy-tailed) envelopes which are excellent models in many applications, such as natural language modeling. We derive a minimax lower bound on the redundancy of any code on such envelope classes, including an oracle that knows the envelope. We then propose a constructive code that does not use knowledge of the envelope. The code is computationally efficient and is structured to use an {E}xpanding {T}hreshold for {A}uto-{C}ensoring, and we therefore dub it the \textsc{ETAC}-code. We prove that the \textsc{ETAC}-code achieves the lower bound on the minimax redundancy within a factor logarithmic in the sequence length, and can be therefore qualified as a near-adaptive code over families of heavy-tailed envelopes. For finite and light-tailed envelopes the penalty is even less, and the same code follows closely previous results that explicitly made the light-tailed assumption. Our technical results are founded on methods from regular variation theory and concentration of measure.
Concise Probability Distributions of Eigenvalues of Real-Valued Wishart Matrices
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider the problem of deriving new eigenvalue distributions of real-valued Wishart matrices that arises in many scientific and engineering applications. The distributions are derived using the tools from the theory of skew symmetric matrices. In particular, we relate the multiple integrals of a determinant, which arises while finding the eigenvalue distributions, in terms of the Pfaffian of skew-symmetric matrices. Pfaffians being the square root of skew symmetric matrices are easy to compute than the conventional distributions that involve Zonal polynomials or beta integrals. We show that the plots of the derived distributions are exactly coinciding with the numerically simulated plots.
Landmark-matching Transformation with Large Deformation via n-dimensional Quasi-conformal Maps
Venue: arXiv cs.CG 2015
Year: 2015

We propose a new method to obtain landmark-matching transformations between n-dimensional Euclidean spaces with large deformations. Given a set of feature correspondences, our algorithm searches for an optimal folding-free mapping that satisfies the prescribed landmark constraints. The standard conformality distortion defined for mappings between 2-dimensional spaces is first generalized to the $n$-dimensional conformality distortion $K(f)$ for a mapping $f$ between $n$-dimensional Euclidean spaces $(n \geq 3)$. We then propose a variational model involving $K(f)$ to tackle the landmark-matching problem in higher dimensional spaces. The generalized conformality term $K(f)$ enforces the bijectivity of the optimized mapping and minimizes its local geometric distortions even with large deformations. Another challenge is the high computational cost of the proposed model. To tackle this, we have also proposed a numerical method to solve the optimization problem more efficiently. Alternating direction method with multiplier (ADMM) is applied to split the optimization problem into two subproblems. Preconditioned conjugate gradient method with multi-grid preconditioner is applied to solve one of the sub-problems, while a fixed-point iteration is proposed to solve another subproblem. Experiments have been carried out on both synthetic examples and lung CT images to compute the diffeomorphic landmark-matching transformation with different landmark constraints. Results show the efficacy of our proposed model to obtain a folding-free landmark-matching transformation between $n$-dimensional spaces with large deformations.
Compressive sensing based Bayesian sparse channel estimation for OFDM communication systems: high performance and low complexity
Venue: arXiv cs.IT 2015
Year: 2015

In orthogonal frequency division modulation (OFDM) communication systems, channel state information (CSI) is required at receiver due to the fact that frequency-selective fading channel leads to disgusting inter-symbol interference (ISI) over data transmission. Broadband channel model is often described by very few dominant channel taps and they can be probed by compressive sensing based sparse channel estimation (SCE) methods, e.g., orthogonal matching pursuit algorithm, which can take the advantage of sparse structure effectively in the channel as for prior information. However, these developed methods are vulnerable to both noise interference and column coherence of training signal matrix. In other words, the primary objective of these conventional methods is to catch the dominant channel taps without a report of posterior channel uncertainty. To improve the estimation performance, we proposed a compressive sensing based Bayesian sparse channel estimation (BSCE) method which can not only exploit the channel sparsity but also mitigate the unexpected channel uncertainty without scarifying any computational complexity. The propose method can reveal potential ambiguity among multiple channel estimators that are ambiguous due to observation noise or correlation interference among columns in the training matrix. Computer simulations show that propose method can improve the estimation performance when comparing with conventional SCE methods.
On Redundant Topological Constraints
Venue: arXiv cs.AI 2015
Year: 2015

The Region Connection Calculus (RCC) is a well-known calculus for representing part-whole and topological relations. It plays an important role in qualitative spatial reasoning, geographical information science, and ontology. The computational complexity of reasoning with RCC5 and RCC8 (two fragments of RCC) as well as other qualitative spatial/temporal calculi has been investigated in depth in the literature. Most of these works focus on the consistency of qualitative constraint networks. In this paper, we consider the important problem of redundant qualitative constraints. For a set $Γ$ of qualitative constraints, we say a constraint $(x R y)$ in $Γ$ is redundant if it is entailed by the rest of $Γ$. A prime subnetwork of $Γ$ is a subset of $Γ$ which contains no redundant constraints and has the same solution set as $Γ$. It is natural to ask how to compute such a prime subnetwork, and when it is unique. In this paper, we show that this problem is in general intractable, but becomes tractable if $Γ$ is over a tractable subalgebra $\mathcal{S}$ of a qualitative calculus. Furthermore, if $\mathcal{S}$ is a subalgebra of RCC5 or RCC8 in which weak composition distributes over nonempty intersections, then $Γ$ has a unique prime subnetwork, which can be obtained in cubic time by removing all redundant constraints simultaneously from $Γ$. As a byproduct, we show that any path-consistent network over such a distributive subalgebra is weakly globally consistent and minimal. A thorough empirical analysis of the prime subnetwork upon real geographical data sets demonstrates the approach is able to identify significantly more redundant constraints than previously proposed algorithms, especially in constraint networks with larger proportions of partial overlap relations.
Hilberg Exponents: New Measures of Long Memory in the Process
Venue: arXiv cs.IT 2015
Year: 2015

The paper concerns the rates of power-law growth of mutual information computed for a stationary measure or for a universal code. The rates are called Hilberg exponents and four such quantities are defined for each measure and each code: two random exponents and two expected exponents. A particularly interesting case arises for conditional algorithmic mutual information. In this case, the random Hilberg exponents are almost surely constant on ergodic sources and are bounded by the expected Hilberg exponents. This property is a "second-order" analogue of the Shannon-McMillan-Breiman theorem, proved without invoking the ergodic theorem. It carries over to Hilberg exponents for the underlying probability measure via Shannon-Fano coding and Barron inequality. Moreover, the expected Hilberg exponents can be linked for different universal codes. Namely, if one code dominates another, the expected Hilberg exponents are greater for the former than for the latter. The paper is concluded by an evaluation of Hilberg exponents for certain sources such as the mixture Bernoulli process and the Santa Fe processes.
A Composable Method for Real-Time Control of Active Distribution Networks with Explicit Power Setpoints
Venue: arXiv cs.SY 2015
Year: 2015

The conventional approach for the control of distribution networks, in the presence of active generation and/or controllable loads and storage, involves a combination of both frequency and voltage regulation at different time scales. With the increased penetration of stochastic resources, distributed generation and demand response, this approach shows severe limitations in both the optimal and feasible operation of these networks, as well as in the aggregation of the network resources for upper-layer power systems. An alternative approach is to directly control the targeted grid by defining explicit and real-time setpoints for active/reactive power absorptions/injections defined by a solution of a specific optimization problem; but this quickly becomes intractable when systems get large or diverse. In this paper, we address this problem and propose a method for the explicit control of the grid status, based on a common abstract model characterized by the main property of being composable. That is to say, subsystems can be aggregated into virtual devices that hide their internal complexity. Thus the proposed method can easily cope with systems of any size or complexity. The framework is presented in this Part I, whilst in Part II we illustrate its application to a CIGRÉ low voltage benchmark microgrid. In particular, we provide implementation examples with respect to typical devices connected to distribution networks and evaluate of the performance and benefits of the proposed control framework.
NetworKit: A Tool Suite for Large-scale Complex Network Analysis
Venue: arXiv cs.SI 2015
Year: 2015

We introduce NetworKit, an open-source software package for analyzing the structure of large complex networks. Appropriate algorithmic solutions are required to handle increasingly common large graph data sets containing up to billions of connections. We describe the methodology applied to develop scalable solutions to network analysis problems, including techniques like parallelization, heuristics for computationally expensive problems, efficient data structures, and modular software architecture. Our goal for the software is to package results of our algorithm engineering efforts and put them into the hands of domain experts. NetworKit is implemented as a hybrid combining the kernels written in C++ with a Python front end, enabling integration into the Python ecosystem of tested tools for data analysis and scientific computing. The package provides a wide range of functionality (including common and novel analytics algorithms and graph generators) and does so via a convenient interface. In an experimental comparison with related software, NetworKit shows the best performance on a range of typical analysis tasks.
Massive MIMO performance evaluation based on measured propagation data
Venue: arXiv cs.IT 2015
Year: 2015

Massive MIMO, also known as very-large MIMO or large-scale antenna systems, is a new technique that potentially can offer large network capacities in multi-user scenarios. With a massive MIMO system, we consider the case where a base station equipped with a large number of antenna elements simultaneously serves multiple single-antenna users in the same time-frequency resource. So far, investigations are mostly based on theoretical channels with independent and identically distributed (i.i.d.) complex Gaussian coefficients, i.e., i.i.d. Rayleigh channels. Here, we investigate how massive MIMO performs in channels measured in real propagation environments. Channel measurements were performed at 2.6 GHz using a virtual uniform linear array (ULA) which has a physically large aperture, and a practical uniform cylindrical array (UCA) which is more compact in size, both having 128 antenna ports. Based on measurement data, we illustrate channel behavior of massive MIMO in three representative propagation conditions, and evaluate the corresponding performance. The investigation shows that the measured channels, for both array types, allow us to achieve performance close to that in i.i.d. Rayleigh channels. It is concluded that in real propagation environments we have characteristics that can allow for efficient use of massive MIMO, i.e., the theoretical advantages of this new technology can also be harvested in real channels.
A Survey of Algorithms and Analysis for Adaptive Online Learning
Venue: arXiv cs.LG 2015
Year: 2015

We present tools for the analysis of Follow-The-Regularized-Leader (FTRL), Dual Averaging, and Mirror Descent algorithms when the regularizer (equivalently, prox-function or learning rate schedule) is chosen adaptively based on the data. Adaptivity can be used to prove regret bounds that hold on every round, and also allows for data-dependent regret bounds as in AdaGrad-style algorithms (e.g., Online Gradient Descent with adaptive per-coordinate learning rates). We present results from a large number of prior works in a unified manner, using a modular and tight analysis that isolates the key arguments in easily re-usable lemmas. This approach strengthens pre-viously known FTRL analysis techniques to produce bounds as tight as those achieved by potential functions or primal-dual analysis. Further, we prove a general and exact equivalence between an arbitrary adaptive Mirror Descent algorithm and a correspond- ing FTRL update, which allows us to analyze any Mirror Descent algorithm in the same framework. The key to bridging the gap between Dual Averaging and Mirror Descent algorithms lies in an analysis of the FTRL-Proximal algorithm family. Our regret bounds are proved in the most general form, holding for arbitrary norms and non-smooth regularizers with time-varying weight.
MIMO Zero-Forcing Performance Evaluation Using the Holonomic Gradient Method
Venue: arXiv cs.IT 2015
Year: 2015

For multiple-input multiple-output (MIMO) spatial-multiplexing transmission, zero-forcing detection (ZF) is appealing because of its low complexity. Our recent MIMO ZF performance analysis for Rician--Rayleigh fading, which is relevant in heterogeneous networks, has yielded for the ZF outage probability and ergodic capacity infinite-series expressions. Because they arose from expanding the confluent hypergeometric function $ {_1\! F_1} (\cdot, \cdot, σ) $ around 0, they do not converge numerically at realistically-high Rician $ K $-factor values. Therefore, herein, we seek to take advantage of the fact that $ {_1\! F_1} (\cdot, \cdot, σ) $ satisfies a differential equation, i.e., it is a \textit{holonomic} function. Holonomic functions can be computed by the \textit{holonomic gradient method} (HGM), i.e., by numerically solving the satisfied differential equation. Thus, we first reveal that the moment generating function (m.g.f.) and probability density function (p.d.f.) of the ZF signal-to-noise ratio (SNR) are holonomic. Then, from the differential equation for $ {_1\! F_1} (\cdot, \cdot, σ) $, we deduce those satisfied by the SNR m.g.f. and p.d.f., and demonstrate that the HGM helps compute the p.d.f. accurately at practically-relevant values of $ K $. Finally, numerical integration of the SNR p.d.f. produced by HGM yields accurate ZF outage probability and ergodic capacity results.
Organization mechanism and counting algorithm on Vertex-Cover solutions
Venue: arXiv cs.CC 2015
Year: 2015

Counting the solution number of combinational optimization problems is an important topic in the study of computational complexity, especially on the #P-complete complexity class. In this paper, we first investigate some organizations of Vertex-Cover unfrozen subgraphs by the underlying connectivity and connected components of unfrozen vertices. Then, a Vertex-Cover Solution Number Counting Algorithm is proposed and its complexity analysis is provided, the results of which fit very well with the simulations and have better performance than those by 1-RSB in a neighborhood of c = e for random graphs. Base on the algorithm, variation and fluctuation on the solution number statistics are studied to reveal the evolution mechanism of the solution numbers. Besides, marginal probability distributions on the solution space are investigated on both random graph and scale-free graph to illustrate different evolution characteristics of their solution spaces. Thus, doing solution number counting based on graph expression of solution space should be an alternative and meaningful way to study the hardness of NP-complete and #P-complete problems, and appropriate algorithm design can help to achieve better approximations of solving combinational optimization problems and the corresponding counting problems.
Energy-Efficient Transmission Schedule for Delay-Limited Bursty Data Arrivals under Non-Ideal Circuit Power Consumption
Venue: arXiv cs.IT 2015
Year: 2015

This paper develops a novel approach to obtaining energy-efficient transmission schedules for delay-limited bursty data arrivals under non-ideal circuit power consumption. Assuming a-prior knowledge of packet arrivals, deadlines and channel realizations, we show that the problem can be formulated as a convex program. For both time-invariant and time-varying fading channels, it is revealed that the optimal transmission between any two consecutive channel or data state changing instants, termed epoch, can only take one of the three strategies: (i) no transmission, (ii) transmission with an energy-efficiency (EE) maximizing rate over part of the epoch, or (iii) transmission with a rate greater than the EE-maximizing rate over the whole epoch. Based on this specific structure, efficient algorithms are then developed to find the optimal policies that minimize the total energy consumption with a low computational complexity. The proposed approach can provide the optimal benchmarks for practical schemes designed for transmissions of delay-limited data arrivals, and can be employed to develop efficient online scheduling schemes which require only causal knowledge of data arrivals and deadline requirements.
Justification of Logarithmic Loss via the Benefit of Side Information
Venue: arXiv cs.IT 2015
Year: 2015

We consider a natural measure of relevance: the reduction in optimal prediction risk in the presence of side information. For any given loss function, this relevance measure captures the benefit of side information for performing inference on a random variable under this loss function. When such a measure satisfies a natural data processing property, and the random variable of interest has alphabet size greater than two, we show that it is uniquely characterized by the mutual information, and the corresponding loss function coincides with logarithmic loss. In doing so, our work provides a new characterization of mutual information, and justifies its use as a measure of relevance. When the alphabet is binary, we characterize the only admissible forms the measure of relevance can assume while obeying the specified data processing property. Our results naturally extend to measuring causal influence between stochastic processes, where we unify different causal-inference measures in the literature as instantiations of directed information.
An Information-Theoretic Analysis of Thompson Sampling
Venue: arXiv cs.LG 2015
Year: 2015

We provide an information-theoretic analysis of Thompson sampling that applies across a broad range of online optimization problems in which a decision-maker must learn from partial feedback. This analysis inherits the simplicity and elegance of information theory and leads to regret bounds that scale with the entropy of the optimal-action distribution. This strengthens preexisting results and yields new insight into how information improves performance.
Software Agents Interaction Algorithms in Virtual Learning Environment
Venue: arXiv cs.MA 2015
Year: 2015

This paper highlights the multi-agent learning virtual environment and agents communication algorithms. The researcher proposed three algorithms required software agents interaction in virtual learning information system environment. The first proposed algorithm is agents interaction localization algorithm, the second one is the dynamic agents distribution algorithm (load distribution algorithm), and the third model is Agent communication algorithm based on using agents intermediaries. The main objectives of these algorithms are to reduce the response time for any agents changes in virtual learning environment (VLE) by increasing the information exchange intensity between software agents and reduce the overall network load, and to improve the communication between mobile agents in distributed information system to support effectiveness. Finally the paper describe the algorithms of information exchange between mobile agents in VLE based on the expansion of the address structure and the use of an agent, intermediary agents, matchmaking agents, brokers and their entrepreneurial functions