Date: Fri, 9 Aug 2024 | Total: 150

In this paper, we discuss the asymptotic behavior of the Upper Confidence Bound (UCB) algorithm in the context of multiarmed bandit problems and discuss its implication in downstream inferential tasks. While inferential tasks become challenging when data is collected in a sequential manner, we argue that this problem can be alleviated when the sequential algorithm at hand satisfies certain stability property. This notion of stability is motivated from the seminal work of Lai and Wei (1982). Our first main result shows that such a stability property is always satisfied for the UCB algorithm, and as a result the sample means for each arm are asymptotically normal. Next, we examine the stability properties of the UCB algorithm when the number of arms $K$ is allowed to grow with the number of arm pulls $T$. We show that in such a case the arms are stable when $\frac{\log K}{\log T} \rightarrow 0$, and the number of near-optimal arms are large.

This paper presents a unified algorithm for motion and force control for a six degree-of-freedom spatial manipulator. The motion-force controller performs trajectory tracking, maneuvering the manipulator's end-effector through desired position, orientations and rates. When contacting an obstacle or target object, the force module of the controller restricts the manipulator movements with a novel force exertion method, which prevents damage to the manipulator, the end-effector, and the objects during the contact or collision. The core strategy presented in this paper is to design the linear acceleration for the end-effector which ensures both trajectory tracking and restriction of any contact force at the end-effector. The design of the controller is validated through numerical simulations and digital twin validation.

In dynamic programming and reinforcement learning, the policy for the sequential decision making of an agent in a stochastic environment is usually determined by expressing the goal as a scalar reward function and seeking a policy that maximizes the expected total reward. However, many goals that humans care about naturally concern multiple aspects of the world, and it may not be obvious how to condense those into a single reward function. Furthermore, maximization suffers from specification gaming, where the obtained policy achieves a high expected total reward in an unintended way, often taking extreme or nonsensical actions. Here we consider finite acyclic Markov Decision Processes with multiple distinct evaluation metrics, which do not necessarily represent quantities that the user wants to be maximized. We assume the task of the agent is to ensure that the vector of expected totals of the evaluation metrics falls into some given convex set, called the aspiration set. Our algorithm guarantees that this task is fulfilled by using simplices to approximate feasibility sets and propagate aspirations forward while ensuring they remain feasible. It has complexity linear in the number of possible state-action-successor triples and polynomial in the number of evaluation metrics. Moreover, the explicitly non-maximizing nature of the chosen policy and goals yields additional degrees of freedom, which can be used to apply heuristic safety criteria to the choice of actions. We discuss several such safety criteria that aim to steer the agent towards more conservative behavior.

Polynomial neural networks have been implemented in a range of applications and present an advantageous framework for theoretical machine learning. A polynomial neural network of fixed architecture and activation degree gives an algebraic map from the network's weights to a set of polynomials. The image of this map is the space of functions representable by the network. Its Zariski closure is an affine variety known as a neurovariety. The dimension of a polynomial neural network's neurovariety provides a measure of its expressivity. In this work, we introduce the notion of the activation threshold of a network architecture which expresses when the dimension of a neurovariety achieves its theoretical maximum. In addition, we prove expressiveness results for polynomial neural networks with equi-width~architectures.

