Search

Differentially private graph analysis is a powerful tool for deriving insights from diverse graph data while protecting individual information. Designing private analytic algorithms for different graph queries often requires starting from scratch. In contrast, differentially private synthetic graph generation offers a general paradigm that supports one-time generation for multiple queries. Although a rich set of differentially private graph generation algorithms has been proposed, comparing them effectively remains challenging due to various factors, including differing privacy definitions, diverse graph datasets, varied privacy requirements, and multiple utility metrics. To this end, we propose PGB (Private Graph Benchmark), a comprehensive benchmark designed to enable researchers to compare differentially private graph generation algorithms fairly. We begin by identifying four essential elements of existing works as a 4-tuple: mechanisms, graph datasets, privacy requirements, and utility metrics. We discuss principles regarding these elements to ensure the comprehensiveness of a benchmark. Next, we present a benchmark instantiation that adheres to all principles, establishing a new method to evaluate existing and newly proposed graph generation algorithms. Through extensive theoretical and empirical analysis, we gain valuable insights into the strengths and weaknesses of prior algorithms. Our results indicate that there is no universal solution for all possible cases. Finally, we provide guidelines to help researchers select appropriate mechanisms for various scenarios., Comment: 12 pages

In the zoo of emergent symmetries in quantum many-body physics, the previously unrealized emergent spacetime supersymmetry (SUSY) is particularly intriguing. Although it was known that spacetime SUSY could emerge at the (1+1)d tricritical Ising transition, an experimental realization is still absent. In this letter, we propose to realize the tricritical Ising transition with Rydberg atom arrays, taking advantage of the reconfigurability of these systems. In such systems, the spacetime SUSY manifests itself in the respective correlation functions of a bosonic mode and its fermionic partner. However, the correlation function of the fermionic mode inevitably involves a string operator, making direct measurement challenging in the conventional setting. Here, we utilize the analog--digital hybrid nature of the Rydberg atom arrays, which can simulate a physical Hamiltonian and perform a digital quantum circuit on the same platform, to measure the correlation function of the fermionic mode. This hybridized protocol provides an experimentally feasible way to reveal the hidden structure of the spacetime SUSY that emerges at the tricritical Ising transition., Comment: 7 pages, 3 figures

Recent research on texture synthesis for 3D shapes benefits a lot from dramatically developed 2D text-to-image diffusion models, including inpainting-based and optimization-based approaches. However, these methods ignore the modal gap between the 2D diffusion model and 3D objects, which primarily render 3D objects into 2D images and texture each image separately. In this paper, we revisit the texture synthesis and propose a Variance alignment based 3D-2D Collaborative Denoising framework, dubbed VCD-Texture, to address these issues. Formally, we first unify both 2D and 3D latent feature learning in diffusion self-attention modules with re-projected 3D attention receptive fields. Subsequently, the denoised multi-view 2D latent features are aggregated into 3D space and then rasterized back to formulate more consistent 2D predictions. However, the rasterization process suffers from an intractable variance bias, which is theoretically addressed by the proposed variance alignment, achieving high-fidelity texture synthesis. Moreover, we present an inpainting refinement to further improve the details with conflicting regions. Notably, there is not a publicly available benchmark to evaluate texture synthesis, which hinders its development. Thus we construct a new evaluation set built upon three open-source 3D datasets and propose to use four metrics to thoroughly validate the texturing performance. Comprehensive experiments demonstrate that VCD-Texture achieves superior performance against other counterparts., Comment: ECCV 2024

The recent discoveries of Neptune-sized ultra-short period planets (USPs) challenge existing planet formation theories. It is unclear whether these residents of the Hot Neptune Desert have similar origins to smaller, rocky USPs, or if this discrete population is evidence of a different formation pathway altogether. We report the discovery of TOI-3261b, an ultra-hot Neptune with an orbital period $P$ = 0.88 days. The host star is a $V = 13.2$ magnitude, slightly super-solar metallicity ([Fe/H] $\simeq$ 0.15), inactive K1.5 main sequence star at $d = 300$ pc. Using data from the Transiting Exoplanet Survey Satellite and the Las Cumbres Observatory Global Telescope, we find that TOI-3261b has a radius of $3.82_{-0.35}^{+0.42}$ $R_{\oplus}$. Moreover, radial velocities from ESPRESSO and HARPS reveal a mass of $30.3_{-2.4}^{+2.2}$ $M_{\oplus}$, more than twice the median mass of Neptune-sized planets on longer orbits. We investigate multiple mechanisms of mass loss that can reproduce the current-day properties of TOI-3261b, simulating the evolution of the planet via tidal stripping and photoevaporation. Thermal evolution models suggest that TOI-3261b should retain an envelope potentially enriched with volatiles constituting $\sim$5% of its total mass. This is the second highest envelope mass fraction among ultra-hot Neptunes discovered to date, making TOI-3261b an ideal candidate for atmospheric follow-up observations., Comment: 20 pages, 11 figures, accepted to AJ

