OpenRaiser/Intern-Atlas huggingface dataset:
Learning structured approximations of combinatorial optimization problems
Venue: arXiv cs.RO 2023
Year: 2023

Machine learning pipelines that include a combinatorial optimization layer can give surprisingly efficient heuristics for difficult combinatorial optimization problems. Three questions remain open: which architecture should be used, how should the parameters of the machine learning model be learned, and what performance guarantees can we expect from the resulting algorithms? Following the intuitions of geometric deep learning, we explain why equivariant layers should be used when designing such pipelines, and illustrate how to build such layers on routing, scheduling, and network design applications. We introduce a learning approach that enables to learn such pipelines when the training set contains only instances of the difficult optimization problem and not their optimal solutions, and show its numerical performance on our three applications. Finally, using tools from statistical learning theory, we prove a theorem showing the convergence speed of the estimator. As a corollary, we obtain that, if an approximation algorithm can be encoded by the pipeline for some parametrization, then the learned pipeline will retain the approximation ratio guarantee. On our network design problem, our machine learning pipeline has the approximation ratio guarantee of the best approximation algorithm known and the numerical efficiency of the best heuristic.
Parameterized Complexity of Multi-winner Determination: More Effort Towards Fixed-Parameter Tractability
Venue: arXiv cs.GT 2023
Year: 2023

We study the parameterized complexity of winner determination problems for three prevalent $k$-committee selection rules, namely the minimax approval voting (MAV), the proportional approval voting (PAV), and the Chamberlin-Courant's approval voting (CCAV). It is known that these problems are computationally hard. Although they have been studied from the parameterized complexity point of view with respect to several natural parameters, many of them turned out to be W[1]-hard or W[2]-hard. Aiming at obtaining plentiful fixed-parameter algorithms, we revisit these problems by considering more natural single parameters, combined parameters, and structural parameters.
Sparse Personalized Federated Learning
Venue: arXiv cs.LG 2023
Year: 2023

Federated Learning (FL) is a collaborative machine learning technique to train a global model without obtaining clients' private data. The main challenges in FL are statistical diversity among clients, limited computing capability among clients' equipments, and the excessive communication overhead between the server and clients. To address these challenges, we propose a novel sparse personalized federated learning scheme via maximizing correlation (FedMac). By incorporating an approximated L1-norm and the correlation between client models and global model into standard FL loss function, the performance on statistical diversity data is improved and the communicational and computational loads required in the network are reduced compared with non-sparse FL. Convergence analysis shows that the sparse constraints in FedMac do not affect the convergence rate of the global model, and theoretical results show that FedMac can achieve good sparse personalization, which is better than the personalized methods based on L2-norm. Experimentally, we demonstrate the benefits of this sparse personalization architecture compared with the state-of-the-art personalization methods (e.g. FedMac respectively achieves 98.95%, 99.37%, 90.90%, 89.06% and 73.52% accuracy on the MNIST, FMNIST, CIFAR-100, Synthetic and CINIC-10 datasets under non-i.i.d. variants).
MVPipe: Enabling Lightweight Updates and Fast Convergence in Hierarchical Heavy Hitter Detection
Venue: arXiv cs.NI 2023
Year: 2023

Finding hierarchical heavy hitters (HHHs) (i.e., hierarchical aggregates with exceptionally huge amounts of traffic) is critical to network management, yet it is often challenged by the requirements of fast packet processing, real-time and accurate detection, as well as resource efficiency. Existing HHH detection schemes either incur expensive packet updates for multiple aggregation levels in the IP address hierarchy, or need to process sufficient packets to converge to the required detection accuracy. We present MVPipe, an invertible sketch that achieves both lightweight updates and fast convergence in HHH detection. MVPipe builds on the skewness property of IP traffic to process packets via a pipeline of majority voting executions, such that most packets can be updated for only one or few aggregation levels in the IP address hierarchy. We show how MVPipe can be feasibly deployed in P4-based programmable switches subject to limited switch resources. We also theoretically analyze the accuracy and coverage properties of MVPipe. Evaluation with real-world Internet traces shows that MVPipe achieves high accuracy, high throughput, and fast convergence compared to six state-of-the-art HHH detection schemes. It also incurs low resource overhead in the Tofino switch deployment.
DIT4BEARs Smart Roads Internship
Venue: arXiv cs.LG 2023
Year: 2023

