OpenRaiser/Intern-Atlas huggingface dataset:
Sample Complexity of Adversarially Robust Linear Classification on Separated Data
Venue: arXiv cs.LG 2023
Year: 2023

We consider the sample complexity of learning with adversarial robustness. Most prior theoretical results for this problem have considered a setting where different classes in the data are close together or overlapping. Motivated by some real applications, we consider, in contrast, the well-separated case where there exists a classifier with perfect accuracy and robustness, and show that the sample complexity narrates an entirely different story. Specifically, for linear classifiers, we show a large class of well-separated distributions where the expected robust loss of any algorithm is at least $Ω(\frac{d}{n})$, whereas the max margin algorithm has expected standard loss $O(\frac{1}{n})$. This shows a gap in the standard and robust losses that cannot be obtained via prior techniques. Additionally, we present an algorithm that, given an instance where the robustness radius is much smaller than the gap between the classes, gives a solution with expected robust loss is $O(\frac{1}{n})$. This shows that for very well-separated data, convergence rates of $O(\frac{1}{n})$ are achievable, which is not the case otherwise. Our results apply to robustness measured in any $\ell_p$ norm with $p > 1$ (including $p = \infty$).
Weighted slice rank and a minimax correspondence to Strassen's spectra
Venue: arXiv cs.CC 2023
Year: 2023

Structural and computational understanding of tensors is the driving force behind faster matrix multiplication algorithms, the unraveling of quantum entanglement, and the breakthrough on the cap set problem. Strassen's asymptotic spectra program (FOCS 1986) characterizes optimal matrix multiplication algorithms through monotone functionals. Our work advances and makes novel connections among two recent developments in the study of tensors, namely - the slice rank of tensors, a notion of rank for tensors that emerged from the resolution of the cap set problem (Ann. of Math. 2017), - and the quantum functionals of tensors (STOC 2018), monotone functionals defined as optimizations over moment polytopes. More precisely, we introduce an extension of slice rank that we call weighted slice rank and we develop a minimax correspondence between the asymptotic weighted slice rank and the quantum functionals. Weighted slice rank encapsulates different notions of bipartiteness of quantum entanglement. The correspondence allows us to give a rank-type characterization of the quantum functionals. Moreover, whereas the original definition of the quantum functionals only works over the complex numbers, this new characterization can be extended to all fields. Thereby, in addition to gaining deeper understanding of Strassen's theory for the complex numbers, we obtain a proposal for quantum functionals over other fields. The finite field case is crucial for combinatorial and algorithmic problems where the field can be optimized over.
New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling
Venue: arXiv cs.DS 2023
Year: 2023

Interval scheduling is a basic problem in the theory of algorithms and a classical task in combinatorial optimization. We develop a set of techniques for partitioning and grouping jobs based on their starting and ending times, that enable us to view an instance of interval scheduling on many jobs as a union of multiple interval scheduling instances, each containing only a few jobs. Instantiating these techniques in dynamic and local settings of computation leads to several new results. For $(1+\varepsilon)$-approximation of job scheduling of $n$ jobs on a single machine, we develop a fully dynamic algorithm with $O(\frac{\log{n}}{\varepsilon})$ update and $O(\log{n})$ query worst-case time. Further, we design a local computation algorithm that uses only $O(\frac{\log{N}}{\varepsilon})$ queries when all jobs are length at least $1$ and have starting/ending times within $[0,N]$. Our techniques are also applicable in a setting where jobs have rewards/weights. For this case we design a fully dynamic deterministic algorithm whose worst-case update and query time are $\operatorname{poly}(\log n,\frac{1}{\varepsilon})$. Equivalently, this is the first algorithm that maintains a $(1+\varepsilon)$-approximation of the maximum independent set of a collection of weighted intervals in $\operatorname{poly}(\log n,\frac{1}{\varepsilon})$ time updates/queries. This is an exponential improvement in $1/\varepsilon$ over the running time of a randomized algorithm of Henzinger, Neumann, and Wiese ~[SoCG, 2020], while also removing all dependence on the values of the jobs' starting/ending times and rewards, as well as removing the need for any randomness. We also extend our approaches for interval scheduling on a single machine to examine the setting with $M$ machines.
Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation
Venue: arXiv cs.LG 2023
Year: 2023

Combinatorial optimization is one of the fundamental research fields that has been extensively studied in theoretical computer science and operations research. When developing an algorithm for combinatorial optimization, it is commonly assumed that parameters such as edge weights are exactly known as inputs. However, this assumption may not be fulfilled since input parameters are often uncertain or initially unknown in many applications such as recommender systems, crowdsourcing, communication networks, and online advertisement. To resolve such uncertainty, the problem of combinatorial pure exploration of multi-armed bandits (CPE) and its variants have recieved increasing attention. Earlier work on CPE has studied the semi-bandit feedback or assumed that the outcome from each individual edge is always accessible at all rounds. However, due to practical constraints such as a budget ceiling or privacy concern, such strong feedback is not always available in recent applications. In this article, we review recently proposed techniques for combinatorial pure exploration problems with limited feedback.
5G MEC Computation Handoff for Mobile Augmented Reality
Venue: arXiv cs.NI 2023
Year: 2023