Atomic short-range order (SRO) in direct-bandgap GeSn for infrared photonics has recently attracted attention due to its notable impact on band structures. However, the SRO in GeSn thin films grown by different methods have hardly been compared. This paper compares SRO in GeSn thin films of similar compositions grown by molecular beam epitaxy (MBE) and chemical vapor deposition (CVD) using atom probe tomography. An $\sim$15% stronger preference for Sn-Sn 1$^{st}$ nearest neighbor (1NN) is observed in MBE GeSn than CVD GeSn for both thin film and quantum well samples with Sn composition ranging from 7 to 20%. Interestingly, samples grown by different deposition tools under the same method (either MBE or CVD) showed remarkable consistency in Sn-Sn 1NN SRO, while MBE vs. CVD showed clear differences. Supported by theoretical modeling, we consider that this difference in SRO originates from the impact of surface termination, where MBE surfaces are exposed to ultrahigh vacuum while CVD surfaces are terminated by H to a good extent. This finding not only suggests engineering surface termination or surfactants during the growth as a potential approach to control SRO in GeSn, but also provides insight into the underlying reasons for very different growth temperature between MBE and CVD that directly impact the strain relaxation behavior.

Recent observations have confirmed circumplanetary disks (CPDs) embedded in parental protoplanetary disks (PPDs). On the other hand, planetary-mass companions (PMCs) and planetary-mass objects (PMOs) are likely to harbor their own accretion disks. Unlike PPDs, CPDs and other disks around planet analogues are generally too compact to be spatially resolved by current instrumentation. In this study, we generate over 4,000 spectral energy distributions (SEDs) of circum-PMO-disks (CPMODs) with various host temperature and disk properties, which can be categorized into four prototypes, i.e., full, pre-transitional, transitional and evolved CPMODs. We propose a classification scheme based on their near-to-mid-infrared colors. Using those CPMOD models, we synthesize JWST (NIRCam and MIRI) photometry for F444W, F1000W and F2550W wide filters. We show F444W - F1000W and F444 - F2550W colors can be applied to distinguish different types of CPMODs, especially for those around hot hosts. Our results indicate that the ongoing and future JWST observations are promising to unveil structures and properties of CPMODs., Comment: 18 pages, 7 figures, accepted for publication in ApJ

Collaborative graph analysis across multiple institutions is becoming increasingly popular. Realistic examples include social network analysis across various social platforms, financial transaction analysis across multiple banks, and analyzing the transmission of infectious diseases across multiple hospitals. We define the federated graph analytics, a new problem for collaborative graph analytics under differential privacy. Although differentially private graph analysis has been widely studied, it fails to achieve a good tradeoff between utility and privacy in federated scenarios, due to the limited view of local clients and overlapping information across multiple subgraphs. Motivated by this, we first propose a federated graph analytic framework, named FEAT, which enables arbitrary downstream common graph statistics while preserving individual privacy. Furthermore, we introduce an optimized framework based on our proposed degree-based partition algorithm, called FEAT+, which improves the overall utility by leveraging the true local subgraphs. Finally, extensive experiments demonstrate that our FEAT and FEAT+ significantly outperform the baseline approach by approximately one and four orders of magnitude, respectively., Comment: 13 pages

Context. About 25% -- 50% of white dwarfs are found to be contaminated by heavy elements, which are believed to originate from external sources such as planetary materials. Elemental abundances suggest that most of the pollutants are rocky objects and only a small fraction of white dwarfs bear traces of volatile accretion. Aims. In order to account for the scarcity of volatile pollution, we investigate the role of the white dwarfs' magnetospheres in shielding the volatile content of icy objects. Methods. We estimated the volatile sublimation of inward-drifting exocomets. We assume the orbits of the exocomets are circularized by the Alfven wing drag that is effective for long-period comets. Results. Volatile material can sublimate outside the corotation radius and be shielded by the magnetic field. {The two conditions for this volatile-shielded mechanism are that the magnetosphere radius must be larger than the corotation radius and that the volatiles are depleted outside the corotation radius, which requires a sufficiently slow orbital circularization process.} We applied our model to nine white dwarfs with known rotational periods, magnetic fields, and atmosphere compositions. Our volatile-shielded model may explain the excess of volatile elements such as C and S in the disk relative to the white dwarf atmosphere in WD2326+049 (G29-38). Nevertheless, given the sensitivity of our model to the circularization process and material properties of icy objects, there remains considerable uncertainty in our results. Conclusions. Our work suggests a possible explanation for the scarcity of volatile-accretion signatures among white dwarfs. We also identify a correlation between the magnetic field strength, the spin period, and the composition of pollutants in white dwarf atmospheres., Comment: 13 pages, 11 figures. Accepted for publication in A&A

Predicting simple function classes has been widely used as a testbed for developing theory and understanding of the trained Transformer's in-context learning (ICL) ability. In this paper, we revisit the training of Transformers on linear regression tasks, and different from all the existing literature, we consider a bi-objective prediction task of predicting both the conditional expectation $\mathbb{E}[Y|X]$ and the conditional variance Var$(Y|X)$. This additional uncertainty quantification objective provides a handle to (i) better design out-of-distribution experiments to distinguish ICL from in-weight learning (IWL) and (ii) make a better separation between the algorithms with and without using the prior information of the training distribution. Theoretically, we show that the trained Transformer reaches near Bayes-optimum, suggesting the usage of the information of the training distribution. Our method can be extended to other cases. Specifically, with the Transformer's context window $S$, we prove a generalization bound of $\tilde{\mathcal{O}}(\sqrt{\min\{S, T\}/(n T)})$ on $n$ tasks with sequences of length $T$, providing sharper analysis compared to previous results of $\tilde{\mathcal{O}}(\sqrt{1/n})$. Empirically, we illustrate that while the trained Transformer behaves as the Bayes-optimal solution as a natural consequence of supervised training in distribution, it does not necessarily perform a Bayesian inference when facing task shifts, in contrast to the \textit{equivalence} between these two proposed in many existing literature. We also demonstrate the trained Transformer's ICL ability over covariates shift and prompt-length shift and interpret them as a generalization over a meta distribution.

