Search

For an algebraically closed field $\mathbb{K}$, we consider a Galois $G$-covering $\mathcal{B} \to \mathcal{A}$ between locally bounded $\mathbb{K}$-categories given by bound quivers, where $G$ is torsion-free and acts freely on the objects of $\mathcal{B}$. We define the notion of $(G,\tau_{\mathcal{B}})$-rigid subcategory and of support $(G,\tau_{\mathcal{B}})$-tilting pairs over $\mathcal{B}$-$\rm mod$. These are the analogues of the similar concepts in the context of a finite-dimensional algebra, where we additionally require that the subcategory be $G$-equivariant. When $\mathcal{A}$ is a finite-dimensional algebra, we show that the corresponding push-down functor $\mathcal{F}_{\lambda}: \mathcal{B}$-$\rm mod$ $\to \mathcal{A}$-$\rm mod$ sends $(G,\tau_{\mathcal{B}})$-rigid subcategories (respectively support $(G,\tau_{\mathcal{B}})$-tilting pairs) to $\tau_{\mathcal{A}}$-rigid modules (respectively support $\tau_{\mathcal{A}}$-tilting pairs). We further show that there is a notion of mutation for support $(G,\tau_{\mathcal{B}})$-tilting pairs over $\mathcal{B}$-$\rm mod$. Mutations of support $\tau_\mathcal{A}$-tilting pairs and of support $(G,\tau_\mathcal{B})$-tilting pairs commute with the push-down functor. We derive some consequences of this, and in particular, we derive a $\tau$-tilting analogue of the result of P. Gabriel that locally representation-finiteness is preserved under coverings. Finally, we prove that when the Galois group $G$ is finitely generated free, any rigid $\mathcal{A}$-module (and in particular $\tau_\mathcal{A}$-rigid $\mathcal{A}$-modules) lies in the essential image of the push-down functor.

We study the representation category of thread quivers and their quotients. A thread quiver is a quiver in which some arrows have been replaced by totally ordered sets. Pointwise finite-dimensional (pwf) representations of such a thread quiver admit a Krull-Remak-Schmidt-Azumaya decomposition. We show that an indecomposable representation is induced from an indecomposable representation of a quiver obtained from the original quiver by replacing some of its arrows by a finite linear $\mathbb{A}_n$ quiver. We study injective and projective pwf indecomposable representations and we fully classify them when the quiver satisfies a mild condition. We give a characterization of the indecomposable pwf representations of certain categories whose representation theory has similar properties to finite type or tame type. We further construct new hereditary abelian categories, including a Serre subcategory of pwf representations that includes every indecomposable representation., Comment: 35 pages, 4 figures

In order to solve problems of practical importance, quantum computers will likely need to incorporate quantum error correction, where a logical qubit is redundantly encoded in many noisy physical qubits. The large physical-qubit overhead typically associated with error correction motivates the search for more hardware-efficient approaches. Here, using a microfabricated superconducting quantum circuit, we realize a logical qubit memory formed from the concatenation of encoded bosonic cat qubits with an outer repetition code of distance $d=5$. The bosonic cat qubits are passively protected against bit flips using a stabilizing circuit. Cat-qubit phase-flip errors are corrected by the repetition code which uses ancilla transmons for syndrome measurement. We realize a noise-biased CX gate which ensures bit-flip error suppression is maintained during error correction. We study the performance and scaling of the logical qubit memory, finding that the phase-flip correcting repetition code operates below threshold, with logical phase-flip error decreasing with code distance from $d=3$ to $d=5$. Concurrently, the logical bit-flip error is suppressed with increasing cat-qubit mean photon number. The minimum measured logical error per cycle is on average $1.75(2)\%$ for the distance-3 code sections, and $1.65(3)\%$ for the longer distance-5 code, demonstrating the effectiveness of bit-flip error suppression throughout the error correction cycle. These results, where the intrinsic error suppression of the bosonic encodings allows us to use a hardware-efficient outer error correcting code, indicate that concatenated bosonic codes are a compelling paradigm for reaching fault-tolerant quantum computation., Comment: Comments on the manuscript welcome!

