OpenRaiser/Intern-Atlas huggingface dataset:
Beam-align: distributed user association for mmWave networks with multi-connectivity
Venue: arXiv cs.NI 2024
Year: 2024

Since the spectrum below 6 GHz bands is insufficient to meet the high bandwidth requirements of 5G use cases, 5G networks expand their operation to mmWave bands. However, operation at these bands has to cope with a high penetration loss and susceptibility to blocking objects. Beamforming and multi-connectivity (MC) can together mitigate these challenges. But, to design such an optimal user association scheme leveraging these two features is non-trivial and computationally expensive. Previous studies either considered a fixed MC degree for all users or overlooked beamforming. Driven by the question what is the optimal degree of MC for each user in a mmWave network, we formulate a user association scheme that maximizes throughput considering beam formation and MC. Our numerical analysis shows that there is no one-size-fits-all degree of optimal MC; it depends on the number of users, their rate requirements, locations, and the maximum number of active beams at a BS.Based on the optimal association, we design BEAM-ALIGN: an efficient heuristic with polynomial-time complexity O(|U|log|U|), where |U| is the number of users. Moreover, BEAM-ALIGN only uses local BS information - i.e. the received signal quality at the user. Differing from prior works, BEAM-ALIGN considers beamforming, multiconnectivity and line-of-sight probability. Via simulations, we show that BEAM-ALIGN performs close to optimal in terms of per-user capacity and satisfaction while it outperforms frequently-used signal-to-interference-and-noise-ratio based association schemes. We then show that BEAM-ALIGN has a robust performance under various challenging scenarios: the presence of blockers, rain, and clustered users.
Generalized Policy Improvement Algorithms with Theoretically Supported Sample Reuse
Venue: arXiv cs.LG 2024
Year: 2024

We develop a new class of model-free deep reinforcement learning algorithms for data-driven, learning-based control. Our Generalized Policy Improvement algorithms combine the policy improvement guarantees of on-policy methods with the efficiency of sample reuse, addressing a trade-off between two important deployment requirements for real-world control: (i) practical performance guarantees and (ii) data efficiency. We demonstrate the benefits of this new class of algorithms through extensive experimental analysis on a broad range of simulated control tasks.
On two-variable guarded fragment logic with expressive local Presburger constraints
Venue: arXiv cs.LO 2024
Year: 2024

We consider the extension of the two-variable guarded fragment logic with local Presburger quantifiers. These are quantifiers that can express properties such as "the number of incoming blue edges plus twice the number of outgoing red edges is at most three times the number of incoming green edges" and captures various description logics with counting, but without constant symbols. We show that the satisfiability problem for this logic is EXP-complete. While the lower bound already holds for the standard two-variable guarded fragment logic, the upper bound is established by a novel, yet simple deterministic graph-based algorithm.
A Theoretical Computer Science Perspective on Free Will
Venue: arXiv cs.CC 2024
Year: 2024

We consider the paradoxical concept of free will from the perspective of Theoretical Computer Science (TCS), a branch of mathematics concerned with understanding the underlying principles of computation and complexity, including the implications and surprising consequences of resource limitations.
Bounding and computing obstacle numbers of graphs
Venue: arXiv cs.CG 2024
Year: 2024

