Search

We introduce the problem of active causal structure learning with advice. In the typical well-studied setting, the learning algorithm is given the essential graph for the observational distribution and is asked to recover the underlying causal directed acyclic graph (DAG) $G^*$ while minimizing the number of interventions made. In our setting, we are additionally given side information about $G^*$ as advice, e.g. a DAG $G$ purported to be $G^*$. We ask whether the learning algorithm can benefit from the advice when it is close to being correct, while still having worst-case guarantees even when the advice is arbitrarily bad. Our work is in the same space as the growing body of research on algorithms with predictions. When the advice is a DAG $G$, we design an adaptive search algorithm to recover $G^*$ whose intervention cost is at most $O(\max\{1, \log \psi\})$ times the cost for verifying $G^*$; here, $\psi$ is a distance measure between $G$ and $G^*$ that is upper bounded by the number of variables $n$, and is exactly 0 when $G=G^*$. Our approximation factor matches the state-of-the-art for the advice-less setting., Comment: Accepted into ICML 2023

Local search is a powerful heuristic in optimization and computer science, the complexity of which was studied in the white box and black box models. In the black box model, we are given a graph $G = (V,E)$ and oracle access to a function $f : V \to \mathbb{R}$. The local search problem is to find a vertex $v$ that is a local minimum, i.e. with $f(v) \leq f(u)$ for all $(u,v) \in E$, using as few queries as possible. The query complexity is well understood on the grid and the hypercube, but much less is known beyond. We show the query complexity of local search on $d$-regular expanders with constant degree is $\Omega\left(\frac{\sqrt{n}}{\log{n}}\right)$, where $n$ is the number of vertices. This matches within a logarithmic factor the upper bound of $O(\sqrt{n})$ for constant degree graphs from Aldous (1983), implying that steepest descent with a warm start is an essentially optimal algorithm for expanders. The best lower bound known from prior work was $\Omega\left(\frac{\sqrt[8]{n}}{\log{n}}\right)$, shown by Santha and Szegedy (2004) for quantum and randomized algorithms. We obtain this result by considering a broader framework of graph features such as vertex congestion and separation number. We show that for each graph, the randomized query complexity of local search is $\Omega\left(\frac{n^{1.5}}{g}\right)$, where $g$ is the vertex congestion of the graph; and $\Omega\left(\sqrt[4]{\frac{s}{\Delta}}\right)$, where $s$ is the separation number and $\Delta$ is the maximum degree. For separation number the previous bound was $\Omega\left(\sqrt[8]{\frac{s}{\Delta}} /\log{n}\right)$, given by Santha and Szegedy for quantum and randomized algorithms. We also show a variant of the relational adversary method from Aaronson (2006), which is asymptotically at least as strong as the version in Aaronson (2006) for all randomized algorithms and strictly stronger for some problems.

Recovering causal relationships from data is an important problem. Using observational data, one can typically only recover causal graphs up to a Markov equivalence class and additional assumptions or interventional data are needed for complete recovery. In this work, under some standard assumptions, we study causal graph discovery via adaptive interventions with node-dependent interventional costs. For this setting, we show that no algorithm can achieve an approximation guarantee that is asymptotically better than linear in the number of vertices with respect to the verification number; a well-established benchmark for adaptive search algorithms. Motivated by this negative result, we define a new benchmark that captures the worst-case interventional cost for any search algorithm. Furthermore, with respect to this new benchmark, we provide adaptive search algorithms that achieve logarithmic approximations under various settings: atomic, bounded size interventions and generalized cost objectives., Comment: Accepted into ICML 2023

As machine learning algorithms are deployed ubiquitously to a variety of domains, it is imperative to make these often black-box models transparent. Several recent works explain black-box models by capturing the most influential features for prediction per instance; such explanation methods are univariate, as they characterize importance per feature. We extend univariate explanation to a higher-order; this enhances explainability, as bivariate methods can capture feature interactions in black-box models, represented as a directed graph. Analyzing this graph enables us to discover groups of features that are equally important (i.e., interchangeable), while the notion of directionality allows us to identify the most influential features. We apply our bivariate method on Shapley value explanations, and experimentally demonstrate the ability of directional explanations to discover feature interactions. We show the superiority of our method against state-of-the-art on CIFAR10, IMDB, Census, Divorce, Drug, and gene data.