The recently devised chiral algebra bootstrap computes the form factors of a special class of ``twistorial'' 4d QFTs as correlation functions of the theory's 2d celestial chiral algebra. Examples of twistorial theories include self-dual Yang-Mills theory coupled to special massless matter content, and certain form factors in these theories are equivalent to a subset of MHV amplitudes in massless QCD, coupled to the same matter. In this paper, we extend the chiral algebra bootstrap to include scattering in the presence of charged sources, using a self-dual dyon in a twistorial theory as our main example. Self-dual theories in the presence of such sources lift to holomorphic gauge theories on non-Hausdorff twistor space, and we generalize the Koszul duality construction of Costello and Paquette to this setting. With this approach, we easily reproduce a recent formula of Adamo, Bogna, Mason, and Sharma for $n$-point MHV scattering of gluons off the self-dual dyon., Comment: 33 + 4 pages, no figures. comments welcome!

Large language models (LLMs) can be used to analyze cyber threat intelligence (CTI) data from cybercrime forums, which contain extensive information and key discussions about emerging cyber threats. However, to date, the level of accuracy and efficiency of LLMs for such critical tasks has yet to be thoroughly evaluated. Hence, this study assesses the performance of an LLM system built on the OpenAI GPT-3.5-turbo model [8] to extract CTI information. To do so, a random sample of more than 700 daily conversations from three cybercrime forums - XSS, Exploit_in, and RAMP - was extracted, and the LLM system was instructed to summarize the conversations and predict 10 key CTI variables, such as whether a large organization and/or a critical infrastructure is being targeted, with only simple human-language instructions. Then, two coders reviewed each conversation and evaluated whether the information extracted by the LLM was accurate. The LLM system performed well, with an average accuracy score of 96.23%, an average precision of 90% and an average recall of 88.2%. Various ways to enhance the model were uncovered, such as the need to help the LLM distinguish between stories and past events, as well as being careful with verb tenses in prompts. Nevertheless, the results of this study highlight the relevance of using LLMs for cyber threat intelligence.

For finite dimensional algebras over algebraically closed fields, we study the sets of pairwise Hom-orthogonal modules and obtain new results on some open conjectures on the behaviour of bricks and several related problems, which we generally refer to as brick-Brauer-Thrall (bBT) conjectures. Using some algebraic and geometric tools, and in terms of the notion of Hom-orthogonality, we find necessary and sufficient conditions for the existence of infinite families of bricks of the same dimension. This sheds new lights on the bBT conjectures and we prove many of them for some new families of algebras. Our results imply some interesting algebraic and geometric characterizations of brick-finite algebras as conceptual generalizations of local algebras. We also verify the bBT conjectures for any algebra whose Auslander-Reiten quiver has a generalized standard component. On the one hand, our work relates and develops some recent studies of the bBT conjectures which are conducted in several directions. On the other hand, it extends some earlier results of Chindris-Kinser-Weyman, where the algebras with preprojective components were treated., Comment: 23 pages

Quantum machine learning has gained considerable attention as quantum technology advances, presenting a promising approach for efficiently learning complex data patterns. Despite this promise, most contemporary quantum methods require significant resources for variational parameter optimization and face issues with vanishing gradients, leading to experiments that are either limited in scale or lack potential for quantum advantage. To address this, we develop a general-purpose, gradient-free, and scalable quantum reservoir learning algorithm that harnesses the quantum dynamics of neutral-atom analog quantum computers to process data. We experimentally implement the algorithm, achieving competitive performance across various categories of machine learning tasks, including binary and multi-class classification, as well as timeseries prediction. Effective and improving learning is observed with increasing system sizes of up to 108 qubits, demonstrating the largest quantum machine learning experiment to date. We further observe comparative quantum kernel advantage in learning tasks by constructing synthetic datasets based on the geometric differences between generated quantum and classical data kernels. Our findings demonstrate the potential of utilizing classically intractable quantum correlations for effective machine learning. We expect these results to stimulate further extensions to different quantum hardware and machine learning paradigms, including early fault-tolerant hardware and generative machine learning tasks., Comment: 10 + 14 pages, 4 + 7 figures