DeepONet has recently been proposed as a representative framework for learning nonlinear mappings between function spaces. However, when it comes to approximating solution operators of partial differential equations (PDEs) with discontinuous solutions, DeepONet poses a foundational approximation lower bound due to its linear reconstruction property. Inspired by the moving mesh (R-adaptive) method, we propose an R-adaptive DeepONet method, which contains the following components: (1) the output data representation is transformed from the physical domain to the computational domain using the equidistribution principle; (2) the maps from input parameters to the solution and the coordinate transformation function over the computational domain are learned using DeepONets separately; (3) the solution over the physical domain is obtained via post-processing methods such as the (linear) interpolation method. Additionally, we introduce a solution-dependent weighting strategy in the training process to reduce the final error. We establish an upper bound for the reconstruction error based on piecewise linear interpolation and show that the introduced R-adaptive DeepONet can reduce this bound. Moreover, for two prototypical PDEs with sharp gradients or discontinuities, we prove that the approximation error decays at a superlinear rate with respect to the trunk basis size, unlike the linear decay observed in vanilla DeepONets. Therefore, the R-adaptive DeepONet overcomes the limitations of DeepONet, and can reduce the approximation error for problems with discontinuous solutions. Numerical experiments on PDEs with discontinuous solutions, including the linear advection equation, the Burgers' equation with low viscosity, and the compressible Euler equations of gas dynamics, are conducted to verify the advantages of the R-adaptive DeepONet over available variants of DeepONet.

Estimating the maximum mean finds a variety of applications in practice. In this paper, we study estimation of the maximum mean using an upper confidence bound (UCB) approach where the sampling budget is adaptively allocated to one of the systems. We study in depth the existing grand average (GA) estimator, and propose a new largest-size average (LSA) estimator. Specifically, we establish statistical guarantees, including strong consistency, asymptotic mean squared errors, and central limit theorems (CLTs) for both estimators, which are new to the literature. We show that LSA is preferable over GA, as the bias of the former decays at a rate much faster than that of the latter when sample size increases. By using the CLTs, we further construct asymptotically valid confidence intervals for the maximum mean, and propose a single hypothesis test for a multiple comparison problem with application to clinical trials. Statistical efficiency of the resulting point and interval estimates and the proposed single hypothesis test is demonstrated via numerical examples.

In this paper, we prove the compact embedding from the variable-order Sobolev space $W^{s(x,y),p(x,y)}_0 (\Omega)$ to the Nakano space $L^{q(x)}(\Omega)$ with a critical exponent $q(x)$ satisfying some conditions. It is noteworthy that the embedding can be compact even when $q(x)$ reaches the critical Sobolev exponent $p_s^*(x)$. As an application, we obtain a nontrivial solution of the Choquard equation \begin{equation*} \displaystyle (-\Delta)_{p(\cdot,\cdot)}^{s(\cdot,\cdot)}u+|u|^{p(x,x)-2}u=\left(\int_{\Omega}\frac{|u(y)|^{r(y)}}{|x-y|^{\frac{\alpha(x)+\alpha(y)}{2}}}dy\right) |u(x)|^{r(x)-2}u(x)\quad\text{in $\Omega$} \end{equation*} with variable upper critical exponent in the sense of Hardy-Littlewood-Sobolev inequality under an appropriate boundary condition.

People are influenced by the choices of others, a phenomenon observed across contexts in the social and behavioral sciences. Social influence can lock in an initial popularity advantage of an option over a higher quality alternative. Yet several experiments designed to enable social influence have found that social systems self-correct rather than lock-in. Here we identify a behavioral phenomenon that makes inferior lock-in possible, which we call the 'marginal majority effect': A discontinuous increase in the choice probability of an option as its popularity exceeds that of a competing option. We demonstrate the existence of marginal majority effects in several recent experiments and show that lock-in always occurs when the effect is large enough to offset the quality effect on choice, but rarely otherwise. Our results reconcile conflicting past empirical evidence and connect a behavioral phenomenon to the possibility of social lock-in.

The optimal allocation of channels and power resources plays a crucial role in ensuring minimal interference, maximal data rates, and efficient energy utilisation. As a successful approach for tackling resource management problems in wireless networks, Graph Neural Networks (GNNs) have attracted a lot of attention. This article proposes a GNN-based algorithm to address the joint resource allocation problem in heterogeneous wireless networks. Concretely, we model the heterogeneous wireless network as a heterogeneous graph and then propose a graph neural network structure intending to allocate the available channels and transmit power to maximise the network throughput. Our proposed joint channel and power allocation graph neural network (JCPGNN) comprises a shared message computation layer and two task-specific layers, with a dedicated focus on channel and power allocation tasks, respectively. Comprehensive experiments demonstrate that the proposed algorithm achieves satisfactory performance but with higher computational efficiency compared to traditional optimisation algorithms.

