Search

There has been a recent surge of powerful tools to show rapid mixing of Markov chains, via functional inequalities such as Poincar\'e inequalities. In many situations, Markov chains fail to mix rapidly from a worst-case initialization, yet are expected to approximately sample from a random initialization. For example, this occurs if the target distribution has metastable states, small clusters accounting for a vanishing fraction of the mass that are essentially disconnected from the bulk of the measure. Under such conditions, a Poincar\'e inequality cannot hold, necessitating new tools to prove sampling guarantees. We develop a framework to analyze simulated annealing, based on establishing so-called weak Poincar\'e inequalities. These inequalities imply mixing from a suitably warm start, and simulated annealing provides a way to chain such warm starts together into a sampling algorithm. We further identify a local-to-global principle to prove weak Poincar\'e inequalities, mirroring the spectral independence and localization schemes frameworks for analyzing mixing times of Markov chains. As our main application, we prove that simulated annealing samples from the Gibbs measure of a spherical spin glass for inverse temperatures up to a natural threshold, matching recent algorithms based on algorithmic stochastic localization. This provides the first Markov chain sampling guarantee that holds beyond the uniqueness threshold for spherical spin glasses, where mixing from a worst-case initialization is provably slow. As an ingredient in our proof, we prove bounds on the operator norm of the covariance matrix of spherical spin glasses in the full replica-symmetric regime. Additionally, we resolve questions related to the mixing of Glauber dynamics in the ferromagnetic Potts model from a uniform monochromatic coloring, and sampling using data-based initializations., Comment: 101 pages

Over the years, there has been extensive work on fully dynamic algorithms for classic graph problems that admit greedy solutions. Examples include $(\Delta+1)$ vertex coloring, maximal independent set, and maximal matching. For all three problems, there are randomized algorithms that maintain a valid solution after each edge insertion or deletion to the $n$-vertex graph by spending $\polylog n$ time, provided that the adversary is oblivious. However, none of these algorithms work against adaptive adversaries whose updates may depend on the output of the algorithm. In fact, even breaking the trivial bound of $O(n)$ against adaptive adversaries remains open for all three problems. For instance, in the case of $(\Delta+1)$ vertex coloring, the main challenge is that an adaptive adversary can keep inserting edges between vertices of the same color, necessitating a recoloring of one of the endpoints. The trivial algorithm would simply scan all neighbors of one endpoint to find a new available color (which always exists) in $O(n)$ time. In this paper, we break this linear barrier for the $(\Delta+1)$ vertex coloring problem. Our algorithm is randomized, and maintains a valid $(\Delta+1)$ vertex coloring after each edge update by spending $\widetilde{O}(n^{8/9})$ time with high probability., Comment: Full Version of a SODA '25 paper

In this paper, we revisit the online recoloring problem introduced recently by Azar et al. In online recoloring, there is a fixed set $V$ of $n$ vertices and an initial coloring $c_0: V\rightarrow [k]$ for some $k\in \mathbb{Z}^{>0}$. Under an online sequence $\sigma$ of requests where each request is an edge $(u_t,v_t)$, a proper vertex coloring $c$ of the graph $G_t$ induced by requests until time $t$ needs to be maintained for all $t$; i.e., for any $(u,v)\in G_t$, $c(u)\neq c(v)$. The objective is to minimize the total weight of vertices recolored for the sequence $\sigma$. We obtain the first competitive algorithms for capacitated online recoloring and fully dynamic recoloring. Our first set of results is for $2$-recoloring using algorithms that are $(1+\varepsilon)$-resource augmented where $\varepsilon\in (0,1)$ is an arbitrarily small constant. Our main result is an $O(\log n)$-competitive deterministic algorithm for weighted bipartite graphs, which is asymptotically optimal in light of an $\Omega(\log n)$ lower bound that holds for an unbounded amount of augmentation. We also present an $O(n\log n)$-competitive deterministic algorithm for fully dynamic recoloring, which is optimal within an $O(\log n)$ factor in light of a $\Omega(n)$ lower bound that holds for an unbounded amount of augmentation. Our second set of results is for $\Delta$-recoloring in an $(1+\varepsilon)$-overprovisioned setting where the maximum degree of $G_t$ is bounded by $(1-\varepsilon)\Delta$ for all $t$, and each color assigned to at most $(1+\varepsilon)\frac{n}{\Delta}$ vertices, for an arbitrary $\varepsilon > 0$. Our main result is an $O(1)$-competitive randomized algorithm for $\Delta = O(\sqrt{n/\log n})$. We also present an $O(\Delta)$-competitive deterministic algorithm for $\Delta \le \varepsilon n/2$. Both results are asymptotically optimal., Comment: Full version of an ESA '24 paper

