OpenRaiser/Intern-Atlas huggingface dataset:
Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
Venue: arXiv cs.DS 2021
Year: 2021

We give the first approximation algorithm for mixed packing and covering semidefinite programs (SDPs) with polylogarithmic dependence on width. Mixed packing and covering SDPs constitute a fundamental algorithmic primitive with recent applications in combinatorial optimization, robust learning, and quantum complexity. The current approximate solvers for positive semidefinite programming can handle only pure packing instances, and technical hurdles prevent their generalization to a wider class of positive instances. For a given multiplicative accuracy of $ε$, our algorithm takes $O(\log^3(ndρ) \cdot ε^{-3})$ parallelizable iterations, where $n$, $d$ are dimensions of the problem and $ρ$ is a width parameter of the instance, generalizing or improving all previous parallel algorithms in the positive linear and semidefinite programming literature. When specialized to pure packing SDPs, our algorithm's iteration complexity is $O(\log^2 (nd) \cdot ε^{-2})$, a slight improvement and derandomization of the state-of-the-art (Allen-Zhu et. al. '16, Peng et. al. '16, Wang et. al. '15). For a wide variety of structured instances commonly found in applications, the iterations of our algorithm run in nearly-linear time. In doing so, we give matrix analytic techniques for overcoming obstacles that have stymied prior approaches to this open problem, as stated in past works (Peng et. al. '16, Mahoney et. al. '16). Crucial to our analysis are a simplification of existing algorithms for mixed positive linear programs, achieved by removing an asymmetry caused by modifying covering constraints, and a suite of matrix inequalities whose proofs are based on analyzing the Schur complements of matrices in a higher dimension. We hope that both our algorithm and techniques open the door to improved solvers for positive semidefinite programming, as well as its applications.
Robustness analytics to data heterogeneity in edge computing
Venue: arXiv cs.DC 2021
Year: 2021