The research internship at UiT - The Arctic University of Norway was offered for our team being the winner of the 'Smart Roads - Winter Road Maintenance 2021' Hackathon. The internship commenced on 3 May 2021 and ended on 21 May 2021 with meetings happening twice each week. In spite of having different nationalities and educational backgrounds, we both interns tried to collaborate as a team as much as possible. The most alluring part was working on this project made us realize the critical conditions faced by the arctic people, where it was hard to gain such a unique experience from our residence. We developed and implemented several deep learning models to classify the states (dry, moist, wet, icy, snowy, slushy). Depending upon the best model, the weather forecast app will predict the state taking the Ta, Tsurf, Height, Speed, Water, etc. into consideration. The crucial part was to define a safety metric which is the product of the accident rates based on friction and the accident rates based on states. We developed a regressor that will predict the safety metric depending upon the state obtained from the classifier and the friction obtained from the sensor data. A pathfinding algorithm has been designed using the sensor data, open street map data, weather data.
Deep Learning on a Data Diet: Finding Important Examples Early in Training
Venue: arXiv cs.LG 2023
Year: 2023

Recent success in deep learning has partially been driven by training increasingly overparametrized networks on ever larger datasets. It is therefore natural to ask: how much of the data is superfluous, which examples are important for generalization, and how do we find them? In this work, we make the striking observation that, in standard vision datasets, simple scores averaged over several weight initializations can be used to identify important examples very early in training. We propose two such scores -- the Gradient Normed (GraNd) and the Error L2-Norm (EL2N) scores -- and demonstrate their efficacy on a range of architectures and datasets by pruning significant fractions of training data without sacrificing test accuracy. In fact, using EL2N scores calculated a few epochs into training, we can prune half of the CIFAR10 training set while slightly improving test accuracy. Furthermore, for a given dataset, EL2N scores from one architecture or hyperparameter configuration generalize to other configurations. Compared to recent work that prunes data by discarding examples that are rarely forgotten over the course of training, our scores use only local information early in training. We also use our scores to detect noisy examples and study training dynamics through the lens of important examples -- we investigate how the data distribution shapes the loss surface and identify subspaces of the model's data representation that are relatively stable over training.
On Optimal Approximations for $k$-Submodular Maximization via Multilinear Extension
Venue: arXiv cs.DS 2023
Year: 2023

We investigate a more generalized form of submodular maximization, referred to as $k$-submodular maximization, with applications across social networks and machine learning domains. In this work, we propose the multilinear extension of $k$-submodular functions and unified Frank-Wolfe-type frameworks based on that. Our frameworks accomodate 1) monotone or non-monotone functions, and 2) various constraint types including matroid constraints, knapsack constraints, and their combinations. Notably, we attain an asymptotically optimal $1/2$-approximation for monotone $k$-submodular maximization problems with knapsack constraints, surpassing the previous $1/3$-approximation. The foundation for our analysis stems from new insights into specific linear and monotone properties pertaining to the multilinear extension.
Complexity-Optimized Sparse Bayesian Learning for Scalable Classification Tasks
Venue: arXiv cs.LG 2023
Year: 2023

Sparse Bayesian Learning (SBL) constructs an extremely sparse probabilistic model with very competitive generalization. However, SBL needs to invert a big covariance matrix with complexity $O(M^3)$ (M: feature size) for updating the regularization priors, making it difficult for problems with high dimensional feature space or large data size. As it may easily suffer from the memory overflow issue in such problems. This paper addresses this issue with a newly proposed diagonal Quasi-Newton (DQN) method for SBL called DQN-SBL where the inversion of big covariance matrix is ignored so that the complexity is reduced to $O(M)$. The DQN-SBL is thoroughly evaluated for non linear and linear classifications with various benchmarks of different sizes. Experimental results verify that DQN-SBL receives competitive generalization with a very sparse model and scales well to large-scale problems.
Dormancy-aware timed branching bisimilarity, with an application to communication protocol analysis
Venue: arXiv cs.LO 2023
Year: 2023

A variant of the standard notion of branching bisimilarity for processes with discrete relative timing is proposed which is coarser than the standard notion. Using a version of ACP (Algebra of Communicating Processes) with abstraction for processes with discrete relative timing, it is shown that the proposed variant allows of both the functional correctness and the performance properties of the PAR (Positive Acknowledgement with Retransmission) protocol to be analyzed. In the version of ACP concerned, the difference between the standard notion of branching bisimilarity and its proposed variant is characterized by a single axiom schema.
A Non-invasive Technique to Detect Authentic/Counterfeit SRAM Chips
Venue: arXiv cs.CR 2023
Year: 2023