In this paper, we consider the supervised pretrained transformer for a class of sequential decision-making problems. The class of considered problems is a subset of the general formulation of reinforcement learning in that there is no transition probability matrix, and the class of problems covers bandits, dynamic pricing, and newsvendor problems as special cases. Such a structure enables the use of optimal actions/decisions in the pretraining phase, and the usage also provides new insights for the training and generalization of the pretrained transformer. We first note that the training of the transformer model can be viewed as a performative prediction problem, and the existing methods and theories largely ignore or cannot resolve the arisen out-of-distribution issue. We propose a natural solution that includes the transformer-generated action sequences in the training procedure, and it enjoys better properties both numerically and theoretically. The availability of the optimal actions in the considered tasks also allows us to analyze the properties of the pretrained transformer as an algorithm and explains why it may lack exploration and how this can be automatically resolved. Numerically, we categorize the advantages of the pretrained transformer over the structured algorithms such as UCB and Thompson sampling into three cases: (i) it better utilizes the prior knowledge in the pretraining data; (ii) it can elegantly handle the misspecification issue suffered by the structured algorithms; (iii) for short time horizon such as $T\le50$, it behaves more greedy and enjoys much better regret than the structured algorithms which are designed for asymptotic optimality.

The planet's mass loss is important for the planet's formation and evolution. The radius valley (RV) is believed to be triggered by evaporation-induced mass loss. As an alternative mechanism for the RV, the mass loss of post-impact planets is thoroughly investigated in this work. The impact energy is converted to the planet's internal energy, enhancing its core energy and accelerating mass loss and orbital migration. As the host star changes from K-type to F-type, the planet's mass loss and orbital migration increase. When the initial gas-to-core mass ratio (GCR) is small, the migration efficiency for planets around K-type stars will increase, which helps to suppress mass loss and retain the planet's mass and radius within a specific range. On the contrary, planets around more massive F-type stars experience more substantial mass loss, potentially leading to complete mass loss, and migrate to orbits with longer periods. Our calculation shows that planets around different spectral types of host stars give rise to an RV ranging from 1.3-2.0 $R_{\oplus}$, consistent with the observed range of 1.3-2.6 $R_{\oplus}$. Despite the presence of uncertain parameters, the planetesimal impact can promote the RV establishment for planets around host stars of different spectral types., Comment: 19 pages, 12 figures; ApJ Accepted

In digital IC design, compared with post-synthesis netlists or layouts, the early register-transfer level (RTL) stage offers greater optimization flexibility for both designers and EDA tools. However, timing information is typically unavailable at this early stage. Some recent machine learning (ML) solutions propose to predict the total negative slack (TNS) and worst negative slack (WNS) of an entire design at the RTL stage, but the fine-grained timing information of individual registers remains unavailable. In this work, we address the unique challenges of RTL timing prediction and introduce our solution named RTL-Timer. To the best of our knowledge, this is the first fine-grained general timing estimator applicable to any given design. RTL-Timer explores multiple promising RTL representations and proposes customized loss functions to capture the maximum arrival time at register endpoints. RTL-Timer's fine-grained predictions are further applied to guide optimization in a standard synthesis flow. The average results on unknown test designs demonstrate a correlation above 0.89, contributing around 3% WNS and 10% TNS improvement after optimization., Comment: Published as a conference paper at Design Automation Conference (DAC) 2024

In this paper, we study the problem of watermarking large language models (LLMs). We consider the trade-off between model distortion and detection ability and formulate it as a constrained optimization problem based on the green-red algorithm of Kirchenbauer et al. (2023a). We show that the optimal solution to the optimization problem enjoys a nice analytical property which provides a better understanding and inspires the algorithm design for the watermarking process. We develop an online dual gradient ascent watermarking algorithm in light of this optimization formulation and prove its asymptotic Pareto optimality between model distortion and detection ability. Such a result guarantees an averaged increased green list probability and henceforth detection ability explicitly (in contrast to previous results). Moreover, we provide a systematic discussion on the choice of the model distortion metrics for the watermarking problem. We justify our choice of KL divergence and present issues with the existing criteria of ``distortion-free'' and perplexity. Finally, we empirically evaluate our algorithms on extensive datasets against benchmark algorithms.

With the proliferation of spatio-textual data, Top-k KNN spatial keyword queries (TkQs), which return a list of objects based on a ranking function that evaluates both spatial and textual relevance, have found many real-life applications. Existing geo-textual indexes for TkQs use traditional retrieval models like BM25 to compute text relevance and usually exploit a simple linear function to compute spatial relevance, but its effectiveness is limited. To improve effectiveness, several deep learning models have recently been proposed, but they suffer severe efficiency issues. To the best of our knowledge, there are no efficient indexes specifically designed to accelerate the top-k search process for these deep learning models. To tackle these issues, we propose a novel technique, which Learns to Index the Spatio-Textual data for answering embedding based spatial keyword queries (called LIST). LIST is featured with two novel components. Firstly, we propose a lightweight and effective relevance model that is capable of learning both textual and spatial relevance. Secondly, we introduce a novel machine learning based Approximate Nearest Neighbor Search (ANNS) index, which utilizes a new learning-to-cluster technique to group relevant queries and objects together while separating irrelevant queries and objects. Two key challenges in building an effective and efficient index are the absence of high-quality labels and unbalanced clustering results. We develop a novel pseudo-label generation technique to address the two challenges. Experimental results show that LIST significantly outperforms state-of-the-art methods on effectiveness, with improvements up to 19.21% and 12.79% in terms of NDCG@1 and Recall@10, and is three orders of magnitude faster than the most effective baseline.