Federated Learning is a framework that jointly trains a model \textit{with} complete knowledge on a remotely placed centralized server, but \textit{without} the requirement of accessing the data stored in distributed machines. Some work assumes that the data generated from edge devices are identically and independently sampled from a common population distribution. However, such ideal sampling may not be realistic in many contexts. Also, models based on intrinsic agency, such as active sampling schemes, may lead to highly biased sampling. So an imminent question is how robust Federated Learning is to biased sampling? In this work\footnote{\url{https://github.com/jiaqian/robustness_of_FL}}, we experimentally investigate two such scenarios. First, we study a centralized classifier aggregated from a collection of local classifiers trained with data having categorical heterogeneity. Second, we study a classifier aggregated from a collection of local classifiers trained by data through active sampling at the edge. We present evidence in both scenarios that Federated Learning is robust to data heterogeneity when local training iterations and communication frequency are appropriately chosen.
Intra-Camera Supervised Person Re-Identification
Venue: arXiv cs.CV 2021
Year: 2021

Existing person re-identification (re-id) methods mostly exploit a large set of cross-camera identity labelled training data. This requires a tedious data collection and annotation process, leading to poor scalability in practical re-id applications. On the other hand unsupervised re-id methods do not need identity label information, but they usually suffer from much inferior and insufficient model performance. To overcome these fundamental limitations, we propose a novel person re-identification paradigm based on an idea of independent per-camera identity annotation. This eliminates the most time-consuming and tedious inter-camera identity labelling process, significantly reducing the amount of human annotation efforts. Consequently, it gives rise to a more scalable and more feasible setting, which we call Intra-Camera Supervised (ICS) person re-id, for which we formulate a Multi-tAsk mulTi-labEl (MATE) deep learning method. Specifically, MATE is designed for self-discovering the cross-camera identity correspondence in a per-camera multi-task inference framework. Extensive experiments demonstrate the cost-effectiveness superiority of our method over the alternative approaches on three large person re-id datasets. For example, MATE yields 88.7% rank-1 score on Market-1501 in the proposed ICS person re-id setting, significantly outperforming unsupervised learning models and closely approaching conventional fully supervised learning competitors.
Road Traffic Poisoning of Navigation Apps: Threats and Countermeasures
Venue: arXiv cs.CR 2021
Year: 2021

Assisted-navigation applications have a relevant impact on our daily life. However, technological progress in virtualization technologies and Software-Defined Radios recently enabled new attack vectors, namely, road traffic poisoning. These attacks open up several dreadful scenarios, which are addressed in this contribution by identifying the associated challenges and proposing innovative countermeasures.
Regret Bounds for Discounted MDPs
Venue: arXiv cs.LG 2021
Year: 2021

Reinforcement learning (RL) has traditionally been understood from an episodic perspective; the concept of non-episodic RL, where there is no restart and therefore no reliable recovery, remains elusive. A fundamental question in non-episodic RL is how to measure the performance of a learner and derive algorithms to maximize such performance. Conventional wisdom is to maximize the difference between the average reward received by the learner and the maximal long-term average reward. In this paper, we argue that if the total time budget is relatively limited compared to the complexity of the environment, such comparison may fail to reflect the finite-time optimality of the learner. We propose a family of measures, called $γ$-regret, which we believe to better capture the finite-time optimality. We give motivations and derive lower and upper bounds for such measures. Note: A follow-up work (arXiv:2010.00587) has improved both our lower and upper bound, the gap is now closed at $\tildeΘ\left(\frac{\sqrt{SAT}}{(1 - γ)^{\frac{1}{2}}}\right)$.
Learning to Generate Levels From Nothing
Venue: arXiv cs.AI 2021
Year: 2021

Machine learning for procedural content generation has recently become an active area of research. Levels vary in both form and function and are mostly unrelated to each other across games. This has made it difficult to assemble suitably large datasets to bring machine learning to level design in the same way as it's been used for image generation. Here we propose Generative Playing Networks which design levels for itself to play. The algorithm is built in two parts; an agent that learns to play game levels, and a generator that learns the distribution of playable levels. As the agent learns and improves its ability, the space of playable levels, as defined by the agent, grows. The generator targets the agent's playability estimates to then update its understanding of what constitutes a playable level. We call this process of learning the distribution of data found through self-discovery with an environment, self-supervised inductive learning. Unlike previous approaches to procedural content generation, Generative Playing Networks are end-to-end differentiable and do not require human-designed examples or domain knowledge. We demonstrate the capability of this framework by training an agent and level generator for a 2D dungeon crawler game.
Distributed Graph Realizations
Venue: arXiv cs.DC 2021
Year: 2021

We study graph realization problems from a distributed perspective and we study it in the node capacitated clique (NCC) model of distributed computing, recently introduced for representing peer-to-peer networks. We focus on two central variants, degree-sequence realization and minimum threshold-connectivity realization both of which result in overlay network realizations. Overlay network realizations can be either explicit or implicit. Explicit realizations require both endpoints of any edge in the realized graph to be aware of the edge. In implicit realizations, on the other hand, at least one endpoint of each edge of the realized graph needs to be aware of the edge. The main realization algorithms we present are the following. 1. An $\tilde{O}(\min\{\sqrt{m},Δ\})$ time algorithm for implicit realization of a degree sequence. Here, $Δ= \max_v d(v)$ is the maximum degree and $m = (1/2) \sum_v d(v)$ is the number of edges in the final realization. An $\tilde{O}(Δ)$ time algorithm for an explicit realization of a degree sequence. We first compute an implicit realization and then transform it into an explicit one in $\tilde{O}(Δ)$ additional rounds. 2. An $\tilde{O}(Δ)$ time algorithm for the threshold connectivity problem that obtains an explicit solution and an improved $\tilde{O}(1)$ algorithm for implicit realization when all nodes know each other's IDs. These algorithms are 2-approximations w.r.t. the number of edges. We complement our upper bounds with lower bounds to show that the above algorithms are tight up to factors of $\log n$. Additionally, we provide algorithms for realizing trees and an $\tilde{O}(1)$ round algorithm for approximate degree sequence realization.
Sparse and Structured Visual Attention
Venue: arXiv cs.CL 2021
Year: 2021

Visual attention mechanisms are widely used in multimodal tasks, as visual question answering (VQA). One drawback of softmax-based attention mechanisms is that they assign some probability mass to all image regions, regardless of their adjacency structure and of their relevance to the text. In this paper, to better link the image structure with the text, we replace the traditional softmax attention mechanism with two alternative sparsity-promoting transformations: sparsemax, which is able to select only the relevant regions (assigning zero weight to the rest), and a newly proposed Total-Variation Sparse Attention (TVmax), which further encourages the joint selection of adjacent spatial locations. Experiments in VQA show gains in accuracy as well as higher similarity to human attention, which suggests better interpretability.
Performative Prediction
Venue: arXiv cs.LG 2021
Year: 2021

When predictions support decisions they may influence the outcome they aim to predict. We call such predictions performative; the prediction influences the target. Performativity is a well-studied phenomenon in policy-making that has so far been neglected in supervised learning. When ignored, performativity surfaces as undesirable distribution shift, routinely addressed with retraining. We develop a risk minimization framework for performative prediction bringing together concepts from statistics, game theory, and causality. A conceptual novelty is an equilibrium notion we call performative stability. Performative stability implies that the predictions are calibrated not against past outcomes, but against the future outcomes that manifest from acting on the prediction. Our main results are necessary and sufficient conditions for the convergence of retraining to a performatively stable point of nearly minimal loss. In full generality, performative prediction strictly subsumes the setting known as strategic classification. We thus also give the first sufficient conditions for retraining to overcome strategic feedback effects.
An Efficient Permissioned Blockchain with Provable Reputation Mechanism
Venue: arXiv cs.CR 2021
Year: 2021

The design of permissioned blockchains places an access control requirement for members to read, access, and write information over the blockchains. In this paper, we study a hierarchical scenario to include three types of participants: providers, collectors, and governors. To be specific, providers forward transactions, collected from terminals, to collectors; collectors upload received transactions to governors after verifying and labeling them; and governors validate a part of received labeled transactions, pack valid ones into a block, and append a new block on the ledger. Collectors in the hierarchical model play a crucial role in the design: they have connections with both providers and governors, and are responsible for collecting, verifying, and uploading transactions. However, collectors are rational and some of them may behave maliciously (not necessarily for their own benefits). In this paper, we introduce a reputation protocol as a measure of the reliability of collectors in the permissioned blockchain environment. Its objective is to encourage collectors to behave truthfully and, in addition, to reduce the verification cost. The verification cost on provider $p$ is defined as the total number of invalid transactions provided by $p$ and checked by governors. Through theoretical analysis, our protocol with the reputation mechanism has a significant improvement in efficiency. Specifically, the verification loss that governors suffer is proved to be asymptotically $O(\sqrt{T_{total}})$ ($T_{total}$, representing the number of transactions verified by governors and provided by $p$), as long as there exists at least one collector who behaves well. At last, two typical cases where our model can be well applied are also demonstrated.
Bottom-Up Temporal Action Localization with Mutual Regularization
Venue: arXiv cs.CV 2021
Year: 2021

Recently, temporal action localization (TAL), i.e., finding specific action segments in untrimmed videos, has attracted increasing attentions of the computer vision community. State-of-the-art solutions for TAL involves evaluating the frame-level probabilities of three action-indicating phases, i.e. starting, continuing, and ending; and then post-processing these predictions for the final localization. This paper delves deep into this mechanism, and argues that existing methods, by modeling these phases as individual classification tasks, ignored the potential temporal constraints between them. This can lead to incorrect and/or inconsistent predictions when some frames of the video input lack sufficient discriminative information. To alleviate this problem, we introduce two regularization terms to mutually regularize the learning procedure: the Intra-phase Consistency (IntraC) regularization is proposed to make the predictions verified inside each phase; and the Inter-phase Consistency (InterC) regularization is proposed to keep consistency between these phases. Jointly optimizing these two terms, the entire framework is aware of these potential constraints during an end-to-end optimization process. Experiments are performed on two popular TAL datasets, THUMOS14 and ActivityNet1.3. Our approach clearly outperforms the baseline both quantitatively and qualitatively. The proposed regularization also generalizes to other TAL methods (e.g., TSA-Net and PGCN). code: https://github.com/PeisenZhao/Bottom-Up-TAL-with-MR
Self-Enhanced GNN: Improving Graph Neural Networks Using Model Outputs
Venue: arXiv cs.LG 2021
Year: 2021

Graph neural networks (GNNs) have received much attention recently because of their excellent performance on graph-based tasks. However, existing research on GNNs focuses on designing more effective models without considering much about the quality of the input data. In this paper, we propose self-enhanced GNN (SEG), which improves the quality of the input data using the outputs of existing GNN models for better performance on semi-supervised node classification. As graph data consist of both topology and node labels, we improve input data quality from both perspectives. For topology, we observe that higher classification accuracy can be achieved when the ratio of inter-class edges (connecting nodes from different classes) is low and propose topology update to remove inter-class edges and add intra-class edges. For node labels, we propose training node augmentation, which enlarges the training set using the labels predicted by existing GNN models. SEG is a general framework that can be easily combined with existing GNN models. Experimental results validate that SEG consistently improves the performance of well-known GNN models such as GCN, GAT and SGC across different datasets.
Conditional Mutual information-based Contrastive Loss for Financial Time Series Forecasting
Venue: arXiv cs.LG 2021
Year: 2021

We present a representation learning framework for financial time series forecasting. One challenge of using deep learning models for finance forecasting is the shortage of available training data when using small datasets. Direct trend classification using deep neural networks trained on small datasets is susceptible to the overfitting problem. In this paper, we propose to first learn compact representations from time series data, then use the learned representations to train a simpler model for predicting time series movements. We consider a class-conditioned latent variable model. We train an encoder network to maximize the mutual information between the latent variables and the trend information conditioned on the encoded observed variables. We show that conditional mutual information maximization can be approximated by a contrastive loss. Then, the problem is transformed into a classification task of determining whether two encoded representations are sampled from the same class or not. This is equivalent to performing pairwise comparisons of the training datapoints, and thus, improves the generalization ability of the encoder network. We use deep autoregressive models as our encoder to capture long-term dependencies of the sequence data. Empirical experiments indicate that our proposed method has the potential to advance state-of-the-art performance.
Computing the k Densest Subgraphs of a Graph
Venue: arXiv cs.DS 2021
Year: 2021

Computing cohesive subgraphs is a central problem in graph theory. While many formulations of cohesive subgraphs lead to NP-hard problems, finding a densest subgraph can be done in polynomial time. As such, the densest subgraph model has emerged as the most popular notion of cohesiveness. Recently, the data mining community has started looking into the problem of computing k densest subgraphs in a given graph, rather than one, with various restrictions on the possible overlap between the subgraphs. However, there seems to be very little known on this important and natural generalization from a theoretical perspective. In this paper we hope to remedy this situation by analyzing three natural variants of the k densest subgraphs problem. Each variant differs depending on the amount of overlap that is allowed between the subgraphs. In one extreme, when no overlap is allowed, we prove that the problem is NP-hard for k >= 3. On the other extreme, when overlap is allowed without any restrictions and the solution subgraphs only have to be distinct, we show that the problem is fixed-parameter tractable with respect to k, and admits a PTAS for constant k. Finally, when a limited of overlap is allowed between the subgraphs, we prove that the problem is NP-hard for k = 2.
Profile-Guided, Multi-Version Binary Rewriting
Venue: arXiv cs.CR 2021
Year: 2021

The static instrumentation of machine code, also known as binary rewriting, is a power technique, but suffers from high runtime overhead compared to compiler-level instrumentation. Recent research has shown that tools can achieve near-to-zero overhead when rewriting binaries (excluding the overhead from the application specific instrumentation). However, the users of binary rewriting tools often have difficulties in understanding why their instrumentation is slow and how to optimize their instrumentation. We are inspired by a traditional program optimization workflow, where one can profile the program execution to identify performance hot spots, modify the source code or apply suitable compiler optimizations, and even apply profile-guided optimization. We present profile-guided, Multi-Version Binary Rewriting to enable this optimization workflow for static binary instrumentation. Our new techniques include three components. First, we augment existing binary rewriting to support call path profiling; one can interactively view instrumentation costs and understand the calling contexts where the costs incur. Second, we present Versioned Structure Binary Editing, which is a general binary transformation technique. Third, we use call path profiles to guide the application of binary transformation. We apply our new techniques to shadow stack and basic block code coverage. Our instrumentation optimization workflow helps us identify several opportunities with regard to code transformation and instrumentation data layout. Our evaluation on SPEC CPU 2017 shows that the geometric overhead of shadow stack and block coverage is reduced from 7.6% and 161.3% to 1.4% and 4.0%, respectively. We also achieve promising results on Apache HTTP Server, where the shadow stack overhead is reduced from about 20% to 3.5%.
Capacity-achieving Spatially Coupled Sparse Superposition Codes with AMP Decoding
Venue: arXiv cs.IT 2021
Year: 2021

Sparse superposition codes, also called sparse regression codes (SPARCs), are a class of codes for efficient communication over the AWGN channel at rates approaching the channel capacity. In a standard SPARC, codewords are sparse linear combinations of columns of an i.i.d. Gaussian design matrix, while in a spatially coupled SPARC the design matrix has a block-wise structure, where the variance of the Gaussian entries can be varied across blocks. A well-designed spatial coupling structure can significantly enhance the error performance of iterative decoding algorithms such as Approximate Message Passing (AMP). In this paper, we obtain a non-asymptotic bound on the probability of error of spatially coupled SPARCs with AMP decoding. Applying this bound to a simple band-diagonal design matrix, we prove that spatially coupled SPARCs with AMP decoding achieve the capacity of the AWGN channel. The bound also highlights how the decay of error probability depends on each design parameter of the spatially coupled SPARC. An attractive feature of AMP decoding is that its asymptotic mean squared error (MSE) can be predicted via a deterministic recursion called state evolution. Our result provides the first proof that the MSE concentrates on the state evolution prediction for spatially coupled designs. Combined with the state evolution prediction, this result implies that spatially coupled SPARCs with the proposed band-diagonal design are capacity-achieving. Using the proof technique used to establish the main result, we also obtain a concentration inequality for the MSE of AMP applied to compressed sensing with spatially coupled design matrices. Finally we provide numerical simulation results that demonstrate the finite length error performance of spatially coupled SPARCs. The performance is compared with coded modulation schemes that use LDPC codes from the DVB-S2 standard.