Search

In the Learning to Defer (L2D) framework, a prediction model can either make a prediction or defer it to an expert, as determined by a rejector. Current L2D methods train the rejector to decide whether to reject the entire prediction, which is not desirable when the model predicts long sequences. We present an L2D setting for sequence outputs where the system can defer specific outputs of the whole model prediction to an expert in an effort to interleave the expert and machine throughout the prediction. We propose two types of model-based post-hoc rejectors for pre-trained predictors: a token-level rejector, which defers specific token predictions to experts with next token prediction capabilities, and a one-time rejector for experts without such abilities, which defers the remaining sequence from a specific point onward. In the experiments, we also empirically demonstrate that such granular deferrals achieve better cost-accuracy tradeoffs than whole deferrals on Traveling salesman solvers and News summarization models.

Verifying the provenance of content is crucial to the function of many organizations, e.g., educational institutions, social media platforms, firms, etc. This problem is becoming increasingly difficult as text generated by Large Language Models (LLMs) becomes almost indistinguishable from human-generated content. In addition, many institutions utilize in-house LLMs and want to ensure that external, non-sanctioned LLMs do not produce content within the institution. In this paper, we answer the following question: Given a piece of text, can we identify whether it was produced by LLM $A$ or $B$ (where $B$ can be a human)? We model LLM-generated text as a sequential stochastic process with complete dependence on history and design zero-shot statistical tests to distinguish between (i) the text generated by two different sets of LLMs $A$ (in-house) and $B$ (non-sanctioned) and also (ii) LLM-generated and human-generated texts. We prove that the type I and type II errors for our tests decrease exponentially in the text length. In designing our tests, we derive concentration inequalities on the difference between log-perplexity and the average entropy of the string under $A$. Specifically, for a given string, we demonstrate that if the string is generated by $A$, the log-perplexity of the string under $A$ converges to the average entropy of the string under $A$, except with an exponentially small probability in string length. We also show that if $B$ generates the text, except with an exponentially small probability in string length, the log-perplexity of the string under $A$ converges to the average cross-entropy of $B$ and $A$. Lastly, we present preliminary experimental results to support our theoretical results. By enabling guaranteed (with high probability) finding of the origin of harmful LLM-generated text with arbitrary size, we can help combat misinformation.

Ensuring a smooth rate of efflux of particles from an outlet without unpredictable clogging events is crucial in processing powders and grains. We show by experiments and simulations that an obstacle placed near the outlet can greatly suppress clog formation in a 3-dimensional granular flow; this counterintuitive phenomenon had previously been demonstrated in 2-dimensional systems. Remarkably, clog suppression is very effective even when the obstacle cross-section is comparable to that of a single grain, and is only a small fraction of the outlet area. Data from two dissimilar obstacle shapes indicate that the underlying mechanism for clog suppression is geometric: while the magnitude of the effect can be affected by dynamical factors, the optimal location of the obstacle is determined entirely by a simple geometric rule. An optimally-placed obstacle arranges for the most-probable clogging arch to be at a perilous and unstable spot, where the local flow geometry is at a point of expansion and a slight perturbation leaves the arch without downstream support. This geometric principle does not rely on previously conjectured dynamical mechanisms and admits generalization to other agent-based and particulate systems.

Reconstructing compositional 3D representations of scenes, where each object is represented with its own 3D model, is a highly desirable capability in robotics and augmented reality. However, most existing methods rely heavily on strong appearance priors for object discovery, therefore only working on those classes of objects on which the method has been trained, or do not allow for object manipulation, which is necessary to scan objects fully and to guide object discovery in challenging scenarios. We address these limitations with a novel interaction-guided and class-agnostic method based on object displacements that allows a user to move around a scene with an RGB-D camera, hold up objects, and finally outputs one 3D model per held-up object. Our main contribution to this end is a novel approach to detecting user-object interactions and extracting the masks of manipulated objects. On a custom-captured dataset, our pipeline discovers manipulated objects with 78.3% precision at 100% recall and reconstructs them with a mean chamfer distance of 0.90cm. Compared to Co-Fusion, the only comparable interaction-based and class-agnostic baseline, this corresponds to a reduction in chamfer distance of 73% while detecting 99% fewer false positives., Comment: 7 pages, 8 figures, published in the 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2024)