Current imaging observations of protoplanetary disks using ALMA primarily focus on the sub-millimeter wavelength, leaving a gap in effective observational approaches for centimeter-sized dust, which is crucial to the issue of planet formation. The forthcoming SKA and ngVLA may rectify this deficiency. In this paper, we employ multi-fluid hydrodynamic numerical simulations and radiative transfer calculations to investigate the potential of SKA1-Mid, ngVLA, and SKA2 for imaging protoplanetary disks at sub-cm/cm wavelengths. We create mock images with ALMA/SKA/ngVLA at multi-wavelengths based on the hydrodynamical simulation output, and test different sensitivity and spatial resolutions. We discover that both SKA and ngVLA will serve as excellent supplements to the existing observational range of ALMA, and their high resolution enables them to image substructures in the disk's inner region ($\sim$ 5 au from the stellar). Our results indicate that SKA and ngVLA can be utilized for more extended monitoring programs in the centimeter waveband. While in the sub-centimeter range, ngVLA possesses the capability to produce high-fidelity images within shorter observation times ($\sim$ 1 hour on source time) than previous research, holding potential for future survey observations. We also discuss for the first time the potential of SKA2 for observing protoplanetary disks at a 0.7 cm wavelength., Comment: 10 pages, 6 figures, accepted by ApJ. Welcome any comments and suggestions!

Assertion-based verification (ABV) is a critical method for ensuring design circuits comply with their architectural specifications, which are typically described in natural language. This process often requires significant interpretation by engineers to convert these specifications into functional verification assertions. Existing methods for generating assertions from natural language specifications are limited to sentences extracted by engineers, discouraging the practical application. In this work, we present AssertLLM, an automatic assertion generation framework for complete specification files. AssertLLM breaks down the complex task into three phases, incorporating three customized Large Language Models (LLMs) for extracting structural specifications, mapping signal definitions, and generating assertions. Additionally, we provide an open-source benchmark for assessing assertion generation capabilities. Our evaluation of AssertLLM on a full design, encompassing 23 signals, demonstrates that 89% of the generated assertions are both syntactically and functionally accurate.

Differentially private triangle counting in graphs is essential for analyzing connection patterns and calculating clustering coefficients while protecting sensitive individual information. Previous works have relied on either central or local models to enforce differential privacy. However, a significant utility gap exists between the central and local models of differentially private triangle counting, depending on whether or not a trusted server is needed. In particular, the central model provides a high accuracy but necessitates a trusted server. The local model does not require a trusted server but suffers from limited accuracy. Our paper introduces a crypto-assisted differentially private triangle counting system, named CARGO, leveraging cryptographic building blocks to improve the effectiveness of differentially private triangle counting without assumption of trusted servers. It achieves high utility similar to the central model but without the need for a trusted server like the local model. CARGO consists of three main components. First, we introduce a similarity-based projection method that reduces the global sensitivity while preserving more triangles via triangle homogeneity. Second, we present a triangle counting scheme based on the additive secret sharing that securely and accurately computes the triangles while protecting sensitive information. Third, we design a distributed perturbation algorithm that perturbs the triangle count with minimal but sufficient noise. We also provide a comprehensive theoretical and empirical analysis of our proposed methods. Extensive experiments demonstrate that our CARGO significantly outperforms the local model in terms of utility and achieves high-utility triangle counting comparable to the central model., Comment: Accepted by ICDE 2024

The automatic generation of RTL code (e.g., Verilog) using natural language instructions and large language models (LLMs) has attracted significant research interest recently. However, most existing approaches heavily rely on commercial LLMs such as ChatGPT, while open-source LLMs tailored for this specific design generation task exhibit notably inferior performance. The absence of high-quality open-source solutions restricts the flexibility and data privacy of this emerging technique. In this study, we present a new customized LLM solution with a modest parameter count of only 7B, achieving better performance than GPT-3.5 on two representative benchmarks for RTL code generation. This remarkable balance between accuracy and efficiency is made possible by leveraging our new RTL code dataset and a customized LLM algorithm, both of which will be made fully open-source. Furthermore, we have successfully quantized our LLM to 4-bit with a total size of 4GB, enabling it to function on a single laptop with only slight performance degradation. This efficiency allows the RTL generator to serve as a local assistant for engineers, ensuring all design privacy concerns are addressed.

In this study, we introduce JarviX, a sophisticated data analytics framework. JarviX is designed to employ Large Language Models (LLMs) to facilitate an automated guide and execute high-precision data analyzes on tabular datasets. This framework emphasizes the significance of varying column types, capitalizing on state-of-the-art LLMs to generate concise data insight summaries, propose relevant analysis inquiries, visualize data effectively, and provide comprehensive explanations for results drawn from an extensive data analysis pipeline. Moreover, JarviX incorporates an automated machine learning (AutoML) pipeline for predictive modeling. This integration forms a comprehensive and automated optimization cycle, which proves particularly advantageous for optimizing machine configuration. The efficacy and adaptability of JarviX are substantiated through a series of practical use case studies.

