Search

We study the regret in stochastic Multi-Armed Bandits (MAB) with multiple agents that communicate over an arbitrary connected communication graph. We show a near-optimal individual regret bound of $\tilde{O}(\sqrt{AT/m}+A)$, where $A$ is the number of actions, $T$ the time horizon, and $m$ the number of agents. In particular, assuming a sufficient number of agents, we achieve a regret bound of $\tilde{O}(A)$, which is independent of the sub-optimality gaps and the diameter of the communication graph. To the best of our knowledge, our study is the first to show an individual regret bound in cooperative stochastic MAB that is independent of the graph's diameter and applicable to non-fully-connected communication graphs., Comment: 42 pages, 1 figure

In many repeated auction settings, participants care not only about how frequently they win but also how their winnings are distributed over time. This problem arises in various practical domains where avoiding congested demand is crucial, such as online retail sales and compute services, as well as in advertising campaigns that require sustained visibility over time. We introduce a simple model of this phenomenon, modeling it as a budgeted auction where the value of a win is a concave function of the time since the last win. This implies that for a given number of wins, even spacing over time is optimal. We also extend our model and results to the case when not all wins result in "conversions" (realization of actual gains), and the probability of conversion depends on a context. The goal is to maximize and evenly space conversions rather than just wins. We study the optimal policies for this setting in second-price auctions and offer learning algorithms for the bidders that achieve low regret against the optimal bidding policy in a Bayesian online setting. Our main result is a computationally efficient online learning algorithm that achieves $\tilde O(\sqrt T)$ regret. We achieve this by showing that an infinite-horizon Markov decision process (MDP) with the budget constraint in expectation is essentially equivalent to our problem, even when limiting that MDP to a very small number of states. The algorithm achieves low regret by learning a bidding policy that chooses bids as a function of the context and the system's state, which will be the time elapsed since the last win (or conversion). We show that state-independent strategies incur linear regret even without uncertainty of conversions. We complement this by showing that there are state-independent strategies that, while still having linear regret, achieve a $(1-\frac 1 e)$ approximation to the optimal reward.

We establish two theorems that illustrate the uniqueness of inverse q-Sturm-Liouville problems based on a specified set of spectral data. The first uniqueness theorem employs the method of transformation operators to provide a q-analog of the Levinson-Marchenko uniqueness theorem. The second uniqueness theorem is a q-analog of the Ashrafyan uniqueness theorem. We introduced a q-analog of the Gelfand-Levitan approach, which involves converting q-difference operators into q-integral operators to prove the theorem.

We introduce efficient differentially private (DP) algorithms for several linear algebraic tasks, including solving linear equalities over arbitrary fields, linear inequalities over the reals, and computing affine spans and convex hulls. As an application, we obtain efficient DP algorithms for learning halfspaces and affine subspaces. Our algorithms addressing equalities are strongly polynomial, whereas those addressing inequalities are weakly polynomial. Furthermore, this distinction is inevitable: no DP algorithm for linear programming can be strongly polynomial-time efficient.

The second law of thermodynamics stipulates that entropy production is non-negative in macroscopic systems, reaching zero at thermodynamic equilibrium. As a corollary, this implies that the state trajectory of macroscopic systems is inherently time-irreversible under out-of-equilibrium conditions. However, over the past half-century, various studies have demonstrated that this principle does not hold for the composition sample path of some isothermal reactive systems. Theoretical frameworks leading to this unexpected observation primarily focus on zero-dimensional (perfectly homogeneous) systems, which exclude the effect of local fluctuations. This oversimplification might account for the paradoxical theoretical prediction. In the absence of pertinent experimental data, this paper aims to investigate this phenomenon through microscopic simulations.

Developing language model-based dialogue agents requires effective data to train models that can follow specific task logic. However, most existing data augmentation methods focus on increasing diversity in language, topics, or dialogue acts at the utterance level, largely neglecting a critical aspect of task logic diversity at the dialogue level. This paper proposes a novel data augmentation method designed to enhance the diversity of synthetic dialogues by focusing on task execution logic. Our method uses LLMs to generate decision tree-structured task plans, which enables the derivation of diverse dialogue trajectories for a given task. Each trajectory, referred to as a "dialog flow", guides the generation of a multi-turn dialogue that follows a unique trajectory. We apply this method to generate a task-oriented dialogue dataset comprising 3,886 dialogue flows across 15 different domains. We validate the effectiveness of this dataset using the next action prediction task, where models fine-tuned on our dataset outperform strong baselines, including GPT-4. Upon acceptance of this paper, we plan to release the code and data publicly., Comment: 16 pages