Using high resolution Vlasov - Poisson simulations, evolution of driven ``cold" electron plasma wave (EPW) in the presence of stationary inhomogeneous background of ions is studied. Mode coupling dynamics between ``cold'' EPW with phase velocity $v_{\phi}$ greater than thermal velocity i.e $v_{\phi} \gg v_{thermal}$ and its inhomogeneity induced sidebands is illustrated as an initial value problem. In driven cases, formation of BGK like phase space structures corresponding to sideband modes due to energy exchange from primary mode to bulk particles via wave-wave and wave-particle interactions leading to particle trapping is demonstrated for inhomogeneous plasma. Qualitative comparison studies between initial value perturbation and driven problem is presented, which examines the relative difference in energy transfer time between the interacting modes. Effect of variation in background ion inhomogeneity amplitude as well as ion inhomogeneity scale length on the driven EPWs is reported.

Attention-based transformers have been remarkably successful at modeling generative processes across various domains and modalities. In this paper, we study the behavior of transformers on data drawn from \kth Markov processes, where the conditional distribution of the next symbol in a sequence depends on the previous $k$ symbols observed. We observe a surprising phenomenon empirically which contradicts previous findings: when trained for sufficiently long, a transformer with a fixed depth and $1$ head per layer is able to achieve low test loss on sequences drawn from \kth Markov sources, even as $k$ grows. Furthermore, this low test loss is achieved by the transformer's ability to represent and learn the in-context conditional empirical distribution. On the theoretical side, our main result is that a transformer with a single head and three layers can represent the in-context conditional empirical distribution for \kth Markov sources, concurring with our empirical observations. Along the way, we prove that \textit{attention-only} transformers with $O(\log_2(k))$ layers can represent the in-context conditional empirical distribution by composing induction heads to track the previous $k$ symbols in the sequence. These results provide more insight into our current understanding of the mechanisms by which transformers learn to capture context, by understanding their behavior on Markov sources., Comment: 29 pages, 10 figures

In the self-consistent dynamo limit, the magnetic feedback on the velocity field is sufficiently strong to induce a change in the topology of the magnetic field. Consequently, the magnetic energy reaches a state of non-linear saturation. Here, we investigate the role played by helical and non-helical drives in the triggering and the eventual saturation of a self-consistent dynamo. Evidence of small-scale dynamo (SSD) activity is found for both helical and non-helical forcing, driven at the largest possible scale. Based on the spectrum analysis, we find that the evolution of kinetic energy follows Kolmogorov's $k^-{\frac{5}{3}}$ law while that of magnetic energy follows Kazantsev's $k^{\frac{3}{2}}$ scaling. Also, we have verified that the aforementioned scalings remain valid for various magnetic Prandtl numbers (Pm). Statistical analysis is found to support our numerical finds.