Realizing nonabelian topological orders and their anyon excitations is an esteemed objective. In this work, we propose a novel approach towards this goal: quantum simulating topological orders in the doubled Hilbert space - the space of density matrices. We show that ground states of all quantum double models (toric code being the simplest example) can be efficiently prepared in the doubled Hilbert space; only finite-depth local operations are needed. In contrast, this is not the case in the conventional Hilbert space: Ground states of only some of these models are known to be efficiently preparable. Additionally, we find that nontrivial anyon braiding effects, both abelian and nonabelian, can be realized in the doubled Hilbert space, although the intrinsic nature of density matrices restricts possible excitations., Comment: Published version. 7 pages, 4 figures

In modern VLSI design flow, the register-transfer level (RTL) stage is a critical point, where designers define precise design behavior with hardware description languages (HDLs) like Verilog. Since the RTL design is in the format of HDL code, the standard way to evaluate its quality requires time-consuming subsequent synthesis steps with EDA tools. This time-consuming process significantly impedes design optimization at the early RTL stage. Despite the emergence of some recent ML-based solutions, they fail to maintain high accuracy for any given RTL design. In this work, we propose an innovative pre-synthesis PPA estimation framework named MasterRTL. It first converts the HDL code to a new bit-level design representation named the simple operator graph (SOG). By only adopting single-bit simple operators, this SOG proves to be a general representation that unifies different design types and styles. The SOG is also more similar to the target gate-level netlist, reducing the gap between RTL representation and netlist. In addition to the new SOG representation, MasterRTL proposes new ML methods for the RTL-stage modeling of timing, power, and area separately. Compared with state-of-the-art solutions, the experiment on a comprehensive dataset with 90 different designs shows accuracy improvement by 0.33, 0.22, and 0.15 in correlation for total negative slack (TNS), worst negative slack (WNS), and power, respectively., Comment: To be published in the Proceedings of 42nd IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 2023

In this work, we propose a Unified framework of Sequential Search and Recommendation (UnifiedSSR) for joint learning of user behavior history in both search and recommendation scenarios. Specifically, we consider user-interacted products in the recommendation scenario, user-interacted products and user-issued queries in the search scenario as three distinct types of user behaviors. We propose a dual-branch network to encode the pair of interacted product history and issued query history in the search scenario in parallel. This allows for cross-scenario modeling by deactivating the query branch for the recommendation scenario. Through the parameter sharing between dual branches, as well as between product branches in two scenarios, we incorporate cross-view and cross-scenario associations of user behaviors, providing a comprehensive understanding of user behavior patterns. To further enhance user behavior modeling by capturing the underlying dynamic intent, an Intent-oriented Session Modeling module is designed for inferring intent-oriented semantic sessions from the contextual information in behavior sequences. In particular, we consider self-supervised learning signals from two perspectives for intent-oriented semantic session locating, which encourage session discrimination within each behavior sequence and session alignment between dual behavior sequences. Extensive experiments on three public datasets demonstrate that UnifiedSSR consistently outperforms state-of-the-art methods for both search and recommendation.

Inspired by the recent success of large language models (LLMs) like ChatGPT, researchers start to explore the adoption of LLMs for agile hardware design, such as generating design RTL based on natural-language instructions. However, in existing works, their target designs are all relatively simple and in a small scale, and proposed by the authors themselves, making a fair comparison among different LLM solutions challenging. In addition, many prior works only focus on the design correctness, without evaluating the design qualities of generated design RTL. In this work, we propose an open-source benchmark named RTLLM, for generating design RTL with natural language instructions. To systematically evaluate the auto-generated design RTL, we summarized three progressive goals, named syntax goal, functionality goal, and design quality goal. This benchmark can automatically provide a quantitative evaluation of any given LLM-based solution. Furthermore, we propose an easy-to-use yet surprisingly effective prompt engineering technique named self-planning, which proves to significantly boost the performance of GPT-3.5 in our proposed benchmark.

Learning with rejection has been a prototypical model for studying the human-AI interaction on prediction tasks. Upon the arrival of a sample instance, the model first uses a rejector to decide whether to accept and use the AI predictor to make a prediction or reject and defer the sample to humans. Learning such a model changes the structure of the original loss function and often results in undesirable non-convexity and inconsistency issues. For the classification with rejection problem, several works develop consistent surrogate losses for the joint learning of the predictor and the rejector, while there have been fewer works for the regression counterpart. This paper studies the regression with rejection (RwR) problem and investigates a no-rejection learning strategy that uses all the data to learn the predictor. We first establish the consistency for such a strategy under the weak realizability condition. Then for the case without the weak realizability, we show that the excessive risk can also be upper bounded with the sum of two parts: prediction error and calibration error. Lastly, we demonstrate the advantage of such a proposed learning strategy with empirical evidence.