An obstacle representation of a graph $G$ consists of a set of pairwise disjoint simply-connected closed regions and a one-to-one mapping of the vertices of $G$ to points such that two vertices are adjacent in $G$ if and only if the line segment connecting the two corresponding points does not intersect any obstacle. The obstacle number of a graph is the smallest number of obstacles in an obstacle representation of the graph in the plane such that all obstacles are simple polygons. It is known that the obstacle number of each $n$-vertex graph is $O(n \log n)$ [Balko, Cibulka, and Valtr, 2018] and that there are $n$-vertex graphs whose obstacle number is $Ω(n/(\log\log n)^2)$ [Dujmović and Morin, 2015]. We improve this lower bound to $Ω(n/\log\log n)$ for simple polygons and to $Ω(n)$ for convex polygons. To obtain these stronger bounds, we improve known estimates on the number of $n$-vertex graphs with bounded obstacle number, solving a conjecture by Dujmović and Morin. We also show that if the drawing of some $n$-vertex graph is given as part of the input, then for some drawings $Ω(n^2)$ obstacles are required to turn them into an obstacle representation of the graph. Our bounds are asymptotically tight in several instances. We complement these combinatorial bounds by two complexity results. First, we show that computing the obstacle number of a graph $G$ is fixed-parameter tractable in the vertex cover number of $G$. Second, we show that, given a graph $G$ and a simple polygon $P$, it is NP-hard to decide whether $G$ admits an obstacle representation using $P$ as the only obstacle.
On-Device Training Under 256KB Memory
Venue: arXiv cs.CV 2024
Year: 2024

On-device training enables the model to adapt to new data collected from the sensors by fine-tuning a pre-trained model. Users can benefit from customized AI models without having to transfer the data to the cloud, protecting the privacy. However, the training memory consumption is prohibitive for IoT devices that have tiny memory resources. We propose an algorithm-system co-design framework to make on-device training possible with only 256KB of memory. On-device training faces two unique challenges: (1) the quantized graphs of neural networks are hard to optimize due to low bit-precision and the lack of normalization; (2) the limited hardware resource does not allow full back-propagation. To cope with the optimization difficulty, we propose Quantization-Aware Scaling to calibrate the gradient scales and stabilize 8-bit quantized training. To reduce the memory footprint, we propose Sparse Update to skip the gradient computation of less important layers and sub-tensors. The algorithm innovation is implemented by a lightweight training system, Tiny Training Engine, which prunes the backward computation graph to support sparse updates and offload the runtime auto-differentiation to compile time. Our framework is the first solution to enable tiny on-device training of convolutional neural networks under 256KB SRAM and 1MB Flash without auxiliary memory, using less than 1/1000 of the memory of PyTorch and TensorFlow while matching the accuracy on tinyML application VWW. Our study enables IoT devices not only to perform inference but also to continuously adapt to new data for on-device lifelong learning. A video demo can be found here: https://youtu.be/0pUFZYdoMY8.
The Structure of Hypergraphs Arising in Cellular Mobile Communication Systems
Venue: arXiv cs.NI 2024
Year: 2024

An assumption that researchers have often used to model interference in a wireless network is the unit disk graph model. While many theoretical results and performance guarantees have been obtained under this model, an open research direction is to extend these results to hypergraph interference models. Motivated by recent results that the worst-case performance of the distributed maximal scheduling algorithm is characterized by the interference degree of the hypergraph, in the present work we investigate properties of the interference degree of the hypergraph and the structure of hypergraphs arising from physical constraints. We show that the problem of computing the interference degree of a hypergraph is NP-hard and we prove some properties and results concerning this hypergraph invariant. We investigate which hypergraphs are realizable, i.e. which hypergraphs arise in practice, based on physical constraints, as the interference model of a wireless network. In particular, a question that arises naturally is: what is the maximal value of $r$ such that the hypergraph $K_{1,r}$ is realizable? We determine this quantity for various integral and nonintegral values of the path loss exponent of signal propagation. We also investigate hypergraphs generated by line networks.
Online SuBmodular + SuPermodular (BP) Maximization with Bandit Feedback
Venue: arXiv cs.LG 2024
Year: 2024