Concentric Tube Robots (CTRs) have garnered significant interest within the surgical robotics community because of their flexibility, dexterity, and ease of miniaturization. However, mastering the unique kinematics and design principles of CTRs can be challenging for newcomers to the field. In this paper, we present an educational kit aimed at lowering the barriers to entry into concentric tube robot research. Our goal is to provide accessible learning resources for CTRs, bridging the knowledge gap between traditional robotic arms and these specialized devices. The proposed kit includes (1) An open-source design and assembly instructions for an economical (cost of materials $\approx$ 700 USD) modular CTR; (2) A set of self-study materials to learn the basics of CTR modeling and control, including automatically-graded assignments. To evaluate the effectiveness of our educational kit, we conducted a human subjects study involving first-year graduate students in engineering. Over a four-week period, participants -- none of whom had any prior knowledge of concentric tube robots -- successfully built their first CTR using the provided materials, implemented the robot's kinematics in MATLAB, and conducted a tip-tracking experiment with an optical tracking device. Our findings suggest that the proposed kit facilitates learning and hands-on experience with CTRs, and furthermore, it has the potential to help early-stage graduate students get rapidly started with CTR research. By disseminating these resources, we hope to broaden participation in concentric tube robot research to a wider a more diverse group of researchers.

We present the first analytical calculation that shows that perturbations with angular dependence can lead to an instability in gauged Q-balls. We find an explicit condition on the parameters for the Q-ball to become unstable. We compare our predictions to the numerical calculation in Kinach et al., and show agreement, including a correct prediction of the instability/stability of the two parameter points analyzed in that paper., Comment: 12 pages

Many natural Markov chains fail to mix to their stationary distribution in polynomially many steps. Often, this slow mixing is inevitable since it is computationally intractable to sample from their stationary measure. Nevertheless, Markov chains can be shown to always converge quickly to measures that are locally stationary, i.e., measures that don't change over a small number of steps. These locally stationary measures are analogous to local minima in continuous optimization, while stationary measures correspond to global minima. While locally stationary measures can be statistically far from stationary measures, do they enjoy provable theoretical guarantees that have algorithmic implications? We study this question in this work and demonstrate three algorithmic applications of locally stationary measures: 1. We show that Glauber dynamics on the hardcore model can be used to find independent sets of size $\Omega\left(\frac{\log d}{d} \cdot n\right)$ in triangle-free graphs of degree at most $d$. 2. Let $W$ be a symmetric real matrix with bounded spectral diameter and $v$ be a unit vector. Given the matrix $M = \lambda vv^\top + W$ with a planted rank-one spike along vector $v$, for sufficiently large constant $\lambda$, Glauber dynamics on the Ising model defined by $M$ samples vectors $x \in \{\pm 1\}^n$ that have constant correlation with the vector $v$. 3. Let $M = A_{\mathbf{G}} - \frac{d}{n}\mathbf{1}\mathbf{1}^\top$ be a centered version of the adjacency matrix where the graph $\mathbf{G}$ is drawn from a sparse 2-community stochastic block model. We show that for sufficiently large constant signal-to-noise ratio, Glauber dynamics on the Ising model defined by $M$ samples vectors $x \in \{\pm 1\}^n$ that have constant correlation with the hidden community vector $\mathbf{\sigma}$., Comment: 36 pages

Motivated by the community detection problem in Bayesian inference, as well as the recent explosion of interest in spin glasses from statistical physics, we study the classical Glauber dynamics for sampling from Ising models with sparse random interactions. It is now well-known that when the interaction matrix has spectral diameter less than $1$, Glauber dynamics mixes in $O(n\log n)$ steps. Unfortunately, such criteria fail dramatically for interactions supported on arguably the most well-studied sparse random graph: the Erd\H{o}s--R\'{e}nyi random graph $G(n,d/n)$, due to the presence of almost linearly many outlier eigenvalues of unbounded magnitude. We prove that for the \emph{Viana--Bray spin glass}, where the interactions are supported on $G(n,d/n)$ and randomly assigned $\pm\beta$, Glauber dynamics mixes in $n^{1+o(1)}$ time with high probability as long as $\beta \le O(1/\sqrt{d})$, independent of $n$. We further extend our results to random graphs drawn according to the $2$-community stochastic block model, as well as when the interactions are given by a "centered" version of the adjacency matrix. The latter setting is particularly relevant for the inference problem in community detection. Indeed, we use this to show that Glauber dynamics succeeds at recovering communities in the stochastic block model in a companion paper [LMR+24]. The primary technical ingredient in our proof is showing that with high probability, a sparse random graph can be decomposed into two parts -- a \emph{bulk} which behaves like a graph with bounded maximum degree and a well-behaved spectrum, and a \emph{near-forest} with favorable pseudorandom properties. We then use this decomposition to design a localization procedure that interpolates to simpler Ising models supported only on the near-forest, and then execute a pathwise analysis to establish a modified log-Sobolev inequality., Comment: 67 pages, 4 figures