Uncertainty sampling is a prevalent active learning algorithm that queries sequentially the annotations of data samples which the current prediction model is uncertain about. However, the usage of uncertainty sampling has been largely heuristic: (i) There is no consensus on the proper definition of "uncertainty" for a specific task under a specific loss; (ii) There is no theoretical guarantee that prescribes a standard protocol to implement the algorithm, for example, how to handle the sequentially arrived annotated data under the framework of optimization algorithms such as stochastic gradient descent. In this work, we systematically examine uncertainty sampling algorithms under both stream-based and pool-based active learning. We propose a notion of equivalent loss which depends on the used uncertainty measure and the original loss function and establish that an uncertainty sampling algorithm essentially optimizes against such an equivalent loss. The perspective verifies the properness of existing uncertainty measures from two aspects: surrogate property and loss convexity. Furthermore, we propose a new notion for designing uncertainty measures called \textit{loss as uncertainty}. The idea is to use the conditional expected loss given the features as the uncertainty measure. Such an uncertainty measure has nice analytical properties and generality to cover both classification and regression problems, which enable us to provide the first generalization bound for uncertainty sampling algorithms under both stream-based and pool-based settings, in the full generality of the underlying model and problem. Lastly, we establish connections between certain variants of the uncertainty sampling algorithms with risk-sensitive objectives and distributional robustness, which can partly explain the advantage of uncertainty sampling algorithms when the sample size is small., Comment: Update: add numerical illustrations and experiments; correct some typos and modify the numbering

In this paper, we consider the uncertainty quantification problem for regression models. Specifically, we consider an individual calibration objective for characterizing the quantiles of the prediction model. While such an objective is well-motivated from downstream tasks such as newsvendor cost, the existing methods have been largely heuristic and lack of statistical guarantee in terms of individual calibration. We show via simple examples that the existing methods focusing on population-level calibration guarantees such as average calibration or sharpness can lead to harmful and unexpected results. We propose simple nonparametric calibration methods that are agnostic of the underlying prediction model and enjoy both computational efficiency and statistical consistency. Our approach enables a better understanding of the possibility of individual calibration, and we establish matching upper and lower bounds for the calibration error of our proposed methods. Technically, our analysis combines the nonparametric analysis with a covering number argument for parametric analysis, which advances the existing theoretical analyses in the literature of nonparametric density estimation and quantile bandit problems. Importantly, the nonparametric perspective sheds new theoretical insights into regression calibration in terms of the curse of dimensionality and reconciles the existing results on the impossibility of individual calibration. To our knowledge, we make the first effort to reach both individual calibration and finite-sample guarantee with minimal assumptions in terms of conformal prediction. Numerical experiments show the advantage of such a simple approach under various metrics, and also under covariates shift. We hope our work provides a simple benchmark and a starting point of theoretical ground for future research on regression calibration., Comment: Accepted at NeurIPS 2023 and update a camera-ready version; Add some experiments and literature reviews

Realizing topological orders and topological quantum computation is a central task of modern physics. An important but notoriously hard question in this endeavor is how to diagnose topological orders that lack conventional order parameters. A breakthrough in this problem is the discovery of topological entanglement entropy, which can be used to detect nontrivial topological order from a ground state wave function, but is far from enough for fully determining the topological order. In this work, we take a key step further in this direction: We propose a simple entanglement-based protocol for extracting the quantum dimensions of all anyons from a single ground state wave function in two dimensions. The choice of the space manifold and the ground state is arbitrary. This protocol is both validated in the continuum and verified on lattices, and we anticipate it to be realizable in various quantum simulation platforms., Comment: Published version. 15 pages, 7 captioned figures

In this paper, we study the predict-then-optimize problem where the output of a machine learning prediction task is used as the input of some downstream optimization problem, say, the objective coefficient vector of a linear program. The problem is also known as predictive analytics or contextual linear programming. The existing approaches largely suffer from either (i) optimization intractability (a non-convex objective function)/statistical inefficiency (a suboptimal generalization bound) or (ii) requiring strong condition(s) such as no constraint or loss calibration. We develop a new approach to the problem called \textit{maximum optimality margin} which designs the machine learning loss function by the optimality condition of the downstream optimization. The max-margin formulation enjoys both computational efficiency and good theoretical properties for the learning procedure. More importantly, our new approach only needs the observations of the optimal solution in the training data rather than the objective function, which makes it a new and natural approach to the inverse linear programming problem under both contextual and context-free settings; we also analyze the proposed method under both offline and online settings, and demonstrate its performance using numerical experiments., Comment: to be published in ICML 2023

Quantum entanglement is a particularly useful characterization of topological orders which lack conventional order parameters. In this work, we study the entanglement in topologically ordered states between two arbitrary spatial regions, using two distinct mixed-state entanglement measures: the so-called "computable cross-norm or realignment" (CCNR) negativity, and the more well-known partial-transpose (PT) negativity. We first generally compute the entanglement measures: We obtain general expressions both in (2+1)D Chern-Simons field theories under certain simplifying conditions, and in the Pauli stabilizer formalism that applies to lattice models in all dimensions. While the field-theoretic results are expected to be topological and universal, the lattice results contain nontopological/nonuniversal terms as well. This raises the important problem of continuum-lattice comparison which is crucial for practical applications. When the two spatial regions and the remaining subsystem do not have triple intersection, we solve the problem by proposing a general strategy for extracting the topological and universal terms in both entanglement measures. Examples in the (2+1)D $Z_2$ toric code model are also presented. In the presence of trisection points, however, our result suggests that the subleading piece in the PT negativity is not topological and depends on the local geometry of the trisections, which is in harmonics with a technical subtlety in the field-theoretic calculation., Comment: Published version, 22 pages, 9 captioned figures