We investigate the possibility of electromagnetic fields leaving imprints on gravitational wave (GW) signals from Neutron Star-Black hole (NSBH) mergers, specifically in the context of extreme mass ratio inspirals (EMRIs). Using black hole perturbation theory (BHPT) in the context of a minimally coupled Einstein-Maxwell system, we demonstrate that electromagnetic quasi normal modes(QNMs) can excite gravitational QNMs with frequencies that are linear or quadratic in the electromagnetic QNMs, at first level of mixing. Moreover, We then study the electromagnetism-gravity coupling by approximating the Regge-Wheeler and Zerilli potentials with Dirac delta functions. In this example, we examine gravitational perturbations induced by the electromagnetic field of an ideal dipole radially free fall towards the blackhole, building on calculations from a companion paper [1]. Our results show that both linear and quadratic electromagnetic QNMs appear in gravitational perturbations. In addition, linear gravitational QNMs are also excited due to the electromagnetic source, with their amplitudes depending on the details of the electromagnetic and gravitational potentials, analogous to gravitational mode mixing analysis. Furthermore, at late stages, gravitational perturbations might exhibit polynomial tails induced by electromagnetic perturbations. This article sets the stage for future numerical investigations aimed at identifying such modes in various scenarios., Comment: 27 pages, and 3 figures

Document-grounded dialogue systems aim to answer user queries by leveraging external information. Previous studies have mainly focused on handling free-form documents, often overlooking structured data such as lists, which can represent a range of nuanced semantic relations. Motivated by the observation that even advanced language models like GPT-3.5 often miss semantic cues from lists, this paper aims to enhance question answering (QA) systems for better interpretation and use of structured lists. To this end, we introduce the LIST2QA dataset, a novel benchmark to evaluate the ability of QA systems to respond effectively using list information. This dataset is created from unlabeled customer service documents using language models and model-based filtering processes to enhance data quality, and can be used to fine-tune and evaluate QA models. Apart from directly generating responses through fine-tuned models, we further explore the explicit use of Intermediate Steps for Lists (ISL), aligning list items with user backgrounds to better reflect how humans interpret list items before generating responses. Our experimental results demonstrate that models trained on LIST2QA with our ISL approach outperform baselines across various metrics. Specifically, our fine-tuned Flan-T5-XL model shows increases of 3.1% in ROUGE-L, 4.6% in correctness, 4.5% in faithfulness, and 20.6% in completeness compared to models without applying filtering and the proposed ISL method.

Let $G=(V,E)$ be a strongly connected graph with $|V|\geq 3$. For $T\subseteq V$, the strongly connected graph $G$ is $2$-T-connected if $G$ is $2$-edge-connected and for each vertex $w$ in $T$, $w$ is not a strong articulation point. This concept generalizes the concept of $2$-vertex connectivity when $T$ contains all the vertices in $G$. This concept also generalizes the concept of $2$-edge connectivity when $|T|=0$. The concept of $2$-T-connectivity was introduced by Durand de Gevigney and Szigeti in $2018$. In this paper, we prove that there is a polynomial-time 4-approximation algorithm for the following problem: given a $2$-T-connected graph $G=(V,E)$, identify a subset $E^ {2T} \subseteq E$ of minimum cardinality such that $(V,E^{2T})$ is $2$-T-connected.

Purpose: Demonstrate quantitative characterization of 3D patient-specific absorbed dose distributions using Haralick texture analysis and interpret measures in terms of underlying physics and radiation dosimetry. Methods: Retrospective analysis is performed for 137 patients who underwent permanent implant prostate brachytherapy using two simulation conditions: ``TG186'' (realistic tissues including 0-3.8% intraprostatic calcifications; interseed attenuation) and ``TG43'' (water-model; no interseed attenuation). Haralick features (homogeneity, contrast, correlation, local homogeneity, entropy) are calculated using the original Haralick formalism, and a modified approach designed to reduce grey-level quantization sensitivity. Trends in textural features are compared to clinical dosimetric measures (D90; minimum absorbed dose to the hottest 90% of a volume) and changes in patient target volume % intraprostatic calcifications by volume (%IC). Results: Both original and modified measures quantify the spatial differences in absorbed dose distributions. Strong correlations between differences in textural measures calculated under TG43 and TG186 conditions and %IC are observed for all measures. For example, differences between measures of contrast and correlation increase and decrease respectively as patients with higher levels of %IC are evaluated, reflecting the large differences across adjacent voxels (higher dose in voxels with calcification) when calculated under TG186 conditions. Conversely, the D90 metric is relatively weakly correlated with textural measures, as it generally does not characterize the spatial distribution of absorbed dose. Conclusion: patient-specific 3D dose distributions may be quantified using Haralick analysis, and trends may be interpreted in terms of fundamental physics.

Efficiently trading off exploration and exploitation is one of the key challenges in online Reinforcement Learning (RL). Most works achieve this by carefully estimating the model uncertainty and following the so-called optimistic model. Inspired by practical ensemble methods, in this work we propose a simple and novel batch ensemble scheme that provably achieves near-optimal regret for stochastic Multi-Armed Bandits (MAB). Crucially, our algorithm has just a single parameter, namely the number of batches, and its value does not depend on distributional properties such as the scale and variance of the losses. We complement our theoretical results by demonstrating the effectiveness of our algorithm on synthetic benchmarks.

