OpenRaiser/Intern-Atlas huggingface dataset:
Learning an Explicit Hyperparameter Prediction Function Conditioned on Tasks
Venue: arXiv cs.LG 2023
Year: 2023

Meta learning has attracted much attention recently in machine learning community. Contrary to conventional machine learning aiming to learn inherent prediction rules to predict labels for new query data, meta learning aims to learn the learning methodology for machine learning from observed tasks, so as to generalize to new query tasks by leveraging the meta-learned learning methodology. In this study, we interpret such learning methodology as learning an explicit hyper-parameter prediction function shared by all training tasks. Specifically, this function is represented as a parameterized function called meta-learner, mapping from a training/test task to its suitable hyper-parameter setting, extracted from a pre-specified function set called meta learning machine. Such setting guarantees that the meta-learned learning methodology is able to flexibly fit diverse query tasks, instead of only obtaining fixed hyper-parameters by many current meta learning methods, with less adaptability to query task's variations. Such understanding of meta learning also makes it easily succeed from traditional learning theory for analyzing its generalization bounds with general losses/tasks/models. The theory naturally leads to some feasible controlling strategies for ameliorating the quality of the extracted meta-learner, verified to be able to finely ameliorate its generalization capability in some typical meta learning applications, including few-shot regression, few-shot classification and domain generalization.
Prioritized training on points that are learnable, worth learning, and not yet learned (workshop version)
Venue: arXiv cs.LG 2023
Year: 2023

We introduce Goldilocks Selection, a technique for faster model training which selects a sequence of training points that are "just right". We propose an information-theoretic acquisition function -- the reducible validation loss -- and compute it with a small proxy model -- GoldiProx -- to efficiently choose training points that maximize information about a validation set. We show that the "hard" (e.g. high loss) points usually selected in the optimization literature are typically noisy, while the "easy" (e.g. low noise) samples often prioritized for curriculum learning confer less information. Further, points with uncertain labels, typically targeted by active learning, tend to be less relevant to the task. In contrast, Goldilocks Selection chooses points that are "just right" and empirically outperforms the above approaches. Moreover, the selected sequence can transfer to other architectures; practitioners can share and reuse it without the need to recreate it.
A General Approach to Approximate Multistage Subgraph Problems
Venue: arXiv cs.DS 2023
Year: 2023

In a Subgraph Problem we are given some graph and want to find a feasible subgraph that optimizes some measure. We consider Multistage Subgraph Problems (MSPs), where we are given a sequence of graph instances (stages) and are asked to find a sequence of subgraphs, one for each stage, such that each is optimal for its respective stage and the subgraphs for subsequent stages are as similar as possible. We present a framework that provides a $(1/\sqrt{2χ})$-approximation algorithm for the $2$-stage restriction of an MSP if the similarity of subsequent solutions is measured as the intersection cardinality and said MSP is preficient, i.e., we can efficiently find a single-stage solution that prefers some given subset. The approximation factor is dependent on the instance's intertwinement $χ$, a similarity measure for multistage graphs. We also show that for any MSP, independent of similarity measure and preficiency, given an exact or approximation algorithm for a constant number of stages, we can approximate the MSP for an unrestricted number of stages. Finally, we combine and apply these results and show that the above restrictions describe a very rich class of MSPs and that proving membership for this class is mostly straightforward. As examples, we explicitly state these proofs for natural multistage versions of Perfect Matching, Shortest s-t-Path, Minimum s-t-Cut and further classical problems on bipartite or planar graphs, namely Maximum Cut, Vertex Cover, Independent Set, and Biclique.
Deep Convolutional Correlation Iterative Particle Filter for Visual Tracking
Venue: arXiv cs.CV 2023
Year: 2023

This work proposes a novel framework for visual tracking based on the integration of an iterative particle filter, a deep convolutional neural network, and a correlation filter. The iterative particle filter enables the particles to correct themselves and converge to the correct target position. We employ a novel strategy to assess the likelihood of the particles after the iterations by applying K-means clustering. Our approach ensures a consistent support for the posterior distribution. Thus, we do not need to perform resampling at every video frame, improving the utilization of prior distribution information. Experimental results on two different benchmark datasets show that our tracker performs favorably against state-of-the-art methods.
Capacitated Network Design Games on a Generalized Fair Allocation Model
Venue: arXiv cs.GT 2023
Year: 2023