While there has been a large body of research attempting to circumvent tokenization for language modeling (Clark et al., 2022; Xue et al., 2022), the current consensus is that it is a necessary initial step for designing state-of-the-art performant language models. In this paper, we investigate tokenization from a theoretical point of view by studying the behavior of transformers on simple data generating processes. When trained on data drawn from certain simple $k^{\text{th}}$-order Markov processes for $k > 1$, transformers exhibit a surprising phenomenon - in the absence of tokenization, they empirically fail to learn the right distribution and predict characters according to a unigram model (Makkuva et al., 2024). With the addition of tokenization, however, we empirically observe that transformers break through this barrier and are able to model the probabilities of sequences drawn from the source near-optimally, achieving small cross-entropy loss. With this observation as starting point, we study the end-to-end cross-entropy loss achieved by transformers with and without tokenization. With the appropriate tokenization, we show that even the simplest unigram models (over tokens) learnt by transformers are able to model the probability of sequences drawn from $k^{\text{th}}$-order Markov sources near optimally. Our analysis provides a justification for the use of tokenization in practice through studying the behavior of transformers on Markovian data., Comment: 58 pages, 10 figures

We study the dependence of alignment and confinement on the aggregate morphology of self-aligning soft disks in a planer box geometry confined along y direction. We show that the wall accumulation of aggregates becomes non-uniform upon increase in alignment strength and decrease in box width. The height of these structures is found to be a non-monotonic function of alignment strength. Additionally, we identify two distinct categories of wall aggregates: layered and non-layered structures each exhibiting distinct local structural properties. For non-layered structures, local properties stay nearly constant as we move away from the boundary, while for layered structures, they increase with distance from the boundary. Our analysis shows that active pressure difference is a useful indicator for different aggregate morphologies and the peaks in the pressure curve are indicative of the average and minimum height of the structure.

Major cryptocurrency networks have relied on random peering choice rules for making connections in their peer-to-peer networks. Generally, these choices have good properties, particularly for open, permissionless networks. Random peering choices however do not take into account that some actors may choose to optimize who they connect to such that they are quicker to hear about information being propagated in the network. In this paper, we explore the dynamics of such greedy strategies. We study a model in which nodes select peers with the objective of minimizing their average distance to a designated subset of nodes in the network, and consider the impact of several factors including the peer selection process, degree constraints, and the size of the designated subset. The latter is particularly interesting in the context of blockchain networks as generally only a subset of nodes are the propagation source for content. We first analyze an idealized version of the game where each node has full knowledge of the current network and aims to select the $d$ best connections, and prove the existence of equilibria under various model assumptions. Since in reality nodes only have local knowledge based on their peers' behavior, we also study a greedy protocol which runs in rounds, with each node replacing its worst-performing edge with a new random edge. We exactly characterize stability properties of networks that evolve with this peering rule and derive regimes where stability is possible and even inevitable. We also run extensive simulations with this peering rule examining both how the network evolves and how different network parameters affect the stability properties of the network. Our findings generally show that the only stable networks that arise from greedy peering choices are low-diameter and result in disparate performance for nodes in the network.