The combination of 5G and Multi-access Edge Computing (MEC) can significantly reduce application delay by lowering transmission delay and bringing computational capabilities closer to the end user. Therefore, 5G MEC could enable excellent user experience in applications like Mobile Augmented Reality (MAR), which are computation-intensive, and delay and jitter-sensitive. However, existing 5G handoff algorithms often do not consider the computational load of MEC servers, are too complex for real-time execution, or do not integrate easily with the standard protocol stack. Thus they can impair the performance of 5G MEC. To address this gap, we propose Comp-HO, a handoff algorithm that finds a local solution to the joint problem of optimizing signal strength and computational load. Additionally, Comp-HO can easily be integrated into current LTE and 5G base stations thanks to its simplicity and standard-friendly deployability. Specifically, we evaluate Comp-HO through a custom NS-3 simulator which we calibrate via MAR prototype measurements from a real-world 5G testbed. We simulate both Comp-HO and several classic handoff algorithms. The results show that, even without a global optimum, the proposed algorithm still significantly reduces the number of large delays, caused by congestion at MECs, at the expense of a small increase in transmission delay.
Split block Bloom filters
Venue: arXiv cs.DS 2023
Year: 2023

This short note describes a Bloom filter variant that takes advantage of modern SIMD instructions to increase speed by 30%-450%. This filter, the split block Bloom filter, is used by StarRocks, Apache Impala, Apache Kudu, Apache Parquet, Apache Arrow, Apache Drill, and Alibaba Cloud's Hologres.
Answer Counting under Guarded TGDs
Venue: arXiv cs.DB 2023
Year: 2023

We study the complexity of answer counting for ontology-mediated queries and for querying under constraints, considering conjunctive queries and unions thereof (UCQs) as the query language and guarded TGDs as the ontology and constraint language, respectively. Our main result is a classification according to whether answer counting is fixed-parameter tractable (FPT), W[1]-equivalent, #W[1]-equivalent, #W[2]-hard, or #A[2]-equivalent, lifting a recent classification for UCQs without ontologies and constraints due to Dell et al. The classification pertains to various structural measures, namely treewidth, contract treewidth, starsize, and linked matching number. Our results rest on the assumption that the arity of relation symbols is bounded by a constant and, in the case of ontology-mediated querying, that all symbols from the ontology and query can occur in the data (so-called full data schema). We also study the meta-problems for the mentioned structural measures, that is, to decide whether a given ontology-mediated query or constraint-query specification is equivalent to one for which the structural measure is bounded.
Outage Probability Analysis of Uplink Cell-Free Massive MIMO Network with and without Pilot Contamination
Venue: arXiv cs.IT 2023
Year: 2023

This paper derives approximate outage probability (OP) expressions for uplink cell-free massive multiple-input-multiple-output (CF-mMIMO) systems with and without pilot contamination. The system's access points (APs) are considered to have imperfect channel state information (CSI). The signal-to-interference-plus-noise ratio (SINR) of the CF-mMIMO system is approximated via a Log-normal distribution using a two-step moment matching method. OP and ergodic rate expressions are derived with the help of the approximated Log-normal distribution. For the no-pilot contamination scenario, an exact expression is first derived using conditional expectations in terms of a multi-fold integral. Then, a novel dimension reduction method is used to approximate it by the sum of single-variable integrations. Both the approximations derived for the CF-mMIMO systems are also useful for single-cell collocated massive MIMO (mMIMO) systems and lead to closed-form expression. The derived expressions closely match the simulated numerical values for OP and ergodic rate.
Breaking the Deadly Triad with a Target Network
Venue: arXiv cs.LG 2023
Year: 2023

The deadly triad refers to the instability of a reinforcement learning algorithm when it employs off-policy learning, function approximation, and bootstrapping simultaneously. In this paper, we investigate the target network as a tool for breaking the deadly triad, providing theoretical support for the conventional wisdom that a target network stabilizes training. We first propose and analyze a novel target network update rule which augments the commonly used Polyak-averaging style update with two projections. We then apply the target network and ridge regularization in several divergent algorithms and show their convergence to regularized TD fixed points. Those algorithms are off-policy with linear function approximation and bootstrapping, spanning both policy evaluation and control, as well as both discounted and average-reward settings. In particular, we provide the first convergent linear $Q$-learning algorithms under nonrestrictive and changing behavior policies without bi-level optimization.
A Survey of Requirements for COVID-19 Mitigation Strategies. Part II: Elicitation of Requirements
Venue: arXiv cs.CY 2023
Year: 2023

