OpenRaiser/Intern-Atlas huggingface dataset:
Agafonov's Proof of Agafonov's Theorem: A Modern Account and New Insights
Venue: arXiv cs.DM 2022
Year: 2022

We give a modern account of Agafonov's original proof of his eponymous theorem. The original proof was only reported in Russian in a journal not widely available, and the work most commonly cited in western literature is instead the English translation of a summary version containing no proofs, and the main proof relied heavily on material well-known in Russian mathematical circles of the day, which perhaps obscures the main thrust of argumentation for modern readers.Our present account recasts Aganofov's arguments using more basic building blocks than in the original proof, and contains some further embellishments to Agafonov's original arguments, made in the interest of clarity. We posit that the modern account provides new insight to the underlying phenomena of the theorem.We also provides some historical context to Agafonov's work, including a short description of some of the ideas that led to Agafonov's own proof, especially emphasizing the important work of Postnikova.
A Study of Learning Search Approximation in Mixed Integer Branch and Bound: Node Selection in SCIP
Venue: arXiv cs.NE 2022
Year: 2022

In line with the growing trend of using machine learning to help solve combinatorial optimisation problems, one promising idea is to improve node selection within a mixed integer programming (MIP) branch-and-bound tree by using a learned policy. Previous work using imitation learning indicates the feasibility of acquiring a node selection policy, by learning an adaptive node searching order. In contrast, our imitation learning policy is focused solely on learning which of a node's children to select. We present an offline method to learn such a policy in two settings: one that comprises a heuristic by committing to pruning of nodes; one that is exact and backtracks from a leaf to guarantee finding the optimal integer solution. The former setting corresponds to a child selector during plunging, while the latter is akin to a diving heuristic. We apply the policy within the popular open-source solver SCIP, in both heuristic and exact settings. Empirical results on five MIP datasets indicate that our node selection policy leads to solutions significantly more quickly than the state-of-the-art precedent in the literature. While we do not beat the highly-optimised SCIP state-of-practice baseline node selector in terms of solving time on exact solutions, our heuristic policies have a consistently better optimality gap than all baselines, if the accuracy of the predictive model is sufficient. Further, the results also indicate that, when a time limit is applied, our heuristic method finds better solutions than all baselines in the majority of problems tested. We explain the results by showing that the learned policies have imitated the SCIP baseline, but without the latter's early plunge abort. Our recommendation is that, despite the clear improvements over the literature, this kind of MIP child selector is better seen in a broader approach using learning in MIP branch-and-bound tree decisions.
Open Data Quality Evaluation: A Comparative Analysis of Open Data in Latvia
Venue: arXiv cs.DB 2022
Year: 2022

Nowadays open data is entering the mainstream - it is free available for every stakeholder and is often used in business decision-making. It is important to be sure data is trustable and error-free as its quality problems can lead to huge losses. The research discusses how (open) data quality could be assessed. It also covers main points which should be considered developing a data quality management solution. One specific approach is applied to several Latvian open data sets. The research provides a step-by-step open data sets analysis guide and summarizes its results. It is also shown there could exist differences in data quality depending on data supplier (centralized and decentralized data releases) and, unfortunately, trustable data supplier cannot guarantee data quality problems absence. There are also underlined common data quality problems detected not only in Latvian open data but also in open data of 3 European countries.
A tight uniform continuity bound for the Arimoto-Rényi conditional entropy and its extension to classical-quantum states
Venue: arXiv cs.IT 2022
Year: 2022

We prove a tight uniform continuity bound for Arimoto's version of the conditional $α$-Rényi entropy, for the range $α\in [0, 1)$. This definition of the conditional Rényi entropy is the most natural one among the multiple forms which exist in the literature, since it satisfies two desirable properties of a conditional entropy, namely, the fact that conditioning reduces entropy, and that the associated reduction in uncertainty cannot exceed the information gained by conditioning. Furthermore, it has found interesting applications in various information theoretic tasks such as guessing with side information and sequential decoding. This conditional entropy reduces to the conditional Shannon entropy in the limit $α\to 1$, and this in turn allows us to recover the recently obtained tight uniform continuity bound for the latter from our result. Finally, we apply our result to obtain a tight uniform continuity bound for the conditional $α$-Rényi entropy of a classical-quantum state, for $α$ in the same range as above. This again yields the corresponding known bound for the conditional entropy of the state in the limit $α\to 1$.
A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces
Venue: arXiv cs.LG 2022
Year: 2022