We provide a thorough comparison of the GMHD3D code and the PLUTO4.4 code for both two and three-dimensional hydrodynamic and magnetohydrodynamic problems. The open-source finite-volume solver PLUTO4.4 and the in-house developed pseudo-spectral multi-GPU solver GMHD3D both can be used to model the dynamics and turbulent motions of astrophysical plasmas. Although GMHD3D and PLUTO4.4 utilize different implementations, it is found that simulation results for hydrodynamic and magnetohydrodynamic problems, such as the rate of instability growth, 3-dimensional turbulent dynamics, oscillation of kinetic & magnetic energy, and recurrence dynamics, are remarkably similar. However, it is shown that the pseudo spectral solver GMHD3D is significantly more superior than the grid based solver PLUTO4.4 for certain category of physics problems.

Motivated by deep neural network applications, we study the problem of scheduling splittable jobs (e.g., neural network inference tasks) on configurable machines (e.g., multi-instance GPUs). We are given $n$ jobs and a set $C$ of configurations (e.g, representing ways to configure a GPU) consisting of multisets of blocks (e.g., representing GPU instances). A schedule consists of a set of machines, each assigned some configuration in $C$ with each block in the configuration assigned to process one job. The amount of a job's demand that is satisfied by a given block is an arbitrary function of the job and block. The objective is to satisfy all demands on as few machines as possible. We provide a tight logarithmic approximation algorithm for this problem in the general setting, an asymptotic $(2 + \varepsilon)$-approximation with $O(1)$ input configurations for arbitrary $\varepsilon > 0$, and a polynomial time approximation scheme when both the number and size of configurations are $O(1)$.

This paper describes our system for addressing SMM4H 2023 Shared Task 2 on "Classification of sentiment associated with therapies (aspect-oriented)". In our work, we adopt an approach based on Natural language inference (NLI) to formulate this task as a sentence pair classification problem, and train transformer models to predict sentiment associated with a therapy on a given text. Our best model achieved 75.22\% F1-score which was 11\% (4\%) more than the mean (median) score of all teams' submissions., Comment: Accepted in Workshop on Social Media Mining for Health 2023 (#SMM4H)

Consider public health officials aiming to spread awareness about a new vaccine in a community interconnected by a social network. How can they distribute information with minimal resources, so as to avoid polarization and ensure community-wide convergence of opinion? To tackle such challenges, we initiate the study of sample complexity of opinion convergence in networks. Our framework is built on the recognized opinion formation game, where we regard the opinion of each agent as a data-derived model, unlike previous works that treat opinions as data-independent scalars. The opinion model for every agent is initially learned from its local samples and evolves game-theoretically as all agents communicate with neighbors and revise their models towards an equilibrium. Our focus is on the sample complexity needed to ensure that the opinions converge to an equilibrium such that the final model of every agent has low generalization error. Our paper has two main technical results. First, we present a novel polynomial time optimization framework to quantify the total sample complexity for arbitrary networks, when the underlying learning problem is (generalized) linear regression. Second, we leverage this optimization to study the network gain which measures the improvement of sample complexity when learning over a network compared to that in isolation. Towards this end, we derive network gain bounds for various network classes including cliques, star graphs, and random regular graphs. Additionally, our framework provides a method to study sample distribution within the network, suggesting that it is sufficient to allocate samples inversely to the degree. Empirical results on both synthetic and real-world networks strongly support our theoretical findings.

We perform a general analysis of thin-wall Q-balls in AdS space. We provide numeric solutions and highly accurate analytic approximations over much of the parameter space. These analytic solutions show that AdS Q-balls exhibit significant differences from the corresponding flat space solitons. This includes having a maximum radius beyond which the Q-balls are unstable to a new type of state where the Q-ball coexists with a gas of massive particles. The phase transition to this novel state is found to be a zero-temperature third-order transition. This, through the AdS/CFT correspondence, has implications for a scalar condensate in the boundary theory., Comment: 21 pages, 10 figures. Updated to published version

