OpenRaiser/Intern-Atlas huggingface dataset:
A Fast Randomized Geometric Algorithm for Computing Riemann-Roch Spaces
Venue: arXiv cs.SC 2020
Year: 2020

We propose a probabilistic variant of Brill-Noether's algorithm for computing a basis of the Riemann-Roch space $L(D)$ associated to a divisor $D$ on a projective nodal plane curve $\mathcal C$ over a sufficiently large perfect field $k$. Our main result shows that this algorithm requires at most $O(\max(\mathrm{deg}(\mathcal C)^{2ω}, \mathrm{deg}(D_+)^ω))$ arithmetic operations in $k$, where $ω$ is a feasible exponent for matrix multiplication and $D_+$ is the smallest effective divisor such that $D_+\geq D$. This improves the best known upper bounds on the complexity of computing Riemann-Roch spaces. Our algorithm may fail, but we show that provided that a few mild assumptions are satisfied, the failure probability is bounded by $O(\max(\mathrm{deg}(\mathcal C)^4, \mathrm{deg}(D_+)^2)/\lvert \mathcal E\rvert)$, where $\mathcal E$ is a finite subset of $k$ in which we pick elements uniformly at random. We provide a freely available C++/NTL implementation of the proposed algorithm and we present experimental data. In particular, our implementation enjoys a speedup larger than 6 on many examples (and larger than 200 on some instances over large finite fields) compared to the reference implementation in the Magma computer algebra system. As a by-product, our algorithm also yields a method for computing the group law on the Jacobian of a smooth plane curve of genus $g$ within $O(g^ω)$ operations in $k$, which equals the best known complexity for this problem.
Multi-Task Learning of Generalizable Representations for Video Action Recognition
Venue: arXiv cs.CV 2020
Year: 2020

In classic video action recognition, labels may not contain enough information about the diverse video appearance and dynamics, thus, existing models that are trained under the standard supervised learning paradigm may extract less generalizable features. We evaluate these models under a cross-dataset experiment setting, as the above label bias problem in video analysis is even more prominent across different data sources. We find that using the optical flows as model inputs harms the generalization ability of most video recognition models. Based on these findings, we present a multi-task learning paradigm for video classification. Our key idea is to avoid label bias and improve the generalization ability by taking data as its own supervision or supervising constraints on the data. First, we take the optical flows and the RGB frames by taking them as auxiliary supervisions, and thus naming our model as Reversed Two-Stream Networks (Rev2Net). Further, we collaborate the auxiliary flow prediction task and the frame reconstruction task by introducing a new training objective to Rev2Net, named Decoding Discrepancy Penalty (DDP), which constraints the discrepancy of the multi-task features in a self-supervised manner. Rev2Net is shown to be effective on the classic action recognition task. It specifically shows a strong generalization ability in the cross-dataset experiments.
Gen-Oja: A Two-time-scale approach for Streaming CCA
Venue: arXiv cs.LG 2020
Year: 2020

In this paper, we study the problems of principal Generalized Eigenvector computation and Canonical Correlation Analysis in the stochastic setting. We propose a simple and efficient algorithm, Gen-Oja, for these problems. We prove the global convergence of our algorithm, borrowing ideas from the theory of fast-mixing Markov chains and two-time-scale stochastic approximation, showing that it achieves the optimal rate of convergence. In the process, we develop tools for understanding stochastic processes with Markovian noise which might be of independent interest.
Train Sparsely, Generate Densely: Memory-efficient Unsupervised Training of High-resolution Temporal GAN
Venue: arXiv cs.CV 2020
Year: 2020

Training of Generative Adversarial Network (GAN) on a video dataset is a challenge because of the sheer size of the dataset and the complexity of each observation. In general, the computational cost of training GAN scales exponentially with the resolution. In this study, we present a novel memory efficient method of unsupervised learning of high-resolution video dataset whose computational cost scales only linearly with the resolution. We achieve this by designing the generator model as a stack of small sub-generators and training the model in a specific way. We train each sub-generator with its own specific discriminator. At the time of the training, we introduce between each pair of consecutive sub-generators an auxiliary subsampling layer that reduces the frame-rate by a certain ratio. This procedure can allow each sub-generator to learn the distribution of the video at different levels of resolution. We also need only a few GPUs to train a highly complex generator that far outperforms the predecessor in terms of inception scores.
Evolutionary-Neural Hybrid Agents for Architecture Search
Venue: arXiv cs.LG 2020
Year: 2020

