OpenRaiser/Intern-Atlas huggingface dataset:
Learning-Augmented Weighted Paging
Venue: arXiv cs.DS 2021
Year: 2021

We consider a natural semi-online model for weighted paging, where at any time the algorithm is given predictions, possibly with errors, about the next arrival of each page. The model is inspired by Belady's classic optimal offline algorithm for unweighted paging, and extends the recently studied model for learning-augmented paging (Lykouris and Vassilvitskii, 2018) to the weighted setting. For the case of perfect predictions, we provide an $\ell$-competitive deterministic and an $O(\log \ell)$-competitive randomized algorithm, where $\ell$ is the number of distinct weight classes. Both these bounds are tight, and imply an $O(\log W)$- and $O(\log \log W)$-competitive ratio, respectively, when the page weights lie between $1$ and $W$. Previously, it was not known how to use these predictions in the weighted setting and only bounds of $k$ and $O(\log k)$ were known, where $k$ is the cache size. Our results also generalize to the interleaved paging setting and to the case of imperfect predictions, with the competitive ratios degrading smoothly from $O(\ell)$ and $O(\log \ell)$ to $O(k)$ and $O(\log k)$, respectively, as the prediction error increases. Our results are based on several insights on structural properties of Belady's algorithm and the sequence of page arrival predictions, and novel potential functions that incorporate these predictions. For the case of unweighted paging, the results imply a very simple potential function based proof of the optimality of Belady's algorithm, which may be of independent interest.
Modelling imperfect knowledge via location semantics for realistic privacy risks estimation in trajectory data
Venue: arXiv cs.CR 2021
Year: 2021

Mobility patterns of vehicles and people provide powerful data sources for location-based services such as fleet optimization and traffic flow analysis. Location-based service providers must balance the value they extract from trajectory data with protecting the privacy of the individuals behind those trajectories. Reaching this goal requires measuring accurately the values of utility and privacy. Current measurement approaches assume adversaries with perfect knowledge, thus overestimate the privacy risk. To address this issue we introduce a model of an adversary with imperfect knowledge about the target. The model is based on equivalence areas, spatio-temporal regions with a semantic meaning, e.g. the target's home, whose size and accuracy determine the skill of the adversary. We then derive the standard privacy metrics of k-anonymity, l-diversity and t-closeness from the definition of equivalence areas. These metrics can be computed on any dataset, irrespective of whether and what kind of anonymization has been applied to it. This work is of high relevance to all service providers acting as processors of trajectory data who want to manage privacy risks and optimize the privacy vs. utility trade-off of their services.
Sydr: Cutting Edge Dynamic Symbolic Execution
Venue: arXiv cs.CR 2021
Year: 2021

The security development lifecycle (SDL) is becoming an industry standard. Dynamic symbolic execution (DSE) has enormous amount of applications in computer security (fuzzing, vulnerability discovery, reverse-engineering, etc.). We propose several performance and accuracy improvements for dynamic symbolic execution. Skipping non-symbolic instructions allows to build a path predicate 1.2--3.5 times faster. Symbolic engine simplifies formulas during symbolic execution. Path predicate slicing eliminates irrelevant conjuncts from solver queries. We handle each jump table (switch statement) as multiple branches and describe the method for symbolic execution of multi-threaded programs. The proposed solutions were implemented in Sydr tool. Sydr performs inversion of branches in path predicate. Sydr combines DynamoRIO dynamic binary instrumentation tool with Triton symbolic engine. We evaluated Sydr features on 64-bit Linux executables.
Hidden chaos factors inducing random walks which reduce hospital operative efficiency
Venue: arXiv cs.IT 2021
Year: 2021