Model initialization techniques are vital for improving the performance and reliability of deep learning models in medical computer vision applications. While much literature exists on non-medical images, the impacts on medical images, particularly chest X-rays (CXRs) are less understood. Addressing this gap, our study explores three deep model initialization techniques: Cold-start, Warm-start, and Shrink and Perturb start, focusing on adult and pediatric populations. We specifically focus on scenarios with periodically arriving data for training, thereby embracing the real-world scenarios of ongoing data influx and the need for model updates. We evaluate these models for generalizability against external adult and pediatric CXR datasets. We also propose novel ensemble methods: F-score-weighted Sequential Least-Squares Quadratic Programming (F-SLSQP) and Attention-Guided Ensembles with Learnable Fuzzy Softmax to aggregate weight parameters from multiple models to capitalize on their collective knowledge and complementary representations. We perform statistical significance tests with 95% confidence intervals and p-values to analyze model performance. Our evaluations indicate models initialized with ImageNet-pre-trained weights demonstrate superior generalizability over randomly initialized counterparts, contradicting some findings for non-medical images. Notably, ImageNet-pretrained models exhibit consistent performance during internal and external testing across different training scenarios. Weight-level ensembles of these models show significantly higher recall (p<0.05) during testing compared to individual models. Thus, our study accentuates the benefits of ImageNet-pretrained weight initialization, especially when used with weight-level ensembles, for creating robust and generalizable deep learning solutions., Comment: 40 pages, 8 tables, 7 figures, 3 supplementary figures and 4 supplementary tables

Deep learning (DL) has demonstrated its innate capacity to independently learn hierarchical features from complex and multi-dimensional data. A common understanding is that its performance scales up with the amount of training data. Another data attribute is the inherent variety. It follows, therefore, that semantic redundancy, which is the presence of similar or repetitive information, would tend to lower performance and limit generalizability to unseen data. In medical imaging data, semantic redundancy can occur due to the presence of multiple images that have highly similar presentations for the disease of interest. Further, the common use of augmentation methods to generate variety in DL training may be limiting performance when applied to semantically redundant data. We propose an entropy-based sample scoring approach to identify and remove semantically redundant training data. We demonstrate using the publicly available NIH chest X-ray dataset that the model trained on the resulting informative subset of training data significantly outperforms the model trained on the full training set, during both internal (recall: 0.7164 vs 0.6597, p<0.05) and external testing (recall: 0.3185 vs 0.2589, p<0.05). Our findings emphasize the importance of information-oriented training sample selection as opposed to the conventional practice of using all available training data., Comment: 3 Tables, 11 Figures, 20 pages

A spanning tree $T$ of graph $G$ is a $\rho$-approximate universal Steiner tree (UST) for root vertex $r$ if, for any subset of vertices $S$ containing $r$, the cost of the minimal subgraph of $T$ connecting $S$ is within a $\rho$ factor of the minimum cost tree connecting $S$ in $G$. Busch et al. (FOCS 2012) showed that every graph admits $2^{O(\sqrt{\log n})}$-approximate USTs by showing that USTs are equivalent to strong sparse partition hierarchies (up to poly-logs). Further, they posed poly-logarithmic USTs and strong sparse partition hierarchies as open questions. We settle these open questions by giving polynomial-time algorithms for computing both $O(\log ^ 7 n)$-approximate USTs and poly-logarithmic strong sparse partition hierarchies. For graphs with constant doubling dimension or constant pathwidth we improve this to $O(\log n)$-approximate USTs and $O(1)$ strong sparse partition hierarchies. Our doubling dimension result is tight up to second order terms. We reduce the existence of these objects to the previously studied cluster aggregation problem and what we call dangling nets., Comment: @FOCS23