Neural Architecture Search has shown potential to automate the design of neural networks. Deep Reinforcement Learning based agents can learn complex architectural patterns, as well as explore a vast and compositional search space. On the other hand, evolutionary algorithms offer higher sample efficiency, which is critical for such a resource intensive application. In order to capture the best of both worlds, we propose a class of Evolutionary-Neural hybrid agents (Evo-NAS). We show that the Evo-NAS agent outperforms both neural and evolutionary agents when applied to architecture search for a suite of text and image classification benchmarks. On a high-complexity architecture search space for image classification, the Evo-NAS agent surpasses the accuracy achieved by commonly used agents with only 1/3 of the search cost.
On embeddability of unit disk graphs onto straight lines
Venue: arXiv cs.CG 2020
Year: 2020

Unit disk graphs are the intersection graphs of unit radius disks in the Euclidean plane. Deciding whether there exists an embedding of a given unit disk graph, i.e. unit disk graph recognition, is an important geometric problem, and has many application areas. In general, this problem is known to be $\exists\mathbb{R}$-complete. In some applications, the objects that correspond to unit disks, have predefined (geometrical) structures to be placed on. Hence, many researchers attacked this problem by restricting the domain of the disk centers. One example to such applications is wireless sensor networks, where each disk corresponds to a wireless sensor node, and a pair of intersecting disks corresponds to a pair of sensors being able to communicate with one another. It is usually assumed that the nodes have identical sensing ranges, and thus a unit disk graph model is used to model problems concerning wireless sensor networks. We consider the unit disk graph realization problem on a restricted domain, by assuming a scenario where the wireless sensor nodes are deployed on the corridors of a building. Based on this scenario, we impose a geometric constraint such that the unit disks must be centered onto given straight lines. In this paper, we first describe a polynomial-time reduction which shows that deciding whether a graph can be realized as unit disks onto given straight lines is NP-hard, when the given lines are parallel to either $x$-axis or $y$-axis. Using the reduction we described, we also show that this problem is NP-complete when the given lines are only parallel to $x$-axis (and one another). We obtain those results using the idea of the logic engine introduced by Bhatt and Cosmadakis in 1987.
Generating Realistic Training Images Based on Tonality-Alignment Generative Adversarial Networks for Hand Pose Estimation
Venue: arXiv cs.CV 2020
Year: 2020

Hand pose estimation from a monocular RGB image is an important but challenging task. The main factor affecting its performance is the lack of a sufficiently large training dataset with accurate hand-keypoint annotations. In this work, we circumvent this problem by proposing an effective method for generating realistic hand poses and show that state-of-the-art algorithms for hand pose estimation can be greatly improved by utilizing the generated hand poses as training data. Specifically, we first adopt an augmented reality (AR) simulator to synthesize hand poses with accurate hand-keypoint labels. Although the synthetic hand poses come with precise joint labels, eliminating the need of manual annotations, they look unnatural and are not the ideal training data. To produce more realistic hand poses, we propose to blend a synthetic hand pose with a real background, such as arms and sleeves. To this end, we develop tonality-alignment generative adversarial networks (TAGANs), which align the tonality and color distributions between synthetic hand poses and real backgrounds, and can generate high quality hand poses. We evaluate TAGAN on three benchmarks, including the RHP, STB, and CMU-PS hand pose datasets. With the aid of the synthesized poses, our method performs favorably against the state-of-the-arts in both 2D and 3D hand pose estimations.
Performance Analysis of Low-Interference N-Continuous OFDM
Venue: arXiv cs.IT 2020
Year: 2020