The success of modern machine learning is due in part to the adaptive optimization methods that have been developed to deal with the difficulties of training large models over complex datasets. One such method is gradient clipping: a practical procedure with limited theoretical underpinnings. In this work, we study clipping in a least squares problem under streaming SGD. We develop a theoretical analysis of the learning dynamics in the limit of large intrinsic dimension-a model and dataset dependent notion of dimensionality. In this limit we find a deterministic equation that describes the evolution of the loss and demonstrate that this equation predicts the path of clipped SGD on synthetic, CIFAR10, and Wikitext2 data. We show that with Gaussian noise clipping cannot improve SGD performance. Yet, in other noisy settings, clipping can provide benefits with tuning of the clipping threshold. We propose a simple heuristic for near optimal scheduling of the clipping threshold which requires the tuning of only one hyperparameter. We conclude with a discussion about the links between high-dimensional clipping and neural network training.

We develop a framework for analyzing the training and learning rate dynamics on a large class of high-dimensional optimization problems, which we call the high line, trained using one-pass stochastic gradient descent (SGD) with adaptive learning rates. We give exact expressions for the risk and learning rate curves in terms of a deterministic solution to a system of ODEs. We then investigate in detail two adaptive learning rates -- an idealized exact line search and AdaGrad-Norm -- on the least squares problem. When the data covariance matrix has strictly positive eigenvalues, this idealized exact line search strategy can exhibit arbitrarily slower convergence when compared to the optimal fixed learning rate with SGD. Moreover we exactly characterize the limiting learning rate (as time goes to infinity) for line search in the setting where the data covariance has only two distinct eigenvalues. For noiseless targets, we further demonstrate that the AdaGrad-Norm learning rate converges to a deterministic constant inversely proportional to the average eigenvalue of the data covariance matrix, and identify a phase transition when the covariance density of eigenvalues follows a power law distribution. We provide our code for evaluation at https://github.com/amackenzie1/highline2024., Comment: We fixed typos, made clarifications to the document, added a new Conclusions and Limitations section, and included a link to the code used for the numerical simulations that generated the figures in the paper

We consider the three parameter solvable neural scaling model introduced by Maloney, Roberts, and Sully. The model has three parameters: data complexity, target complexity, and model-parameter-count. We use this neural scaling model to derive new predictions about the compute-limited, infinite-data scaling law regime. To train the neural scaling model, we run one-pass stochastic gradient descent on a mean-squared loss. We derive a representation of the loss curves which holds over all iteration counts and improves in accuracy as the model parameter count grows. We then analyze the compute-optimal model-parameter-count, and identify 4 phases (+3 subphases) in the data-complexity/target-complexity phase-plane. The phase boundaries are determined by the relative importance of model capacity, optimizer noise, and embedding of the features. We furthermore derive, with mathematical proof and extensive numerical evidence, the scaling-law exponents in all of these phases, in particular computing the optimal model-parameter-count as a function of floating point operation budget.