We consider chiral, generally nonlinear density waves in one dimension, modelling the bosonized edge modes of a two-dimensional fermionic topological insulator. Using the coincidence between bosonization and Lie-Poisson dynamics on an affine U(1) group, we show that wave profiles which are periodic in time produce Berry phases accumulated by the underlying fermionic field. These phases can be evaluated in closed form for any Hamiltonian, and they serve as a diagnostic of nonlinearity. As an explicit example, we discuss the Korteweg-de Vries equation, viewed as a model of nonlinear quantum Hall edge modes.

Fusion surface models, as introduced by Inamura and Ohmori, extend the concept of anyon chains to 2+1 dimensions, taking fusion 2-categories as their input. In this work, we construct and analyze fusion surface models on the honeycomb lattice built from braided fusion 1-categories. These models preserve mutually commuting plaquette operators and anomalous 1-form symmetries. Their Hamiltonian is chosen to mimic the structure of Kitaev's honeycomb model, which is unitarily equivalent to the Ising fusion surface model. In the anisotropic limit, where one coupling constant is dominant, the fusion surface models reduce to Levin-Wen string-nets. In the isotropic limit, they are described by weakly coupled anyon chains and are likely to realize chiral topological order. We focus on three specific examples: (i) Kitaev's honeycomb model with a perturbation breaking time-reversal symmetry that realizes chiral Ising topological order, (ii) a $\mathbb{Z}_N$ generalization proposed by Barkeshli et al., which potentially realizes chiral parafermion topological order, and (iii) a novel Fibonacci honeycomb model featuring a non-invertible 1-form symmetry.

In this work, we consider non-collocated sensors and actuators, and we address the problem of minimizing the number of sensor-to-actuator transmissions while ensuring that the L2 gain of the system remains under a threshold. By using causal factorization and system level synthesis, we reformulate this problem as a rank minimization problem over a convex set. When heuristics like nuclear norm minimization are used for rank minimization, the resulting matrix is only numerically low rank and must be truncated, which can lead to an infeasible solution. To address this issue, we introduce approximate causal factorization to control the factorization error and provide a bound on the degradation of the L2 gain in terms of the factorization error. The effectiveness of our method is demonstrated using a benchmark.

This work explores the conditions under which global contraction manifests in the leaky continuous time reservoirs, thus guaranteeing Generalized Synchronization. Results on continuous time reservoirs make use of the logarithmic norm of the connectivity matrix. Further analysis yields some simple guidelines on how to better construct the connectivity matrix in these systems. Additionally, we outline how the Universal Approximation Property of discrete time reservoirs is readily satisfied by virtue of the activation function being contracting, and how continuous time reservoirs may inherit a limited form of universal approximation by virtue of them overlapping with Neural Ordinary Differential Equations. The ability of the Reservoir Computing framework to universally approximate topological conjugates, along with their fast training, make them a compelling data-driven, black-box surrogate of dynamical systems, and a potential mechanism for developing digital twins.

The emergence of learned indexes has caused a paradigm shift in our perception of indexing by considering indexes as predictive models that estimate keys' positions within a data set, resulting in notable improvements in key search efficiency and index size reduction; however, a significant challenge inherent in learned index modeling is its constrained support for update operations, necessitated by the requirement for a fixed distribution of records. Previous studies have proposed various approaches to address this issue with the drawback of high overhead due to multiple model retraining. In this paper, we present UpLIF, an adaptive self-tuning learned index that adjusts the model to accommodate incoming updates, predicts the distribution of updates for performance improvement, and optimizes its index structure using reinforcement learning. We also introduce the concept of balanced model adjustment, which determines the model's inherent properties (i.e. bias and variance), enabling the integration of these factors into the existing index model without the need for retraining with new data. Our comprehensive experiments show that the system surpasses state-of-the-art indexing solutions (both traditional and ML-based), achieving an increase in throughput of up to 3.12 times with 1000 times less memory usage.

