OpenRaiser/Intern-Atlas huggingface dataset:
Taking a hint: How to leverage loss predictors in contextual bandits?
Venue: arXiv cs.LG 2020
Year: 2020

We initiate the study of learning in contextual bandits with the help of loss predictors. The main question we address is whether one can improve over the minimax regret $\mathcal{O}(\sqrt{T})$ for learning over $T$ rounds, when the total error of the predictor $\mathcal{E} \leq T$ is relatively small. We provide a complete answer to this question, including upper and lower bounds for various settings: adversarial versus stochastic environments, known versus unknown $\mathcal{E}$, and single versus multiple predictors. We show several surprising results, such as 1) the optimal regret is $\mathcal{O}(\min\{\sqrt{T}, \sqrt{\mathcal{E}}T^\frac{1}{4}\})$ when $\mathcal{E}$ is known, a sharp contrast to the standard and better bound $\mathcal{O}(\sqrt{\mathcal{E}})$ for non-contextual problems (such as multi-armed bandits); 2) the same bound cannot be achieved if $\mathcal{E}$ is unknown, but as a remedy, $\mathcal{O}(\sqrt{\mathcal{E}}T^\frac{1}{3})$ is achievable; 3) with $M$ predictors, a linear dependence on $M$ is necessary, even if logarithmic dependence is possible for non-contextual problems. We also develop several novel algorithmic techniques to achieve matching upper bounds, including 1) a key action remapping technique for optimal regret with known $\mathcal{E}$, 2) implementing Catoni's robust mean estimator efficiently via an ERM oracle leading to an efficient algorithm in the stochastic setting with optimal regret, 3) constructing an underestimator for $\mathcal{E}$ via estimating the histogram with bins of exponentially increasing size for the stochastic setting with unknown $\mathcal{E}$, and 4) a self-referential scheme for learning with multiple predictors, all of which might be of independent interest.
The interval greedy algorithm for discrete optimization problems with interval objective function
Venue: arXiv cs.DS 2020
Year: 2020

We consider a wide class of the discrete optimization problems with interval objective function. We give a generalization of the greedy algorithm for the problems. Using the algorithm, we obtain the set of all possible greedy solutions and the set of all possible values of the objective function for the solutions. For a given probability distribution on intervals of objective function' coefficients, we compute probabilities of the solutions, compute expected values of the objective function for them and other probabilistic characteristics of the problem.
Occlusion Aware Unsupervised Learning of Optical Flow From Video
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we proposed an unsupervised learning method for estimating the optical flow between video frames, especially to solve the occlusion problem. Occlusion is caused by the movement of an object or the movement of the camera, defined as when certain pixels are visible in one video frame but not in adjacent frames. Due to the lack of pixel correspondence between frames in the occluded area, incorrect photometric loss calculation can mislead the optical flow training process. In the video sequence, we found that the occlusion in the forward ($t\rightarrow t+1$) and backward ($t\rightarrow t-1$) frame pairs are usually complementary. That is, pixels that are occluded in subsequent frames are often not occluded in the previous frame and vice versa. Therefore, by using this complementarity, a new weighted loss is proposed to solve the occlusion problem. In addition, we calculate gradients in multiple directions to provide richer supervision information. Our method achieves competitive optical flow accuracy compared to the baseline and some supervised methods on KITTI 2012 and 2015 benchmarks. This source code has been released at https://github.com/jianfenglihg/UnOpticalFlow.git.
Time-Space Tradeoffs for Finding a Long Common Substring
Venue: arXiv cs.DS 2020
Year: 2020