In this work, we propose KeRNS: an algorithm for episodic reinforcement learning in non-stationary Markov Decision Processes (MDPs) whose state-action set is endowed with a metric. Using a non-parametric model of the MDP built with time-dependent kernels, we prove a regret bound that scales with the covering dimension of the state-action space and the total variation of the MDP with time, which quantifies its level of non-stationarity. Our method generalizes previous approaches based on sliding windows and exponential discounting used to handle changing environments. We further propose a practical implementation of KeRNS, we analyze its regret and validate it experimentally.
Vector Balancing in Lebesgue Spaces
Venue: arXiv cs.DS 2022
Year: 2022

A tantalizing conjecture in discrete mathematics is the one of Komlós, suggesting that for any vectors $\mathbf{a}_1,\ldots,\mathbf{a}_n \in B_2^m$ there exist signs $x_1, \dots, x_n \in \{ -1,1\}$ so that $\|\sum_{i=1}^n x_i\mathbf{a}_i\|_\infty \le O(1)$. It is a natural extension to ask what $\ell_q$-norm bound to expect for $\mathbf{a}_1,\ldots,\mathbf{a}_n \in B_p^m$. We prove that, for $2 \le p \le q \le \infty$, such vectors admit fractional colorings $x_1, \dots, x_n \in [-1,1]$ with a linear number of $\pm 1$ coordinates so that $\|\sum_{i=1}^n x_i\mathbf{a}_i\|_q \leq O(\sqrt{\min(p,\log(2m/n))}) \cdot n^{1/2-1/p+ 1/q}$, and that one can obtain a full coloring at the expense of another factor of $\frac{1}{1/2 - 1/p + 1/q}$. In particular, for $p \in (2,3]$ we can indeed find signs $\mathbf{x} \in \{ -1,1\}^n$ with $\|\sum_{i=1}^n x_i\mathbf{a}_i\|_\infty \le O(n^{1/2-1/p} \cdot \frac{1}{p-2})$. Our result generalizes Spencer's theorem, for which $p = q = \infty$, and is tight for $m = n$. Additionally, we prove that for any fixed constant $δ>0$, in a centrally symmetric body $K \subseteq \mathbb{R}^n$ with measure at least $e^{-δn}$ one can find such a fractional coloring in polynomial time. Previously this was known only for a small enough constant -- indeed in this regime classical nonconstructive arguments do not apply and partial colorings of the form $\mathbf{x} \in \{ -1,0,1\}^n$ do not necessarily exist.
From Symmetry to Geometry: Tractable Nonconvex Problems
Venue: arXiv cs.LG 2022
Year: 2022

As science and engineering have become increasingly data-driven, the role of optimization has expanded to touch almost every stage of the data analysis pipeline, from signal and data acquisition to modeling and prediction. The optimization problems encountered in practice are often nonconvex. While challenges vary from problem to problem, one common source of nonconvexity is nonlinearity in the data or measurement model. Nonlinear models often exhibit symmetries, creating complicated, nonconvex objective landscapes, with multiple equivalent solutions. Nevertheless, simple methods (e.g., gradient descent) often perform surprisingly well in practice. The goal of this survey is to highlight a class of tractable nonconvex problems, which can be understood through the lens of symmetries. These problems exhibit a characteristic geometric structure: local minimizers are symmetric copies of a single "ground truth" solution, while other critical points occur at balanced superpositions of symmetric copies of the ground truth, and exhibit negative curvature in directions that break the symmetry. This structure enables efficient methods to obtain global minimizers. We discuss examples of this phenomenon arising from a wide range of problems in imaging, signal processing, and data analysis. We highlight the key role of symmetry in shaping the objective landscape and discuss the different roles of rotational and discrete symmetries. This area is rich with observed phenomena and open problems; we close by highlighting directions for future research.
Hands-on Bayesian Neural Networks -- a Tutorial for Deep Learning Users
Venue: arXiv cs.LG 2022
Year: 2022