Agricultural landscapes are quite complex, especially in the Global South where fields are smaller, and agricultural practices are more varied. In this paper we report on our progress in digitizing the agricultural landscape (natural and man-made) in our study region of India. We use high resolution imagery and a UNet style segmentation model to generate the first of its kind national-scale multi-class panoptic segmentation output. Through this work we have been able to identify individual fields across 151.7M hectares, and delineating key features such as water resources and vegetation. We share how this output was validated by our team and externally by downstream users, including some sample use cases that can lead to targeted data driven decision making. We believe this dataset will contribute towards digitizing agriculture by generating the foundational baselayer., Comment: 34 pages, 7 tables, 15 figs

Bandit algorithms have garnered significant attention due to their practical applications in real-world scenarios. However, beyond simple settings such as multi-arm or linear bandits, optimal algorithms remain scarce. Notably, no optimal solution exists for pure exploration problems in the context of generalized linear model (GLM) bandits. In this paper, we narrow this gap and develop the first track-and-stop algorithm for general pure exploration problems under the logistic bandit called logistic track-and-stop (Log-TS). Log-TS is an efficient algorithm that asymptotically matches an approximation for the instance-specific lower bound of the expected sample complexity up to a logarithmic factor., Comment: 25 pages, 2 figures. arXiv admin note: text overlap with arXiv:2006.16073 by other authors

The recent mass ($0.77 \pm ^{0.20}_{0.17}M_{\odot}$) and radius ($10.4\pm^{0.86}_{0.78} \text{km}$) measurement of HESS J1731-347 made it one of the most fascinating object if it is indeed a neutron star. In this work, we examine the current status of the dense matter equation of states in the context of this compact object being a neutron star. We use three sets of equation of states corresponding to the three classes - neutron stars, strange stars, and hybrid stars and perform Bayesian model selection on them. Our results show that for hadronic models, the EoS is preferred to be stiff at the intermediate densities. This makes the Brueckner-Hartree-Fock approximation and models based on Effective-interactions deviate from current astrophysical observations on the inclusion of HESS J1731-347. Furthermore, for the strange star family, the equation of states composed of three flavor quarks prefers relatively smaller bag parameters. Analyzing the hybrid family of equation of states consisting of a first-order phase transition revealed preferences for early first-order phase transition. Comparing all the preferred equations of state among each family, it was found that the current astrophysical constraints most prefer the hybrid equation of states., Comment: 15 figures, 19 pages

We study active data collection strategies for operator learning when the target operator is linear and the input functions are drawn from a mean-zero stochastic process with continuous covariance kernels. With an active data collection strategy, we establish an error convergence rate in terms of the decay rate of the eigenvalues of the covariance kernel. We can achieve arbitrarily fast error convergence rates with sufficiently rapid eigenvalue decay of the covariance kernels. This contrasts with the passive (i.i.d.) data collection strategies, where the convergence rate is never faster than linear decay ($\sim n^{-1}$). In fact, for our setting, we show a \emph{non-vanishing} lower bound for any passive data collection strategy, regardless of the eigenvalues decay rate of the covariance kernel. Overall, our results show the benefit of active data collection strategies in operator learning over their passive counterparts., Comment: Moved Proofs to the Appendix

This paper proposes a computationally tractable algorithm for learning infinite-horizon average-reward linear mixture Markov decision processes (MDPs) under the Bellman optimality condition. Our algorithm for linear mixture MDPs achieves a nearly minimax optimal regret upper bound of $\widetilde{\mathcal{O}}(d\sqrt{\mathrm{sp}(v^*)T})$ over $T$ time steps where $\mathrm{sp}(v^*)$ is the span of the optimal bias function $v^*$ and $d$ is the dimension of the feature mapping. Our algorithm applies the recently developed technique of running value iteration on a discounted-reward MDP approximation with clipping by the span. We prove that the value iteration procedure, even with the clipping operation, converges. Moreover, we show that the associated variance term due to random transitions can be bounded even under clipping. Combined with the weighted ridge regression-based parameter estimation scheme, this leads to the nearly minimax optimal regret guarantee.