Understanding the origin and structure of mean magnetic fields in astrophysical conditions is a major challenge. Shear flows often coexist in such astrophysical conditions and the role of flow shear on dynamo mechanism is only beginning to be investigated. Here, we present a direct numerical simulation (DNS) study of the effect of flow shear on dynamo instability for a variety of base flows with controllable mirror symmetry (i.e, fluid helicity). Our observations suggest that for helical base flow, the effect of shear is to suppress the small scale dynamo (SSD) action, i.e, shear helps the large scale magnetic field to manifest itself by suppressing SSD action. For non-helical base flows, flow shear has the opposite effect of amplifying the small-scale dynamo action. The magnetic energy growth rate ($\gamma$) for non-helical base flows are found to follow an algebraic nature of the form, $\gamma = - aS + bS^\frac{2}{3}$ , where a, b > 0 are real constants and S is the shear flow strength and $\gamma$ is found to be independent of scale of flow shear. Studies with different shear profiles and shear scale lengths for non-helical base flows have been performed to test the universality of our finding.

Pruning schemes have been widely used in practice to reduce the complexity of trained models with a massive number of parameters. In fact, several practical studies have shown that if a pruned model is fine-tuned with some gradient-based updates it generalizes well to new samples. Although the above pipeline, which we refer to as pruning + fine-tuning, has been extremely successful in lowering the complexity of trained models, there is very little known about the theory behind this success. In this paper, we address this issue by investigating the pruning + fine-tuning framework on the overparameterized matrix sensing problem with the ground truth $U_\star \in \mathbb{R}^{d \times r}$ and the overparameterized model $U \in \mathbb{R}^{d \times k}$ with $k \gg r$. We study the approximate local minima of the mean square error, augmented with a smooth version of a group Lasso regularizer, $\sum_{i=1}^k \| U e_i \|_2$. In particular, we provably show that pruning all the columns below a certain explicit $\ell_2$-norm threshold results in a solution $U_{\text{prune}}$ which has the minimum number of columns $r$, yet close to the ground truth in training loss. Moreover, in the subsequent fine-tuning phase, gradient descent initialized at $U_{\text{prune}}$ converges at a linear rate to its limit. While our analysis provides insights into the role of regularization in pruning, we also show that running gradient descent in the absence of regularization results in models which {are not suitable for greedy pruning}, i.e., many columns could have their $\ell_2$ norm comparable to that of the maximum. To the best of our knowledge, our results provide the first rigorous insights on why greedy pruning + fine-tuning leads to smaller models which also generalize well., Comment: 49 pages, 2 figures

Q-balls are non-topological solitons arising in scalar field theories. Solutions for rotating Q-balls (and the related boson stars) have been shown to exist when the angular momentum is equal to an integer multiple of the Q-ball charge $Q$. Here we consider the possibility of classically long-lived metastable rotating Q-balls with small angular momentum, even for large charge, for all scalar theories that support non-rotating Q-balls. This is relevant for rotating extensions of Q-balls and related solitons such as boson stars as it impacts their cosmological phenomenology., Comment: 17 pages; major revision, matches EPJC version

We consider the sequential decision-making problem where the mean outcome is a non-linear function of the chosen action. Compared with the linear model, two curious phenomena arise in non-linear models: first, in addition to the "learning phase" with a standard parametric rate for estimation or regret, there is an "burn-in period" with a fixed cost determined by the non-linear function; second, achieving the smallest burn-in cost requires new exploration algorithms. For a special family of non-linear functions named ridge functions in the literature, we derive upper and lower bounds on the optimal burn-in cost, and in addition, on the entire learning trajectory during the burn-in period via differential equations. In particular, a two-stage algorithm that first finds a good initial action and then treats the problem as locally linear is statistically optimal. In contrast, several classical algorithms, such as UCB and algorithms relying on regression oracles, are provably suboptimal., Comment: Revised Section 3 and added an upper bound agnostic to the link function $f$