We consider the problem of finding, given two documents of total length $n$, a longest string occurring as a substring of both documents. This problem, known as the Longest Common Substring (LCS) problem, has a classic $O(n)$-time solution dating back to the discovery of suffix trees (Weiner, 1973) and their efficient construction for integer alphabets (Farach-Colton, 1997). However, these solutions require $Θ(n)$ space, which is prohibitive in many applications. To address this issue, Starikovskaya and Vildhøj (CPM 2013) showed that for $n^{2/3} \le s \le n^{1-o(1)}$, the LCS problem can be solved in $O(s)$ space and $O(\frac{n^2}{s})$ time. Kociumaka et al. (ESA 2014) generalized this tradeoff to $1 \leq s \leq n$, thus providing a smooth time-space tradeoff from constant to linear space. In this paper, we obtain a significant speed-up for instances where the length $L$ of the sought LCS is large. For $1 \leq s \leq n$, we show that the LCS problem can be solved in $O(s)$ space and $\tilde{O}(\frac{n^2}{L\cdot s}+n)$ time. The result is based on techniques originating from the LCS with Mismatches problem (Flouri et al., 2015; Charalampopoulos et al., CPM 2018), on space-efficient locally consistent parsing (Birenzwige et al., SODA 2020), and on the structure of maximal repetitions (runs) in the input documents.
Joint Device-Edge Inference over Wireless Links with Pruning
Venue: arXiv cs.IT 2020
Year: 2020

We propose a joint feature compression and transmission scheme for efficient inference at the wireless network edge. Our goal is to enable efficient and reliable inference at the edge server assuming limited computational resources at the edge device. Previous work focused mainly on feature compression, ignoring the computational cost of channel coding. We incorporate the recently proposed deep joint source-channel coding (DeepJSCC) scheme, and combine it with novel filter pruning strategies aimed at reducing the redundant complexity from neural networks. We evaluate our approach on a classification task, and show improved results in both end-to-end reliability and workload reduction at the edge device. This is the first work that combines DeepJSCC with network pruning, and applies it to image classification over the wireless edge.
Analysis of Indexing Structures for Immutable Data
Venue: arXiv cs.DB 2020
Year: 2020

In emerging applications such as blockchains and collaborative data analytics, there are strong demands for data immutability, multi-version accesses, and tamper-evident controls. This leads to three new index structures for immutable data, namely Merkle Patricia Trie (MPT), Merkle Bucket Tree (MBT), and Pattern-Oriented-Split Tree (POS-Tree). Although these structures have been adopted in real applications, there is no systematic evaluation of their pros and cons in the literature. This makes it difficult for practitioners to choose the right index structure for their applications, as there is only a limited understanding of the characteristics of each index. To alleviate the above deficiency, we present a comprehensive analysis of the existing index structures for immutable data, evaluating both their asymptotic and empirical performance. Specifically, we show that MPT, MBT, and POS-Tree are all instances of a recently proposed framework, dubbed \my{Structurally Invariant and Reusable Indexes (SIRI)}. We propose to evaluate the SIRI instances based on five essential metrics: their efficiency for four index operations (i.e., lookup, update, comparison, and merge), as well as their \my{deduplication ratios} (i.e., the size of the index with deduplication over the size without deduplication). We establish the worst-case guarantees of each index in terms of these five metrics, and we experimentally evaluate all indexes in a large variety of settings. Based on our theoretical and empirical analysis, we conclude that POS-Tree is a favorable choice for indexing immutable data.
VESR-Net: The Winning Solution to Youku Video Enhancement and Super-Resolution Challenge
Venue: arXiv cs.CV 2020
Year: 2020

This paper introduces VESR-Net, a method for video enhancement and super-resolution (VESR). We design a separate non-local module to explore the relations among video frames and fuse video frames efficiently, and a channel attention residual block to capture the relations among feature maps for video frame reconstruction in VESR-Net. We conduct experiments to analyze the effectiveness of these designs in VESR-Net, which demonstrates the advantages of VESR-Net over previous state-of-the-art VESR methods. It is worth to mention that among more than thousands of participants for Youku video enhancement and super-resolution (Youku-VESR) challenge, our proposed VESR-Net beat other competitive methods and ranked the first place.
MIMO-NOMA Networks Relying on Reconfigurable Intelligent Surface: A Signal Cancellation Based Design
Venue: arXiv cs.IT 2020
Year: 2020