The low-interference N-continuous orthogonal frequency division multiplexing (NC-OFDM) system [25], [26] is investigated in terms of power spectrum density (PSD) and bit error rate (BER), to prove and quantify its advantages over traditional NC-OFDM. The PSD and BER performances of the low-interference scheme are analyzed and compared under the parameters of the highest derivative order (HDO) and the length of the smooth signal. In the context of PSD, different from one discontinuous point per NC-OFDM symbol in [25], the sidelobe suppression performance is evaluated upon considering two discontinuous points due to the finite continuity of the smooth signal and its higher-order derivatives. It was shown that with an increased HDO and an increased length of the smooth signal, a more rapid sidelobe decaying is achieved, for the significant continuity improvement of the OFDM signal and its higher-order derivatives. However, our PSD analysis also shows that if the length of the smooth signal is set inappropriately, the performance may be degraded, even if the HDO is large. Furthermore, it was shown in the error performance analysis that under the assumptions of perfect and imperfect synchronization, the low-interference scheme incurs small BER performance degradation for a short length of the smooth signal or a small HDO as opposed to conventional NC-OFDM. Based on analysis and simulation results, the trade-offs between sidelobe suppression and BER are studied with the above two parameters.
Taking Control of Intra-class Variation in Conditional GANs Under Weak Supervision
Venue: arXiv cs.CV 2020
Year: 2020

Generative Adversarial Networks (GANs) are able to learn mappings between simple, relatively low-dimensional, random distributions and points on the manifold of realistic images in image-space. The semantics of this mapping, however, are typically entangled such that meaningful image properties cannot be controlled independently of one another. Conditional GANs (cGANs) provide a potential solution to this problem, allowing specific semantics to be enforced during training. This solution, however, depends on the availability of precise labels, which are sometimes difficult or near impossible to obtain, e.g. labels representing lighting conditions or describing the background. In this paper we introduce a new formulation of the cGAN that is able to learn disentangled, multivariate models of semantically meaningful variation and which has the advantage of requiring only the weak supervision of binary attribute labels. For example, given only labels of ambient / non-ambient lighting, our method is able to learn multivariate lighting models disentangled from other factors such as the identity and pose. We coin the method intra-class variation isolation (IVI) and the resulting network the IVI-GAN. We evaluate IVI-GAN on the CelebA dataset and on synthetic 3D morphable model data, learning to disentangle attributes such as lighting, pose, expression, and even the background.
The Power of The Hybrid Model for Mean Estimation
Venue: arXiv cs.CR 2020
Year: 2020

We explore the power of the hybrid model of differential privacy (DP), in which some users desire the guarantees of the local model of DP and others are content with receiving the trusted-curator model guarantees. In particular, we study the utility of hybrid model estimators that compute the mean of arbitrary real-valued distributions with bounded support. When the curator knows the distribution's variance, we design a hybrid estimator that, for realistic datasets and parameter settings, achieves a constant factor improvement over natural baselines. We then analytically characterize how the estimator's utility is parameterized by the problem setting and parameter choices. When the distribution's variance is unknown, we design a heuristic hybrid estimator and analyze how it compares to the baselines. We find that it often performs better than the baselines, and sometimes almost as well as the known-variance estimator. We then answer the question of how our estimator's utility is affected when users' data are not drawn from the same distribution, but rather from distributions dependent on their trust model preference. Concretely, we examine the implications of the two groups' distributions diverging and show that in some cases, our estimators maintain fairly high utility. We then demonstrate how our hybrid estimator can be incorporated as a sub-component in more complex, higher-dimensional applications. Finally, we propose a new privacy amplification notion for the hybrid model that emerges due to interaction between the groups, and derive corresponding amplification results for our hybrid estimators.
Universal Streaming of Subset Norms
Venue: arXiv cs.DS 2020
Year: 2020