In this work, we present a three-part system that automatically sorts books on a shelf using the PR- 2 platform. The paper describes a methodology to sufficiently detect and recognize books using a multistep vision pipeline based on deep learning models as well as conventional computer vision. Furthermore, the difficulties of relocating books using a bi-manual robot along with solutions based on MoveIt and BioIK are being addressed. Experiments show that the performance is overall good enough to repeatedly sort three books on a shelf. Nevertheless, further improvements are being discussed, potentially leading to a more robust book recognition and more versatile manipulation techniques.

During the inspiralling of a white dwarf (WD) into an intermediate-mass black hole (~ 10^{2-5} M_sun), both gravitational waves (GWs) and electromagnetic (EM) radiation are emitted. Once the eccentric orbit's pericenter radius approaches the tidal radius, the WD would be tidally stripped upon each pericenter passage. The accretion of these stripped mass would produce EM radiation. It is suspected that the recently discovered new types of transients, namely the quasi-periodic eruptions and the fast ultraluminous X-ray bursts, might originate from such systems. Modeling these flares requires a prediction of the amount of stripped mass from the WD and the details of the mass supply to the accretion disk. We run hydrodynamical simulations to study the orbital parameter dependence of the stripped mass. We find that our results match the analytical estimate that the stripped mass is proportional to z^{5/2}, where z is the excess depth by which the WD overfills its instantaneous Roche lobe at the pericenter. The corresponding fallback rate of the stripped mass is calculated, which may be useful in interpreting the individual flaring light curve in candidate EM sources. We further calculate the long-term mass-loss evolution of a WD during its inspiral and the detectability of the GW and EM signals. The EM signal from the mass-loss stage can be easily detected: the limiting distance is ~ 320(M_h/10^4 M_sun)^{1/2} Mpc for Einstein Probe. The GW signal, for the space-borne detectors such as Laser Interferometer Space Antenna or TianQin, can be detected only within the Local Supercluster (~ 33 Mpc)., Comment: 18 pages, 13 figures, Accepted for publication in ApJ

Publishing graph statistics under node differential privacy has attracted much attention since it provides a stronger privacy guarantee than edge differential privacy. Existing works related to node differential privacy assume a trusted data curator who holds the whole graph. However, in many applications, a trusted curator is usually not available due to privacy and security issues. In this paper, for the first time, we investigate the problem of publishing the graph degree distribution under Node Local Differential privacy (Node-LDP), which does not rely on a trusted server. We propose an algorithm to publish the degree distribution with Node-LDP by exploring how to select the optimal graph projection parameter and how to execute the local graph projection. Specifically, we propose a Crypto-assisted local projection method that combines LDP and cryptographic primitives, achieving higher accuracy than our baseline PureLDP local projection method. On the other hand, we improve our baseline Node-level parameter selection by proposing an Edge-level parameter selection that preserves more neighboring information and provides better utility. Finally, extensive experiments on real-world graphs show that Edge-level local projection provides higher accuracy than Node-level local projection, and Crypto-assisted parameter selection owns the better utility than PureLDP parameter selection, improving by up to 79.8% and 57.2% respectively., Comment: Accepted by IEEE BigData 2022, https://ieeexplore.ieee.org/document/10020435