La Fuenfría Hospital (LFH) operative parameters such as: hospitalised patients; daily admissions and discharges were studies for the hospital as a whole, and per each Hospital's service unit (just called "service" here). Data were used to build operative parameter value series and their variation. Conventional statistical analyses and fractal dimension analyses were performed on the series. Statistical analyses indicated that the data did not follow a Gauss (i.e. "normal") distribution, thus nonparametric statistical analyses were chosen to describe data. The sequence of admitted daily admissions and patients staying on each service were found to be a kind of random series of a kind called random walks (Rw). Rw are sequences where what happens next ($ y_{t+Δt}$), depends on what happens now ($ y_{t}$) plus a random variable ($ ε$), $ y_{t+Δt}= y_t + ε$. Rw analysed with parametric or non parametric statistics may simulate cycles and drifts which resemble seasonal variations or fake trends. Globally, admitted patients Rws in LFFH, were found to be determined by the time elapsed between daily discharges and admissions. The factor determining LFH Rw were found to be the difference between daily admissions and discharges. The analysis suggests discharges are replaced by admissions with some random delay and that the random difference determinants LFH Rws. The daily difference between hospitalised patients follows the same statistical distribution as the daily difference between admissions and discharges. These suggest that if the daily difference between admissions and discharges is minimised, i.e., a patient is admitted without delay when another is discharged, the number of admitted panties would fluctuate less and the number of unoccupied beds would be reduced optimising the Hospital service.
MOFA: Modular Factorial Design for Hyperparameter Optimization
Venue: arXiv cs.LG 2021
Year: 2021

This paper presents a novel and lightweight hyperparameter optimization (HPO) method, MOdular FActorial Design (MOFA). MOFA pursues several rounds of HPO, where each round alternates between exploration of hyperparameter space by factorial design and exploitation of evaluation results by factorial analysis. Each round first explores the configuration space by constructing a low-discrepancy set of hyperparameters that cover this space well while de-correlating hyperparameters, and then exploits evaluation results through factorial analysis that determines which hyperparameters should be further explored and which should become fixed in the next round. We prove that the inference of MOFA achieves higher confidence than other sampling schemes. Each individual round is highly parallelizable and hence offers major improvements of efficiency compared to model-based methods. Empirical results show that MOFA achieves better effectiveness and efficiency compared with state-of-the-art methods.
Energy Aware Deep Reinforcement Learning Scheduling for Sensors Correlated in Time and Space
Venue: arXiv cs.LG 2021
Year: 2021

Millions of battery-powered sensors deployed for monitoring purposes in a multitude of scenarios, e.g., agriculture, smart cities, industry, etc., require energy-efficient solutions to prolong their lifetime. When these sensors observe a phenomenon distributed in space and evolving in time, it is expected that collected observations will be correlated in time and space. In this paper, we propose a Deep Reinforcement Learning (DRL) based scheduling mechanism capable of taking advantage of correlated information. We design our solution using the Deep Deterministic Policy Gradient (DDPG) algorithm. The proposed mechanism is capable of determining the frequency with which sensors should transmit their updates, to ensure accurate collection of observations, while simultaneously considering the energy available. To evaluate our scheduling mechanism, we use multiple datasets containing environmental observations obtained in multiple real deployments. The real observations enable us to model the environment with which the mechanism interacts as realistically as possible. We show that our solution can significantly extend the sensors' lifetime. We compare our mechanism to an idealized, all-knowing scheduler to demonstrate that its performance is near-optimal. Additionally, we highlight the unique feature of our design, energy-awareness, by displaying the impact of sensors' energy levels on the frequency of updates.
Hardware Implementation of Fano Decoder for Polarization-adjusted Convolutional (PAC) Codes
Venue: arXiv cs.IT 2021
Year: 2021

This brief proposes a hardware implementation architecture for Fano decoding of polarization-adjusted convolutional (PAC) codes. This architecture uses a novel branch metric unit specific to PAC codes. The proposed decoder is tested on FPGA, and its performance is evaluated on ASIC using TSMC 28 nm 0.72 V library. The decoder can be clocked at 500 MHz and reach an average information throughput of 38 Mb/s at 3.5 dB signal-to-noise ratio for a block length of 128 and a code rate of 1/2.
On the Request-Trip-Vehicle Assignment Problem
Venue: arXiv cs.DS 2021
Year: 2021