The trace magnetic power spectrum in the solar wind is known to be characterized by a double power law at scales much larger than the proton gyro-radius, with flatter spectral exponents close to -1 found at the lower frequencies below an inertial range with indices closer to $[-1.5,-1.6]$. The origin of the $1/f$ range is still under debate. In this study, we selected 109 magnetically incompressible solar wind intervals ($\delta |\boldsymbol B|/|\boldsymbol B| \ll 1$) from Parker Solar Probe encounters 1 to 13 which display such double power laws, with the aim of understanding the statistics and radial evolution of the low frequency power spectral exponents from Alfv\'en point up to 0.3 AU. New observations from closer to the sun show that in the low frequency range solar wind turbulence can display spectra much shallower than $1/f$, evolving asymptotically to $1/f$ as advection time increases, indicating a dynamic origin for the $1/f$ range formation. We discuss the implications of this result on the Matteini et al. (2018) conjecture for the $1/f$ origin as well as example spectra displaying a triple power law consistent with the model proposed by Chandran et al. (2018), supporting the dynamic role of parametric decay in the young solar wind. Our results provide new constraints on the origin of the $1/f$ spectrum and further show the possibility of the coexistence of multiple formation mechanisms., Comment: Accepted by ApJL

In general, slow solar wind from the streamer belt forms a high plasma beta equatorial plasma sheet around the heliospheric current sheet (HCS) crossing, namely the heliospheric plasma sheet (HPS). Current Parker Solar Probe (PSP) observations show that the HCS crossings near the Sun could be full or partial current sheet crossing (PCS), and they share some common features but also have different properties. In this work, using the PSP observations from encounters 4 to 10, we identify streamer belt solar wind from enhancements in plasma beta, and we further use electron pitch angle distributions to separate it into HPS solar wind that around the full HCS crossings and PCS solar wind that in the vicinity of PCS crossings. Based on our analysis, we find that the PCS solar wind has different characteristics as compared with HPS solar wind: a) PCS solar wind could be non-pressure-balanced structures rather than magnetic holes, and the total pressure enhancement mainly results from the less reduced magnetic pressure; b) some of the PCS solar wind are mirror unstable; c) PCS solar wind is dominated by very low helium abundance but varied alpha-proton differential speed. We suggest the PCS solar wind could originate from coronal loops deep inside the streamer belt, and it is pristine solar wind that still actively interacts with ambient solar wind, thus it is valuable for further investigations on the heating and acceleration of slow solar wind.

In this work, we look at Score-based generative models (also called diffusion generative models) from a geometric perspective. From a new view point, we prove that both the forward and backward process of adding noise and generating from noise are Wasserstein gradient flow in the space of probability measures. We are the first to prove this connection. Our understanding of Score-based (and Diffusion) generative models have matured and become more complete by drawing ideas from different fields like Bayesian inference, control theory, stochastic differential equation and Schrodinger bridge. However, many open questions and challenges remain. One problem, for example, is how to decrease the sampling time? We demonstrate that looking from geometric perspective enables us to answer many of these questions and provide new interpretations to some known results. Furthermore, geometric perspective enables us to devise an intuitive geometric solution to the problem of faster sampling. By augmenting traditional score-based generative models with a projection step, we show that we can generate high quality images with significantly fewer sampling-steps.

While score based generative models, or diffusion models, have found success in image synthesis, they are often coupled with text data or image label to be able to manipulate and conditionally generate images. Even though manipulation of images by changing the text prompt is possible, our understanding of the text embedding and our ability to modify it to edit images is quite limited. Towards the direction of having more control over image manipulation and conditional generation, we propose to learn image components in an unsupervised manner so that we can compose those components to generate and manipulate images in informed manner. Taking inspiration from energy based models, we interpret different score components as the gradient of different energy functions. We show how score based learning allows us to learn interesting components and we can visualize them through generation. We also show how this novel decomposition allows us to compose, generate and modify images in interesting ways akin to dreaming. We make our code available at https://github.com/sandeshgh/Score-based-disentanglement