The COVID-19 pandemic has influenced virtually all aspects of our lives. Across the world, countries have applied various mitigation strategies, based on social, political, and technological instruments. We postulate that multi-agent systems can provide a common platform to study (and balance) their essential properties. We also show how to obtain a comprehensive list of the properties by "distilling" them from media snippets. Finally, we present a preliminary take on their formal specification, using ideas from multi-agent logics.
Calibrating and Improving Graph Contrastive Learning
Venue: arXiv cs.LG 2023
Year: 2023

Graph contrastive learning algorithms have demonstrated remarkable success in various applications such as node classification, link prediction, and graph clustering. However, in unsupervised graph contrastive learning, some contrastive pairs may contradict the truths in downstream tasks and thus the decrease of losses on these pairs undesirably harms the performance in the downstream tasks. To assess the discrepancy between the prediction and the ground-truth in the downstream tasks for these contrastive pairs, we adapt the expected calibration error (ECE) to graph contrastive learning. The analysis of ECE motivates us to propose a novel regularization method, Contrast-Reg, to ensure that decreasing the contrastive loss leads to better performance in the downstream tasks. As a plug-in regularizer, Contrast-Reg effectively improves the performance of existing graph contrastive learning algorithms. We provide both theoretical and empirical results to demonstrate the effectiveness of Contrast-Reg in enhancing the generalizability of the Graph Neural Network(GNN) model and improving the performance of graph contrastive algorithms with different similarity definitions and encoder backbones across various downstream tasks.
Numerical Weather Forecasting using Convolutional-LSTM with Attention and Context Matcher Mechanisms
Venue: arXiv cs.LG 2023
Year: 2023

Numerical weather forecasting using high-resolution physical models often requires extensive computational resources on supercomputers, which diminishes their wide usage in most real-life applications. As a remedy, applying deep learning methods has revealed innovative solutions within this field. To this end, we introduce a novel deep learning architecture for forecasting high-resolution spatio-temporal weather data. Our approach extends the conventional encoder-decoder structure by integrating Convolutional Long-short Term Memory and Convolutional Neural Networks. In addition, we incorporate attention and context matcher mechanisms into the model architecture. Our Weather Model achieves significant performance improvements compared to baseline deep learning models, including ConvLSTM, TrajGRU, and U-Net. Our experimental evaluation involves high-scale, real-world benchmark numerical weather datasets, namely the ERA5 hourly dataset on pressure levels and WeatherBench. Our results demonstrate substantial improvements in identifying spatial and temporal correlations with attention matrices focusing on distinct parts of the input series to model atmospheric circulations. We also compare our model with high-resolution physical models using the benchmark metrics and show that our Weather Model is accurate and easy to interpret.
Stochastic Online Convex Optimization. Application to probabilistic time series forecasting
Venue: arXiv cs.LG 2023
Year: 2023

We introduce a general framework of stochastic online convex optimization to obtain fast-rate stochastic regret bounds. We prove that algorithms such as online newton steps and a scale-free 10 version of Bernstein online aggregation achieve best-known rates in unbounded stochastic settings. We apply our approach to calibrate parametric probabilistic forecasters of non-stationary sub-gaussian time series. Our fast-rate stochastic regret bounds are any-time valid. Our proofs combine self-bounded and Poissonnian inequalities for martingales and sub-gaussian random variables, respectively, under a stochastic exp-concavity assumption.
On weakly and strongly popular rankings
Venue: arXiv cs.GT 2023
Year: 2023

Van Zuylen et al. [35] introduced the notion of a popular ranking in a voting context, where each voter submits a strict ranking of all candidates. A popular ranking $π$ of the candidates is at least as good as any other ranking $σ$ in the following sense: if we compare $π$ to $σ$, at least half of all voters will always weakly prefer $π$. Whether a voter prefers one ranking to another is calculated based on the Kendall distance. A more traditional definition of popularity -- as applied to popular matchings, a well-established topic in computational social choice -- is stricter, because it requires at least half of the voters who are not indifferent between $π$ and $σ$ to prefer $π$. In this paper, we derive structural and algorithmic results in both settings, also improving upon the results in [35]. We also point out connections to the famous open problem of finding a Kemeny consensus with three voters.
Broadcast Rate Requires Nonlinear Coding in a Unicast Index Coding Instance of Size 36
Venue: arXiv cs.IT 2023
Year: 2023