In combinatorial optimization, matroids provide one of the most elegant structures for algorithm design. This is perhaps best identified by the Edmonds-Rado theorem relating the success of the simple greedy algorithm to the anatomy of the optimal basis of a matroid [Edm71; Rad57]. As a response, much energy has been devoted to understanding a matroid's favorable computational properties. Yet surprisingly, not much is understood where parallel algorithm design is concerned. Specifically, while prior work has investigated the task of finding an arbitrary basis in parallel computing settings [KUW88], the more complex task of finding the optimal basis remains unexplored. We initiate this study by reexamining Bor\r{u}vka's minimum weight spanning tree algorithm in the language of matroid theory, identifying a new characterization of the optimal basis by way of a matroid's cocircuits as a result. Furthermore, we then combine such insights with special properties of binary matroids to reduce optimization in a binary matroid to the simpler task of search for an arbitrary basis, with only logarithmic asymptotic overhead. Consequentially, we are able to compose our reduction with a known basis search method of [KUW88] to obtain a novel algorithm for finding the optimal basis of a binary matroid with only sublinearly many adaptive rounds of queries to an independence oracle. To the authors' knowledge, this is the first parallel algorithm for matroid optimization to outperform the greedy algorithm in terms of adaptive complexity, for any class of matroid not represented by a graph.

A Bregman manifold is a synonym for a dually flat space in information geometry which admits as a canonical divergence a Bregman divergence. Bregman manifolds are induced by smooth strictly convex functions like the cumulant or partition functions of regular exponential families, the negative entropy of mixture families, or the characteristic functions of regular cones just to list a few such convex Bregman generators. We describe the design of pyBregMan, a library which implements generic operations on Bregman manifolds and instantiate several common Bregman manifolds used in information sciences. At the core of the library is the notion of Legendre-Fenchel duality inducing a canonical pair of dual potential functions and dual Bregman divergences. The library also implements the Fisher-Rao manifolds of categorical/multinomial distributions and multivariate normal distributions. To demonstrate the use of the pyBregMan kernel manipulating those Bregman and Fisher-Rao manifolds, the library also provides several core algorithms for various applications in statistics, machine learning, information fusion, and so on.

Beyond the Sun-Earth line, spacecraft equipped with various solar telescopes are intended to be deployed at several different vantage points in the heliosphere to carry out coordinated, multi-view observations of the Sun and its dynamic activities. In this context, we investigate solar visibility by imaging instruments onboard the spacecraft orbiting the Sun-Earth Lagrange points L1, L4 and L5, respectively. An optimal arrival time for vertical periodic orbits stationed at L4 and L5 is determined based on geometric considerations that ensure maximum visibility of solar poles or higher latitudes per year. For a different set of orbits around the three Lagrange points (L1, L4 and L5), we calculate the visibility of the solar surface (i.e., observation days per year) as a function of the solar latitude. We also analyze where the solar limb viewed from one of the three Sun-Earth Lagrange points under consideration is projected onto the solar surface visible to the other two. This analysis particularly aims at determining the feasibility of studying solar eruptions, such as flares and coronal mass ejections, with coordinated observations of off-limb erupting coronal structures and their on-disk magnetic footpoints. In addition, visibility analysis of a feature (such as sunspots) on the solar surface is made for multiple spacecraft in various types of orbits with different inclinations to quantify the improvement in continuous tracking of the target feature for studying its long-term evolution from emergence, growth and to decay. A comprehensive comparison of observations from single (L1), double (L1 and L4) and multi-space missions (L1, L4 and L5) is carried out through our solar visibility analysis, and this may help us to design future space missions of constructing multiple solar observatories at the Sun-Earth Lagrange points.