Reconfigurable intelligent surface (RIS) technique stands as a promising signal enhancement or signal cancellation technique for next generation networks. We design a novel passive beamforming weight at RISs in a multiple-input multiple-output (MIMO) non-orthogonal multiple access (NOMA) network for simultaneously serving paired users, where a signal cancellation based (SCB) design is employed. In order to implement the proposed SCB design, we first evaluate the minimal required number of RISs in both the diffuse scattering and anomalous reflector scenarios. Then, new channel statistics are derived for characterizing the effective channel gains. In order to evaluate the network's performance, we derive the closed-form expressions both for the outage probability (OP) and for the ergodic rate (ER). The diversity orders as well as the high-signal-to-noise (SNR) slopes are derived for engineering insights. The network's performance of a finite resolution design has been evaluated. Our analytical results demonstrate that: i) the inter-cluster interference can be eliminated with the aid of large number of RIS elements; ii) the line-of-sight of the BS-RIS and RIS-user links are required for the diffuse scattering scenario, whereas the LoS links are not compulsory for the anomalous reflector scenario.
Generate Descriptive Social Networks for Large Populations from Available Observations: A Novel Methodology and a Generator
Venue: arXiv cs.SI 2020
Year: 2020

When modeling a social dynamics with an agent-oriented approach, researchers have to describe the structure of interactions within the population. Given the intractability of extensive network collecting, they rely on random network generators that are supposed to explore the space of plausible networks. We first identify the needs of modelers, including placing heterogeneous agents on the network given their attributes and differentiating the various types of social links that lead to different interactions. We point out the existence of data in the form of scattered statistics and qualitative observations, that should be used to parameter the generator. We propose a new approach peculiar to agent-based modeling, in which we will generate social links from individuals' observed attributes, and return them as a multiplex network. Interdependencies between socioeconomic attributes, and generative rules, are encoded as Bayesian networks. A methodology guides modelers through the formalization of these parameters. This approach is illustrated by describing the structure of interactions that supports diffusion of contraceptive solutions in rural Kenya.
An Inverse Olympic Medal Tally Transformation for Optimal Lane-level Road Network Path Traversal
Venue: arXiv cs.DS 2020
Year: 2020

Lane-level traversal of (almost) arbitrary input paths is a common problem in the mapping industry. This paper considers the problem of generating \emph{feasible} and maximally convenient lane-level path traversals. The presented approach exploits a graph transformation of an input path which is subsequentially explored by a multi-criteria search algorithm. This approach is able to yield paths traversals that are guaranteed to obey lane crossing rules whenever possible, and minimize the number of legal, yet inconvenient lane crossings along any given input path.
Towards a Complexity-theoretic Understanding of Restarts in SAT solvers
Venue: arXiv cs.CC 2020
Year: 2020

Restarts are a widely-used class of techniques integral to the efficiency of Conflict-Driven Clause Learning (CDCL) Boolean SAT solvers. While the utility of such policies has been well-established empirically, a theoretical explanation of whether restarts are indeed crucial to the power of CDCL solvers is lacking. In this paper, we prove a series of theoretical results that characterize the power of restarts for various models of SAT solvers. More precisely, we make the following contributions. First, we prove an exponential separation between a {\it drunk} randomized CDCL solver model with restarts and the same model without restarts using a family of satisfiable instances. Second, we show that the configuration of CDCL solver with VSIDS branching and restarts (with activities erased after restarts) is exponentially more powerful than the same configuration without restarts for a family of unsatisfiable instances. To the best of our knowledge, these are the first separation results involving restarts in the context of SAT solvers. Third, we show that restarts do not add any proof complexity-theoretic power vis-a-vis a number of models of CDCL and DPLL solvers with non-deterministic static variable and value selection.
Autonomous Driving at Intersections: A Critical-Turning-Point Approach for Left Turns
Venue: arXiv cs.RO 2020
Year: 2020