We study generation through the lens of statistical learning theory. First, we abstract and formalize the results of Gold [1967], Angluin [1979], Angluin [1980] and Kleinberg and Mullainathan [2024] in terms of a binary hypothesis class defined over an abstract example space. Then, we extend the notion of "generation" from Kleinberg and Mullainathan [2024] to two new settings, we call "uniform" and "non-uniform" generation, and provide a characterization of which hypothesis classes are uniformly and non-uniformly generatable. As is standard in learning theory, our characterizations are in terms of the finiteness of a new combinatorial dimension termed the Closure dimension. By doing so, we are able to compare generatability with predictability (captured via PAC and online learnability) and show that these two properties of hypothesis classes are incompatible -- there are classes that are generatable but not predictable and vice versa. Finally, we extend our results to capture prompted generation and give a complete characterization of which classes are prompt generatable, generalizing some of the work by Kleinberg and Mullainathan [2024]., Comment: 35 pages, 2 figures. Reorganization and content addition

We introduce a novel extension of the contextual bandit problem, where new sets of arms can be requested with stochastic time delays and associated costs. In this setting, the learner can select multiple arms from a decision set, with each selection taking one unit of time. The problem is framed as a special case of semi-Markov decision processes (SMDPs). The arm contexts, request times, and costs are assumed to follow an unknown distribution. We consider the regret of an online learning algorithm with respect to the optimal policy that achieves the maximum average reward. By leveraging the Bellman optimality equation, we design algorithms that can effectively select arms and determine the appropriate time to request new arms, thereby minimizing their regret. Under the realizability assumption, we analyze the proposed algorithms and demonstrate that their regret upper bounds align with established results in the contextual bandit literature. We validate the algorithms through experiments on simulated data and a movie recommendation dataset, showing that their performance is consistent with theoretical analyses.

We develop a quasisymmetric analogue of the theory of Schubert cycles, building off of our previous work on a quasisymmetric analogue of Schubert polynomials and divided differences. Our constructions result in a natural geometric interpretation for the ring of quasisymmetric coinvariants., Comment: 44 pages + 3 appendices (12 pages)

Responsible AI (RAI) has emerged as a major focus across industry, policymaking, and academia, aiming to mitigate the risks and maximize the benefits of AI, both on an organizational and societal level. This study explores the global state of RAI through one of the most extensive surveys to date on the topic, surveying 1000 organizations across 20 industries and 19 geographical regions. We define a conceptual RAI maturity model for organizations to map how well they implement organizational and operational RAI measures. Based on this model, the survey assesses the adoption of system-level measures to mitigate identified risks related to, for example, discrimination, reliability, or privacy, and also covers key organizational processes pertaining to governance, risk management, and monitoring and control. The study highlights the expanding AI risk landscape, emphasizing the need for comprehensive risk mitigation strategies. The findings also reveal significant strides towards RAI maturity, but we also identify gaps in RAI implementation that could lead to increased (public) risks from AI systems. This research offers a structured approach to assess and improve RAI practices globally and underscores the critical need for bridging the gap between RAI planning and execution to ensure AI advancement aligns with human welfare and societal benefits.

Deciding if there exists a path from one vertex to another in a graph is known as the s-t connectivity or the reachability problem. Reachability can be solved using graph traversal algorithms like Depth First Search(DFS) or Breadth First Search(BFS) in linear time but these algorithms also take linear space. On the other hand, Savitch's algorithm solves the same problem using O(log^2 n) space but takes quasipolynomial time. A path decomposition P of a directed graph G is a collection of simple directed paths such that every edge of G lies on exactly one path in P. A minimal path decomposition of G is a path decomposition of G having the smallest number of paths possible and the number of paths in a minimal path decomposition of G is called the path number of G. We show that if a path decomposition P of a directed graph G consisting of k directed paths is provided, then reachability in G can be decided simultaneously in O(klog n) space and polynomial time. In fact, our result holds even when a walk decomposition is provided (instead of a path decomposition) where the graph is decomposed into k directed walks (instead of paths) and the walks are not necessarily edge-disjoint. We further show that a minimal path decomposition can be computed in logspace for directed acyclic graphs. This leads to the conclusion that reachability in directed acyclic graphs having bounded path number is logspace computable.