The cost-sharing connection game is a variant of routing games on a network. In this model, given a directed graph with edge costs and edge capacities, each agent wants to construct a path from a source to a sink with low cost. The users share the cost of each edge based on a cost-sharing function. One of the simple cost-sharing functions is defined as the cost divided by the number of users. Most of the previous papers about cost-sharing connection games addressed this cost-sharing function. It models an ideal setting where no overhead arises when people share things, though it might be quite rare in real life; it is more realistic to consider the setting that the cost paid by an agent is the original cost per the number of agents using the edge plus the overhead. In this paper, we model the more realistic scenario of cost-sharing connection games by generalizing cost-sharing functions. The arguments on the model are based on not concrete cost-sharing functions but cost-sharing functions under a reasonable scheme; they are applicable for a broad class of cost-sharing functions satisfying the following natural properties: they are (1) non-increasing, (2) lower bounded by the original cost per the number of the agents, and (3) upper bounded by the original cost, which enables to represent various scenarios of cost-sharing. We investigate the Price of Anarchy (PoA) and the Price of Stability (PoS) under sum-cost and max-cost criteria with the generalized cost-sharing function. Despite the generalization, we obtain the same tight bounds of PoA and PoS as the cost-sharing with no overhead except PoS under sum-cost. Moreover, for the sum-cost case, the lower bound on PoS increases from $\log n$ to $n+1/n-1$ by the generalization, which is also almost tight because the upper bound is $n$.
RoFL: Robustness of Secure Federated Learning
Venue: arXiv cs.CR 2023
Year: 2023

Even though recent years have seen many attacks exposing severe vulnerabilities in Federated Learning (FL), a holistic understanding of what enables these attacks and how they can be mitigated effectively is still lacking. In this work, we demystify the inner workings of existing (targeted) attacks. We provide new insights into why these attacks are possible and why a definitive solution to FL robustness is challenging. We show that the need for ML algorithms to memorize tail data has significant implications for FL integrity. This phenomenon has largely been studied in the context of privacy; our analysis sheds light on its implications for ML integrity. We show that certain classes of severe attacks can be mitigated effectively by enforcing constraints such as norm bounds on clients' updates. We investigate how to efficiently incorporate these constraints into secure FL protocols in the single-server setting. Based on this, we propose RoFL, a new secure FL system that extends secure aggregation with privacy-preserving input validation. Specifically, RoFL can enforce constraints such as $L_2$ and $L_\infty$ bounds on high-dimensional encrypted model updates.
Can Deep Neural Networks Predict Data Correlations from Column Names?
Venue: arXiv cs.DB 2023
Year: 2023

Recent publications suggest using natural language analysis on database schema elements to guide tuning and profiling efforts. The underlying hypothesis is that state-of-the-art language processing methods, so-called language models, are able to extract information on data properties from schema text. This paper examines that hypothesis in the context of data correlation analysis: is it possible to find column pairs with correlated data by analyzing their names via language models? First, the paper introduces a novel benchmark for data correlation analysis, created by analyzing thousands of Kaggle data sets (and available for download). Second, it uses that data to study the ability of language models to predict correlation, based on column names. The analysis covers different language models, various correlation metrics, and a multitude of accuracy metrics. It pinpoints factors that contribute to successful predictions, such as the length of column names as well as the ratio of words. Finally, \rev{the study analyzes the impact of column types on prediction performance.} The results show that schema text can be a useful source of information and inform future research efforts, targeted at NLP-enhanced database tuning and data profiling.
Compositional Vulnerability Detection with Insecurity Separation Logic (Extended Version)
Venue: arXiv cs.PL 2023
Year: 2023

Memory-safety issues and information leakage are known to be depressingly common. We consider the compositional static detection of these kinds of vulnerabilities in first-order C-like programs. Indeed the latter are relational hyper-safety violations, comparing pairs of program executions, making them more challenging to detect than the former, which require reasoning only over individual executions. Existing symbolic leakage detection methods treat only non-interactive programs, avoiding the challenges of nondeterminism. Also, being whole-program analyses they cannot be applied one-function-at-a-time, thereby ruling out incremental analysis. We remedy these shortcomings by presenting Insecurity Separation Logic (InsecSL), an under-approximate relational program logic for soundly detecting information leakage and memory-safety issues in interactive programs. Importantly, InsecSL reasons about pairs of executions, and so is relational, but purposefully resembles the non-relational Incorrectness Separation Logic (ISL) that is already automated in the Infer tool. We show how InsecSL can be automated by bi-abduction based symbolic execution, and we evaluate two implementations of this idea (one based on Infer) on various case-studies.
A generalized hypothesis test for community structure in networks
Venue: arXiv cs.SI 2023
Year: 2023