The request-trip-vehicle assignment problem is at the heart of a popular decomposition strategy for online vehicle routing. In this framework, assignments are done in batches in order to exploit any shareability among vehicles and incoming travel requests. We study a natural ILP formulation and its LP relaxation. Our main result is an LP-based randomized rounding algorithm that, whenever the instance is feasible, leverages mild assumptions to return an assignment whose: i) expected cost is at most that of an optimal solution, and ii) expected fraction of unassigned requests is at most $1/e$. If trip-vehicle assignment costs are $α$-approximate, we pay an additional factor of $α$ in the expected cost. We can relax the feasibility requirement by considering the penalty version of the problem, in which a penalty is paid for each unassigned request. We find that, whenever a request is repeatedly unassigned after a number of rounds, with high probability it is so in accordance with the sequence of LP solutions and not because of a rounding error. We additionally introduce a deterministic rounding heuristic inspired by our randomized technique. Our computational experiments show that our rounding algorithms achieve a performance similar to that of the ILP at a reduced computation time, far improving on our theoretical guarantee. The reason for this is that, although the assignment problem is hard in theory, the natural LP relaxation tends to be very tight in practice.
Enabling New Flexibility in the SUNDIALS Suite of Nonlinear and Differential/Algebraic Equation Solvers
Venue: arXiv cs.MS 2021
Year: 2021

In recent years, the SUite of Nonlinear and DIfferential/ALgebraic equation Solvers (SUNDIALS) has been redesigned to better enable the use of application-specific and third-party algebraic solvers and data structures. Throughout this work, we have adhered to specific guiding principles that minimized the impact to current users while providing maximum flexibility for later evolution of solvers and data structures. The redesign was done through the addition of new linear and nonlinear solvers classes, enhancements to the vector class, and the creation of modern Fortran interfaces. The vast majority of this work has been performed "behind-the-scenes," with minimal changes to the user interface and no reduction in solver capabilities or performance. These changes allow SUNDIALS users to more easily utilize external solver libraries and create highly customized solvers, enabling greater flexibility on extreme-scale, heterogeneous computational architectures.
Online Multi-Object Tracking with delta-GLMB Filter based on Occlusion and Identity Switch Handling
Venue: arXiv cs.CV 2021
Year: 2021

In this paper, we propose an online multi-object tracking (MOT) method in a delta Generalized Labeled Multi-Bernoulli (delta-GLMB) filter framework to address occlusion and miss-detection issues, reduce false alarms, and recover identity switch (ID switch). To handle occlusion and miss-detection issues, we propose a measurement-to-disappeared track association method based on one-step delta-GLMB filter, so it is possible to manage these difficulties by jointly processing occluded or miss-detected objects. This part of proposed method is based on a proposed similarity metric which is responsible for defining the weight of hypothesized reappeared tracks. We also extend the delta-GLMB filter to efficiently recover switched IDs using the cardinality density, size and color features of the hypothesized tracks. We also propose a novel birth model to achieve more effective clutter removal performance. In both occlusion/miss-detection handler and newly-birthed object detector sections of the proposed method, unassigned measurements play a significant role, since they are used as the candidates for reappeared or birth objects. In addition, we perform an ablation study which confirms the effectiveness of our contributions in comparison with the baseline method. We evaluate the proposed method on well-known and publicly available MOT15 and MOT17 test datasets which are focused on pedestrian tracking. Experimental results show that the proposed tracker performs better or at least at the same level of the state-of-the-art online and offline MOT methods. It effectively handles the occlusion and ID switch issues and reduces false alarms as well.
Interpretable and Transferable Models to Understand the Impact of Lockdown Measures on Local Air Quality
Venue: arXiv cs.LG 2021
Year: 2021