Insufficiency of linear coding for the network coding problem was first proved by providing an instance which is solvable only by nonlinear network coding (Dougherty et al., 2005).Based on the work of Effros, et al., 2015, this specific network coding instance can be modeled as a groupcast index coding (GIC)instance with 74 messages and 80 users (where a message can be requested by multiple users). This proves the insufficiency of linear coding for the GIC problem. Using the systematic approach proposed by Maleki et al., 2014, the aforementioned GIC instance can be cast into a unicast index coding (UIC) instance with more than 200 users, each wanting a unique message. This confirms the necessity of nonlinear coding for the UIC problem, but only for achieving the entire capacity region. Nevertheless, the question of whether nonlinear coding is required to achieve the symmetric capacity (broadcast rate) of the UIC problem remained open. In this paper, we settle this question and prove the insufficiency of linear coding, by directly building a UIC instance with only 36users for which there exists a nonlinear index code outperforming the optimal linear code in terms of the broadcast rate.
Optimal Intervention in Economic Networks using Influence Maximization Methods
Venue: arXiv cs.GT 2023
Year: 2023

We consider optimal intervention in the Elliott-Golub-Jackson network model \cite{jackson14} and we show that it can be transformed into an influence maximization-like form, interpreted as the reverse of a default cascade. Our analysis of the optimal intervention problem extends well-established targeting results to the economic network setting, which requires additional theoretical steps. We prove several results about optimal intervention: it is NP-hard and cannot be approximated to a constant factor in polynomial time. In turn, we show that randomizing failure thresholds leads to a version of the problem which is monotone submodular, for which existing powerful approximations in polynomial time can be applied. In addition to optimal intervention, we also show practical consequences of our analysis to other economic network problems: (1) it is computationally hard to calculate expected values in the economic network, and (2) influence maximization algorithms can enable efficient importance sampling and stress testing of large failure scenarios. We illustrate our results on a network of firms connected through input-output linkages inferred from the World Input Output Database.
Cutoff stability under distributional constraints with an application to summer internship matching
Venue: arXiv cs.GT 2023
Year: 2023

We introduce a new two-sided stable matching problem that describes the summer internship matching practice of an Australian university. The model is a case between two models of Kamada and Kojima on matchings with distributional constraints. We study three solution concepts, the strong and weak stability concepts proposed by Kamada and Kojima, and a new one in between the two, called cutoff stability. Kamada and Kojima showed that a strongly stable matching may not exist in their most restricted model with disjoint regional quotas. Our first result is that checking its existence is NP-hard. We then show that a cutoff stable matching exists not just for the summer internship problem but also for the general matching model with arbitrary heredity constraints. We present an algorithm to compute a cutoff stable matching and show that it runs in polynomial time in our special case of summer internship model. However, we also show that finding a maximum size cutoff stable matching is NP-hard, but we provide a Mixed Integer Linear Program formulation for this optimisation problem.
Improving state estimation through projection post-processing for activity recognition with application to football
Venue: arXiv cs.CV 2023
Year: 2023

The past decade has seen an increased interest in human activity recognition based on sensor data. Most often, the sensor data come unannotated, creating the need for fast labelling methods. For assessing the quality of the labelling, an appropriate performance measure has to be chosen. Our main contribution is a novel post-processing method for activity recognition. It improves the accuracy of the classification methods by correcting for unrealistic short activities in the estimate. We also propose a new performance measure, the Locally Time-Shifted Measure (LTS measure), which addresses uncertainty in the times of state changes. The effectiveness of the post-processing method is evaluated, using the novel LTS measure, on the basis of a simulated dataset and a real application on sensor data from football. The simulation study is also used to discuss the choice of the parameters of the post-processing method and the LTS measure.
An Analytic Layer-wise Deep Learning Framework with Applications to Robotics
Venue: arXiv cs.RO 2023
Year: 2023

Deep learning (DL) has achieved great success in many applications, but it has been less well analyzed from the theoretical perspective. The unexplainable success of black-box DL models has raised questions among scientists and promoted the emergence of the field of explainable artificial intelligence (XAI). In robotics, it is particularly important to deploy DL algorithms in a predictable and stable manner as robots are active agents that need to interact safely with the physical world. This paper presents an analytic deep learning framework for fully connected neural networks, which can be applied for both regression problems and classification problems. Examples for regression and classification problems include online robot control and robot vision. We present two layer-wise learning algorithms such that the convergence of the learning systems can be analyzed. Firstly, an inverse layer-wise learning algorithm for multilayer networks with convergence analysis for each layer is presented to understand the problems of layer-wise deep learning. Secondly, a forward progressive learning algorithm where the deep networks are built progressively by using single hidden layer networks is developed to achieve better accuracy. It is shown that the progressive learning method can be used for fine-tuning of weights from convergence point of view. The effectiveness of the proposed framework is illustrated based on classical benchmark recognition tasks using the MNIST and CIFAR-10 datasets and the results show a good balance between performance and explainability. The proposed method is subsequently applied for online learning of robot kinematics and experimental results on kinematic control of UR5e robot with unknown model are presented.