Researchers theorize that many real-world networks exhibit community structure where within-community edges are more likely than between-community edges. While numerous methods exist to cluster nodes into different communities, less work has addressed this question: given some network, does it exhibit statistically meaningful community structure? We answer this question in a principled manner by framing it as a statistical hypothesis test in terms of a general and model-agnostic community structure parameter. Leveraging this parameter, we propose a simple and interpretable test statistic used to formulate two separate hypothesis testing frameworks. The first is an asymptotic test against a baseline value of the parameter while the second tests against a baseline model using bootstrap-based thresholds. We prove theoretical properties of these tests and demonstrate how the proposed method yields rich insights into real-world data sets.
MAFAT: Memory-Aware Fusing and Tiling of Neural Networks for Accelerated Edge Inference
Venue: arXiv cs.LG 2023
Year: 2023

A rising research challenge is running costly machine learning (ML) networks locally on resource-constrained edge devices. ML networks with large convolutional layers can easily exceed available memory, increasing latency due to excessive OS swapping. Previous memory reduction techniques such as pruning and quantization reduce model accuracy and often require retraining. Alternatively, distributed methods partition the convolutions into equivalent smaller sub-computations, but the implementations introduce communication costs and require a network of devices. Distributed partitioning approaches can, however, also be used to run in a reduced memory footprint on a single device by subdividing the network into smaller operations. In this paper, we extend prior work on distributed partitioning into a memory-aware execution on a single device. Our approach extends prior fusing strategies to allow for multiple groups of convolutional layers that are fused and tiled independently. This enables trading off overhead versus data reuse in order to specifically reduces memory footprint. We propose a memory usage predictor coupled with a search algorithm to provide optimized fusing and tiling configurations for an arbitrary set of convolutional layers. When applied to the YOLOv2 object detection network, results show that our approach can run in less than half the memory, and with a speedup of up to 2.78 under severe memory constraints. Additionally, our algorithm will return a configuration with a latency that is within 6% of the best latency measured in a manual search.
Systematic human learning and generalization from a brief tutorial with explanatory feedback
Venue: arXiv cs.LG 2023
Year: 2023

Neural networks have long been used to model human intelligence, capturing elements of behavior and cognition, and their neural basis. Recent advancements in deep learning have enabled neural network models to reach and even surpass human levels of intelligence in many respects, yet unlike humans, their ability to learn new tasks quickly remains a challenge. People can reason not only in familiar domains, but can also rapidly learn to reason through novel problems and situations, raising the question of how well modern neural network models capture human intelligence and in which ways they diverge. In this work, we explore this gap by investigating human adults' ability to learn an abstract reasoning task based on Sudoku from a brief instructional tutorial with explanatory feedback for incorrect responses using a narrow range of training examples. We find that participants who master the task do so within a small number of trials and generalize well to puzzles outside of the training range. We also find that most of those who master the task can describe a valid solution strategy, and such participants perform better on transfer puzzles than those whose strategy descriptions are vague or incomplete. Interestingly, fewer than half of our human participants were successful in acquiring a valid solution strategy, and this ability is associated with high school mathematics education. We consider the challenges these findings pose for building computational models that capture all aspects of our findings and point toward a possible role for learning to engage in explanation-based reasoning to support rapid learning and generalization.
Reed-Muller Identification
Venue: arXiv cs.IT 2023
Year: 2023

Ahlswede and Dueck identification has the potential of exponentially reducing traffic or exponentially increasing rates in applications where a full decoding of the message is not necessary and, instead, a simple verification of the message of interest suffices. However, the proposed constructions can suffer from exponential increase in the computational load at the sender and receiver, rendering these advantages unusable. This has been shown in particular to be the case for a construction achieving identification capacity based on concatenated Reed-Solomon codes. Here, we consider the natural generalization of identification based on Reed-Muller codes and we show that, although without achieving identification capacity, they allow to achieve the exponentially large rates mentioned above without the computational penalty increasing too much the latency with respect to transmission.
From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformers
Venue: arXiv cs.LG 2023
Year: 2023

In this paper we provide, to the best of our knowledge, the first comprehensive approach for incorporating various masking mechanisms into Transformers architectures in a scalable way. We show that recent results on linear causal attention (Choromanski et al., 2021) and log-linear RPE-attention (Luo et al., 2021) are special cases of this general mechanism. However by casting the problem as a topological (graph-based) modulation of unmasked attention, we obtain several results unknown before, including efficient d-dimensional RPE-masking and graph-kernel masking. We leverage many mathematical techniques ranging from spectral analysis through dynamic programming and random walks to new algorithms for solving Markov processes on graphs. We provide a corresponding empirical evaluation.
An Information-state based Approach to the Optimal Output Feedback Control of Nonlinear Systems
Venue: arXiv cs.RO 2023
Year: 2023