We investigate a magnetic dipolar system influenced by Zeeman splitting, DM interaction, and KSEA exchange interaction, with an initial focus on quantum resource dynamics and a final application in modeling a quantum battery (QB). We analyze the effects of dephasing noise and thermal equilibrium on quantum resources, such as the $l_1$-norm of coherence, quantum discord, and concurrence, by solving the Lindblad master equation and evaluating the Gibbs state. Our findings indicate that increased Zeeman splitting diminishes quantum resources under dephasing and thermal equilibrium conditions. However, when we use the Hamiltonian of this system to realize our QB, Zeeman splitting boosts performance metrics such as ergotropy, instantaneous power, capacity, and quantum coherence during cyclic charging. We observe that the axial parameter improves QB performance, with coherence reaching a saturation point, beyond which ergotropy continues to rise, introducing the concept of incoherent ergotropy and highlighting the need to understand its true origin. Both KSEA interaction and the rhombic parameter consistently enhance quantum resources across the dephasing and thermal equilibrium regimes, and thus improve QB performance. The DM interaction improves QB metrics and shields quantum resources against temperature variations in the Gibbs state but remains insensitive during dephasing dynamics. Our work uncovers complex trends, including ergotropy enhancement without quantum coherence, the preferential role of QB capacity over quantum coherence, and the phenomenon of no-work extraction despite the presence of quantum coherence. These findings facilitate a robust foundation for future research on magnetic dipolar QBs, emphasizing non-unitary charging processes, environmental effects, and practical implementations. We show that the NMR platform could be a promising testbed for simulating such QBs., Comment: 17 pages, 10 figures. All comments are welcome

This article presents a new approach based on MiniRocket, called SelF-Rocket, for fast time series classification (TSC). Unlike existing approaches based on random convolution kernels, it dynamically selects the best couple of input representations and pooling operator during the training process. SelF-Rocket achieves state-of-the-art accuracy on the University of California Riverside (UCR) TSC benchmark datasets.

Recent advancements in monocular neural depth estimation, particularly those achieved by the UniDepth network, have prompted the investigation of integrating UniDepth within a Gaussian splatting framework for monocular SLAM.This study presents UDGS-SLAM, a novel approach that eliminates the necessity of RGB-D sensors for depth estimation within Gaussian splatting framework. UDGS-SLAM employs statistical filtering to ensure local consistency of the estimated depth and jointly optimizes camera trajectory and Gaussian scene representation parameters. The proposed method achieves high-fidelity rendered images and low ATERMSE of the camera trajectory. The performance of UDGS-SLAM is rigorously evaluated using the TUM RGB-D dataset and benchmarked against several baseline methods, demonstrating superior performance across various scenarios. Additionally, an ablation study is conducted to validate design choices and investigate the impact of different network backbone encoders on system performance.