Modern deep learning methods constitute incredibly powerful tools to tackle a myriad of challenging problems. However, since deep learning methods operate as black boxes, the uncertainty associated with their predictions is often challenging to quantify. Bayesian statistics offer a formalism to understand and quantify the uncertainty associated with deep neural network predictions. This tutorial provides an overview of the relevant literature and a complete toolset to design, implement, train, use and evaluate Bayesian Neural Networks, i.e. Stochastic Artificial Neural Networks trained using Bayesian methods.
Bitcoin Transaction Forecasting with Deep Network Representation Learning
Venue: arXiv cs.SI 2022
Year: 2022

Bitcoin and its decentralized computing paradigm for digital currency trading are one of the most disruptive technology in the 21st century. This paper presents a novel approach to developing a Bitcoin transaction forecast model, DLForecast, by leveraging deep neural networks for learning Bitcoin transaction network representations. DLForecast makes three original contributions. First, we explore three interesting properties between Bitcoin transaction accounts: topological connectivity pattern of Bitcoin accounts, transaction amount pattern, and transaction dynamics. Second, we construct a time-decaying reachability graph and a time-decaying transaction pattern graph, aiming at capturing different types of spatial-temporal Bitcoin transaction patterns. Third, we employ node embedding on both graphs and develop a Bitcoin transaction forecasting system between user accounts based on historical transactions with built-in time-decaying factor. To maintain an effective transaction forecasting performance, we leverage the multiplicative model update (MMU) ensemble to combine prediction models built on different transaction features extracted from each corresponding Bitcoin transaction graph. Evaluated on real-world Bitcoin transaction data, we show that our spatial-temporal forecasting model is efficient with fast runtime and effective with forecasting accuracy over 60\% and improves the prediction performance by 50\% when compared to forecasting model built on the static graph baseline.
Maximizing coverage while ensuring fairness: a tale of conflicting objective
Venue: arXiv cs.CC 2022
Year: 2022

Ensuring fairness in computational problems has emerged as a $key$ topic during recent years, buoyed by considerations for equitable resource distributions and social justice. It $is$ possible to incorporate fairness in computational problems from several perspectives, such as using optimization, game-theoretic or machine learning frameworks. In this paper we address the problem of incorporation of fairness from a $combinatorial$ $optimization$ perspective. We formulate a combinatorial optimization framework, suitable for analysis by researchers in approximation algorithms and related areas, that incorporates fairness in maximum coverage problems as an interplay between $two$ conflicting objectives. Fairness is imposed in coverage by using coloring constraints that $minimizes$ the discrepancies between number of elements of different colors covered by selected sets; this is in contrast to the usual discrepancy minimization problems studied extensively in the literature where (usually two) colors are $not$ given $a$ $priori$ but need to be selected to minimize the maximum color discrepancy of $each$ individual set. Our main results are a set of randomized and deterministic approximation algorithms that attempts to $simultaneously$ approximate both fairness and coverage in this framework.
A Type Theory for Strictly Unital $\infty$-Categories
Venue: arXiv cs.LO 2022
Year: 2022

We use type-theoretic techniques to present an algebraic theory of $\infty$-categories with strict units. Starting with a known type-theoretic presentation of fully weak $\infty$-categories, in which terms denote valid operations, we extend the theory with a non-trivial definitional equality. This forces some operations to coincide strictly in any model, yielding the strict unit behaviour. We make a detailed investigation of the meta-theoretic properties of this theory. We give a reduction relation that generates definitional equality, and prove that it is confluent and terminating, thus yielding the first decision procedure for equality in a strictly-unital setting. Moreover, we show that our definitional equality relation identifies all terms in a disc context, providing a point comparison with a previously proposed definition of strictly unital $\infty$-category. We also prove a conservativity result, showing that every operation of the strictly unital theory indeed arises from a valid operation in the fully weak theory. From this, we infer that strict unitality is a property of an $\infty$-category rather than additional structure.
Technologies for Trustworthy Machine Learning: A Survey in a Socio-Technical Context
Venue: arXiv cs.LG 2022
Year: 2022