Radiance fields are powerful and, hence, popular models for representing the appearance of complex scenes. Yet, constructing them based on image observations gives rise to ambiguities and uncertainties. We propose a versatile approach for learning Gaussian radiance fields with explicit and fine-grained uncertainty estimates that impose only little additional cost compared to uncertainty-agnostic training. Our key observation is that uncertainties can be modeled as a low-dimensional manifold in the space of radiance field parameters that is highly amenable to Monte Carlo sampling. Importantly, our uncertainties are differentiable and, thus, allow for gradient-based optimization of subsequent captures that optimally reduce ambiguities. We demonstrate state-of-the-art performance on next-best-view planning tasks, including high-dimensional illumination planning for optimal radiance field relighting quality., Comment: Siggraph Asia 2024 conference

We investigate the effects of attractive Hubbard interaction on two-component fermionic atoms in narrow two-dimensional (2D) energy bands that exhibit Rashba spin-orbit coupling (SOC) in the presence of an applied Zeeman field. This narrow-band 2D spin-orbit coupled attractive Fermi-Hubbard model can potentially be realized in cold atom systems in optical lattices with artificially engineered Rashba SOC and Zeeman field. Employing a self-consistent mean field approximation for the pairing potential, we uncover a complex phase diagram featuring various topological superfluid (TS) phases, dependent on the chemical potential and the Zeeman field. We focus on the pairing potential and the corresponding quasiparticle gap characterizing the TS phases, which are notably small for a wide-band model with quadratic dispersion near the $\Gamma$-point, as found in earlier work, and we identify the parameter regimes that maximize the gap. We find that, while generally the value of the pairing potential increases with the reduction of the fermionic bandwidth, as expected for narrow- or flat-band systems, the magnitude of the topological gap characterizing the TS phases reaches a maximum of about $10-12.5\%$ of the interaction strength at finite values of the hopping amplitude, Rashba coupling, and Zeeman field., Comment: 10 pages, 10 figures

A catalytic Turing machine is a variant of a Turing machine in which there exists an auxiliary tape in addition to the input tape and the work tape. This auxiliary tape is initially filled with arbitrary content. The machine can read and write on the auxiliary tape, but it is constrained to restore its initial content when it halts. Studying such a model and finding its powers and limitations has practical applications. In this paper, we study catalytic Turing machines with O(log n)-sized work tape and polynomial-sized auxiliary tape that are allowed to lose at most constant many bits of the auxiliary tape when they halt. We show that such catalytic Turing machines can only decide the same set of languages as standard catalytic Turing machines with the same size work and auxiliary tape.

We study learning-theoretic foundations of operator learning, using the linear layer of the Fourier Neural Operator architecture as a model problem. First, we identify three main errors that occur during the learning process: statistical error due to finite sample size, truncation error from finite rank approximation of the operator, and discretization error from handling functional data on a finite grid of domain points. Finally, we analyze a Discrete Fourier Transform (DFT) based least squares estimator, establishing both upper and lower bounds on the aforementioned errors., Comment: Added Experiments

This paper focuses on studying the configuration spaces of graphs realised in $\mathbb C^2$, such that the configuration space is, after normalisation, one dimensional. If this is the case, then the configuration space is, generically, a smooth complex curve, and can be seen as a Riemann surface. The property of interest in this paper is the genus of this curve. Using tropical geometry, we give an algorithm to compute this genus. We provide an implementation in Python and give various examples.

Neural rendering methods can achieve near-photorealistic image synthesis of scenes from posed input images. However, when the images are imperfect, e.g., captured in very low-light conditions, state-of-the-art methods fail to reconstruct high-quality 3D scenes. Recent approaches have tried to address this limitation by modeling various degradation processes in the image formation model; however, this limits them to specific image degradations. In this paper, we propose a generalizable neural rendering method that can perform high-fidelity novel view synthesis under several degradations. Our method, GAURA, is learning-based and does not require any test-time scene-specific optimization. It is trained on a synthetic dataset that includes several degradation types. GAURA outperforms state-of-the-art methods on several benchmarks for low-light enhancement, dehazing, deraining, and on-par for motion deblurring. Further, our model can be efficiently fine-tuned to any new incoming degradation using minimal data. We thus demonstrate adaptation results on two unseen degradations, desnowing and removing defocus blur. Code and video results are available at vinayak-vg.github.io/GAURA., Comment: European Conference on Computer Vision(ECCV) 2024