The challenge of creating interpretable models has been taken up by two main research communities: ML researchers primarily focused on lower-level explainability methods that suit the needs of engineers, and HCI researchers who have more heavily emphasized user-centered approaches often based on participatory design methods. This paper reviews how these communities have evaluated interpretability, identifying overlaps and semantic misalignments. We propose moving towards a unified framework of evaluation criteria and lay the groundwork for such a framework by articulating the relationships between existing criteria. We argue that explanations serve as mediators between models and stakeholders, whether for intrinsically interpretable models or opaque black-box models analyzed via post-hoc techniques. We further argue that useful explanations require both faithfulness and intelligibility. Explanation plausibility is a prerequisite for intelligibility, while stability is a prerequisite for explanation faithfulness. We illustrate these criteria, as well as specific evaluation methods, using examples from an ongoing study of an interpretable neural network for predicting a particular learner behavior., Comment: 6 pages. Presented at HEXED Workshop @ EDM24

In this work, we revisit and elaborate on twisted holography for AdS$_3 \times S^3 \times X$ with $X= T^4$, K3, with a particular focus on K3. We describe the twist of supergravity, identify the corresponding (generalization of) BCOV theory, and enumerate twisted supergravity states. We use this knowledge, and the technique of Koszul duality, to obtain the $N \rightarrow \infty$, or planar, limit of the chiral algebra of the dual CFT. The resulting symmetries are strong enough to fix planar 2 and 3-point functions in the twisted theory or, equivalently, in a 1/4-BPS subsector of the original duality. This technique can in principle be used to compute corrections to the chiral algebra perturbatively in $1/N$., Comment: 91 pages, 9 figures (v2: minor corrections and additions)

With the ever-growing presence of deep artificial neural networks in every facet of modern life, a growing body of researchers in educational data science -- a field consisting of various interrelated research communities -- have turned their attention to leveraging these powerful algorithms within the domain of education. Use cases range from advanced knowledge tracing models that can leverage open-ended student essays or snippets of code to automatic affect and behavior detectors that can identify when a student is frustrated or aimlessly trying to solve problems unproductively -- and much more. This chapter provides a brief introduction to deep learning, describes some of its advantages and limitations, presents a survey of its many uses in education, and discusses how it may further come to shape the field of educational data science., Comment: 18 pages. To be published in Trust and Inclusion in AI-Mediated Education: Where Human Learning Meets Learning Machines by Springer International

We consider the range of random analytic functions with finite radius of convergence. We show that any unbounded random Taylor series with rotationally invariant coefficients has dense image in the plane. We moreover show that if in addition the coefficients are complex Gaussian with sufficiently regular variances, then the image is the whole complex plane. We do this by exploiting an approximate connection between the coverage problem and spatial branching processes. This answers a long-standing open question of J.-P. Kahane, with sufficient regularity., Comment: Updated to remove unused lemma and changed formatting

We study the problem of differentially-private (DP) stochastic (convex-concave) saddle-points in the polyhedral setting. We propose $(\varepsilon, \delta)$-DP algorithms based on stochastic mirror descent that attain nearly dimension-independent convergence rates for the expected duality gap, a type of guarantee that was known before only for bilinear objectives. For convex-concave and first-order-smooth stochastic objectives, our algorithms attain a rate of $\sqrt{\log(d)/n} + (\log(d)^{3/2}/[n\varepsilon])^{1/3}$, where $d$ is the dimension of the problem and $n$ the dataset size. Under an additional second-order-smoothness assumption, we improve the rate on the expected gap to $\sqrt{\log(d)/n} + (\log(d)^{3/2}/[n\varepsilon])^{2/5}$. Under this additional assumption, we also show, by using bias-reduced gradient estimators, that the duality gap is bounded by $\log(d)/\sqrt{n} + \log(d)/[n\varepsilon]^{1/2}$ with constant success probability. This result provides evidence of the near-optimality of the approach. Finally, we show that combining our methods with acceleration techniques from online learning leads to the first algorithm for DP Stochastic Convex Optimization in the polyhedral setting that is not based on Frank-Wolfe methods. For convex and first-order-smooth stochastic objectives, our algorithms attain an excess risk of $\sqrt{\log(d)/n} + \log(d)^{7/10}/[n\varepsilon]^{2/5}$, and when additionally assuming second-order-smoothness, we improve the rate to $\sqrt{\log(d)/n} + \log(d)/\sqrt{n\varepsilon}$. Instrumental to all of these results are various extensions of the classical Maurey Sparsification Lemma, which may be of independent interest.