Switchbacks are rapid magnetic field reversals that last from seconds to hours. Current Parker Solar Probe (PSP) observations pose many open questions in regard to the nature of switchbacks. For example, are they stable as they propagate through the inner heliosphere, and how are they formed? In this work, we aim to investigate the structure and origin of switchbacks. In order to study the stability of switchbacks, we suppose the small-scale current sheets therein are generated by magnetic braiding, and they should work to stabilize the switchbacks. With more than one thousand switchbacks identified with PSP observations in seven encounters, we find many more current sheets inside than outside switchbacks, indicating that these microstructures should work to stabilize the S-shaped structures of switchbacks. Additionally, we study the helium variations to trace the switchbacks to their origins. We find both helium-rich and helium-poor populations in switchbacks, implying that the switchbacks could originate from both closed and open magnetic field regions in the Sun. Moreover, we observe that the alpha-proton differential speeds also show complex variations as compared to the local Alfv\'en speed. The joint distributions of both parameters show that low helium abundance together with low differential speed is the dominant state in switchbacks. The presence of small-scale current sheets in switchbacks along with the helium features are in line with the hypothesis that switchbacks could originate from the Sun via interchange reconnection process. However, other formation mechanisms are not excluded., Comment: accepted by ApJ

We analyze a merged Parker Solar Probe ($PSP$) and Solar Orbiter ($SO$) dataset covering heliocentric distances $13 \ R_{\odot} \lesssim R \lesssim 220$ $R_{\odot}$ to investigate the radial evolution of power and spectral-index anisotropy in the wavevector space of solar wind turbulence. Our results show that anisotropic signatures of turbulence display a distinct radial evolution when fast, $V_{sw} \geq ~ 400 ~km ~s^{-1}$, and slow, $V_{sw} \leq ~ 400 ~km ~s^{-1}$, wind streams are considered. The anisotropic properties of slow wind in Earth orbit are consistent with a ``critically balanced'' cascade, but both spectral-index anisotropy and power anisotropy diminish with decreasing heliographic distance. Fast streams are observed to roughly retain their near-Sun anisotropic properties, with the observed spectral index and power anisotropies being more consistent with a ``dynamically aligned'' type of cascade, though the lack of extended fast-wind intervals makes it difficult to accurately measure the anisotropic scaling. A high-resolution analysis during the first perihelion of PSP confirms the presence of two sub-ranges within the inertial range, which may be associated with the transition from weak to strong turbulence. The transition occurs at $\kappa d_{i} \approx 6 \times 10^{-2}$, and signifies a shift from -5/3 to -2 and -3/2 to -1.57 scaling in parallel and perpendicular spectra, respectively. Our results provide strong observational constraints for anisotropic theories of MHD turbulence in the solar wind., Comment: Accepted to APJ