This paper develops a data-based approach to the closed-loop output feedback control of nonlinear dynamical systems with a partial nonlinear observation model. We propose an information state based approach to rigorously transform the partially observed problem into a fully observed problem where the information state consists of the past several observations and control inputs. We further show the equivalence of the transformed and the initial partially observed optimal control problems and provide the conditions to solve for the deterministic optimal solution. We develop a data based generalization of the iterative Linear Quadratic Regulator (iLQR) to partially observed systems using a local linear time varying model of the information state dynamics approximated by an Autoregressive moving average (ARMA) model, that is generated using only the input-output data. This open-loop trajectory optimization solution is then used to design a local feedback control law, and the composite law then provides an optimum solution to the partially observed feedback design problem. The efficacy of the developed method is shown by controlling complex high dimensional nonlinear dynamical systems in the presence of model and sensing uncertainty.
Sensitivity of string compressors and repetitiveness measures
Venue: arXiv cs.DS 2023
Year: 2023

The sensitivity of a string compression algorithm $C$ asks how much the output size $C(T)$ for an input string $T$ can increase when a single character edit operation is performed on $T$. This notion enables one to measure the robustness of compression algorithms in terms of errors and/or dynamic changes occurring in the input string. In this paper, we analyze the worst-case multiplicative sensitivity of string compression algorithms, which is defined by $\max_{T \in Σ^n}\{C(T')/C(T) : ed(T, T') = 1\}$, where $ed(T, T')$ denotes the edit distance between $T$ and $T'$. For the most common versions of the Lempel-Ziv 77 compressors, we prove that the worst-case multiplicative sensitivity is upper bounded by a small constant, and give matching lower bounds. We generalize these results to the smallest bidirectional scheme $b$. In addition, we show that the sensitivity of a grammar-based compressor called GCIS is also a small constant. Further, we extend the notion of the worst-case sensitivity to string repetitiveness measures such as the smallest string attractor size $γ$ and the substring complexity $δ$, and show that the worst-case sensitivity of $δ$ is also a small constant. These results contrast with the previously known related results such that the size $z_{\rm 78}$ of the Lempel-Ziv 78 factorization can increase by a factor of $Ω(n^{1/4})$ [Lagarde and Perifel, 2018], and the number $r$ of runs in the Burrows-Wheeler transform can increase by a factor of $Ω(\log n)$ [Giuliani et al., 2021] when a character is prepended to an input string of length $n$. By applying our sensitivity bounds of $δ$ or the smallest grammar to known results (c.f. [Navarro, 2021]), some non-trivial upper bounds for the sensitivities of important string compressors and repetitiveness measures including $γ$, $r$, LZ-End, RePair, LongestMatch, and AVL-grammar are derived.
Fundamental Constructs in Programming Languages
Venue: arXiv cs.PL 2023
Year: 2023

When a new programming language appears, the syntax and intended behaviour of its programs need to be specified. The behaviour of each language construct can be concisely specified by translating it to fundamental constructs (funcons), compositionally. In contrast to the informal explanations commonly found in reference manuals, such formal specifications of translations to funcons can be precise and complete. They are also easy to write and read, and to update when the language evolves. The PLanCompS project has developed a large collection of funcons. Each funcon is defined independently, using a modular variant of structural operational semantics. The definitions are available online, along with tools for generating funcon interpreters from them. This paper introduces and motivates funcons. It illustrates translation of language constructs to funcons, and funcon definition. It also relates funcons to the notation used in some previous language specification frameworks, including monadic semantics and action semantics.
Towards a Practical, Budget-Oblivious Algorithm for the Adwords Problem under Small Bids
Venue: arXiv cs.DS 2023
Year: 2023

Motivated by recent insights into the online bipartite matching problem (\textsc{OBM}), our goal was to extend the optimal algorithm for it, namely \textsc{Ranking}, all the way to the special case of adwords problem, called \textsc{Small}, in which bids are small compared to budgets; the latter has been of considerable practical significance in ad auctions \cite{MSVV}. The attractive feature of our approach was that it would yield a {\em budget-oblivious algorithm}, i.e., the algorithm would not need to know budgets of advertisers and therefore could be used in autobidding platforms. We were successful in obtaining an optimal, budget-oblivious algorithm for \textsc{Single-Valued}, under which each advertiser can make bids of one value only. However, our next extension, to \textsc{Small}, failed because of a fundamental reason, namely failure of the {\em No-Surpassing Property}. Since the probabilistic ideas underlying our algorithm are quite substantial, we have stated them formally, after assuming the No-Surpassing Property, and we leave the open problem of removing this assumption. With the help of two undergrads, we conducted extensive experiments on our algorithm on randomly generated instances. Our findings are that the No-Surpassing Property fails less than $2\%$ of the time and that the performance of our algorithms for \textsc{Single-Valued} and \textsc{Small} are comparable to that of \cite{MSVV}. If further experiments confirm this, our algorithm may be useful as such in practice, especially because of its budget-obliviousness.