Concerns about the societal impact of AI-based services and systems has encouraged governments and other organisations around the world to propose AI policy frameworks to address fairness, accountability, transparency and related topics. To achieve the objectives of these frameworks, the data and software engineers who build machine-learning systems require knowledge about a variety of relevant supporting tools and techniques. In this paper we provide an overview of technologies that support building trustworthy machine learning systems, i.e., systems whose properties justify that people place trust in them. We argue that four categories of system properties are instrumental in achieving the policy objectives, namely fairness, explainability, auditability and safety & security (FEAS). We discuss how these properties need to be considered across all stages of the machine learning life cycle, from data collection through run-time model inference. As a consequence, we survey in this paper the main technologies with respect to all four of the FEAS properties, for data-centric as well as model-centric stages of the machine learning system life cycle. We conclude with an identification of open research problems, with a particular focus on the connection between trustworthy machine learning technologies and their implications for individuals and society.
Optimally Integrating Ad Auction into E-Commerce Platforms
Venue: arXiv cs.GT 2022
Year: 2022

Advertising becomes one of the most popular ways of monetizing an online transaction platform. Usually, sponsored advertisements are posted on the most attractive positions to enhance the number of clicks. However, multiple e-commerce platforms are aware that this action may hurt the search experience of users, even though it can bring more incomes. To balance the advertising revenue and the user experience loss caused by advertisements, most e-commerce platforms choose fixing some areas for advertisements and adopting some simple restrictions on the number of ads, such as a fixed number K of ads on the top positions or one advertisement for every N organic searched results. Different from these common rules of treating the allocation of ads separately (from the arrangements of the organic searched items), in this work we build up an integrated system with mixed arrangements of advertisements and organic items. We focus on the design of truthful mechanisms to properly list the advertisements and organic items and optimally trade off the instant revenue and the user experience. Furthermore, for different settings and practical requirements, we extend our optimal truthful allocation mechanisms to cater for these realistic conditions. Finally, we exert several experiments to verify the improvement of our mechanism compared to the common-used advertising mechanism.
Design Space Exploration of Algorithmic Multi-Port Memories in High-Performance Application-Specific Accelerators
Venue: arXiv cs.AR 2022
Year: 2022

Memory load/store instructions consume an important part in execution time and energy consumption in domain-specific accelerators. For designing highly parallel systems, available parallelism at each granularity is extracted from the workloads. The maximal use of parallelism at each granularity in these high-performance designs requires the utilization of multi-port memories. Currently, true multiport designs are less popular because there is no inherent EDA support for multiport memory beyond 2-ports, utilizing more ports requires circuit-level implementation and hence a high design time. In this work, we present a framework for Design Space Exploration of Algorithmic Multi-Port Memories (AMM) in ASICs. We study different AMM designs in the literature, discuss how we incorporate them in the Pre-RTL Aladdin Framework with different memory depth, port configurations and banking structures. From our analysis on selected applications from the MachSuite (accelerator benchmark suite), we understand and quantify the potential use of AMMs (as true multiport memories) for high performance in applications with low spatial locality in memory access patterns.
Wide Boosting
Venue: arXiv cs.LG 2022
Year: 2022