Learning causal relationships between variables is a fundamental task in causal inference and directed acyclic graphs (DAGs) are a popular choice to represent the causal relationships. As one can recover a causal graph only up to its Markov equivalence class from observations, interventions are often used for the recovery task. Interventions are costly in general and it is important to design algorithms that minimize the number of interventions performed. In this work, we study the problem of identifying the smallest set of interventions required to learn the causal relationships between a subset of edges (target edges). Under the assumptions of faithfulness, causal sufficiency, and ideal interventions, we study this problem in two settings: when the underlying ground truth causal graph is known (subset verification) and when it is unknown (subset search). For the subset verification problem, we provide an efficient algorithm to compute a minimum sized interventional set; we further extend these results to bounded size non-atomic interventions and node-dependent interventional costs. For the subset search problem, in the worst case, we show that no algorithm (even with adaptivity or randomization) can achieve an approximation ratio that is asymptotically better than the vertex cover of the target edges when compared with the subset verification number. This result is surprising as there exists a logarithmic approximation algorithm for the search problem when we wish to recover the whole causal graph. To obtain our results, we prove several interesting structural properties of interventional causal graphs that we believe have applications beyond the subset verification/search problems studied here., Comment: Accepted into AISTATS 2023 (https://aistats.org/aistats2023/accepted.html)

We provide time- and sample-efficient algorithms for learning and testing latent-tree Ising models, i.e. Ising models that may only be observed at their leaf nodes. On the learning side, we obtain efficient algorithms for learning a tree-structured Ising model whose leaf node distribution is close in Total Variation Distance, improving on the results of prior work. On the testing side, we provide an efficient algorithm with fewer samples for testing whether two latent-tree Ising models have leaf-node distributions that are close or far in Total Variation distance. We obtain our algorithms by showing novel localization results for the total variation distance between the leaf-node distributions of tree-structured Ising models, in terms of their marginals on pairs of leaves.

One of the most fundamental graph problems is finding a shortest path from a source to a target node. While in its basic forms the problem has been studied extensively and efficient algorithms are known, it becomes significantly harder as soon as parts of the graph are susceptible to failure. Although one can recompute a shortest replacement path after every outage, this is rather inefficient both in time and/or storage. One way to overcome this problem is to shift computational burden from the queries into a pre-processing step, where a data structure is computed that allows for fast querying of replacement paths, typically referred to as a Distance Sensitivity Oracle (DSO). While DSOs have been extensively studied in the theoretical computer science community, to the best of our knowledge this is the first work to construct DSOs using deep learning techniques. We show how to use deep learning to utilize a combinatorial structure of replacement paths. More specifically, we utilize the combinatorial structure of replacement paths as a concatenation of shortest paths and use deep learning to find the pivot nodes for stitching shortest paths into replacement paths., Comment: arXiv admin note: text overlap with arXiv:2007.11495 by other authors

Post-hoc explanation methods have become a critical tool for understanding black-box classifiers in high-stakes applications. However, high-performing classifiers are often highly nonlinear and can exhibit complex behavior around the decision boundary, leading to brittle or misleading local explanations. Therefore there is an impending need to quantify the uncertainty of such explanation methods in order to understand when explanations are trustworthy. In this work we propose the Gaussian Process Explanation UnCertainty (GPEC) framework, which generates a unified uncertainty estimate combining decision boundary-aware uncertainty with explanation function approximation uncertainty. We introduce a novel geodesic-based kernel, which captures the complexity of the target black-box decision boundary. We show theoretically that the proposed kernel similarity increases with decision boundary complexity. The proposed framework is highly flexible; it can be used with any black-box classifier and feature attribution method. Empirical results on multiple tabular and image datasets show that the GPEC uncertainty estimate improves understanding of explanations as compared to existing methods., Comment: Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS) 2024

Parker Solar Probe and Solar Orbiter data are used to investigate the radial evolution of magnetic turbulence between $0.06 ~ \lesssim R ~\lesssim 1$ au. The spectrum is studied as a function of scale, normalized to the ion inertial scale $d_{i}$. In the vicinity of the Sun, the inertial range is limited to a narrow range of scales and exhibits a power-law exponent of, $\alpha_{B} = -3/2$, independent of plasma parameters. The inertial range grows with distance, progressively extending to larger spatial scales, while steepening towards a $\alpha_{B} =-5/3$ scaling. It is observed that spectra for intervals with large magnetic energy excesses and low Alfv\'enic content steepen significantly with distance, in contrast to highly Alfv\'enic intervals that retain their near-Sun scaling. The occurrence of steeper spectra in slower wind streams may be attributed to the observed positive correlation between solar wind speed and Alfv\'enicity., Comment: Accepted to APJ letters with minor revisions