Contact angle hysteresis of droplets will be examined in light of static friction between liquid drop and solid surface. Unlike frictions in solid-solid interfaces, pinning forces at contact points (2D) or contact lines (3D) would be the cause of friction. We will define coefficients of static friction and relate them with advancing and receding contact angles for the case of 2-dimensional droplets. In our work sessile drops in an inclined plane, and pendent drops in a slanted ceiling will all be analyzed within a single framework with the inclination angle as a free parameter. We can then visualize the gradual change of shapes of a droplet put on a plane as the inclination angle changes adiabatically to make a complete turn. We also point out that there could be two distinct stable configurations of pendent droplets for the same physical conditions, i.e. the bifurcation.

We construct a Weyl-gauging of strongly coupled Einsteinian-Cubic gravity (ECG) in Weyl's geometry via upgraded Weyl's curvature tensors, which include abelian gauge fields, and properly tuned compensating real scalar fields. The model is free from any dimensionful parameters. The bare ECG emerges as the lower energy limit of the Weyl-ECG in the local non-conformal-invariant vacua (i.e., broken phase) in the maximally symmetric spacetimes fixing the vacuum expectation value of the scalar field to the Planck mass scale. Here, the natural presence of (anti-) de Sitter backgrounds spontaneously breaks Weyl's local conformal symmetry akin to the Higgs mechanism, while it is radiatively broken at the renormalization scale at the one-loop level in flat vacua through the Coleman-Weinberg mechanism. The model allows anti-de Sitter and flat spaces but does not allow de Sitter to be vacuum spacetime solutions. The properties of the model deserve further exploration, specifically, those of nonperturbative (e.g., instantons and/or anti-instantons) contributions, for example, in the resurgence or tachyon condensation context requires detailed study.

The main aim of this paper is to simplify and popularise the construction from the 2013 paper by Apostolov, Calderbank, and Gauduchon, which (among other things) derives the Plebanski-Demianski family of solutions of GR using ideas of complex geometry. The starting point of this construction is the observation that the Euclidean versions of these metrics should have two different commuting complex structures, as well as two commuting Killing vector fields. After some linear algebra, this leads to an ansatz for the metrics, which is half-way to their complete determination. Kerr metric is a special 2-parameter subfamily in this class, which makes these considerations directly relevant to Kerr as well. This results in a derivation of the Kerr metric that is self-contained and elementary.

We consider the classical trapped Riesz gas, i.e., $N$ particles at positions $x_i$ in one dimension with a repulsive power law interacting potential $\propto 1/|x_i-x_j|^{k}$, with $k>-2$, in an external confining potential of the form $V(x) \sim |x|^n$. We focus on the equilibrium Gibbs state of the gas, for which the density has a finite support $[-\ell_0/2,\ell_0/2]$. We study the fluctuations of the linear statistics ${\cal L}_N = \sum_{i=1}^N f(x_i)$ in the large $N$ limit for smooth functions $f(x)$. We obtain analytic formulae for the cumulants of ${\cal L}_N$ for general $k>-2$. For long range interactions, i.e. $k<1$, which include the log-gas ($k \to 0$) and the Coulomb gas ($k =-1$) these are obtained for monomials $f(x)= |x|^m$. For short range interactions, i.e. $k>1$, which include the Calogero-Moser model, i.e. $k=2$, we compute the third cumulant of ${\cal L}_N$ for general $f(x)$ and arbitrary cumulants for monomials $f(x)= |x|^m$. We also obtain the large deviation form of the probability distribution of ${\cal L}_N$, which exhibits an "evaporation transition" where the fluctuation of ${\cal L}_N$ is dominated by the one of the largest $x_i$. In addition, in the short range case, we extend our results to a (non-smooth) indicator function $f(x)$, obtaining thereby the higher order cumulants for the full counting statistics of the number of particles in an interval $[-L/2,L/2]$. We show in particular that they exhibit an interesting scaling form as $L/2$ approaches the edge of the gas $L/\ell_0 \to 1$, which we relate to the large deviations of the emptiness probability of the complementary interval on the real line.