In the context of online interactive machine learning with combinatorial objectives, we extend purely submodular prior work to more general non-submodular objectives. This includes: (1) those that are additively decomposable into a sum of two terms (a monotone submodular and monotone supermodular term, known as a BP decomposition); and (2) those that are only weakly submodular. In both cases, this allows representing not only competitive (submodular) but also complementary (supermodular) relationships between objects, enhancing this setting to a broader range of applications (e.g., movie recommendations, medical treatments, etc.) where this is beneficial. In the two-term case, moreover, we study not only the more typical monolithic feedback approach but also a novel framework where feedback is available separately for each term. With real-world practicality and scalability in mind, we integrate Nystrom sketching techniques to significantly reduce the computational cost, including for the purely submodular case. In the Gaussian process contextual bandits setting, we show sub-linear theoretical regret bounds in all cases. We also empirically show good applicability to recommendation systems and data subset selection.
Majorization-minimization for Sparse Nonnegative Matrix Factorization with the $β$-divergence
Venue: arXiv cs.LG 2024
Year: 2024

This article introduces new multiplicative updates for nonnegative matrix factorization with the $β$-divergence and sparse regularization of one of the two factors (say, the activation matrix). It is well known that the norm of the other factor (the dictionary matrix) needs to be controlled in order to avoid an ill-posed formulation. Standard practice consists in constraining the columns of the dictionary to have unit norm, which leads to a nontrivial optimization problem. Our approach leverages a reparametrization of the original problem into the optimization of an equivalent scale-invariant objective function. From there, we derive block-descent majorization-minimization algorithms that result in simple multiplicative updates for either $\ell_{1}$-regularization or the more "aggressive" log-regularization. In contrast with other state-of-the-art methods, our algorithms are universal in the sense that they can be applied to any $β$-divergence (i.e., any value of $β$) and that they come with convergence guarantees. We report numerical comparisons with existing heuristic and Lagrangian methods using various datasets: face images, an audio spectrogram, hyperspectral data, and song play counts. We show that our methods obtain solutions of similar quality at convergence (similar objective values) but with significantly reduced CPU times.
Benign, Tempered, or Catastrophic: A Taxonomy of Overfitting
Venue: arXiv cs.LG 2024
Year: 2024

The practical success of overparameterized neural networks has motivated the recent scientific study of interpolating methods, which perfectly fit their training data. Certain interpolating methods, including neural networks, can fit noisy training data without catastrophically bad test performance, in defiance of standard intuitions from statistical learning theory. Aiming to explain this, a body of recent work has studied benign overfitting, a phenomenon where some interpolating methods approach Bayes optimality, even in the presence of noise. In this work we argue that while benign overfitting has been instructive and fruitful to study, many real interpolating methods like neural networks do not fit benignly: modest noise in the training set causes nonzero (but non-infinite) excess risk at test time, implying these models are neither benign nor catastrophic but rather fall in an intermediate regime. We call this intermediate regime tempered overfitting, and we initiate its systematic study. We first explore this phenomenon in the context of kernel (ridge) regression (KR) by obtaining conditions on the ridge parameter and kernel eigenspectrum under which KR exhibits each of the three behaviors. We find that kernels with powerlaw spectra, including Laplace kernels and ReLU neural tangent kernels, exhibit tempered overfitting. We then empirically study deep neural networks through the lens of our taxonomy, and find that those trained to interpolation are tempered, while those stopped early are benign. We hope our work leads to a more refined understanding of overfitting in modern learning.
GANDALF: Gated Adaptive Network for Deep Automated Learning of Features
Venue: arXiv cs.LG 2024
Year: 2024

We propose a novel high-performance, interpretable, and parameter \& computationally efficient deep learning architecture for tabular data, Gated Adaptive Network for Deep Automated Learning of Features (GANDALF). GANDALF relies on a new tabular processing unit with a gating mechanism and in-built feature selection called Gated Feature Learning Unit (GFLU) as a feature representation learning unit. We demonstrate that GANDALF outperforms or stays at-par with SOTA approaches like XGBoost, SAINT, FT-Transformers, etc. by experiments on multiple established public benchmarks. We have made available the code at github.com/manujosephv/pytorch_tabular under MIT License.
D$^3$FlowSLAM: Self-Supervised Dynamic SLAM with Flow Motion Decomposition and DINO Guidance
Venue: arXiv cs.CV 2024
Year: 2024

