OpenRaiser/Intern-Atlas huggingface dataset:
A Generalized Framework for Joint Dynamic Optimal RF Interface Setting and Next-Hop Selection in IoT networks with Similar Requests
Venue: arXiv cs.NI 2022
Year: 2022

Many applications which run on the Internet-of-Things machines require similar bandwidths. These machines are equipped with multiple Radio Frequency (RF) interfaces for machine-to-machine or machine-to-Base Station(BS) communications. Joint dynamic optimal RF interface setting and next-hop selection in data transmission can maximize the network data rate. For this purpose, we propose a generalized framework for simultaneous selection of these components according to the required bandwidth of machines. This framework is suitable for networks with multiple BSs and sources with similar bandwidth requests. Simulation results show that using the proposed framework, the average data rate of network sources increases up to 117%.
Time-Optimal Sublinear Algorithms for Matching and Vertex Cover
Venue: arXiv cs.DS 2022
Year: 2022

We study the problem of estimating the size of maximum matching and minimum vertex cover in sublinear time. Denoting the number of vertices by $n$ and the average degree in the graph by $\bar{d}$, we obtain the following results for both problems: * A multiplicative $(2+ε)$-approximation that takes $\tilde{O}(n/ε^2)$ time using adjacency list queries. * A multiplicative-additive $(2, εn)$-approximation in $\tilde{O}((\bar{d} + 1)/ε^2)$ time using adjacency list queries. * A multiplicative-additive $(2, εn)$-approximation in $\tilde{O}(n/ε^{3})$ time using adjacency matrix queries. All three results are provably time-optimal up to polylogarithmic factors culminating a long line of work on these problems. Our main contribution and the key ingredient leading to the bounds above is a new and near-tight analysis of the average query complexity of the randomized greedy maximal matching algorithm which improves upon a seminal result of Yoshida, Yamamoto, and Ito [STOC'09].
The Fine-Grained Hardness of Sparse Linear Regression
Venue: arXiv cs.LG 2022
Year: 2022

Sparse linear regression is the well-studied inference problem where one is given a design matrix $\mathbf{A} \in \mathbb{R}^{M\times N}$ and a response vector $\mathbf{b} \in \mathbb{R}^M$, and the goal is to find a solution $\mathbf{x} \in \mathbb{R}^{N}$ which is $k$-sparse (that is, it has at most $k$ non-zero coordinates) and minimizes the prediction error $\|\mathbf{A} \mathbf{x} - \mathbf{b}\|_2$. On the one hand, the problem is known to be $\mathcal{NP}$-hard which tells us that no polynomial-time algorithm exists unless $\mathcal{P} = \mathcal{NP}$. On the other hand, the best known algorithms for the problem do a brute-force search among $N^k$ possibilities. In this work, we show that there are no better-than-brute-force algorithms, assuming any one of a variety of popular conjectures including the weighted $k$-clique conjecture from the area of fine-grained complexity, or the hardness of the closest vector problem from the geometry of numbers. We also show the impossibility of better-than-brute-force algorithms when the prediction error is measured in other $\ell_p$ norms, assuming the strong exponential-time hypothesis.
Feature-based Style Randomization for Domain Generalization
Venue: arXiv cs.CV 2022
Year: 2022

As a recent noticeable topic, domain generalization (DG) aims to first learn a generic model on multiple source domains and then directly generalize to an arbitrary unseen target domain without any additional adaption. In previous DG models, by generating virtual data to supplement observed source domains, the data augmentation based methods have shown its effectiveness. To simulate the possible unseen domains, most of them enrich the diversity of original data via image-level style transformation. However, we argue that the potential styles are hard to be exhaustively illustrated and fully augmented due to the limited referred styles, leading the diversity could not be always guaranteed. Unlike image-level augmentation, we in this paper develop a simple yet effective feature-based style randomization module to achieve feature-level augmentation, which can produce random styles via integrating random noise into the original style. Compared with existing image-level augmentation, our feature-level augmentation favors a more goal-oriented and sample-diverse way. Furthermore, to sufficiently explore the efficacy of the proposed module, we design a novel progressive training strategy to enable all parameters of the network to be fully trained. Extensive experiments on three standard benchmark datasets, i.e., PACS, VLCS and Office-Home, highlight the superiority of our method compared to the state-of-the-art methods.
Alpha Matte Generation from Single Input for Portrait Matting
Venue: arXiv cs.CV 2022
Year: 2022

In the portrait matting, the goal is to predict an alpha matte that identifies the effect of each pixel on the foreground subject. Traditional approaches and most of the existing works utilized an additional input, e.g., trimap, background image, to predict alpha matte. However, (1) providing additional input is not always practical, and (2) models are too sensitive to these additional inputs. To address these points, in this paper, we introduce an additional input-free approach to perform portrait matting. We divide the task into two subtasks, segmentation and alpha matte prediction. We first generate a coarse segmentation map from the input image and then predict the alpha matte by utilizing the image and segmentation map. Besides, we present a segmentation encoding block to downsample the coarse segmentation map and provide useful feature representation to the residual block, since using a single encoder causes the vanishing of the segmentation information. We tested our model on four different benchmark datasets. The proposed method outperformed the MODNet and MGMatting methods that also take a single input. Besides, we obtained comparable results with BGM-V2 and FBA methods that require additional input.
Rack-Aware Regenerating Codes with Multiple Erasure Tolerance
Venue: arXiv cs.IT 2022
Year: 2022

In a modern distributed storage system, storage nodes are organized in racks, and the cross-rack communication dominates the system bandwidth. In We study the rack-aware storage system where all storage nodes are organized in racks and within each rack the nodes can communicate freely without taxing the system bandwidth. Rack-aware regenerating codes (RRCs) were proposed for minimizing the repair bandwidth for single erasures. In the initial setting of RRCs, the repair of a single node requires the participation of all the remaining nodes in the rack containing the failed node as well as a large number of helper racks containing no failures. Consequently, the repair may be infeasible in front of multiple node failures. In this work, a relaxed repair model that can tolerate multiple node failures by simultaneously reducing the intra-rack connections and cross-rack connections is proposed. A tradeoff between the storage and repair bandwidth under the relaxed repair model is derived, and parameters of the two extreme points on the tradeoff curve are characterized for the minimum storage and minimum bandwidth respectively. Moreover, two codes corresponding to the extreme points are explicitly constructed over the fields of size comparable to the code length and with the lowest sub-packetization. Finally, for the convenience of practical use, systematic encoding processes for the two codes are also established.
Graph Neural Networks in Network Neuroscience
Venue: arXiv cs.LG 2022
Year: 2022

Noninvasive medical neuroimaging has yielded many discoveries about the brain connectivity. Several substantial techniques mapping morphological, structural and functional brain connectivities were developed to create a comprehensive road map of neuronal activities in the human brain -namely brain graph. Relying on its non-Euclidean data type, graph neural network (GNN) provides a clever way of learning the deep graph structure and it is rapidly becoming the state-of-the-art leading to enhanced performance in various network neuroscience tasks. Here we review current GNN-based methods, highlighting the ways that they have been used in several applications related to brain graphs such as missing brain graph synthesis and disease classification. We conclude by charting a path toward a better application of GNN models in network neuroscience field for neurological disorder diagnosis and population graph integration. The list of papers cited in our work is available at https://github.com/basiralab/GNNs-in-Network-Neuroscience.
Forward Looking Best-Response Multiplicative Weights Update Methods for Bilinear Zero-sum Games
Venue: arXiv cs.GT 2022
Year: 2022

Our work focuses on extra gradient learning algorithms for finding Nash equilibria in bilinear zero-sum games. The proposed method, which can be formally considered as a variant of Optimistic Mirror Descent \cite{DBLP:conf/iclr/MertikopoulosLZ19}, uses a large learning rate for the intermediate gradient step which essentially leads to computing (approximate) best response strategies against the profile of the previous iteration. Although counter-intuitive at first sight due to the irrationally large, for an iterative algorithm, intermediate learning step, we prove that the method guarantees last-iterate convergence to an equilibrium. Particularly, we show that the algorithm reaches first an $η^{1/ρ}$-approximate Nash equilibrium, with $ρ> 1$, by decreasing the Kullback-Leibler divergence of each iterate by at least $Ω(η^{1+\frac{1}ρ})$, for sufficiently small learning rate, $η$, until the method becomes a contracting map, and converges to the exact equilibrium. Furthermore, we perform experimental comparisons with the optimistic variant of the multiplicative weights update method, by \cite{Daskalakis2019LastIterateCZ} and show that our algorithm has significant practical potential since it offers substantial gains in terms of accelerated convergence.
Mean-Shifted Contrastive Loss for Anomaly Detection
Venue: arXiv cs.CV 2022
Year: 2022

Deep anomaly detection methods learn representations that separate between normal and anomalous images. Although self-supervised representation learning is commonly used, small dataset sizes limit its effectiveness. It was previously shown that utilizing external, generic datasets (e.g. ImageNet classification) can significantly improve anomaly detection performance. One approach is outlier exposure, which fails when the external datasets do not resemble the anomalies. We take the approach of transferring representations pre-trained on external datasets for anomaly detection. Anomaly detection performance can be significantly improved by fine-tuning the pre-trained representations on the normal training images. In this paper, we first demonstrate and analyze that contrastive learning, the most popular self-supervised learning paradigm cannot be naively applied to pre-trained features. The reason is that pre-trained feature initialization causes poor conditioning for standard contrastive objectives, resulting in bad optimization dynamics. Based on our analysis, we provide a modified contrastive objective, the Mean-Shifted Contrastive Loss. Our method is highly effective and achieves a new state-of-the-art anomaly detection performance including $98.6\%$ ROC-AUC on the CIFAR-10 dataset.
TENGraD: Time-Efficient Natural Gradient Descent with Exact Fisher-Block Inversion
Venue: arXiv cs.LG 2022
Year: 2022

This work proposes a time-efficient Natural Gradient Descent method, called TENGraD, with linear convergence guarantees. Computing the inverse of the neural network's Fisher information matrix is expensive in NGD because the Fisher matrix is large. Approximate NGD methods such as KFAC attempt to improve NGD's running time and practical application by reducing the Fisher matrix inversion cost with approximation. However, the approximations do not reduce the overall time significantly and lead to less accurate parameter updates and loss of curvature information. TENGraD improves the time efficiency of NGD by computing Fisher block inverses with a computationally efficient covariance factorization and reuse method. It computes the inverse of each block exactly using the Woodbury matrix identity to preserve curvature information while admitting (linear) fast convergence rates. Our experiments on image classification tasks for state-of-the-art deep neural architecture on CIFAR-10, CIFAR-100, and Fashion-MNIST show that TENGraD significantly outperforms state-of-the-art NGD methods and often stochastic gradient descent in wall-clock time.
On the Coupling of Depth and Egomotion Networks for Self-Supervised Structure from Motion
Venue: arXiv cs.CV 2022
Year: 2022

Structure from motion (SfM) has recently been formulated as a self-supervised learning problem, where neural network models of depth and egomotion are learned jointly through view synthesis. Herein, we address the open problem of how to best couple, or link, the depth and egomotion network components, so that information such as a common scale factor can be shared between the networks. Towards this end, we introduce several notions of coupling, categorize existing approaches, and present a novel tightly-coupled approach that leverages the interdependence of depth and egomotion at training time and at test time. Our approach uses iterative view synthesis to recursively update the egomotion network input, permitting contextual information to be passed between the components. We demonstrate through substantial experiments that our approach promotes consistency between the depth and egomotion predictions at test time, improves generalization, and leads to state-of-the-art accuracy on indoor and outdoor depth and egomotion evaluation benchmarks.
Online Algorithms for Network Robustness under Connectivity Constraints
Venue: arXiv cs.DS 2022
Year: 2022

In this paper, we present algorithms for designing networks that are robust to node failures with minimal or limited number of links. We present algorithms for both the static network setting and the dynamic network setting; setting where new nodes can arrive in the future. For the static setting, we present algorithms for constructing the optimal network in terms of the number of links used for a given node size and the number of nodes that can fail. We then consider the dynamic setting where it is disruptive to remove any of the older links. For this setting, we present online algorithms for two cases: (i) when the number of nodes that can fail remains constant and (ii) when only the proportion of the nodes that can fail remains constant. We show that the proposed algorithm for the first case saves nearly $3/4$th of the total possible links at any point of time. We then present algorithms for various levels of the fraction of the nodes that can fail and characterize their link usage. We show that when $1/2$ the number of nodes can fail at any point of time, the proposed algorithm saves nearly $1/2$ of the total possible links at any point of time. We show that when the number of nodes that can fail is limited to the fraction $1/(2m)$ ($m \in \mathbb{N}$), the proposed algorithm saves nearly as much as $(1-1/2m)$ of the total possible links at any point of time. We also show that when the number of nodes that can fail at any point of time is $1/2$ of the number of nodes plus $n$, $n \in \mathbb{N}$, the number of links saved by the proposed algorithm reduces only linearly in $n$. We conjecture that the saving ratio achieved by the algorithms we present is optimal for the dynamic setting.
Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss
Venue: arXiv cs.LG 2022
Year: 2022

Recent works in self-supervised learning have advanced the state-of-the-art by relying on the contrastive learning paradigm, which learns representations by pushing positive pairs, or similar examples from the same class, closer together while keeping negative pairs far apart. Despite the empirical successes, theoretical foundations are limited -- prior analyses assume conditional independence of the positive pairs given the same class label, but recent empirical applications use heavily correlated positive pairs (i.e., data augmentations of the same image). Our work analyzes contrastive learning without assuming conditional independence of positive pairs using a novel concept of the augmentation graph on data. Edges in this graph connect augmentations of the same data, and ground-truth classes naturally form connected sub-graphs. We propose a loss that performs spectral decomposition on the population augmentation graph and can be succinctly written as a contrastive learning objective on neural net representations. Minimizing this objective leads to features with provable accuracy guarantees under linear probe evaluation. By standard generalization bounds, these accuracy guarantees also hold when minimizing the training contrastive loss. Empirically, the features learned by our objective can match or outperform several strong baselines on benchmark vision datasets. In all, this work provides the first provable analysis for contrastive learning where guarantees for linear probe evaluation can apply to realistic empirical settings.
A Perspective on Time towards Wireless 6G
Venue: arXiv cs.IT 2022
Year: 2022

With the advent of 5G technology, the notion of latency got a prominent role in wireless connectivity, serving as a proxy term for addressing the requirements for real-time communication. As wireless systems evolve towards 6G, the ambition to immerse the digital into the physical reality will increase. Besides making the real-time requirements more stringent, this immersion will bring the notions of time, simultaneity, presence, and causality to a new level of complexity. A growing body of research points out that latency is insufficient to parameterize all real-time requirements. Notably, one such requirement that received a significant attention is information freshness, defined through the Age of Information (AoI) and its derivatives. The objective of this article is to investigate the general notion of timing in wireless communication systems and networks and its relation to effective information generation, processing, transmission, and reconstruction at the senders and receivers. We establish a general statistical framework of timing requirements in wireless communication systems, which subsumes both latency and AoI. The framework is made by associating a timing component with the two basic statistical operations, decision and estimation. We first use the framework to present a representative sample of the existing works that deal with timing in wireless communication. Next, it is shown how the framework can be used with different communication models of increasing complexity, starting from the basic Shannon one-way communication model and arriving to communication models for consensus, distributed learning, and inference. Overall, this paper fills an important gap in the literature by providing a systematic treatment of various timing measures in wireless communication and sets the basis for design and optimization for the next-generation real-time systems.
Nonsmooth Implicit Differentiation for Machine Learning and Optimization
Venue: arXiv cs.LG 2022
Year: 2022

In view of training increasingly complex learning architectures, we establish a nonsmooth implicit function theorem with an operational calculus. Our result applies to most practical problems (i.e., definable problems) provided that a nonsmooth form of the classical invertibility condition is fulfilled. This approach allows for formal subdifferentiation: for instance, replacing derivatives by Clarke Jacobians in the usual differentiation formulas is fully justified for a wide class of nonsmooth problems. Moreover this calculus is entirely compatible with algorithmic differentiation (e.g., backpropagation). We provide several applications such as training deep equilibrium networks, training neural nets with conic optimization layers, or hyperparameter-tuning for nonsmooth Lasso-type models. To show the sharpness of our assumptions, we present numerical experiments showcasing the extremely pathological gradient dynamics one can encounter when applying implicit algorithmic differentiation without any hypothesis.
On the relation between statistical learning and perceptual distances
Venue: arXiv cs.CV 2022
Year: 2022

It has been demonstrated many times that the behavior of the human visual system is connected to the statistics of natural images. Since machine learning relies on the statistics of training data as well, the above connection has interesting implications when using perceptual distances (which mimic the behavior of the human visual system) as a loss function. In this paper, we aim to unravel the non-trivial relationships between the probability distribution of the data, perceptual distances, and unsupervised machine learning. To this end, we show that perceptual sensitivity is correlated with the probability of an image in its close neighborhood. We also explore the relation between distances induced by autoencoders and the probability distribution of the training data, as well as how these induced distances are correlated with human perception. Finally, we find perceptual distances do not always lead to noticeable gains in performance over Euclidean distance in common image processing tasks, except when data is scarce and the perceptual distance provides regularization. We propose this may be due to a \emph{double-counting} effect of the image statistics, once in the perceptual distance and once in the training procedure.
MoCo-Flow: Neural Motion Consensus Flow for Dynamic Humans in Stationary Monocular Cameras
Venue: arXiv cs.CV 2022
Year: 2022

Synthesizing novel views of dynamic humans from stationary monocular cameras is a specialized but desirable setup. This is particularly attractive as it does not require static scenes, controlled environments, or specialized capture hardware. In contrast to techniques that exploit multi-view observations, the problem of modeling a dynamic scene from a single view is significantly more under-constrained and ill-posed. In this paper, we introduce Neural Motion Consensus Flow (MoCo-Flow), a representation that models dynamic humans in stationary monocular cameras using a 4D continuous time-variant function. We learn the proposed representation by optimizing for a dynamic scene that minimizes the total rendering error, over all the observed images. At the heart of our work lies a carefully designed optimization scheme, which includes a dedicated initialization step and is constrained by a motion consensus regularization on the estimated motion flow. We extensively evaluate MoCo-Flow on several datasets that contain human motions of varying complexity, and compare, both qualitatively and quantitatively, to several baselines and ablated variations of our methods, showing the efficacy and merits of the proposed approach. Pretrained model, code, and data will be released for research purposes upon paper acceptance.