We give an elementary approach utilizing only the divided difference formalism for obtaining expansions of Schubert polynomials that are manifestly nonnegative, by studying solutions to the equation $\sum Y_i\partial_i=\mathrm{id}$ on polynomials with no constant term. This in particular recovers the pipe dream and slide polynomial expansions. We also show that slide polynomials satisfy an analogue of the divided difference formalisms for Schubert polynomials and forest polynomials, which gives a simple method for extracting the coefficients of slide polynomials in the slide polynomial decomposition of an arbitrary polynomial., Comment: 29 pages, 7 figures

In decentralized multiagent trajectory planners, agents need to communicate and exchange their positions to generate collision-free trajectories. However, due to localization errors/uncertainties, trajectory deconfliction can fail even if trajectories are perfectly shared between agents. To address this issue, we first present PARM and PARM*, perception-aware, decentralized, asynchronous multiagent trajectory planners that enable a team of agents to navigate uncertain environments while deconflicting trajectories and avoiding obstacles using perception information. PARM* differs from PARM as it is less conservative, using more computation to find closer-to-optimal solutions. While these methods achieve state-of-the-art performance, they suffer from high computational costs as they need to solve large optimization problems onboard, making it difficult for agents to replan at high rates. To overcome this challenge, we present our second key contribution, PRIMER, a learning-based planner trained with imitation learning (IL) using PARM* as the expert demonstrator. PRIMER leverages the low computational requirements at deployment of neural networks and achieves a computation speed up to 5500 times faster than optimization-based approaches., Comment: 7 pages, 3 figures

Software failures inform engineering work, standards, regulations. For example, the Log4J vulnerability brought government and industry attention to evaluating and securing software supply chains. Accessing private engineering records is difficult, so failure analyses tend to use information reported by the news media. However, prior works in this direction have relied on manual analysis. That has limited the scale of their analyses. The community lacks automated support to enable such analyses to consider a wide range of news sources and incidents. In this paper, we propose the Failure Analysis Investigation with LLMs (FAIL) system to fill this gap. FAIL collects, analyzes, and summarizes software failures as reported in the news. FAIL groups articles that describe the same incidents. It then analyzes incidents using existing taxonomies for postmortems, faults, and system characteristics. To tune and evaluate FAIL, we followed the methods of prior works by manually analyzing 31 software failures. FAIL achieved an F1 score of 90% for collecting news about software failures, a V-measure of 0.98 for merging articles reporting on the same incident, and extracted 90% of the facts about failures. We then applied FAIL to a total of 137,427 news articles from 11 providers published between 2010 and 2022. FAIL identified and analyzed 2457 distinct failures reported across 4,184 articles. Our findings include: (1) current generation of large language models are capable of identifying news articles that describe failures, and analyzing them according to structured taxonomies; (2) high recurrences of similar failures within organizations and across organizations; and (3) severity of the consequences of software failures have increased over the past decade. The full FAIL database is available so that researchers, engineers, and policymakers can learn from a diversity of software failures., Comment: Accapted at the 9th IEEE/ACM International Conference on Automated Software Engineering (ASE 2024)

We develop a quasisymmetric analogue of the combinatorial theory of Schubert polynomials and the associated divided difference operators. Our counterparts are "forest polynomials", and a new family of linear operators, whose theory of compositions is governed by forests and the "Thompson monoid". Our approach extends naturally to $m$-colored quasisymmetric functions. We then give several applications of our theory to fundamental quasisymmetric functions, the study of quasisymmetric coinvariant rings and their associated harmonics, and positivity results for various expansions. In particular we resolve a conjecture of Aval-Bergeron-Li regarding quasisymmetric harmonics., Comment: 56 pages, 17 figures, table of forest polynomials added, bibliography updated