We study two problems related to recovering causal graphs from interventional data: (i) $\textit{verification}$, where the task is to check if a purported causal graph is correct, and (ii) $\textit{search}$, where the task is to recover the correct causal graph. For both, we wish to minimize the number of interventions performed. For the first problem, we give a characterization of a minimal sized set of atomic interventions that is necessary and sufficient to check the correctness of a claimed causal graph. Our characterization uses the notion of $\textit{covered edges}$, which enables us to obtain simple proofs and also easily reason about earlier known results. We also generalize our results to the settings of bounded size interventions and node-dependent interventional costs. For all the above settings, we provide the first known provable algorithms for efficiently computing (near)-optimal verifying sets on general graphs. For the second problem, we give a simple adaptive algorithm based on graph separators that produces an atomic intervention set which fully orients any essential graph while using $\mathcal{O}(\log n)$ times the optimal number of interventions needed to $\textit{verify}$ (verifying size) the underlying DAG on $n$ vertices. This approximation is tight as $\textit{any}$ search algorithm on an essential line graph has worst case approximation ratio of $\Omega(\log n)$ with respect to the verifying size. With bounded size interventions, each of size $\leq k$, our algorithm gives an $\mathcal{O}(\log n \cdot \log k)$ factor approximation. Our result is the first known algorithm that gives a non-trivial approximation guarantee to the verifying size on general unweighted graphs and with bounded size interventions.

Machine learning methods have significantly improved in their predictive capabilities, but at the same time they are becoming more complex and less transparent. As a result, explainers are often relied on to provide interpretability to these black-box prediction models. As crucial diagnostics tools, it is important that these explainers themselves are robust. In this paper we focus on one particular aspect of robustness, namely that an explainer should give similar explanations for similar data inputs. We formalize this notion by introducing and defining explainer astuteness, analogous to astuteness of prediction functions. Our formalism allows us to connect explainer robustness to the predictor's probabilistic Lipschitzness, which captures the probability of local smoothness of a function. We provide lower bound guarantees on the astuteness of a variety of explainers (e.g., SHAP, RISE, CXPlain) given the Lipschitzness of the prediction function. These theoretical results imply that locally smooth prediction functions lend themselves to locally robust explanations. We evaluate these results empirically on simulated as well as real datasets.

Parker Solar Probe (PSP) has shown that the solar wind in the inner heliosphere is characterized by the quasi omni-presence of magnetic switchbacks ("switchback" hereinafter), local backward-bends of magnetic field lines. Switchbacks also tend to come in patches, with a large-scale modulation that appears to have a spatial scale size comparable to supergranulation on the Sun. Here we inspect data from the first ten encounters of PSP focusing on different time intervals when clear switchback patches were observed by PSP. We show that the switchbacks modulation, on a timescale of several hours, seems to be independent of whether PSP is near perihelion, when it rapidly traverses large swaths of longitude remaining at the same heliocentric distance, or near the radial-scan part of its orbit, when PSP hovers over the same longitude on the Sun while rapidly moving radially inwards or outwards. This implies that switchback patches must also have an intrinsically temporal modulation most probably originating at the Sun. Between two consecutive patches, the magnetic field is usually very quiescent with weak fluctuations. We compare various parameters between the quiescent intervals and the switchback intervals. The results show that the quiescent intervals are typically less Alfv\'enic than switchback intervals, and the magnetic power spectrum is usually shallower in quiescent intervals. We propose that the temporal modulation of switchback patches may be related to the "breathing" of emerging flux that appears in images as the formation of "bubbles" below prominences in the Hinode/SOT observations.

$PSP$ and $SolO$ data are utilized to investigate magnetic field intermittency in the solar wind (SW). Small-scale intermittency $(20-100d_{i})$ is observed to radially strengthen when methods relying on higher-order moments are considered ($SF_q$, $SDK$), but no clear trend is observed at larger scales. However, lower-order moment-based methods (e.g., PVI) are deemed more appropriate for examining the evolution of the bulk of Coherent Structures (CSs), $PVI \ge 3$. Using PVI, we observe a scale-dependent evolution in the fraction of the dataset occupied by CSs, $f_{PVI \ge 3}$. Specifically, regardless of the SW speed, a subtle increase is found in $f_{PVI\ge3}$ for $\ell =20 d_i$, in contrast to a more pronounced radial increase in CSs observed at larger scales. Intermittency is investigated in relation to plasma parameters. Though, slower SW speed intervals exhibit higher $f_{PVI \geq 6}$ and higher kurtosis maxima, no statistical differences are observed for $f_{PVI \geq 3}$. Highly Alfv\'enic intervals, display lower levels of intermittency. The anisotropy with respect to the angle between the magnetic field and SW flow, $\Theta_{VB}$ is investigated. Intermittency is weaker at $\Theta_{VB} \approx 0^{\circ}$ and is strengthened at larger angles. Considering the evolution at a constant alignment angle, a weakening of intermittency is observed with increasing advection time of the SW. Our results indicate that the strengthening of intermittency in the inner heliosphere is driven by the increase in comparatively highly intermittent perpendicular intervals sampled by the probes with increasing distance, an effect related directly to the evolution of the Parker spiral.

