We study reliable communication over point-to-point adversarial channels in which the adversary can observe the transmitted codeword via some function that takes the $n$-bit codeword as input and computes an $rn$-bit output for some given $r \in [0,1]$. We consider the scenario where the $rn$-bit observation is computationally bounded -- the adversary is free to choose an arbitrary observation function as long as the function can be computed using a polynomial amount of computational resources. This observation-based restriction differs from conventional channel-based computational limitations, where in the later case, the resource limitation applies to the computation of the (adversarial) channel error. For all $r \in [0,1-H(p)]$ where $H(\cdot)$ is the binary entropy function and $p$ is the adversary's error budget, we characterize the capacity of the above channel. For this range of $r$, we find that the capacity is identical to the completely obvious setting ($r=0$). This result can be viewed as a generalization of known results on myopic adversaries and channels with active eavesdroppers for which the observation process depends on a fixed distribution and fixed-linear structure, respectively, that cannot be chosen arbitrarily by the adversary.
相關內容
Sparse code multiple access (SCMA) is the most concerning scheme among non-orthogonal multiple access (NOMA) technologies for 5G wireless communication new interface. Another efficient technique in 5G aimed to improve spectral efficiency for local communications is device-to-device (D2D) communications. Therefore, we utilize the SCMA cellular network coexisting with D2D communications for the connection demand of the Internet of things (IOT), and improve the system sum rate performance of the hybrid network. We first derive the information-theoretic expression of the capacity for all users and find the capacity bound of cellular users based on the mutual interference between cellular users and D2D users. Then we consider the power optimization problem for the cellular users and D2D users jointly to maximize the system sum rate. To tackle the non-convex optimization problem, we propose a geometric programming (GP) based iterative power allocation algorithm. Simulation results demonstrate that the proposed algorithm converges fast and well improves the sum rate performance.
We consider unconstrained optimization problems with nonsmooth and convex objective function in the form of mathematical expectation. The proposed method approximates the objective function with a sample average function by using different sample size in each iteration. The sample size is chosen in an adaptive manner based on the Inexact Restoration. The method uses line search and assumes descent directions with respect to the current approximate function. We prove the almost sure convergence under the standard assumptions. The convergence rate is also considered and the worst-case complexity of $\mathcal{O} (\varepsilon^{-2})$ is proved. Numerical results for two types of problems, machine learning hinge loss and stochastic linear complementarity problems, show the efficiency of the proposed scheme.
Reaching a consensus in a swarm of robots is one of the fundamental problems in swarm robotics, examining the possibility of reaching an agreement within the swarm members. The recently-introduced contamination problem offers a new perspective of the problem, in which swarm members should reach a consensus in spite of the existence of adversarial members that intentionally act to divert the swarm members towards a different consensus. In this paper, we search for a consensus-reaching algorithm under the contamination problem setting by taking a top-down approach: We transform the problem to a centralized two-player game in which each player controls the behavior of a subset of the swarm, trying to force the entire swarm to converge to an agreement on its own value. We define a performance metric for each players performance, proving a correlation between this metric and the chances of the player to win the game. We then present the globally optimal solution to the game and prove that unfortunately it is unattainable in a distributed setting, due to the challenging characteristics of the swarm members. We therefore examine the problem on a simplified swarm model, and compare the performance of the globally optimal strategy with locally optimal strategies, demonstrating its superiority in rigorous simulation experiments.
Asymptotic study on the partition function $p(n)$ began with the work of Hardy and Ramanujan. Later Rademacher obtained a convergent series for $p(n)$ and an error bound was given by Lehmer. Despite having this, a full asymptotic expansion for $p(n)$ with an explicit error bound is not known. Recently O'Sullivan studied the asymptotic expansion of $p^{k}(n)$-partitions into $k$th powers, initiated by Wright, and consequently obtained an asymptotic expansion for $p(n)$ along with a concise description of the coefficients involved in the expansion but without any estimation of the error term. Here we consider a detailed and comprehensive analysis on an estimation of the error term obtained by truncating the asymptotic expansion for $p(n)$ at any positive integer $n$. This gives rise to an infinite family of inequalities for $p(n)$ which finally answers to a question proposed by Chen. Our error term estimation predominantly relies on applications of algorithmic methods from symbolic summation.
In this paper, we consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints that require the minimizers across the network to lie in low-dimensional subspaces. This constrained formulation includes consensus or single-task optimization as special cases, and allows for more general task relatedness models such as multitask smoothness and coupled optimization. In order to cope with communication constraints, we propose and study an adaptive decentralized strategy where the agents employ differential randomized quantizers to compress their estimates before communicating with their neighbors. The analysis shows that, under some general conditions on the quantization noise, and for sufficiently small step-sizes $\mu$, the strategy is stable both in terms of mean-square error and average bit rate: by reducing $\mu$, it is possible to keep the estimation errors small (on the order of $\mu$) without increasing indefinitely the bit rate as $\mu\rightarrow 0$. Simulations illustrate the theoretical findings and the effectiveness of the proposed approach, revealing that decentralized learning is achievable at the expense of only a few bits.
This work considers Gaussian process interpolation with a periodized version of the Mat{\'e}rn covariance function (Stein, 1999, Section 6.7) with Fourier coefficients $\phi$($\alpha$^2 + j^2)^(--$\nu$--1/2). Convergence rates are studied for the joint maximum likelihood estimation of $\nu$ and $\phi$ when the data is sampled according to the model. The mean integrated squared error is also analyzed with fixed and estimated parameters, showing that maximum likelihood estimation yields asymptotically the same error as if the ground truth was known. Finally, the case where the observed function is a ''deterministic'' element of a continuous Sobolev space is also considered, suggesting that bounding assumptions on some parameters can lead to different estimates.
Generative Adversarial Network (GAN) based art has proliferated in the past year, going from a shiny new tool to generate fake human faces to a stage where anyone can generate thousands of artistic images with minimal effort. Some of these images are now ``good'' enough to win accolades from qualified judges. In this paper, we explore how Generative Models have impacted artistry, not only from a qualitative point of view, but also from an angle of exploitation of artisans --both via plagiarism, where models are trained on their artwork without permission, and via profit shifting, where profits in the art market have shifted from art creators to model owners or to traders in the unregulated secondary crypto market. This confluence of factors risks completely detaching humans from the artistic process, devaluing the labor of artists and distorting the public perception of the value of art.
Background: Instrumental variables (IVs) can be used to provide evidence as to whether a treatment X has a causal effect on an outcome Y. Even if the instrument Z satisfies the three core IV assumptions of relevance, independence and the exclusion restriction, further assumptions are required to identify the average causal effect (ACE) of X on Y. Sufficient assumptions for this include: homogeneity in the causal effect of X on Y; homogeneity in the association of Z with X; and no effect modification (NEM). Methods: We describe the NO Simultaneous Heterogeneity (NOSH) assumption, which requires the heterogeneity in the X-Y causal effect to be mean independent of (i.e., uncorrelated with) both Z and heterogeneity in the Z-X association. This happens, for example, if there are no common modifiers of the X-Y effect and the Z-X association, and the X-Y effect is additive linear. We illustrate NOSH using simulations and by re-examining selected published studies. Results: When NOSH holds, the Wald estimand equals the ACE even if both homogeneity assumptions and NEM (which we demonstrate to be special cases of - and therefore stronger than - NOSH) are violated. Conclusions: NOSH is sufficient for identifying the ACE using IVs. Since NOSH is weaker than existing assumptions for ACE identification, doing so may be more plausible than previously anticipated.
In the well-known complexity class NP, many combinatorial problems can be found, whose optimization counterpart are important for many practical settings. Those problems usually consider full knowledge about the input and optimize on this specific input. In a practical setting, however, uncertainty in the input data is a usual phenomenon, whereby this is normally not covered in optimization versions of NP problems. One concept to model the uncertainty in the input data, is \textit{recoverable robustness}. In this setting, a solution on the input is calculated, whereby a possible recovery to a good solution should be guaranteed, whenever uncertainty manifests itself. That is, a solution $\texttt{s}_0$ for the base scenario $\textsf{S}_0$ as well as a solution \texttt{s} for every possible scenario of scenario set \textsf{S} has to be calculated. In other words, not only solution $\texttt{s}_0$ for instance $\textsf{S}_0$ is calculated but solutions \texttt{s} for all scenarios from \textsf{S} are prepared to correct possible errors through uncertainty. This paper introduces a specific concept of recoverable robust problems: Hamming Distance Recoverable Robust Problems. In this setting, solutions $\texttt{s}_0$ and \texttt{s} have to be calculated, such that $\texttt{s}_0$ and \texttt{s} may only differ in at most $\kappa$ elements. That is, one can recover from a harmful scenario by choosing a different solution, which is not too far away from the first solution. This paper surveys the complexity of Hamming distance recoverable robust version of optimization problems, typically found in NP for different types of scenarios. The complexity is primarily situated in the lower levels of the polynomial hierarchy. The main contribution of the paper is that recoverable robust problems with compression-encoded scenarios and $m \in \mathbb{N}$ recoveries are $\Sigma^P_{2m+1}$-complete.
With the rapid increase of large-scale, real-world datasets, it becomes critical to address the problem of long-tailed data distribution (i.e., a few classes account for most of the data, while most classes are under-represented). Existing solutions typically adopt class re-balancing strategies such as re-sampling and re-weighting based on the number of observations for each class. In this work, we argue that as the number of samples increases, the additional benefit of a newly added data point will diminish. We introduce a novel theoretical framework to measure data overlap by associating with each sample a small neighboring region rather than a single point. The effective number of samples is defined as the volume of samples and can be calculated by a simple formula $(1-\beta^{n})/(1-\beta)$, where $n$ is the number of samples and $\beta \in [0,1)$ is a hyperparameter. We design a re-weighting scheme that uses the effective number of samples for each class to re-balance the loss, thereby yielding a class-balanced loss. Comprehensive experiments are conducted on artificially induced long-tailed CIFAR datasets and large-scale datasets including ImageNet and iNaturalist. Our results show that when trained with the proposed class-balanced loss, the network is able to achieve significant performance gains on long-tailed datasets.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191