The COVID-19 related lockdown measures offer a unique opportunity to understand how changes in economic activity and traffic affect ambient air quality and how much pollution reduction potential can the society offer through digitalization and mobilitylimiting policies. In this work, we estimate pollution reduction over the lockdown period by using the measurements from ground air pollution monitoring stations, training a long-term prediction model and comparing its predictions to measured values over the lockdown month.We show that our models achieve state-of-the-art performance on the data from air pollution measurement stations in Switzerland and in China: evaluate up to -15.8% / +34.4% change in NO2 / PM10 in Zurich; -35.3 % / -3.5 % and -42.4 % / -34.7 % in NO2 / PM2.5 in Beijing and Wuhan respectively. Our reduction estimates are consistent with recent publications, yet in contrast to prior works, our method takes local weather into account. What can we learn from pollution emissions during lockdown? The lockdown period was too short to train meaningful models from scratch. To tackle this problem, we use transfer learning to newly fit only traffic-dependent variables. We show that the resulting models are accurate, suitable for an analysis of the post-lockdown period and capable of estimating the future air pollution reduction potential.
Unbalanced Incomplete Multi-view Clustering via the Scheme of View Evolution: Weak Views are Meat; Strong Views do Eat
Venue: arXiv cs.LG 2021
Year: 2021

Incomplete multi-view clustering is an important technique to deal with real-world incomplete multi-view data. Previous works assume that all views have the same incompleteness, i.e., balanced incompleteness. However, different views often have distinct incompleteness, i.e., unbalanced incompleteness, which results in strong views (low-incompleteness views) and weak views (high-incompleteness views). The unbalanced incompleteness prevents us from directly using the previous methods for clustering. In this paper, inspired by the effective biological evolution theory, we design the novel scheme of view evolution to cluster strong and weak views. Moreover, we propose an Unbalanced Incomplete Multi-view Clustering method (UIMC), which is the first effective method based on view evolution for unbalanced incomplete multi-view clustering. Compared with previous methods, UIMC has two unique advantages: 1) it proposes weighted multi-view subspace clustering to integrate these unbalanced incomplete views, which effectively solves the unbalanced incomplete multi-view problem; 2) it designs the low-rank and robust representation to recover the data, which diminishes the impact of the incompleteness and noises. Extensive experimental results demonstrate that UIMC improves the clustering performance by up to 40% on three evaluation metrics over other state-of-the-art methods.
Reconfigurable Intelligent Surface Enabled Federated Learning: A Unified Communication-Learning Design Approach
Venue: arXiv cs.IT 2021
Year: 2021

To exploit massive amounts of data generated at mobile edge networks, federated learning (FL) has been proposed as an attractive substitute for centralized machine learning (ML). By collaboratively training a shared learning model at edge devices, FL avoids direct data transmission and thus overcomes high communication latency and privacy issues as compared to centralized ML. To improve the communication efficiency in FL model aggregation, over-the-air computation has been introduced to support a large number of simultaneous local model uploading by exploiting the inherent superposition property of wireless channels. However, due to the heterogeneity of communication capacities among edge devices, over-the-air FL suffers from the straggler issue in which the device with the weakest channel acts as a bottleneck of the model aggregation performance. This issue can be alleviated by device selection to some extent, but the latter still suffers from a tradeoff between data exploitation and model communication. In this paper, we leverage the reconfigurable intelligent surface (RIS) technology to relieve the straggler issue in over-the-air FL. Specifically, we develop a learning analysis framework to quantitatively characterize the impact of device selection and model aggregation error on the convergence of over-the-air FL. Then, we formulate a unified communication-learning optimization problem to jointly optimize device selection, over-the-air transceiver design, and RIS configuration. Numerical experiments show that the proposed design achieves substantial learning accuracy improvement compared with the state-of-the-art approaches, especially when channel conditions vary dramatically across edge devices.
Policy Gradient Methods for the Noisy Linear Quadratic Regulator over a Finite Horizon
Venue: arXiv cs.LG 2021
Year: 2021