Many commercially available memory chips are fabricated worldwide in untrusted facilities. Therefore, a counterfeit memory chip can easily enter into the supply chain in different formats. Deploying these counterfeit memory chips into an electronic system can severely affect security and reliability domains because of their sub-standard quality, poor performance, and shorter lifespan. Therefore, a proper solution is required to identify counterfeit memory chips before deploying them in mission-, safety-, and security-critical systems. However, a single solution to prevent counterfeiting is challenging due to the diversity of counterfeit types, sources, and refinement techniques. Besides, the chips can pass initial testing and still fail while being used in the system. Furthermore, existing solutions focus on detecting a single counterfeit type (e.g., detecting recycled memory chips). This work proposes a framework that detects major counterfeit static random-access memory (SRAM) types by attesting/identifying the origin of the manufacturer. The proposed technique generates a single signature for a manufacturer and does not require any exhaustive registration/authentication process. We validate our proposed technique using 345 SRAM chips produced by major manufacturers. The silicon results show that the test scores ($F_{1}$ score) of our proposed technique of identifying memory manufacturer and part-number are 93% and 71%, respectively.
Bayesian Controller Fusion: Leveraging Control Priors in Deep Reinforcement Learning for Robotics
Venue: arXiv cs.RO 2023
Year: 2023

We present Bayesian Controller Fusion (BCF): a hybrid control strategy that combines the strengths of traditional hand-crafted controllers and model-free deep reinforcement learning (RL). BCF thrives in the robotics domain, where reliable but suboptimal control priors exist for many tasks, but RL from scratch remains unsafe and data-inefficient. By fusing uncertainty-aware distributional outputs from each system, BCF arbitrates control between them, exploiting their respective strengths. We study BCF on two real-world robotics tasks involving navigation in a vast and long-horizon environment, and a complex reaching task that involves manipulability maximisation. For both these domains, simple handcrafted controllers exist that can solve the task at hand in a risk-averse manner but do not necessarily exhibit the optimal solution given limitations in analytical modelling, controller miscalibration and task variation. As exploration is naturally guided by the prior in the early stages of training, BCF accelerates learning, while substantially improving beyond the performance of the control prior, as the policy gains more experience. More importantly, given the risk-aversity of the control prior, BCF ensures safe exploration and deployment, where the control prior naturally dominates the action distribution in states unknown to the policy. We additionally show BCF's applicability to the zero-shot sim-to-real setting and its ability to deal with out-of-distribution states in the real world. BCF is a promising approach towards combining the complementary strengths of deep RL and traditional robotic control, surpassing what either can achieve independently. The code and supplementary video material are made publicly available at https://krishanrana.github.io/bcf.
Dimensioning spectrum to support ultra-reliable low-latency communication
Venue: arXiv cs.NI 2023
Year: 2023

Industry-led initiatives such as the Next G Alliance (NGA) are currently considering how to dimension the spectrum required to support new classes of services envisioned beyond 5G. In particular, support for URLLC brings the challenge of how to dimension stochastic wireless networks to meet stringent reliability and latency requirements. Our analysis indicates that the bandwidth needed to meet URLLC goals can be in the order of gigahertz, beyond what is available in today's mobile networks. Network densification can ease those bandwidth needs but requires new deployment strategies involving substantially larger numbers of sites. As an alternative, we consider multi-connectivity and multi-operator network sharing as efficient ways to reduce the demand for bandwidth without outright deployment of additional base stations.
Small-Text: Active Learning for Text Classification in Python
Venue: arXiv cs.LG 2023
Year: 2023

We introduce small-text, an easy-to-use active learning library, which offers pool-based active learning for single- and multi-label text classification in Python. It features numerous pre-implemented state-of-the-art query strategies, including some that leverage the GPU. Standardized interfaces allow the combination of a variety of classifiers, query strategies, and stopping criteria, facilitating a quick mix and match, and enabling a rapid and convenient development of both active learning experiments and applications. With the objective of making various classifiers and query strategies accessible for active learning, small-text integrates several well-known machine learning libraries, namely scikit-learn, PyTorch, and Hugging Face transformers. The latter integrations are optionally installable extensions, so GPUs can be used but are not required. Using this new library, we investigate the performance of the recently published SetFit training paradigm, which we compare to vanilla transformer fine-tuning, finding that it matches the latter in classification accuracy while outperforming it in area under the curve. The library is available under the MIT License at https://github.com/webis-de/small-text, in version 1.3.0 at the time of writing.
Bandit Quickest Changepoint Detection
Venue: arXiv cs.LG 2023
Year: 2023

Many industrial and security applications employ a suite of sensors for detecting abrupt changes in temporal behavior patterns. These abrupt changes typically manifest locally, rendering only a small subset of sensors informative. Continuous monitoring of every sensor can be expensive due to resource constraints, and serves as a motivation for the bandit quickest changepoint detection problem, where sensing actions (or sensors) are sequentially chosen, and only measurements corresponding to chosen actions are observed. We derive an information-theoretic lower bound on the detection delay for a general class of finitely parameterized probability distributions. We then propose a computationally efficient online sensing scheme, which seamlessly balances the need for exploration of different sensing options with exploitation of querying informative actions. We derive expected delay bounds for the proposed scheme and show that these bounds match our information-theoretic lower bounds at low false alarm rates, establishing optimality of the proposed method. We then perform a number of experiments on synthetic and real datasets demonstrating the effectiveness of our proposed method.
Always on Voting: A Framework for Repetitive Voting on the Blockchain
Venue: arXiv cs.CR 2023
Year: 2023