Most known algorithms in the streaming model of computation aim to approximate a single function such as an $\ell_p$-norm. In 2009, Nelson [\url{https://sublinear.info}, Open Problem 30] asked if it possible to design \emph{universal algorithms}, that simultaneously approximate multiple functions of the stream. In this paper we answer the question of Nelson for the class of \emph{subset $\ell_0$-norms} in the insertion-only frequency-vector model. Given a family of subsets $\mathcal{S}\subset 2^{[n]}$, we provide a single streaming algorithm that can $(1\pm ε)$-approximate the subset-norm for every $S\in\mathcal{S}$. Here, the subset-$\ell_p$-norm of $v\in \mathbb{R}^n$ with respect to set $S\subseteq [n]$ is the $\ell_p$-norm of vector $v_{|S}$ (which denotes restricting $v$ to $S$, by zeroing all other coordinates). Our main result is a near-tight characterization of the space complexity of every family $\mathcal{S}\subset 2^{[n]}$ of subset-$\ell_0$-norms in insertion-only streams, expressed in terms of the "heavy-hitter dimension" of $\mathcal{S}$, a new combinatorial quantity that is related to the VC-dimension of $\mathcal{S}$. In contrast, we show that the more general turnstile and sliding-window models require a much larger space usage. All these results easily extend to $\ell_1$. In addition, we design algorithms for two other subset-$\ell_p$-norm variants. These can be compared to the Priority Sampling algorithm of Duffield, Lund and Thorup [JACM 2007], which achieves additive approximation $ε\|{v}\|$ for all possible subsets ($\mathcal{S}=2^{[n]}$) in the entry-wise update model. One of our algorithms extends this algorithm to handle turnstile updates, and another one achieves multiplicative approximation given a family $\mathcal{S}$.
Locally Consistent Parsing for Text Indexing in Small Space
Venue: arXiv cs.DS 2020
Year: 2020

We consider two closely related problems of text indexing in a sub-linear working space. The first problem is the Sparse Suffix Tree (SST) construction of a set of suffixes $B$ using only $O(|B|)$ words of space. The second problem is the Longest Common Extension (LCE) problem, where for some parameter $1\leτ\le n$, the goal is to construct a data structure that uses $O(\frac {n}τ)$ words of space and can compute the longest common prefix length of any pair of suffixes. We show how to use ideas based on the Locally Consistent Parsing technique, that was introduced by Sahinalp and Vishkin [STOC '94], in some non-trivial ways in order to improve the known results for the above problems. We introduce new Las-Vegas and deterministic algorithms for both problems. We introduce the first Las-Vegas SST construction algorithm that takes $O(n)$ time. This is an improvement over the last result of Gawrychowski and Kociumaka [SODA '17] who obtained $O(n)$ time for Monte-Carlo algorithm, and $O(n\sqrt{\log |B|})$ time for Las-Vegas algorithm. In addition, we introduce a randomized Las-Vegas construction for an LCE data structure that can be constructed in linear time and answers queries in $O(τ)$ time. For the deterministic algorithms, we introduce an SST construction algorithm that takes $O(n\log \frac{n}{|B|})$ time (for $|B|=Ω(\log n)$). This is the first almost linear time, $O(n\cdot poly\log{n})$, deterministic SST construction algorithm, where all previous algorithms take at least $Ω\left(\min\{n|B|,\frac{n^2}{|B|}\}\right)$ time. For the LCE problem, we introduce a data structure that answers LCE queries in $O(τ\sqrt{\log^*n})$ time, with $O(n\logτ)$ construction time (for $τ=O(\frac{n}{\log n})$). This data structure improves both query time and construction time upon the results of Tanimura et al. [CPM '16].
Graded Monads and Graded Logics for the Linear Time -- Branching Time Spectrum
Venue: arXiv cs.LO 2020
Year: 2020

State-based models of concurrent systems are traditionally considered under a variety of notions of process equivalence. In the particular case of labelled transition systems, these equivalences range from trace equivalence to (strong) bisimilarity, and are organized in what is known as the linear time -- branching time spectrum. A combination of universal coalgebra and graded monads provides a generic framework in which the semantics of concurrency can be parametrized both over the branching type of the underlying transition systems and over the granularity of process equivalence. We show in the present paper that this framework of graded semantics does subsume the most important equivalences from the linear time -- branching time spectrum. An important feature of graded semantics is that it allows for the principled extraction of characteristic modal logics. We have established invariance of these graded logics under the given graded semantics in earlier work; in the present paper, we extend the logical framework with an explicit propositional layer and provide a generic expressiveness criterion that generalizes the classical Hennessy-Milner theorem to coarser notions of process equivalence. We extract graded logics for a range of graded semantics on labelled transition systems and probabilistic systems, and give exemplaric proofs of their expressiveness based on our generic criterion.
Inferring Point Clouds from Single Monocular Images by Depth Intermediation
Venue: arXiv cs.CV 2020
Year: 2020

In this paper, we propose a pipeline to generate 3D point cloud of an object from a single-view RGB image. Most previous work predict the 3D point coordinates from single RGB images directly. We decompose this problem into depth estimation from single images and point cloud completion from partial point clouds. Our method sequentially predicts the depth maps from images and then infers the complete 3D object point clouds based on the predicted partial point clouds. We explicitly impose the camera model geometrical constraint in our pipeline and enforce the alignment of the generated point clouds and estimated depth maps. Experimental results for the single image 3D object reconstruction task show that the proposed method outperforms existing state-of-the-art methods. Both the qualitative and quantitative results demonstrate the generality and suitability of our method.
Missed by Filter Lists: Detecting Unknown Third-Party Trackers with Invisible Pixels
Venue: arXiv cs.CR 2020
Year: 2020

Web tracking has been extensively studied over the last decade. To detect tracking, previous studies and user tools rely on filter lists. However, it has been shown that filter lists miss trackers. In this paper, we propose an alternative method to detect trackers inspired by analyzing behavior of invisible pixels. By crawling 84,658 webpages from 8,744 domains, we detect that third-party invisible pixels are widely deployed: they are present on more than 94.51% of domains and constitute 35.66% of all third-party images. We propose a fine-grained behavioral classification of tracking based on the analysis of invisible pixels. We use this classification to detect new categories of tracking and uncover new collaborations between domains on the full dataset of 4,216,454 third-party requests. We demonstrate that two popular methods to detect tracking, based on EasyList&EasyPrivacy and on Disconnect lists respectively miss 25.22% and 30.34% of the trackers that we detect. Moreover, we find that if we combine all three lists 379,245 requests originated from 8,744 domains still track users on 68.70% of websites.
Random Spiking and Systematic Evaluation of Defenses Against Adversarial Examples
Venue: arXiv cs.LG 2020
Year: 2020

Image classifiers often suffer from adversarial examples, which are generated by strategically adding a small amount of noise to input images to trick classifiers into misclassification. Over the years, many defense mechanisms have been proposed, and different researchers have made seemingly contradictory claims on their effectiveness. We present an analysis of possible adversarial models, and propose an evaluation framework for comparing different defense mechanisms. As part of the framework, we introduce a more powerful and realistic adversary strategy. Furthermore, we propose a new defense mechanism called Random Spiking (RS), which generalizes dropout and introduces random noises in the training process in a controlled manner. Evaluations under our proposed framework suggest RS delivers better protection against adversarial examples than many existing schemes.
On the Probabilistic Degree of OR over the Reals
Venue: arXiv cs.CC 2020
Year: 2020

We study the probabilistic degree over reals of the OR function on $n$ variables. For an error parameter $ε$ in (0,1/3), the $ε$-error probabilistic degree of any Boolean function $f$ over reals is the smallest non-negative integer $d$ such that the following holds: there exists a distribution $D$ of polynomials entirely supported on polynomials of degree at most $d$ such that for all $z \in \{0,1\}^n$, we have $Pr_{P \sim D} [P(z) = f(z) ] \geq 1- ε$. It is known from the works of Tarui ({Theoret. Comput. Sci.} 1993) and Beigel, Reingold, and Spielman ({ Proc. 6th CCC} 1991), that the $ε$-error probabilistic degree of the OR function is at most $O(\log n.\log 1/ε)$. Our first observation is that this can be improved to $O{\log {{n}\choose{\leq \log 1/ε}}}$, which is better for small values of $ε$. In all known constructions of probabilistic polynomials for the OR function (including the above improvement), the polynomials $P$ in the support of the distribution $D$ have the following special structure:$P = 1 - (1-L_1).(1-L_2)...(1-L_t)$, where each $L_i(x_1,..., x_n)$ is a linear form in the variables $x_1,...,x_n$, i.e., the polynomial $1-P(x_1,...,x_n)$ is a product of affine forms. We show that the $ε$-error probabilistic degree of OR when restricted to polynomials of the above form is $Ω( \log a/\log^2 a )$ where $a = \log {{n}\choose{\leq \log 1/ε}}$. Thus matching the above upper bound (up to poly-logarithmic factors).