We present a new algorithm to optimize distributions defined implicitly by parameterized stochastic diffusions. Doing so allows us to modify the outcome distribution of sampling processes by optimizing over their parameters. We introduce a general framework for first-order optimization of these processes, that performs jointly, in a single loop, optimization and sampling steps. This approach is inspired by recent advances in bilevel optimization and automatic implicit differentiation, leveraging the point of view of sampling as optimization over the space of probability distributions. We provide theoretical guarantees on the performance of our method, as well as experimental results demonstrating its effectiveness. We apply it to training energy-based models and finetuning denoising diffusions., Comment: 38 pages, 16 figures. Updated with additional experiments

This paper develops some theory of the Dyson equation for correlated linearizations and uses it to solve a problem on asymptotic deterministic equivalent for the test error in random features regression. The theory developed for the correlated Dyson equation includes existence-uniqueness, spectral support bounds, and stability properties. This theory is new for constructing deterministic equivalents for pseudo-resolvents of a class of correlated linear pencils. In the application, this theory is used to give a deterministic equivalent of the test error in random features ridge regression, in a proportional scaling regime, wherein we have conditioned on both training and test datasets., Comment: 57 page, 2 figures

We analyze the dynamics of streaming stochastic gradient descent (SGD) in the high-dimensional limit when applied to generalized linear models and multi-index models (e.g. logistic regression, phase retrieval) with general data-covariance. In particular, we demonstrate a deterministic equivalent of SGD in the form of a system of ordinary differential equations that describes a wide class of statistics, such as the risk and other measures of sub-optimality. This equivalence holds with overwhelming probability when the model parameter count grows proportionally to the number of data. This framework allows us to obtain learning rate thresholds for stability of SGD as well as convergence guarantees. In addition to the deterministic equivalent, we introduce an SDE with a simplified diffusion coefficient (homogenized SGD) which allows us to analyze the dynamics of general statistics of SGD iterates. Finally, we illustrate this theory on some standard examples and show numerical simulations which give an excellent match to the theory., Comment: Preliminary version

We provide a recursive description of all decompositions of the positive roots $R^+$ of a quotient root system $R$ into disjoint unions of inversion sets. Our description is type-independent and generalizes the analogous result for type $\mathbb A$ root systems in [USRA]. The main tool is the notion of an inflation of a subset of a quotient root system. This new notion allows us to treat all root systems (and their quotients) uniformly. We also obtain some numerical results about the number of special decompositions. The new sequences we obtain may be considered as extensions of Catalan numbers., Comment: Preliminary Version

In this paper, we explore the application of large language models (LLMs) for generating code-tracing questions in introductory programming courses. We designed targeted prompts for GPT4, guiding it to generate code-tracing questions based on code snippets and descriptions. We established a set of human evaluation metrics to assess the quality of questions produced by the model compared to those created by human experts. Our analysis provides insights into the capabilities and potential of LLMs in generating diverse code-tracing questions. Additionally, we present a unique dataset of human and LLM-generated tracing questions, serving as a valuable resource for both the education and NLP research communities. This work contributes to the ongoing dialogue on the potential uses of LLMs in educational settings., Comment: Accepted by Findings of EMNLP, 2023

We prove that over an algebraically closed field $\mathbb{K}$ of characteristic different from $2$, the group algebra $R=\mathbb{K} D_\infty$ of the infinite dihedral group $D_\infty$ has exactly six conjugacy classes of involutions (equivalently, of idempotents). This allows us to recover the fact that $R$ admits exactly four non-isomorphic indecomposable projective modules of the form $eR$ where $e$ is an idempotent, a result that was first established by Berman and Buz\'asi., Comment: 6 pages