We explore reinforcement learning methods for finding the optimal policy in the linear quadratic regulator (LQR) problem. In particular, we consider the convergence of policy gradient methods in the setting of known and unknown parameters. We are able to produce a global linear convergence guarantee for this approach in the setting of finite time horizon and stochastic state dynamics under weak assumptions. The convergence of a projected policy gradient method is also established in order to handle problems with constraints. We illustrate the performance of the algorithm with two examples. The first example is the optimal liquidation of a holding in an asset. We show results for the case where we assume a model for the underlying dynamics and where we apply the method to the data directly. The empirical evidence suggests that the policy gradient method can learn the global optimal solution for a larger class of stochastic systems containing the LQR framework and that it is more robust with respect to model mis-specification when compared to a model-based approach. The second example is an LQR system in a higher dimensional setting with synthetic data.
Cost-effective Variational Active Entity Resolution
Venue: arXiv cs.LG 2021
Year: 2021

Accurately identifying different representations of the same real-world entity is an integral part of data cleaning and many methods have been proposed to accomplish it. The challenges of this entity resolution task that demand so much research attention are often rooted in the task-specificity and user-dependence of the process. Adopting deep learning techniques has the potential to lessen these challenges. In this paper, we set out to devise an entity resolution method that builds on the robustness conferred by deep autoencoders to reduce human-involvement costs. Specifically, we reduce the cost of training deep entity resolution models by performing unsupervised representation learning. This unveils a transferability property of the resulting model that can further reduce the cost of applying the approach to new datasets by means of transfer learning. Finally, we reduce the cost of labelling training data through an active learning approach that builds on the properties conferred by the use of deep autoencoders. Empirical evaluation confirms the accomplishment of our cost-reduction desideratum while achieving comparable effectiveness with state-of-the-art alternatives.
Online Descriptor Enhancement via Self-Labelling Triplets for Visual Data Association
Venue: arXiv cs.CV 2021
Year: 2021

Object-level data association is central to robotic applications such as tracking-by-detection and object-level simultaneous localization and mapping. While current learned visual data association methods outperform hand-crafted algorithms, many rely on large collections of domain-specific training examples that can be difficult to obtain without prior knowledge. Additionally, such methods often remain fixed during inference-time and do not harness observed information to better their performance. We propose a self-supervised method for incrementally refining visual descriptors to improve performance in the task of object-level visual data association. Our method optimizes deep descriptor generators online, by continuously training a widely available image classification network pre-trained with domain-independent data. We show that earlier layers in the network outperform later-stage layers for the data association task while also allowing for a 94% reduction in the number of parameters, enabling the online optimization. We show that self-labelling challenging triplets--choosing positive examples separated by large temporal distances and negative examples close in the descriptor space--improves the quality of the learned descriptors for the multi-object tracking task. Finally, we demonstrate that our approach surpasses other visual data-association methods applied to a tracking-by-detection task, and show that it provides better performance-gains when compared to other methods that attempt to adapt to observed information.
Zero Queueing for Multi-Server Jobs
Venue: arXiv cs.PF 2021
Year: 2021

Cloud computing today is dominated by multi-server jobs. These are jobs that request multiple servers simultaneously and hold onto all of these servers for the duration of the job. Multi-server jobs add a lot of complexity to the traditional one-job-per-server model: an arrival might not "fit" into the available servers and might have to queue, blocking later arrivals and leaving servers idle. From a queueing perspective, almost nothing is understood about multi-server job queueing systems; even understanding the exact stability region is a very hard problem. In this paper, we investigate a multi-server job queueing model under scaling regimes where the number of servers in the system grows. Specifically, we consider a system with multiple classes of jobs, where jobs from different classes can request different numbers of servers and have different service time distributions, and jobs are served in first-come-first-served order. The multi-server job model opens up new scaling regimes where both the number of servers that a job needs and the system load scale with the total number of servers. Within these scaling regimes, we derive the first results on stability, queueing probability, and the transient analysis of the number of jobs in the system for each class. In particular we derive sufficient conditions for zero queueing. Our analysis introduces a novel way of extracting information from the Lyapunov drift, which can be applicable to a broader scope of problems in queueing systems.