Left-turn planning is one of the formidable challenges for autonomous vehicles, especially at unsignalized intersections due to the unknown intentions of oncoming vehicles. This paper addresses the challenge by proposing a critical turning point (CTP) based hierarchical planning approach. This includes a high-level candidate path generator and a low-level partially observable Markov decision process (POMDP) based planner. The proposed (CTP) concept, inspired by human-driving behaviors at intersections, aims to increase the computational efficiency of the low-level planner and to enable human-friendly autonomous driving. The POMDP based low-level planner takes unknown intentions of oncoming vehicles into considerations to perform less conservative yet safe actions. With proper integration, the proposed hierarchical approach is capable of achieving safe planning results with high commute efficiency at unsignalized intersections in real time.
AGL: a Scalable System for Industrial-purpose Graph Machine Learning
Venue: arXiv cs.SI 2020
Year: 2020

Machine learning over graphs have been emerging as powerful learning tools for graph data. However, it is challenging for industrial communities to leverage the techniques, such as graph neural networks (GNNs), and solve real-world problems at scale because of inherent data dependency in the graphs. As such, we cannot simply train a GNN with classic learning systems, for instance parameter server that assumes data parallel. Existing systems store the graph data in-memory for fast accesses either in a single machine or graph stores from remote. The major drawbacks are in three-fold. First, they cannot scale because of the limitations on the volume of the memory, or the bandwidth between graph stores and workers. Second, they require extra development of graph stores without well exploiting mature infrastructures such as MapReduce that guarantee good system properties. Third, they focus on training but ignore the optimization of inference over graphs, thus makes them an unintegrated system. In this paper, we design AGL, a scalable, fault-tolerance and integrated system, with fully-functional training and inference for GNNs. Our system design follows the message passing scheme underlying the computations of GNNs. We design to generate the $k$-hop neighborhood, an information-complete subgraph for each node, as well as do the inference simply by merging values from in-edge neighbors and propagating values to out-edge neighbors via MapReduce. In addition, the $k$-hop neighborhood contains information-complete subgraphs for each node, thus we simply do the training on parameter servers due to data independency. Our system AGL, implemented on mature infrastructures, can finish the training of a 2-layer graph attention network on a graph with billions of nodes and hundred billions of edges in 14 hours, and complete the inference in 1.2 hour.
Finite Open-World Query Answering with Number Restrictions
Venue: arXiv cs.LO 2020
Year: 2020

Open-world query answering is the problem of deciding, given a set of facts, conjunction of constraints, and query, whether the facts and constraints imply the query. This amounts to reasoning over all instances that include the facts and satisfy the constraints. We study finite open-world query answering (FQA), which assumes that the underlying world is finite and thus only considers the finite completions of the instance. The major known decidable cases of FQA derive from the following: the guarded fragment of first-order logic, which can express referential constraints (data in one place points to data in another) but cannot express number restrictions such as functional dependencies; and the guarded fragment with number restrictions but on a signature of arity only two. In this paper, we give the first decidability results for FQA that combine both referential constraints and number restrictions for arbitrary signatures: we show that, for unary inclusion dependencies and functional dependencies, the finiteness assumption of FQA can be lifted up to taking the finite implication closure of the dependencies. Our result relies on new techniques to construct finite universal models of such constraints, for any bound on the maximal query size.
Submitting surveys via a conversational interface: an evaluation of user acceptance and approach effectiveness
Venue: arXiv cs.HC 2020
Year: 2020