Qubit technologies using nitrogen-vacancy color centers in diamonds require precise knowledge of the centers, including the number of emitters within a diffraction-limited spot and their orientations. However, the number of emitters is challenging to determine when there is finite background, which affects the precision of resulting quantum protocols. Here we show the photoluminescence (PL) intensity and quantum correlation (Hanbury Brown and Twiss) measurements as a function of polarization for one- and two-emitter systems. The sample was made by implanting low concentrations of adenine (C5H5N5) into a low nitrogen chemical vapor deposition diamond. This approach yielded well-spaced regions with few nitrogen-vacancy centers. By mapping the PL intensity and quantum correlation as a function of polarization, we can distinguish two emitter systems from single emitters with background, providing a method to quantify the background signal at implanted sites, which might be different from off-site background levels. This approach also provides a valuable new all-optical mechanism for the determination of one or two emitter systems useful for quantum sensing, communication, and computation tasks.

With the rise of software-as-a-service and microservice architectures, RESTful APIs are now ubiquitous in mobile and web applications. A service can have tens or hundreds of API methods, making it a challenge for programmers to find the right combination of methods to solve their task. We present APIphany, a component-based synthesizer for programs that compose calls to RESTful APIs. The main innovation behind APIphany is the use of precise semantic types, both to specify user intent and to direct the search. APIphany contributes three novel mechanisms to overcome challenges in adapting component-based synthesis to the REST domain: (1) a type inference algorithm for augmenting REST specifications with semantic types; (2) an efficient synthesis technique for "wrangling" semi-structured data, which is commonly required in working with RESTful APIs; and (3) a new form of simulated execution to avoid executing APIs calls during synthesis. We evaluate APIphany on three real-world APIs and 32 tasks extracted from GitHub repositories and StackOverflow. In our experiments, APIphany found correct solutions to 29 tasks, with 23 of them reported among top ten synthesis results.

Predictions of coronal mass ejections (CMEs) and solar energetic particles (SEPs) are a central issue in space weather forecasting. In recent years, interest in space weather predictions has expanded to include impacts at other planets beyond Earth as well as spacecraft scattered throughout the heliosphere. In this sense, the scope of space weather science now encompasses the whole heliospheric system, and multi-point measurements of solar transients can provide useful insights and validations for prediction models. In this work, we aim to analyse the whole inner heliospheric context between two eruptive flares that took place in late 2020, i.e. the M4.4 flare of November 29 and the C7.4 flare of December 7. This period is especially interesting because the STEREO-A spacecraft was located ~60{\deg} east of the Sun-Earth line, giving us the opportunity to test the capabilities of "predictions at 360{\deg}" using remote-sensing observations from the Lagrange L1 and L5 points as input. We simulate the CMEs that were ejected during our period of interest and the SEPs accelerated by their shocks using the WSA-Enlil-SEPMOD modelling chain and four sets of input parameters, forming a "mini-ensemble". We validate our results using in-situ observations at six locations, including Earth and Mars. We find that, despite some limitations arising from the models' architecture and assumptions, CMEs and shock-accelerated SEPs can be reasonably studied and forecast in real time at least out to several tens of degrees away from the eruption site using the prediction tools employed here., Comment: 50 pages, 16 figures, 3 tables, accepted for publication in Space Weather (v2 contains updated CCMC links after their website update)