Elections repeat commonly after a fixed time interval, ranging from months to years. This results in limitations on governance since elected candidates or policies are difficult to remove before the next elections, if needed, and allowed by the corresponding law. Participants may decide (through a public deliberation) to change their choices but have no opportunity to vote for these choices before the next elections. Another issue is the peak-end effect, where the judgment of voters is based on how they felt a short time before the elections. To address these issues, we propose Always on Voting (AoV) -- a repetitive voting framework that allows participants to vote and change elected candidates or policies without waiting for the next elections. Participants are permitted to privately change their vote at any point in time, while the effect of their change is manifested at the end of each epoch, whose duration is shorter than the time between two main elections. To thwart the problem of peak-end effect in epochs, the ends of epochs are randomized and made unpredictable, while preserved within soft bounds. These goals are achieved using the synergy between a Bitcoin puzzle oracle, verifiable delay function, and smart contracts.
Content-driven Music Recommendation: Evolution, State of the Art, and Challenges
Venue: arXiv cs.IR 2023
Year: 2023

The music domain is among the most important ones for adopting recommender systems technology. In contrast to most other recommendation domains, which predominantly rely on collaborative filtering (CF) techniques, music recommenders have traditionally embraced content-based (CB) approaches. In the past years, music recommendation models that leverage collaborative and content data -- which we refer to as content-driven models -- have been replacing pure CF or CB models. In this survey, we review 55 articles on content-driven music recommendation. Based on a thorough literature analysis, we first propose an onion model comprising five layers, each of which corresponds to a category of music content we identified: signal, embedded metadata, expert-generated content, user-generated content, and derivative content. We provide a detailed characterization of each category along several dimensions. Second, we identify six overarching challenges, according to which we organize our main discussion: increasing recommendation diversity and novelty, providing transparency and explanations, accomplishing context-awareness, recommending sequences of music, improving scalability and efficiency, and alleviating cold start. Each article addresses one or more of these challenges is categorized according to the content layers of our onion model, the article's goal(s), and main methodological choices. Furthermore, articles are discussed in temporal order to shed light on the evolution of content-driven music recommendation strategies. Finally, we provide our personal selection of the persisting grand challenges which are still waiting to be solved in future research endeavors.
Ultra-Fast, High-Performance 8x8 Approximate Multipliers by a New Multicolumn 3,3:2 Inexact Compressor and its Derivatives
Venue: arXiv cs.AR 2023
Year: 2023

A multiplier, as a key component in many different applications, is a time-consuming, energy-intensive computation block. Approximate computing is a practical design paradigm that attempts to improve hardware efficacy while keeping computation quality satisfactory. A novel multicolumn 3,3:2 inexact compressor is presented in this paper. It takes three partial products from two adjacent columns each for rapid partial product reduction. The proposed inexact compressor and its derivates enable us to design a high-speed approximate multiplier. Then, another ultra-fast, high-efficient approximate multiplier is achieved utilizing a systematic truncation strategy. The proposed multipliers accumulate partial products in only two stages, one fewer stage than other approximate multipliers in the literature. Implementation results by Synopsys Design Compiler and 45 nm technology node demonstrates nearly 11.11% higher speed for the second proposed design over the fastest existing approximate multiplier. Furthermore, the new approximate multipliers are applied to the image processing application of image sharpening, and their performance in this application is highly satisfactory. It is shown in this paper that the error pattern of an approximate multiplier, in addition to the mean error distance and error rate, has a direct effect on the outcomes of the image processing application.
Thought Flow Nets: From Single Predictions to Trains of Model Thought
Venue: arXiv cs.LG 2023
Year: 2023

When humans solve complex problems, they typically create a sequence of ideas (involving an intuitive decision, reflection, error correction, etc.) in order to reach a conclusive decision. Contrary to this, today's models are mostly trained to map an input to one single and fixed output. In this paper, we investigate how we can give models the opportunity of a second, third and $k$-th thought. Taking inspiration from Hegel's dialectics, we propose the concept of a thought flow which creates a sequence of predictions. We present a self-correction mechanism that is trained to estimate the model's correctness and performs iterative prediction updates based on the correctness prediction's gradient. We introduce our method at the example of question answering and conduct extensive experiments that demonstrate (i) our method's ability to correct its own predictions and (ii) its potential to notably improve model performances. In addition, we conduct a qualitative analysis of thought flow correction patterns and explore how thought flow predictions affect human users within a crowdsourcing study. We find that (iii) thought flows enable improved user performance and are perceived as more natural, correct, and intelligent as single and/or top-3 predictions.