The paper considers implementations of some randomized algorithms in connection with obtaining a random $n^2 \times n^2$ Sudoku matrix with programming language C++. For this purpose we describes the set $\Pi_n$ of all $(2n) \times n$ matrices, consisting of elements of the set $\mathbb{Z}_n =\{ 1,2,\ldots ,n\}$, such that every row is a permutation. We emphasize the relationship between these matrices and the $n^2 \times n^2$ Sudoku matrices. An algorithm to obtain random $\Pi_n$ matrices is presented in this paper. Several auxiliary algorithms that are related to the underlying problem have been described. We evaluated all algorithms according to two criteria - probability evaluation, and time for generation of random objects and checking of belonging to a specific set. This evaluations are interesting from both theoretical and practical point of view because they are particularly useful in the analysis of computer programs.

In these decades, it has been gradually established that edge modes of a wide class of topologically ordered systems are governed by the bulk-edge correspondence and anyon condensation. The former has been studied many times because it can be summarized as the correspondence between conformal field theory and topological quantum field theory, but the latter has captured attention more recently because it suggests that one can deform the theories from one to another condensable or Witt equivalent. We reinterpret this phenomenon as the appearance of integrable flow at the edges of a topologically ordered system. By revisiting the existing phenomena from this view, one can relate the anyon condensation to the existing formalism of integrable models and their renormalization group flow. Moreover, we observe the robustness of the bulk-edge correspondence even under the existence of irrelevant perturbations at the edges. This formulation can enable one to analyze edge modes at the level of quantum fluid (non-linear) dynamics, or mixed state topological order even in non-Hermitian systems. Moreover, especially in the study of a class of non-Hermitian systems, we show a fundamental necessity to revisit Rogers-Ramanujan type identities as an appearance of the hidden (fractional) supersymmetric model which has a close relation to string field theories. Our view can give a unified paradigm to study edge modes of topologically ordered systems at the level of their dynamics potentially in both Hermitian and non-Hermitian systems.

We study the binary symmetric perceptron model, and in particular its atypical solutions. While the solution-space of this problem is dominated by isolated configurations~\cite{aubin2019storage}, it is also solvable for a certain range of constraint density $\alpha$ and threshold $\kappa$. We provide in this paper a statistical measure probing sequences of solutions, where two consecutive elements shares a strong overlap. After simplifications, we test its predictions by comparing it to Monte-Carlo simulations. We obtain good agreement and show that connected states with a Markovian correlation profile can fully decorrelate from their initialization only for $\kappa>\kappa_{\rm no-mem.\, state}$ ($\kappa_{\rm no-mem.\, state}\sim \sqrt{0.91\log(N)}$ for $\alpha=0.5$ and $N$ being the dimension of the problem). For $\kappa<\kappa_{\rm no-mem.\, state}$, we show that decorrelated sequences still exist but have a non-trivial correlations profile. To study this regime we introduce an $Ansatz$ for the correlations that we label as the nested Markov chain.

In this paper, we propose a novel construction for a symmetric encryption scheme, referred as SEBQ which is based on the structure of quasigroup. We utilize concepts of chaining like mode of operation and present a block cipher with in-built properties. We prove that SEBQ shows resistance against chosen plaintext attack (CPA) and by applying unbalanced Feistel transformation [19], it achieves security against chosen ciphertext attacks (CCA). Subsequently, we conduct an assessment of the randomness of the proposed scheme by running the NIST test suite and we analyze the impact of the initial vector, secret key and plaintext on ciphertext through an avalanche effect analysis. We also compare the results with existing schemes based on quasigroups [11,46]. Moreover, we analyze the computational complexity in terms of number of operations needed for encryption and decryption process.