In this paper, we introduce a self-supervised deep SLAM method that robustly operates in dynamic scenes while accurately identifying dynamic components. Our method leverages a dual-flow representation for static flow and dynamic flow, facilitating effective scene decomposition in dynamic environments. We propose a dynamic update module based on this representation and develop a dense SLAM system that excels in dynamic scenarios. In addition, we design a self-supervised training scheme using DINO as a prior, enabling label-free training. Our method achieves superior accuracy compared to other self-supervised methods. It also matches or even surpasses the performance of existing supervised methods in some cases. All code and data will be made publicly available upon acceptance.
Distributed Differentiable Dynamic Game for Multi-robot Coordination
Venue: arXiv cs.RO 2024
Year: 2024

This paper develops a Distributed Differentiable Dynamic Game (D3G) framework, which can efficiently solve the forward and inverse problems in multi-robot coordination. We formulate multi-robot coordination as a dynamic game, where the behavior of a robot is dictated by its own dynamics and objective that also depends on others' behavior. In the forward problem, D3G enables all robots collaboratively to seek the Nash equilibrium of the game in a distributed manner, by developing a distributed shooting-based Nash solver. In the inverse problem, where each robot aims to find (learn) its objective (and dynamics) parameters to mimic given coordination demonstrations, D3G proposes a differentiation solver based on Differential Pontryagin's Maximum Principle, which allows each robot to update its parameters in a distributed and coordinated manner. We test the D3G in simulation with two types of robots given different task configurations. The results demonstrate the effectiveness of D3G for solving both forward and inverse problems in comparison with existing methods.
Semi-supervised Predictive Clustering Trees for (Hierarchical) Multi-label Classification
Venue: arXiv cs.LG 2024
Year: 2024

Semi-supervised learning (SSL) is a common approach to learning predictive models using not only labeled examples, but also unlabeled examples. While SSL for the simple tasks of classification and regression has received a lot of attention from the research community, this is not properly investigated for complex prediction tasks with structurally dependent variables. This is the case of multi-label classification and hierarchical multi-label classification tasks, which may require additional information, possibly coming from the underlying distribution in the descriptive space provided by unlabeled examples, to better face the challenging task of predicting simultaneously multiple class labels. In this paper, we investigate this aspect and propose a (hierarchical) multi-label classification method based on semi-supervised learning of predictive clustering trees. We also extend the method towards ensemble learning and propose a method based on the random forest approach. Extensive experimental evaluation conducted on 23 datasets shows significant advantages of the proposed method and its extension with respect to their supervised counterparts. Moreover, the method preserves interpretability and reduces the time complexity of classical tree-based models.
Exploring the Online Micro-targeting Practices of Small, Medium, and Large Businesses
Venue: arXiv cs.CY 2024
Year: 2024

Facebook and other advertising platforms exploit users data for marketing purposes by allowing advertisers to select specific users and target them (the practice is being called micro-targeting). However, advertisers such as Cambridge Analytica have maliciously used these targeting features to manipulate users in the context of elections. The European Commission plans to restrict or ban some targeting functionalities in the new European Democracy Action Plan act to protect users from such harms. The difficulty is that we do not know the economic impact of these restrictions on regular advertisers. In this paper, to inform the debate, we take a first step by understanding who is advertising on Facebook and how they use the targeting functionalities. For this, we asked 890 U.S. users to install a monitoring tool on their browsers to collect the ads they receive on Facebook and information about how these ads were targeted. By matching advertisers on Facebook with their LinkedIn profiles, we could see that 71% of advertisers are small and medium-sized businesses with 200 employees or less, and they are responsible for 61% of ads and 57% of ad impressions. Regarding micro-targeting, we found that only 32% of small and medium-sized businesses and 30% of large-sized businesses micro-target at least one of their ads. These results should not be interpreted as micro-targeting not being useful as a marketing strategy, but rather that advertisers prefer to outsource the micro-targeting task to ad platforms. Indeed, Facebook is employing optimization algorithms that exploit user data to decide which users should see what ads; which means ad platforms are performing an algorithmic-driven micro-targeting. Hence, when setting restrictions, legislators should take into account both the traditional advertiser-driven micro-targeting as well as algorithmic-driven micro-targeting performed by ad platforms.
Identifying and characterizing superspreaders of low-credibility content on Twitter
Venue: arXiv cs.SI 2024
Year: 2024