Conversational interfaces are currently on the rise: more and more applications rely on a chat-like interaction pattern to increase their acceptability and to improve user experience. Also in the area of questionnaire design and administration, interaction design is increasingly looked at as an important ingredient of a digital solution. For those reasons, we designed and developed a conversational survey tool to administer questionnaires with a colloquial form through a chat-like Web interface. In this paper, we present the evaluation results of our approach, taking into account both the user point of view - by assessing user acceptance and preferences in terms of survey compilation experience - and the survey design perspective - by investigating the effectiveness of a conversational survey in comparison to a traditional questionnaire. We show that users clearly appreciate the conversational form and prefer it over a traditional approach and that, from a data collection point of view, the conversational method shows the same reliability and a higher response quality with respect to a traditional questionnaire.
Overhead-Aware Design of Reconfigurable Intelligent Surfaces in Smart Radio Environments
Venue: arXiv cs.IT 2020
Year: 2020

Reconfigurable intelligent surfaces have emerged as a promising technology for future wireless networks. Given that a large number of reflecting elements is typically used, and that the surface has no signal processing capabilities, a major challenge is to cope with the overhead that is required to estimate the channel state information and to report the optimized phase shifts to the surface. This issue has not been addressed by previous works, which do not explicitly consider the overhead during the resource allocation phase. This work aims at filling this gap, developing an overhead-aware resource allocation framework for wireless networks where reconfigurable intelligent surfaces are used to improve the communication performance. An overhead model is developed and incorporated in the expressions of the system rate and energy efficiencies, which are then optimized with respect to the phase shifts of the reconfigurable intelligent surface, the transmit and receive filters, and the power and bandwidth used for the communication and feedback phases. The bi-objective maximization of the rate and energy efficiency is carried out as well. The proposed framework allows characterizing the trade-off between optimized radio resources and the related overhead in networks with reconfigurable intelligent surfaces.
Maximum Clique in Disk-Like Intersection Graphs
Venue: arXiv cs.CG 2020
Year: 2020

We study the complexity of Maximum Clique in intersection graphs of convex objects in the plane. On the algorithmic side, we extend the polynomial-time algorithm for unit disks [Clark '90, Raghavan and Spinrad '03] to translates of any fixed convex set. We also generalize the efficient polynomial-time approximation scheme (EPTAS) and subexponential algorithm for disks [Bonnet et al. '18, Bonamy et al. '18] to homothets of a fixed centrally symmetric convex set. The main open question on that topic is the complexity of Maximum Clique in disk graphs. It is not known whether this problem is NP-hard. We observe that, so far, all the hardness proofs for Maximum Clique in intersection graph classes $\mathcal I$ follow the same road. They show that, for every graph $G$ of a large-enough class $\mathcal C$, the complement of an even subdivision of $G$ belongs to the intersection class $\mathcal I$. Then they conclude invoking the hardness of Maximum Independent Set on the class $\mathcal C$, and the fact that the even subdivision preserves that hardness. However there is a strong evidence that this approach cannot work for disk graphs [Bonnet et al. '18]. We suggest a new approach, based on a problem that we dub Max Interval Permutation Avoidance, which we prove unlikely to have a subexponential-time approximation scheme. We transfer that hardness to Maximum Clique in intersection graphs of objects which can be either half-planes (or unit disks) or axis-parallel rectangles. That problem is not amenable to the previous approach. We hope that a scaled down (merely NP-hard) variant of Max Interval Permutation Avoidance could help making progress on the disk case, for instance by showing the NP-hardness for (convex) pseudo-disks.
Fuzzy k-Nearest Neighbors with monotonicity constraints: Moving towards the robustness of monotonic noise
Venue: arXiv cs.LG 2020
Year: 2020

This paper proposes a new model based on Fuzzy k-Nearest Neighbors for classification with monotonic constraints, Monotonic Fuzzy k-NN (MonFkNN). Real-life data-sets often do not comply with monotonic constraints due to class noise. MonFkNN incorporates a new calculation of fuzzy memberships, which increases robustness against monotonic noise without the need for relabeling. Our proposal has been designed to be adaptable to the different needs of the problem being tackled. In several experimental studies, we show significant improvements in accuracy while matching the best degree of monotonicity obtained by comparable methods. We also show that MonFkNN empirically achieves improved performance compared with Monotonic k-NN in the presence of large amounts of class noise.