In this paper, we investigate a variant of the classical stochastic Multi-armed Bandit (MAB) problem, where the payoff received by an agent (either cost or reward) is both delayed, and directly corresponds to the magnitude of the delay. This setting models faithfully many real world scenarios such as the time it takes for a data packet to traverse a network given a choice of route (where delay serves as the agent's cost); or a user's time spent on a web page given a choice of content (where delay serves as the agent's reward). Our main contributions are tight upper and lower bounds for both the cost and reward settings. For the case that delays serve as costs, which we are the first to consider, we prove optimal regret that scales as $\sum_{i:\Delta_i > 0}\frac{\log T}{\Delta_i} + d^*$, where $T$ is the maximal number of steps, $\Delta_i$ are the sub-optimality gaps and $d^*$ is the minimal expected delay amongst arms. For the case that delays serves as rewards, we show optimal regret of $\sum_{i:\Delta_i > 0}\frac{\log T}{\Delta_i} + \bar{d}$, where $\bar d$ is the second maximal expected delay. These improve over the regret in the general delay-dependent payoff setting, which scales as $\sum_{i:\Delta_i > 0}\frac{\log T}{\Delta_i} + D$, where $D$ is the maximum possible delay. Our regret bounds highlight the difference between the cost and reward scenarios, showing that the improvement in the cost scenario is more significant than for the reward. Finally, we accompany our theoretical results with an empirical evaluation.

This paper investigates quantum obesity (QO), quantum discord (QD), and the quantum steering ellipsoid (QSE) for bipartite Gisin states subjected to Garfinkle-Horowitz-Strominger (GHS) dilation of spacetime on the second qubit. These three quantifiers are introduced to characterize quantum correlations beyond entanglement and can also function as entanglement witnesses. Our results demonstrate a monotonic decrease in the physical accessibility of both QD and QO as the dilation parameter increases within the region-I of the second qubit. Conversely, in the anti-particle region, the accessibility of QD and QO stabilizes at finite values of the dilation parameter owing to the influence of the Pauli exclusion principle and Fermi-Dirac statistics, subsequently increasing gradually. Notably, the QSE in the region-I expands as the Dirac field frequency rises and the dilation parameter diminishes, while the opposite trend is observed in the anti-particle region., Comment: 11pages, 7 figures

We investigate the ability of the Euclid telescope to detect galaxy-scale gravitational lenses. To do so, we perform a systematic visual inspection of the $0.7\,\rm{deg}^2$ Euclid ERO data towards the Perseus cluster using both the high-resolution VIS $I_{\scriptscriptstyle\rm E}$ band, and the lower resolution NISP bands. We inspect every extended source brighter than magnitude $23$ in $I_{\scriptscriptstyle\rm E}$ with $41$ expert human classifiers. This amounts to $12\,086$ stamps of $10^{\prime\prime}\,\times\,10^{\prime\prime}$. We find $3$ grade A and $13$ grade B candidates. We assess the validity of these $16$ candidates by modelling them and checking that they are consistent with a single source lensed by a plausible mass distribution. Five of the candidates pass this check, five others are rejected by the modelling and six are inconclusive. Extrapolating from the five successfully modelled candidates, we infer that the full $14\,000\,{\rm deg}^2$ of the Euclid Wide Survey should contain $100\,000^{+70\,000}_{-30\,000}$ galaxy-galaxy lenses that are both discoverable through visual inspection and have valid lens models. This is consistent with theoretical forecasts of $170\,000$ discoverable galaxy-galaxy lenses in Euclid. Our five modelled lenses have Einstein radii in the range $0.\!\!^{\prime\prime}68\,<\,\theta_\mathrm{E}\,<1.\!\!^{\prime\prime}24$, but their Einstein radius distribution is on the higher side when compared to theoretical forecasts. This suggests that our methodology is likely missing small Einstein radius systems. Whilst it is implausible to visually inspect the full Euclid data set, our results corroborate the promise that Euclid will ultimately deliver a sample of around $10^5$ galaxy-scale lenses., Comment: 21 pages, 20 figures, submitted to A&A

Engineering magnetism in layered magnets could result in novel phenomena related to two-dimensional (2D) magnetism, which can be useful for fundamental research and practical applications. Extensive doping efforts such as substitution and intercalation have been adopted to tune antiferromagnetic (AFM) properties in M2P2X6 compounds. The substitutional doping in this material family has mainly focused on bimetallic substitution. Recently, the metal substitution can also be extended to more than two metal elements, leading to medium and high-entropy alloys (MEAs and HEAs), which are fairly underexplored in layered magnetic systems including M2P2X6. In this work, we explored the magnetic properties of the previously unreported Cu- and Cr-substituted Ni2P2S6 i.e., CuxNi2(1-x)CrxP2S6. Our study reveals a relatively systematic evolution of AFM phases with substitution than that observed in traditional bimetallic substitution in M2P2X6. Furthermore, the Cu and Cr substitutions in Ni2P2S6 are found to enhance the ferromagnetic (FM) correlation, which is also accompanied by a possible weak FM phase at low temperatures for the intermediate compositions from 0.32 to 0.80. Our work provides a strategy to establish ferromagnetism in AFM M2P2X6 that can also be used for property tuning in other layered magnets.

We present ALLaM: Arabic Large Language Model, a series of large language models to support the ecosystem of Arabic Language Technologies (ALT). ALLaM is carefully trained considering the values of language alignment and knowledge transfer at scale. Our autoregressive decoder-only architecture models demonstrate how second-language acquisition via vocabulary expansion and pretraining on a mixture of Arabic and English text can steer a model towards a new language (Arabic) without any catastrophic forgetting in the original language (English). Furthermore, we highlight the effectiveness of using parallel/translated data to aid the process of knowledge alignment between languages. Finally, we show that extensive alignment with human preferences can significantly enhance the performance of a language model compared to models of a larger scale with lower quality alignment. ALLaM achieves state-of-the-art performance in various Arabic benchmarks, including MMLU Arabic, ACVA, and Arabic Exams. Our aligned models improve both in Arabic and English from their base aligned models.

This paper introduces a new macroscopic perspective for simulating transportation networks. The idea is to look at the network as connected nodes. Each node sends an information package to its neighbors. Basically, the information package contains a state change that a specific node experienced, and it might affect the traffic network state in the future. Different types of information can be counted in transportation network. Each information type has different characteristics. It propagates through the network and interacts with other IPs and nodes. As a result, the model enables implementing and analyzing dynamic and inconvenient control strategies. This paper focus on flow dynamics and demand routing information under complex environment. The flow dynamics flows the LWR theory along the links. The demand routing follows a node equilibrium model. The node model takes into account the users preferences and choices under dynamic control agents such as dynamic tolling and sends the needed information for other facilities to operate. A DNL model is developed based on the IPM. Several case studies demonstrate the use IPM and its potential to provide a reliable and results for real world complicated transportation applications.

Wi-Fi channel measurements across different bands, e.g., sub-7-GHz and 60-GHz bands, are asynchronous due to the uncoordinated nature of distinct standards protocols, e.g., 802.11ac/ax/be and 802.11ad/ay. Multi-band Wi-Fi fusion has been considered before on a frame-to-frame basis for simple classification tasks, which does not require fine-time-scale alignment. In contrast, this paper considers asynchronous sequence-to-sequence fusion between sub-7-GHz channel state information (CSI) and 60-GHz beam signal-to-noise-ratio~(SNR)s for more challenging tasks such as continuous coordinate estimation. To handle the timing disparity between asynchronous multi-band Wi-Fi channel measurements, this paper proposes a multi-band neural dynamic fusion (NDF) framework. This framework uses separate encoders to embed the multi-band Wi-Fi measurement sequences to separate initial latent conditions. Using a continuous-time ordinary differential equation (ODE) modeling, these initial latent conditions are propagated to respective latent states of the multi-band channel measurements at the same time instances for a latent alignment and a post-ODE fusion, and at their original time instances for measurement reconstruction. We derive a customized loss function based on the variational evidence lower bound (ELBO) that balances between the multi-band measurement reconstruction and continuous coordinate estimation. We evaluate the NDF framework using an in-house multi-band Wi-Fi testbed and demonstrate substantial performance improvements over a comprehensive list of single-band and multi-band baseline methods., Comment: 13 pages, 13 figures, 4 tables

Recently, layered materials transition metal thiophosphate MPX3 (M = transition metals, X = S or Se) have gained significant attention because of their rich magnetic, optical, and electronic properties. Specifically, the diverse magnetic structures and the robustness of magnetism in the two-dimensional limit have made them prominent candidates to study two-dimensional magnetism. Numerous efforts such as substitutions and interlayer intercalations have been made to tune the properties of these materials, which has greatly deepened the understanding of the underlying mechanisms that govern the properties. In this work, we focus on modifying the magnetism of Ising-type antiferromagnet FePS3 using electrochemical lithium intercalation. Our work unveils the effectiveness of electrochemical intercalation as a controllable tool to modulating magnetism, including tuning magnetic ordering temperature and inducing low temperature spin-glass state, offering an approach for implementing this material into applications.

In this study, we investigate the influence of Hawking decoherence on the quantum correlations of Dirac fields between \textit{Alice} and \textit{Bob}. Initially, they share a \textit{Gisin} state near the Schwarzschild black hole (SBH) in an asymptotically flat region. Then, \textit{Alice} remains stationary in this region, while \textit{Bob} hovers near the event horizon (EH) of the SBH. We expect that \textit{Bob}, using his excited detector, will detect a thermal Fermi-Dirac particle distribution. We assess the quantum correlations in the evolved \textit{Gisin} state using quantum consonance and uncertainty-induced non-locality across physically accessible, physically inaccessible, and spacetime regions. Our investigation examines how these measures vary with Hawking temperature, Dirac particle frequency, and the parameters of the initial \textit{Gisin} state. Additionally, we analyze the distribution of these quantum correlation measures across all possible regions, noting a redistribution towards the physically inaccessible region. Our findings demonstrate that Hawking decoherence reduces the quantum correlations of Dirac fields in the physically accessible region, with the extent of reduction depending on the initial state parameters. Moreover, as Hawking decoherence intensifies in the physically inaccessible and spacetime regions, the quantum correlations of Dirac fields reemerge and ultimately converge to specific values at infinite Hawking temperature. These results contribute to our understanding of quantum correlation dynamics within the framework of relativistic quantum information (RQI)., Comment: 16 pages, 9 figures

Recent advancements in IoT technologies have underscored the importance of using sensor data to understand environmental contexts effectively. This paper introduces a novel embedded system designed to autonomously label sensor data directly on IoT devices, thereby enhancing the efficiency of data collection methods. We present an integrated hardware and software solution equipped with specialized labeling sensors that streamline the capture and labeling of diverse types of sensor data. By implementing local processing with lightweight labeling methods, our system minimizes the need for extensive data transmission and reduces dependence on external resources. Experimental validation with collected data and a Convolutional Neural Network model achieved a high classification accuracy of up to 91.67%, as confirmed through 4-fold cross-validation. These results demonstrate the system's robust capability to collect audio and vibration data with correct labels., Comment: This paper is accepted by the 4th Workshop on Collaborative Technologies and Data Science in Smart City Applications (CODASSCA 2024)

Boosting is a highly successful ML-born optimization setting in which one is required to computationally efficiently learn arbitrarily good models based on the access to a weak learner oracle, providing classifiers performing at least slightly differently from random guessing. A key difference with gradient-based optimization is that boosting's original model does not requires access to first order information about a loss, yet the decades long history of boosting has quickly evolved it into a first order optimization setting -- sometimes even wrongfully defining it as such. Owing to recent progress extending gradient-based optimization to use only a loss' zeroth ($0^{th}$) order information to learn, this begs the question: what loss functions can be efficiently optimized with boosting and what is the information really needed for boosting to meet the original boosting blueprint's requirements? We provide a constructive formal answer essentially showing that any loss function can be optimized with boosting and thus boosting can achieve a feat not yet known to be possible in the classical $0^{th}$ order setting, since loss functions are not required to be be convex, nor differentiable or Lipschitz -- and in fact not required to be continuous either. Some tools we use are rooted in quantum calculus, the mathematical field -- not to be confounded with quantum computation -- that studies calculus without passing to the limit, and thus without using first order information., Comment: NeurIPS'24

Automated evaluation is crucial for streamlining text summarization benchmarking and model development, given the costly and time-consuming nature of human evaluation. Traditional methods like ROUGE do not correlate well with human judgment, while recently proposed LLM-based metrics provide only summary-level assessment using Likert-scale scores. This limits deeper model analysis, e.g., we can only assign one hallucination score at the summary level, while at the sentence level, we can count sentences containing hallucinations. To remedy those limitations, we propose FineSurE, a fine-grained evaluator specifically tailored for the summarization task using large language models (LLMs). It also employs completeness and conciseness criteria, in addition to faithfulness, enabling multi-dimensional assessment. We compare various open-source and proprietary LLMs as backbones for FineSurE. In addition, we conduct extensive benchmarking of FineSurE against SOTA methods including NLI-, QA-, and LLM-based methods, showing improved performance especially on the completeness and conciseness dimensions. The code is available at https://github.com/DISL-Lab/FineSurE-ACL24., Comment: Accepted at ACL 2024 (main, long)

This study identifies the potential vulnerabilities of Large Language Models (LLMs) to 'jailbreak' attacks, specifically focusing on the Arabic language and its various forms. While most research has concentrated on English-based prompt manipulation, our investigation broadens the scope to investigate the Arabic language. We initially tested the AdvBench benchmark in Standardized Arabic, finding that even with prompt manipulation techniques like prefix injection, it was insufficient to provoke LLMs into generating unsafe content. However, when using Arabic transliteration and chatspeak (or arabizi), we found that unsafe content could be produced on platforms like OpenAI GPT-4 and Anthropic Claude 3 Sonnet. Our findings suggest that using Arabic and its various forms could expose information that might remain hidden, potentially increasing the risk of jailbreak attacks. We hypothesize that this exposure could be due to the model's learned connection to specific words, highlighting the need for more comprehensive safety training across all language forms., Comment: Accepted by EMNLP 2024

We propose a practical framework to synthesize the broadband sound-field on a small rigid surface based on the physics of sound propagation. The sound-field is generated as a composite map of two components: the room component and the device component, with acoustic plane waves as the core tool for the generation. This decoupling of room and device components significantly reduces the problem complexity and provides accurate rendering of the sound-field. We describe in detail the theoretical foundations, and efficient procedures of the implementation. The effectiveness of the proposed framework is established through rigorous validation under different environment setups., Comment: 17 pages, double-spaced, 5 figures

We describe a new method for estimating the direction of sound in a reverberant environment from basic principles of sound propagation. The method utilizes SNR-adaptive features from time-delay and energy of the directional components after acoustic wave decomposition of the observed sound field to estimate the line-of-sight direction under noisy and reverberant conditions. The effectiveness of the approach is established with measured data of different microphone array configurations under various usage scenarios., Comment: 5 pages, 2 figures, conference

We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(\varepsilon,\delta)$-PAC version of the problem, with sample complexity of $O\big( (\operatorname{poly}(K) + 1 / \varepsilon^2) \log (|H| / \delta) \big)$ for any finite hypothesis class $H$. In terms of the leading dependence on $\varepsilon$, this improves upon existing bounds for the problem, that are of the form $O(K/\varepsilon^2)$. We also provide an extension of this result to general classes and establish similar sample complexity bounds in which $\log |H|$ is replaced by the Natarajan dimension. This matches the optimal rate in the full-information version of the problem and resolves an open question studied by Daniely, Sabato, Ben-David, and Shalev-Shwartz (2011) who demonstrated that the multiplicative price of bandit feedback in realizable PAC learning is $\Theta(K)$. We complement this by revealing a stark contrast with the agnostic case, where the price of bandit feedback is only $O(1)$ as $\varepsilon \to 0$. Our algorithm utilizes a stochastic optimization technique to minimize a log-barrier potential based on Frank-Wolfe updates for computing a low-variance exploration distribution over the hypotheses, and is made computationally efficient provided access to an ERM oracle over $H$.

Can a deep neural network be approximated by a small decision tree based on simple features? This question and its variants are behind the growing demand for machine learning models that are *interpretable* by humans. In this work we study such questions by introducing *interpretable approximations*, a notion that captures the idea of approximating a target concept $c$ by a small aggregation of concepts from some base class $\mathcal{H}$. In particular, we consider the approximation of a binary concept $c$ by decision trees based on a simple class $\mathcal{H}$ (e.g., of bounded VC dimension), and use the tree depth as a measure of complexity. Our primary contribution is the following remarkable trichotomy. For any given pair of $\mathcal{H}$ and $c$, exactly one of these cases holds: (i) $c$ cannot be approximated by $\mathcal{H}$ with arbitrary accuracy; (ii) $c$ can be approximated by $\mathcal{H}$ with arbitrary accuracy, but there exists no universal rate that bounds the complexity of the approximations as a function of the accuracy; or (iii) there exists a constant $\kappa$ that depends only on $\mathcal{H}$ and $c$ such that, for *any* data distribution and *any* desired accuracy level, $c$ can be approximated by $\mathcal{H}$ with a complexity not exceeding $\kappa$. This taxonomy stands in stark contrast to the landscape of supervised classification, which offers a complex array of distribution-free and universally learnable scenarios. We show that, in the case of interpretable approximations, even a slightly nontrivial a-priori guarantee on the complexity of approximations implies approximations with constant (distribution-free and accuracy-free) complexity. We extend our trichotomy to classes $\mathcal{H}$ of unbounded VC dimension and give characterizations of interpretability based on the algebra generated by $\mathcal{H}$., Comment: To appear at COLT 2024

Abernethy et al. (2011) showed that Blackwell approachability and no-regret learning are equivalent, in the sense that any algorithm that solves a specific Blackwell approachability instance can be converted to a sublinear regret algorithm for a specific no-regret learning instance, and vice versa. In this paper, we study a more fine-grained form of such reductions, and ask when this translation between problems preserves not only a sublinear rate of convergence, but also preserves the optimal rate of convergence. That is, in which cases does it suffice to find the optimal regret bound for a no-regret learning instance in order to find the optimal rate of convergence for a corresponding approachability instance? We show that the reduction of Abernethy et al. (2011) does not preserve rates: their reduction may reduce a $d$-dimensional approachability instance $I_1$ with optimal convergence rate $R_1$ to a no-regret learning instance $I_2$ with optimal regret-per-round of $R_2$, with $R_{2}/R_{1}$ arbitrarily large (in particular, it is possible that $R_1 = 0$ and $R_{2} > 0$). On the other hand, we show that it is possible to tightly reduce any approachability instance to an instance of a generalized form of regret minimization we call improper $\phi$-regret minimization (a variant of the $\phi$-regret minimization of Gordon et al. (2008) where the transformation functions may map actions outside of the action set). Finally, we characterize when linear transformations suffice to reduce improper $\phi$-regret minimization problems to standard classes of regret minimization problems in a rate preserving manner. We prove that some improper $\phi$-regret minimization instances cannot be reduced to either subclass of instance in this way, suggesting that approachability can capture some problems that cannot be phrased in the language of online learning.

One of the most central result in combinatorics says that the descent statistic and the excedance statistic are equidistribued over the symmetric group. As a continuation of the work of Shareshian-Wachs (Adv. Math., 225(6) (2010), 2921--2966), we provide a curious $t$-symmetric decomposition for the generating polynomial of the joint distribution of the descent and excedance statistics over the symmetric group., Comment: 7 pages

Large Language Models (LLMs) are powerful models for generation tasks, but they may not generate good quality outputs in their first attempt. Apart from model fine-tuning, existing approaches to improve prediction accuracy and quality typically involve LLM self-improvement / self-reflection that incorporate feedback from models themselves. Despite their effectiveness, these methods are hindered by their high computational cost and lack of scalability. In this work, we propose CERET, a method for refining text generations by considering semantic stability, entailment and inter-sample uncertainty measures. Experimental results show that CERET outperforms Self-consistency and Self-rerank baselines consistently under various task setups, by ~1.6% in Rouge-1 for abstractive summarization and ~3.5% in hit rate for question answering. Compared to LLM Self-rerank method, our approach only requires 9.4% of its latency and is more cost-effective., Comment: The source code and data samples are released at https://github.com/amazon-science/CERET-LLM-refine

We introduce a novel online learning framework that unifies and generalizes pre-established models, such as delayed and corrupted feedback, to encompass adversarial environments where action feedback evolves over time. In this setting, the observed loss is arbitrary and may not correlate with the true loss incurred, with each round updating previous observations adversarially. We propose regret minimization algorithms for both the full-information and bandit settings, with regret bounds quantified by the average feedback accuracy relative to the true loss. Our algorithms match the known regret bounds across many special cases, while also introducing previously unknown bounds.

We revisit the fundamental question of formally defining what constitutes a reconstruction attack. While often clear from the context, our exploration reveals that a precise definition is much more nuanced than it appears, to the extent that a single all-encompassing definition may not exist. Thus, we employ a different strategy and aim to "sandwich" the concept of reconstruction attacks by addressing two complementing questions: (i) What conditions guarantee that a given system is protected against such attacks? (ii) Under what circumstances does a given attack clearly indicate that a system is not protected? More specifically, * We introduce a new definitional paradigm -- Narcissus Resiliency -- to formulate a security definition for protection against reconstruction attacks. This paradigm has a self-referential nature that enables it to circumvent shortcomings of previously studied notions of security. Furthermore, as a side-effect, we demonstrate that Narcissus resiliency captures as special cases multiple well-studied concepts including differential privacy and other security notions of one-way functions and encryption schemes. * We formulate a link between reconstruction attacks and Kolmogorov complexity. This allows us to put forward a criterion for evaluating when such attacks are convincingly successful.

Let $\mathcal{C}_n$ denote the set of words $w=w_1\cdots w_n$ on the alphabet of positive integers satisfying $w_{i+1}\leq w_i+1$ for $1 \leq i \leq n-1$ with $w_1=1$. The members of $\mathcal{C}_n$ are known as Catalan words and are enumerated by the $n$-th Catalan number $C_n$. The problem of finding the cardinality of various avoidance classes of $\mathcal{C}_n$ has been an ongoing object of study, and members of $\mathcal{C}_n$ avoiding one or two classical or a single consecutive pattern have been enumerated. In this paper, we extend these results to vincular patterns and seek to determine the cardinality of each avoidance class corresponding to a pattern of type (1,2) or (2,1). In several instances, a simple explicit formula for this cardinality may be given. In the more difficult cases, we find only a formula for the (ordinary) generating function which enumerates the class in question. We make extensive use of functional equations in establishing our generating function results., Comment: 30 pages and 2 tables

We revisit the classical problem of multiclass classification with bandit feedback (Kakade, Shalev-Shwartz and Tewari, 2008), where each input classifies to one of $K$ possible labels and feedback is restricted to whether the predicted label is correct or not. Our primary inquiry is with regard to the dependency on the number of labels $K$, and whether $T$-step regret bounds in this setting can be improved beyond the $\smash{\sqrt{KT}}$ dependence exhibited by existing algorithms. Our main contribution is in showing that the minimax regret of bandit multiclass is in fact more nuanced, and is of the form $\smash{\widetilde{\Theta}\left(\min \left\{|H| + \sqrt{T}, \sqrt{KT \log |H|} \right\} \right) }$, where $H$ is the underlying (finite) hypothesis class. In particular, we present a new bandit classification algorithm that guarantees regret $\smash{\widetilde{O}(|H|+\sqrt{T})}$, improving over classical algorithms for moderately-sized hypothesis classes, and give a matching lower bound establishing tightness of the upper bounds (up to log-factors) in all parameter regimes.

We describe the design and results from the BraTS 2023 Intracranial Meningioma Segmentation Challenge. The BraTS Meningioma Challenge differed from prior BraTS Glioma challenges in that it focused on meningiomas, which are typically benign extra-axial tumors with diverse radiologic and anatomical presentation and a propensity for multiplicity. Nine participating teams each developed deep-learning automated segmentation models using image data from the largest multi-institutional systematically expert annotated multilabel multi-sequence meningioma MRI dataset to date, which included 1000 training set cases, 141 validation set cases, and 283 hidden test set cases. Each case included T2, T2/FLAIR, T1, and T1Gd brain MRI sequences with associated tumor compartment labels delineating enhancing tumor, non-enhancing tumor, and surrounding non-enhancing T2/FLAIR hyperintensity. Participant automated segmentation models were evaluated and ranked based on a scoring system evaluating lesion-wise metrics including dice similarity coefficient (DSC) and 95% Hausdorff Distance. The top ranked team had a lesion-wise median dice similarity coefficient (DSC) of 0.976, 0.976, and 0.964 for enhancing tumor, tumor core, and whole tumor, respectively and a corresponding average DSC of 0.899, 0.904, and 0.871, respectively. These results serve as state-of-the-art benchmarks for future pre-operative meningioma automated segmentation algorithms. Additionally, we found that 1286 of 1424 cases (90.3%) had at least 1 compartment voxel abutting the edge of the skull-stripped image edge, which requires further investigation into optimal pre-processing face anonymization steps., Comment: 16 pages, 11 tables, 10 figures, MICCAI