The world's digital information ecosystem continues to struggle with the spread of misinformation. Prior work has suggested that users who consistently disseminate a disproportionate amount of low-credibility content -- so-called superspreaders -- are at the center of this problem. We quantitatively confirm this hypothesis and introduce simple metrics to predict the top superspreaders several months into the future. We then conduct a qualitative review to characterize the most prolific superspreaders and analyze their sharing behaviors. Superspreaders include pundits with large followings, low-credibility media outlets, personal accounts affiliated with those media outlets, and a range of influencers. They are primarily political in nature and use more toxic language than the typical user sharing misinformation. We also find concerning evidence that suggests Twitter may be overlooking prominent superspreaders. We hope this work will further public understanding of bad actors and promote steps to mitigate their negative impacts on healthy digital discourse.
Improving Privacy-Preserving Vertical Federated Learning by Efficient Communication with ADMM
Venue: arXiv cs.LG 2024
Year: 2024

Federated learning (FL) enables distributed resource-constrained devices to jointly train shared models while keeping the training data local for privacy purposes. Vertical FL (VFL), which allows each client to collect partial features, has attracted intensive research efforts recently. We identified the main challenges that existing VFL frameworks are facing: the server needs to communicate gradients with the clients for each training step, incurring high communication cost that leads to rapid consumption of privacy budgets. To address these challenges, in this paper, we introduce a VFL framework with multiple heads (VIM), which takes the separate contribution of each client into account, and enables an efficient decomposition of the VFL optimization objective to sub-objectives that can be iteratively tackled by the server and the clients on their own. In particular, we propose an Alternating Direction Method of Multipliers (ADMM)-based method to solve our optimization problem, which allows clients to conduct multiple local updates before communication, and thus reduces the communication cost and leads to better performance under differential privacy (DP). We provide the user-level DP mechanism for our framework to protect user privacy. Moreover, we show that a byproduct of VIM is that the weights of learned heads reflect the importance of local clients. We conduct extensive evaluations and show that on four vertical FL datasets, VIM achieves significantly higher performance and faster convergence compared with the state-of-the-art. We also explicitly evaluate the importance of local clients and show that VIM enables functionalities such as client-level explanation and client denoising. We hope this work will shed light on a new way of effective VFL training and understanding.
Comparative Study on Supervised versus Semi-supervised Machine Learning for Anomaly Detection of In-vehicle CAN Network
Venue: arXiv cs.LG 2024
Year: 2024

As the central nerve of the intelligent vehicle control system, the in-vehicle network bus is crucial to the security of vehicle driving. One of the best standards for the in-vehicle network is the Controller Area Network (CAN bus) protocol. However, the CAN bus is designed to be vulnerable to various attacks due to its lack of security mechanisms. To enhance the security of in-vehicle networks and promote the research in this area, based upon a large scale of CAN network traffic data with the extracted valuable features, this study comprehensively compared fully-supervised machine learning with semi-supervised machine learning methods for CAN message anomaly detection. Both traditional machine learning models (including single classifier and ensemble models) and neural network based deep learning models are evaluated. Furthermore, this study proposed a deep autoencoder based semi-supervised learning method applied for CAN message anomaly detection and verified its superiority over other semi-supervised methods. Extensive experiments show that the fully-supervised methods generally outperform semi-supervised ones as they are using more information as inputs. Typically the developed XGBoost based model obtained state-of-the-art performance with the best accuracy (98.65%), precision (0.9853), and ROC AUC (0.9585) beating other methods reported in the literature.