We scrutinize the light sail scenario of the first interstellar object (ISO) 1I/2017 U1 (`Oumuamua) by making comparisons between physical models and observational constraints. These analyses can be generalized for future surveys of `Oumuamua-like objects. The light sail goes through a drift in the interstellar space due to the magnetic field and gas atoms, which poses challenges to the navigation system. When the light sail enters the inner solar system, the sideways radiation pressure leads to a considerable non-radial displacement. The immensely high dimensional ratio and the tumbling motion could cause a light curve with an extremely large amplitude and could even make the light sail invisible from time to time. These observational features allow us to examine the light sail scenario of interstellar objects. Our results show that the drift of the freely rotating light sail in the interstellar medium is $\sim 100\,$au even if the travel distance is only 1 pc. The probability is < 1.5\% for the expected brightness modulation of the light sail to match with `Oumuamua's observed variation amplitude ($\sim$ 2.5 -- 3). In addition, the probability is 0.4% for the tumbling light-sail to be visible (brighter than V=27) in all 55 observations spread over two months after discovery. Radiation pressure could cause a larger displacement that is normal to the orbital plane for a lightsail than that for `Oumuamua. Also, the ratio of anti-solar to sideways acceleration of `Oumuamua deviates from that of the light sail by ~ 1.5{\sigma}. We suggest that `Oumuamua is unlikely a light sail. The dynamics of an intruding light sail, if exist, has distinct observational signatures, which can be quantitatively identified and analyzed with our methods in future surveys., Comment: 17 pages, 13 figures Comments are welcome

Multipartite entanglement is a key resource for quantum computation. It is expected theoretically that entanglement transition may happen for multipartite random quantum states, however, which is still absent experimentally. Here, we report the observation of entanglement transition quantified by negativity using a fully connected 20-qubit superconducting processor. We implement multi-layer pseudo-random circuits to generate pseudo-random pure states of 7 to 15 qubits. Then, we investigate negativity spectra of reduced density matrices obtained by quantum state tomography for 6 qubits.Three different phases can be identified by calculating logarithmic negativities based on the negativity spectra. We observe the phase transitions by changing the sizes of environment and subsystems. The randomness of our circuits can be also characterized by quantifying the distance between the distribution of output bit-string probabilities and Porter-Thomas distribution. Our simulator provides a powerful tool to generate random states and understand the entanglement structure for multipartite quantum systems.

We present a general approach to the bulk-boundary correspondence of noninvertible topological phases, including both topological and fracton orders. This is achieved by a novel bulk construction protocol where solvable $(d+1)$-dimensional bulk models with noninvertible topology are constructed from the so-called generalized Ising (GI) models in $d$ dimensions. The GI models can then terminate on the boundaries of the bulk models. The construction generates abundant examples, including not only prototype ones such as $Z_2$ toric code models in any dimensions no less than two, and the X-cube fracton model, but also more diverse ones such as the $Z_2\times Z_2$ topological order, the 4d $Z_2$ topological order with pure-loop excitations, etc. The boundary of the solvable model is potentially anomalous and corresponds to precisely only sectors of the GI model that host certain total symmetry charges and/or satisfy certain boundary conditions. We derive a concrete condition for such bulk-boundary correspondence. The condition is violated only when the bulk model is either trivial or fracton ordered. A generalized notion of Kramers-Wannier duality plays an important role in the construction. Also, utilizing the duality, we find an example where a single anomalous theory can be realized on the boundaries of two distinct bulk fracton models, a phenomenon not expected in the case of topological orders. More generally, topological orders may also be generated starting with lattice models beyond the GI models, such as those with symmetry protected topological orders, through a variant bulk construction, which we provide in an appendix., Comment: published version, 17+18 pages, 5 figures

In this paper, we study the problem of bandits with knapsacks (BwK) in a non-stationary environment. The BwK problem generalizes the multi-arm bandit (MAB) problem to model the resource consumption associated with playing each arm. At each time, the decision maker/player chooses to play an arm, and s/he will receive a reward and consume certain amount of resource from each of the multiple resource types. The objective is to maximize the cumulative reward over a finite horizon subject to some knapsack constraints on the resources. Existing works study the BwK problem under either a stochastic or adversarial environment. Our paper considers a non-stationary environment which continuously interpolates between these two extremes. We first show that the traditional notion of variation budget is insufficient to characterize the non-stationarity of the BwK problem for a sublinear regret due to the presence of the constraints, and then we propose a new notion of global non-stationarity measure. We employ both non-stationarity measures to derive upper and lower bounds for the problem. Our results are based on a primal-dual analysis of the underlying linear programs and highlight the interplay between the constraints and the non-stationarity. Finally, we also extend the non-stationarity measure to the problem of online convex optimization with constraints and obtain new regret bounds accordingly.

Object dropping may occur when the robotic arm grasps objects with uneven mass distribution due to additional moments generated by objects' gravity. To solve this problem, we present a novel work that does not require extra wrist and tactile sensors and large amounts of experiments for learning. First, we obtain the center-of-mass position of the rod object using the widely fixed joint torque sensors on the robot arm and RGBD camera. Further, we give the strategy of grasping to improve grasp stability. Simulation experiments are performed in "Mujoco". Results demonstrate that our work is effective in enhancing grasping robustness.

The one-dimensional lattice Schwinger model has recently been realized by using bosons in optical lattices. This model contains both confinement and deconfinement phases, whose phase diagram is controlled by the mass of the matter field and the topological angle. Since varying the mass of matter field is straightforward experimentally, we propose how to tune the topological angle, allowing accessing the entire phase diagram. We propose that direct experimental evidence of confinement and deconfinement can be obtained by measuring whether a physical charge is localized around a fixed gauge charge to screen it. We also discuss the PXP model realized in the Rydberg atoms array, which is equivalent to the lattice Schwinger model when all local gauge charges are fixed as zero. Although the gauge charges are fixed, we can alternatively probe the confinement and the deconfinement in the PXP model by studying the relative motion of a pair of a physical charge and an anti-charge. Our scheme can be directly implemented in these two relevant experimental platforms of ultracold atom quantum simulators., Comment: 8 pages, 6 figures

GeSn on Si has attracted much research interest due to its tunable direct bandgap for mid-infrared applications. Recently, short-range order (SRO) in GeSn alloys has been theoretically predicted, which profoundly impacts the band structure. However, characterizing SRO in GeSn is challenging. Guided by physics-informed Poisson statistical analyses of Kth-nearest neighbors (KNN) in atom probe tomography, a new approach is demonstrated here for 3D nanoscale SRO mapping and semi-quantitative strain mapping in GeSn. For GeSn with ~14 at.% Sn, the SRO parameters of Sn-Sn 1NN in 10x10x10 nm$^{3}$ nanocubes can deviate from that of the random alloys by $\pm$15%. The relatively large fluctuation of the SRO parameters contributes to band-edge softening observed optically. Sn-Sn 1NN also tends to be more favored towards the surface, less favored under strain relaxation or tensile strain, while almost independent of local Sn composition. An algorithm based on least square fit of atomic positions further verifies this Poisson-KNN statistical method. Compared to existing macroscopic spectroscopy or electron microscopy techniques, this new APT statistical analysis uniquely offers 3D SRO mapping at nanoscale resolution in a relatively large volume with millions of atoms. It can also be extended to investigate SRO in other alloy systems.