Gradient Boosting (GB) is a popular methodology used to solve prediction problems by minimizing a differentiable loss function, $L$. GB performs very well on tabular machine learning (ML) problems; however, as a pure ML solver it lacks the ability to fit models with probabilistic but correlated multi-dimensional outputs, for example, multiple correlated Bernoulli outputs. GB also does not form intermediate abstract data embeddings, one property of Deep Learning that gives greater flexibility and performance on other types of problems. This paper presents a simple adjustment to GB motivated in part by artificial neural networks. Specifically, our adjustment inserts a matrix multiplication between the output of a GB model and the loss, $L$. This allows the output of a GB model to have increased dimension prior to being fed into the loss and is thus ``wider'' than standard GB implementations. We call our method Wide Boosting (WB) and show that WB outperforms GB on mult-dimesional output tasks and that the embeddings generated by WB contain are more useful in downstream prediction tasks than GB output predictions alone.
Estimating Probabilistic Safe WCET Ranges of Real-Time Systems at Design Stages
Venue: arXiv cs.SE 2022
Year: 2022

Estimating worst-case execution times (WCET) is an important activity at early design stages of real-time systems. Based on WCET estimates, engineers make design and implementation decisions to ensure that task executions always complete before their specified deadlines. However, in practice, engineers often cannot provide precise point WCET estimates and prefer to provide plausible WCET ranges. Given a set of real-time tasks with such ranges, we provide an automated technique to determine for what WCET values the system is likely to meet its deadlines, and hence operate safely with a probabilistic guarantee. Our approach combines a search algorithm for generating worst-case scheduling scenarios with polynomial logistic regression for inferring probabilistic safe WCET ranges. We evaluated our approach by applying it to three industrial systems from different domains and several synthetic systems. Our approach efficiently and accurately estimates probabilistic safe WCET ranges within which deadlines are likely to be satisfied with a high degree of confidence.
Blockchain Meets COVID-19: A Framework for Contact Information Sharing and Risk Notification System
Venue: arXiv cs.CR 2022
Year: 2022

COVID-19 is a severe global epidemic in human history. Even though there are particular medications and vaccines to curb the epidemic, tracing and isolating the infection source is the best option to slow the virus spread and reduce infection and death rates. There are three disadvantages to the existing contact tracing system: 1. User data is stored in a centralized database that could be stolen and tampered with, 2. User's confidential personal identity may be revealed to a third party or organization, 3. Existing contact tracing systems only focus on information sharing from one dimension, such as location-based tracing, which significantly limits the effectiveness of such systems. We propose a global COVID-19 information sharing and risk notification system that utilizes the Blockchain, Smart Contract, and Bluetooth. To protect user privacy, we design a novel Blockchain-based platform that can share consistent and non-tampered contact tracing information from multiple dimensions, such as location-based for indirect contact and Bluetooth-based for direct contact. Hierarchical smart contract architecture is also designed to achieve global agreements from users about how to process and utilize user data, thereby enhancing the data usage transparency. Furthermore, we propose a mechanism to protect user identity privacy from multiple aspects. More importantly, our system can notify the users about the exposure risk via smart contracts. We implement a prototype system to conduct extensive measurements to demonstrate the feasibility and effectiveness of our system.
Perceptron Synthesis Network: Rethinking the Action Scale Variances in Videos
Venue: arXiv cs.CV 2022
Year: 2022

Video action recognition has been partially addressed by the CNNs stacking of fixed-size 3D kernels. However, these methods may under-perform for only capturing rigid spatial-temporal patterns in single-scale spaces, while neglecting the scale variances across different action primitives. To overcome this limitation, we propose to learn the optimal-scale kernels from the data. More specifically, an \textit{action perceptron synthesizer} is proposed to generate the kernels from a bag of fixed-size kernels that are interacted by dense routing paths. To guarantee the interaction richness and the information capacity of the paths, we design the novel \textit{optimized feature fusion layer}. This layer establishes a principled universal paradigm that suffices to cover most of the current feature fusion techniques (e.g., channel shuffling, and channel dropout) for the first time. By inserting the \textit{synthesizer}, our method can easily adapt the traditional 2D CNNs to the video understanding tasks such as action recognition with marginal additional computation cost. The proposed method is thoroughly evaluated over several challenging datasets (i.e., Somehting-to-Somthing, Kinetics and Diving48) that highly require temporal reasoning or appearance discriminating, achieving new state-of-the-art results. Particularly, our low-resolution model outperforms the recent strong baseline methods, i.e., TSM and GST, with less than 30\% of their computation cost.