cssi/SciSciGPT-SciSciNet huggingface dataset:
Exponential bounds for the hypergeometric distribution.

We establish exponential bounds for the hypergeometric distribution which include a finite sampling correction factor, but are otherwise analogous to bounds for the binomial distribution due to Leon and Perron (Statist. Probab. Lett.62 (2003) 345-354) and Talagrand (Ann. Probab.22 (1994) 28-76). We also extend a convex ordering of Kemperman's (Nederl. Akad. Wetensch. Proc. Ser. A76 = Indag. Math.35 (1973) 149-164) for sampling without replacement from populations of real numbers between zero and one: a population of all zeros or ones (and hence yielding a hypergeometric distribution in the upper bound) gives the extreme case.
The Libra toolkit for probabilistic models

The Libra Toolkit is a collection of algorithms for learning and inference with discrete probabilistic models, including Bayesian networks, Markov networks, dependency networks, and sum-product networks. Compared to other toolkits, Libra places a greater emphasis on learning the structure of tractable models in which exact inference is efficient. It also includes a variety of algorithms for learning graphical models in which inference is potentially intractable, and for performing exact and approximate inference. Libra is released under a 2-clause BSD license to encourage broad use in academia and industry.
Community Identity and User Engagement in a Multi-Community Landscape

A community's identity defines and shapes its internal dynamics. Our current understanding of this interplay is mostly limited to glimpses gathered from isolated studies of individual communities. In this work we provide a systematic exploration of the nature of this relation across a wide variety of online communities. To this end we introduce a quantitative, language-based typology reflecting two key aspects of a community's identity: how distinctive, and how temporally dynamic it is. By mapping almost 300 Reddit communities into the landscape induced by this typology, we reveal regularities in how patterns of user engagement vary with the characteristics of a community. Our results suggest that the way new and existing users engage with a community depends strongly and systematically on the nature of the collective identity it fosters, in ways that are highly consequential to community maintainers. For example, communities with distinctive and highly dynamic identities are more likely to retain their users. However, such niche communities also exhibit much larger acculturation gaps between existing users and newcomers, which potentially hinder the integration of the latter. More generally, our methodology reveals differences in how various social phenomena manifest across communities, and shows that structuring the multi-community landscape can lead to a better understanding of the systematic nature of this diversity.
Hausdorff dimensions of very well intrinsically approximable subsets of quadratic hypersurfaces

We prove an analogue of a theorem of A. Pollington and S. Velani ('05), furnishing an upper bound on the Hausdorff dimension of certain subsets of the set of very well intrinsically approximable points on a quadratic hypersurface. The proof incorporates the framework of intrinsic approximation on such hypersurfaces first developed in the authors' joint work with D. Kleinbock (preprint '14) with ideas from work of D. Kleinbock, E. Lindenstrauss, and B. Weiss ('04).
Asynchronous dynamic Bayesian networks

Systems such as sensor networks and teams of autonomous robots consist of multiple autonomous entities that interact with each other in a distributed, asynchronous manner. These entities need to keep track of the state of the system as it evolves. Asynchronous systems lead to special challenges for monitoring, as nodes must update their beliefs independently of each other and no central coordination is possible. Furthermore, the state of the system continues to change as beliefs are being updated. Previous approaches to developing distributed asynchronous probabilistic reasoning systems have used static models. We present an approach using dynamic models, that take into account the way the system changes state over time. Our approach, which is based on belief propagation, is fully distributed and asynchronous, and allows the world to keep on changing as messages are being sent around. Experimental results show that our approach compares favorably to the factored frontier algorithm.
Central limit theorem for a class of SPDEs

In this paper we establish the central limit theorem for a class of stochastic partial differential equations and as an application derive this theorem for two widely studied population models: super-Brownian motion and the Fleming-Viot process.
K-theoretic exceptional collections at roots of unity

Using cyclotomic specializations of equivariant K-theory with respect to a torus action we derive congruences for discrete invariants of exceptional objects in derived categories of coherent sheaves on a class of varieties that includes Grassmannians and smooth quadrics. For example, we prove that if , where the ni's are powers of a fixed prime number p, then the rank of an exceptional object on X is congruent to ±1 modulo p.
Evaluating Trajectory Collision Probability through Adaptive Importance Sampling for Safe Motion Planning

This paper presents a tool for addressing a key component in many algorithms for planning robot trajectories under uncertainty: evaluation of the safety of a robot whose actions are governed by a closed-loop feedback policy near a nominal planned trajectory. We describe an adaptive importance sampling Monte Carlo framework that enables the evaluation of a given control policy for satisfaction of a probabilistic collision avoidance constraint which also provides an associated certificate of accuracy (in the form of a confidence interval). In particular this adaptive technique is well-suited to addressing the complexities of rigid-body collision checking applied to non-linear robot dynamics. As a Monte Carlo method it is amenable to parallelization for computational tractability, and is generally applicable to a wide gamut of simulatable systems, including alternative noise models. Numerical experiments demonstrating the effectiveness of the adaptive importance sampling procedure are presented and discussed.
Why things fall

In this paper we discuss Internal Relativity, a recent program to address the problem of quantum gravity. In our approach we change the relationship between spacetime and matter. Currently we view matter as propagating on spacetime. Einstein’s equations encode how spacetime curves due to the presence of matter and how spacetime, in turn, tells matter how to propagate. In internal realtivity matter and spacetime cease to exist as distinct entities, rather, they arise simultaneously from an underlying quantum system. It is through the emergent matter degrees of freedom that geometry is inferred. We have termed our program Internal Relativity to stress the importance of looking at the system from the point of view of an internal observer. We argue that special relativity is then a natural consequence of this viewpoint. The most important new aspect of Internal Relativity involves how gravity appears. It is not just a new quantum theory of gravity but a new theory of gravity. We also argue that the presence of a massive object implies curvature. In particular we show that Newtonian gravity arises in the appropriate limit. Our argument implies that there is no propagation without gravitation.
The Errors of Statistical Hypotheses and Scientific Theories

The process of error recognition is explored first in statistics, and then in science. The Type II error found in statistical hypothesis testing is found analogous to Karl Popper’s “logical probability” that is intended to measure the likelihood that a scientific theory can avoid its refutation. Nevertheless, Popper’s reliance on deductive thinking is found detracting from his demarcation that separates science and metaphysics. An improved critical logic for science is presented that permits error recognition more broadly: for induction by Popper’s falsification principle; but also for deduction and emotionality. The reality of induction creates a limitation for a science that has not accommodated a fuller menu of error recognition. The reality of induction places limits of what can be known from empiricism, and this has philosophical implications.
Modelocked mid-infrared frequency combs in a silicon microresonator

We demonstrate a near-octave spanning and soliton modelocked mid-infrared frequency comb in a silicon microresonator. The soliton state can be accomplished via either pump laser detuning or electrical tuning of the free-carrier lifetime.
Geometrically convergent distributed optimization with uncoordinated step-sizes

A recent algorithmic family for distributed optimization, DIGing's, have been shown to have geometric convergence over time-varying undirected/directed graphs [1]. Nevertheless, an identical step-size for all agents is needed. In this paper, we study the convergence rates of the Adapt-Then-Combine (ATC) variation of the DIGing algorithm under uncoordinated step-sizes. We show that the ATC variation of DIGing algorithm converges geometrically fast even if the step-sizes are different among the agents. In addition, our analysis implies that the ATC structure can accelerate convergence compared to the distributed gradient descent (DGD) structure which has been used in the original DIGing algorithm.
Fast Direct Methods for Gaussian Processes

A number of problems in probability and statistics can be addressed using the multivariate normal (Gaussian) distribution. In the one-dimensional case, computing the probability for a given mean and variance simply requires the evaluation of the corresponding Gaussian density. In the $n$ -dimensional setting, however, it requires the inversion of an $n \times n$ covariance matrix, $C$ , as well as the evaluation of its determinant, $\det (C)$ . In many cases, such as regression using Gaussian processes, the covariance matrix is of the form $C = \sigma ^2 I + K$ , where $K$ is computed using a specified covariance kernel which depends on the data and additional parameters (hyperparameters). The matrix $C$ is typically dense, causing standard direct methods for inversion and determinant evaluation to require $\mathcal {O}(n^3)$ work. This cost is prohibitive for large-scale modeling. Here, we show that for the most commonly used covariance functions, the matrix $C$ can be hierarchically factored into a product of block low-rank updates of the identity matrix, yielding an $\mathcal {O} (n\,\log^2\, n)$ algorithm for inversion. More importantly, we show that this factorization enables the evaluation of the determinant $\det (C)$ , permitting the direct calculation of probabilities in high dimensions under fairly broad assumptions on the kernel defining $K$ . Our fast algorithm brings many problems in marginalization and the adaptation of hyperparameters within practical reach using a single CPU core. The combination of nearly optimal scaling in terms of problem size with high-performance computing resources will permit the modeling of previously intractable problems. We illustrate the performance of the scheme on standard covariance kernels.
Ternary Inorganic Compounds Containing Carbon, Nitrogen, and Oxygen at High Pressures.

Ternary CxNyOz compounds are actively researched as novel high energy density and ultrahard materials. Although some synthesis work has been performed at ambient conditions, very little is known about the high pressure chemistry of of CxNyOz compounds. In this work, first-principles variable-composition evolutionary structure prediction calculations are performed with the goal of discovering novel mixed CxNyOz materials at ambient and high pressure conditions. By systematically searching ternary variable composition crystalline materials, the full ternary phase diagram is constructed in the range of pressures from 0 to 100 GPa. The search finds the C2N2O crystal containing an extended covalent network of C, N, and O atoms, having space group symmetry Cmc21, and stable above just 10 GPa. Several other novel metastable (CO)x–(N)y crystalline compounds discovered during the search, including two polymorphs of C2NO2 and two polymorphs of C3N2O3 crystals, are found to be energetically favorable compared to pol...
On quantum-classical equivalence for composed communication problems

An open problem in communication complexity proposed by several authors is to provethat for every Boolean function f, the task of computing f(x ∧ y) has polynomiallyrelated classical and quantum bounded-error complexities. We solve a variant of thisquestion. For every f, we prove that the task of computing, on input x and y, both of thequantities f(x∧y) and f(x∨y) has polynomially related classical and quantum boundederrorcomplexities. We further show that the quantum bounded-error complexity ispolynomially related to the classical deterministic complexity and the block sensitivityof f. This result holds regardless of prior entanglement.
Are Abstracts Enough for Hypothesis Generation

The potential for automatic hypothesis generation (HG) systems to improve research productivity keeps pace with the growing set of publicly available scientific information. But as data becomes easier to acquire, we must understand the effect different textual data sources have on our resulting hypotheses. Are abstracts enough for HG, or does it need full-text papers? How many papers does an HG system need to make valuable predictions? How sensitive is a general-purpose HG system to hyperparameter values or input quality? What effect does corpus size and document length have on HG results? To answer these questions we train multiple versions of knowledge network-based HG system, MOLIERE, on varying corpora in order to compare challenges and trade offs in terms of result quality and computational requirements. MOLIERE generalizes main principles of similar knowledge network-based HG systems and reinforces them with topic modeling components. The corpora include the abstract and full-text versions of PubMed Central, as well as iterative halves of MEDLINE, which allows us to compare the effect document length and count has on the results. We find that, quantitatively, corpora with a higher median document length result in marginally higher quality results, yet require substantially longer to process. However, qualitatively, full-length papers introduce a significant number of intruder terms to the resulting topics, which decreases human interpretability. Additionally, we find that the effect of document length is greater than that of document count, even if both sets contain only paper abstracts.Reproducibility: Our code and data are available online at sybrandt.com/2018/abstracts.
A Splitting Method For Overcoming the Curse of Dimensionality in Hamilton-Jacobi Equations Arising from Nonlinear Optimal Control and Differential Games with Applications to Trajectory Generation

Recent observations have been made that bridge splitting methods arising from optimization, to the Hopf and Lax formulas for Hamilton-Jacobi Equations with Hamiltonians $H(p)$. This has produced extremely fast algorithms in computing solutions of these PDEs. More recent observations were made in generalizing the Hopf and Lax formulas to state-and-time-dependent cases $H(x,p,t)$. In this article, we apply a new splitting method based on the Primal Dual Hybrid Gradient algorithm (a.k.a. Chambolle-Pock) to nonlinear optimal control and differential games problems, based on techniques from the derivation of the new Hopf and Lax formulas, which allow us to compute solutions at points $(x,t)$ directly, i.e. without the use of grids in space. This algorithm also allows us to create trajectories directly. Thus we are able to lift the curse of dimensionality a bit, and therefore compute solutions in much higher dimensions than before. And in our numerical experiments, we actually observe that our computations scale polynomially in time. Furthermore, this new algorithm is embarrassingly parallelizable.
PacGAN: The power of two samples in generative adversarial networks

Generative adversarial networks (GANs) are a technique for learning generative models of complex data distributions from samples. Despite remarkable advances in generating realistic images, a major shortcoming of GANs is the fact that they tend to produce samples with little diversity, even when trained on diverse datasets. This phenomenon, known as mode collapse, has been the focus of much recent work. We study a principled approach to handling mode collapse, which we call packing. The main idea is to modify the discriminator to make decisions based on multiple samples from the same class, either real or artificially generated. We draw analysis tools from binary hypothesis testing---in particular the seminal result of Blackwell---to prove a fundamental connection between packing and mode collapse. We show that packing naturally penalizes generators with mode collapse, thereby favoring generator distributions with less mode collapse during the training process. Numerical experiments on benchmark datasets suggest that packing provides significant improvements.
EXTERNAL ZONOTOPAL ALGEBRA

Zonotopal algebra studies pairs of dual algebraic structures that are associated with a linear matroid X and are connected to corresponding dual geometries. Both the geometry and the algebra encode in their statistics combinatorial properties of the matroid. We provide in this paper a general, unified, framework for the chapter in zonotopal algebra that is known as external. The approach is critically based on employing simultaneously the two dual algebraic constructs and invokes the underlying matroidal and geometric structures in an essential way.
Boolean function analysis meets stochastic optimization: an approximation scheme for stochastic knapsack

The stochastic knapsack problem is the stochastic variant of the classical knapsack problem in which the algorithm designer is given a a knapsack with a given capacity and a collection of items where each item is associated with a profit and a probability distribution on its size. The goal is to select a subset of items with maximum profit and violate the capacity constraint with probability at most p (referred to as the overflow probability). While several approximation algorithms [27, 22, 4, 17, 30] have been developed for this problem, most of these algorithms relax the capacity constraint of the knapsack. In this paper, we design efficient approximation schemes for this problem without relaxing the capacity constraint. (i) Our first result is in the case when item sizes are Bernoulli random variables. In this case, we design a (nearly) fully polynomial time approximation scheme (FPTAS) which only relaxes the overflow probability. (ii) Our second result generalizes the first result to the case when all the item sizes are supported on a (common) set of constant size. In this case, we obtain a quasi-FPTAS. (iii) Our third result is in the case when item sizes are so-called "hypercontractive" random variables i.e., random variables whose second and fourth moments are within constant factors of each other. In other words, the kurtosis of the random variable is upper bounded by a constant. This class has been widely studied in probability theory and most natural random variables are hypercontractive including well-known families such as Poisson, Gaussian, exponential and Laplace distributions. In this case, we design a polynomial time approximation scheme which relaxes both the overflow probability and maximum profit. Crucially, all of our algorithms meet the capacity constraint exactly, a result which was previously known only when the item sizes were Poisson or Gaussian random variables [22, 24]. Our results rely on new connections between Boolean function analysis and stochastic optimization and are obtained by an adaption and extension of ideas such as (central) limit theorems, moment matching theorems and the inuential critical index machinery of Servedio [43] developed in the context of complexity theoretic analysis of halfspaces. We believe that these ideas and techniques may prove to be useful in other stochastic optimization problems as well.
Stanley's nonunimodal Gorenstein h-vector is optimal

We classify all possible $h$-vectors of graded artinian Gorenstein algebras in socle degree 4 and codimension $\leq 17$, and in socle degree 5 and codimension $\leq 25$. We obtain as a consequence that the least number of variables allowing the existence of a nonunimodal Gorenstein $h$-vector is 13 for socle degree 4, and 17 for socle degree 5. In particular, the smallest nonunimodal Gorenstein $h$-vector is $(1,13,12,13,1)$, which was constructed by Stanley in his 1978 seminal paper on level algebras. This solves a long-standing open question in this area. All of our results are characteristic free.
Zero-error Function Computation on a Directed Acyclic Network

We study the rate region of variable-length source-network codes that are used to compute a function of messages observed over a network. The particular network considered here is the simplest instance of a directed acyclic graph (DAG) that is not a tree. Existing work on zero-error function computation in DAG networks provides bounds on the computation capacity, which is a measure of the amount of communication required per edge in the worst case. This work focuses on the average case: an achievable rate tuple describes the expected amount of communication required on each edge, where the expectation is over the probability mass function of the source messages. We describe a systematic procedure to obtain outer bounds to the rate region for computing an arbitrary demand function at the terminal. Our bounding technique works by lower bounding the entropy of the descriptions observed by the terminal conditioned on the function value and by utilizing the Schur-concave property of the entropy function.
The power of linear reconstruction attacks

We consider the power of "linear reconstruction attacks" in statistical data privacy, showing that they can be applied to a much wider range of settings than previously understood. Linear attacks have been studied before [3, 6, 11, 1, 14] but have so far been applied only in settings with releases that are "obviously" linear.Consider a database curator who manages a database of sensitive information but wants to release statistics about how a sensitive attribute (say, disease) in the database relates to some nonsensitive attributes (e.g., postal code, age, gender, etc). This setting is widely considered in the literature, partly since it arises with medical data. Specifically, we show one can mount linear reconstruction attacks based on any release that gives:1. the fraction of records that satisfy a given non-degenerate boolean function. Such releases include contingency tables (previously studied by Kasiviswanathan et al. [11]) as well as more complex outputs like the error rate of classifiers such as decision trees;2. any one of a large class of M-estimators (that is, the output of empirical risk minimization algorithms), including the standard estimators for linear and logistic regression.We make two contributions: first, we show how these types of releases can be transformed into a linear format, making them amenable to existing polynomial-time reconstruction algorithms. This is already perhaps surprising, since many of the above releases (like M-estimators) are obtained by solving highly nonlinear formulations.Second, we show how to analyze the resulting attacks under various distributional assumptions on the data. Specifically, we consider a setting in which the same statistic (either 1 or 2 above) is released about how the sensitive attribute relates to all subsets of size k (out of a total of d) nonsensitive boolean attributes.
Jupiter’s Phase Variations from Cassini: A Testbed for Future Direct-imaging Missions

We present empirical phase curves of Jupiter from ~0° to 140° as measured in multiple optical bandpasses by Cassini/Imaging Science Subsystem (ISS) during the Millennium flyby of Jupiter in late 2000 to early 2001. Phase curves are of interest for studying the energy balance of Jupiter and understanding the scattering behavior of the planet as an exoplanet analog. We find that Jupiter is significantly darker at partial phases than an idealized Lambertian planet by roughly 25% and is not well fit by Jupiter-like exoplanet atmospheric models across all wavelengths. We provide analytic fits to Jupiter's phase function in several Cassini/ISS imaging filter bandpasses. In addition, these observations show that Jupiter's color is more variable with phase angle than predicted by models. Therefore, the color of even a near Jupiter-twin planet observed at a partial phase cannot be assumed to be comparable to that of Jupiter at full phase. We discuss how the Wide-Field Infrared Survey Telescope and other future direct-imaging missions can enhance the study of cool giants.
MLSEB: Edge Bundling Using Moving Least Squares Approximation.

Edge bundling methods can effectively alleviate visual clutter and reveal high-level graph structures in large graph visualization. Researchers have devoted significant efforts to improve edge bundling according to different metrics. As the edge bundling family evolve rapidly, the quality of edge bundles receives increasing attention in the literature accordingly. In this paper, we present MLSEB, a novel method to generate edge bundles based on moving least squares (MLS) approximation. In comparison with previous edge bundling methods, we argue that our MLSEB approach can generate better results based on a quantitative metric of quality, and also ensure scalability and the efficiency for visualizing large graphs.
Fps-Sft: A Multi-Dimensional Sparse Fourier Transform Based on the Fourier Projection-Slice Theorem

We propose a multidimensional sparse Fourier transform inspired by the idea of the Fourier projection-slice theorem, called FPS-SFT. FPS-SFT extracts samples along lines (1-dimensional slices from a multidimensional data cube), which are parameterized by random slopes and offsets. The discrete Fourier transform (DFT) along those lines represents projections of multidimensional DFT of the data onto those lines. The multidimensional frequencies that are contained in the signal can be reconstructed from the DFT along lines with a low sample and computational complexity provided that the signal is sparse in the frequency domain and the lines are appropriately designed. The performance of FPS-SFT is demonstrated both theoretically and numerically. A sparse image reconstruction application is illustrated, which shows the capability of the FPS-SFT in solving less sparse scenarios containing non-uniformly distributed frequencies.
Interpolation Macdonald operators at infinity

Abstract We study the interpolation Macdonald functions, remarkable inhomogeneous generalizations of Macdonald functions, and a sequence A 1 , A 2 , … of commuting operators whose common eigenfunctions are the interpolation Macdonald functions. Such a sequence of operators arises in the projective limit of finite families of commuting q-difference operators studied by Okounkov, Knop and Sahi. The main theorem is an explicit formula for the operators A k . Our formula involves the family of Hall–Littlewood functions and a new family of inhomogeneous Hall–Littlewood functions, for which we give an explicit construction and identify as a degeneration of the interpolation Macdonald functions when q → 0 . This article is inspired by the recent papers of Nazarov–Sklyanin on Macdonald and Sekiguchi–Debiard operators, and our main theorem is an extension of their results.
EMERGENT STRUCTURES IN LARGE NETWORKS

We consider a large class of exponential random graph models and prove the existence of a region of parameter space corresponding to the emergent multipartite structure, separated by a phase transition from a region of disordered graphs. An essential feature is the formalism of graph limits as developed by Lovasz et al. for dense random graphs.
Next Order Energy Asymptotics for Riesz Potentials on Flat Tori

Let $\Lambda$ be a lattice in ${\bf R}^d$ with positive co-volume. Among $\Lambda$-periodic $N$-point configurations, we consider the minimal renormalized Riesz $s$-energy $\mathcal{E}_{s,\Lambda}(N)$. While the dominant term in the asymptotic expansion of $\mathcal{E}_{s,\Lambda}(N)$ as $N$ goes to infinity in the long range case that $0 0$ they are of the form $C_{s,d}|\Lambda|^{-s/d}N^{1+s/d}$ and $-\frac{2}{d}N\log N+\left(C_{\log,d}-2\zeta'_{\Lambda}(0)\right)N$ where we show that the constant $C_{s,d}$ is independent of the lattice $\Lambda$.
Variance estimates and almost Euclidean structure

We introduce and initiate the study of new parameters associated with any norm and any log-concave measure on $\mathbb R^n$, which provide sharp distributional inequalities. In the Gaussian context this investigation sheds light to the importance of the statistical measures of dispersion of the norm in connection with the local structure of the ambient space. As a byproduct of our study, we provide a short proof of Dvoretzky's theorem which not only supports the aforementioned significance but also complements the classical probabilistic formulation.
A stabilized mixed formulation for unsteady Brinkman equation based on the method of horizontal lines

In this paper, we present a stabilized mixed formulation for unsteady Brinkman equation. The formulation is systematically derived based on the variational multiscale formalism and the method of horizontal lines. The derivation does not need the assumption that the fine-scale variables do not depend on the time, which is the case with the conventional derivation of multiscale stabilized formulations for transient mixed problems. An expression for the stabilization parameter is obtained in terms of a bubble function, and appropriate bubble functions for various finite elements are also presented. Under the proposed formulation, equal-order interpolation for the velocity and pressure (which is computationally the most convenient) is stable. Representative numerical results are presented to illustrate the performance of the proposed formulation. Spatial and temporal convergence studies are also performed, and the proposed formulation performed well. Copyright © 2011 John Wiley & Sons, Ltd.
A generalization of an inequality of Lech relating multiplicity and colength

We study conjectured generalizations of a formula of Lech which relates the multiplicity of a finite colength ideal in an equicharacteristic local ring to its colength and prove one of these genera...
High probability generalization bounds for uniformly stable algorithms with nearly optimal rate

Algorithmic stability is a classical approach to understanding and analysis of the generalization error of learning algorithms. A notable weakness of most stability-based generalization bounds is that they hold only in expectation. Generalization with high probability has been established in a landmark paper of Bousquet and Elisseeff (2002) albeit at the expense of an additional $\sqrt{n}$ factor in the bound. Specifically, their bound on the estimation error of any $\gamma$-uniformly stable learning algorithm on $n$ samples and range in $[0,1]$ is $O(\gamma \sqrt{n \log(1/\delta)} + \sqrt{\log(1/\delta)/n})$ with probability $\geq 1-\delta$. The $\sqrt{n}$ overhead makes the bound vacuous in the common settings where $\gamma \geq 1/\sqrt{n}$. A stronger bound was recently proved by the authors (Feldman and Vondrak, 2018) that reduces the overhead to at most $O(n^{1/4})$. Still, both of these results give optimal generalization bounds only when $\gamma = O(1/n)$. We prove a nearly tight bound of $O(\gamma \log(n)\log(n/\delta) + \sqrt{\log(1/\delta)/n})$ on the estimation error of any $\gamma$-uniformly stable algorithm. It implies that for algorithms that are uniformly stable with $\gamma = O(1/\sqrt{n})$, estimation error is essentially the same as the sampling error. Our result leads to the first high-probability generalization bounds for multi-pass stochastic gradient descent and regularized ERM for stochastic convex problems with nearly optimal rate --- resolving open problems in prior work. Our proof technique is new and we introduce several analysis tools that might find additional applications.
Physical Characterization of Active Asteroid (6478) Gault

Main belt asteroid (6478) Gault has been dynamically linked with two overlapping asteroid families: Phocaea, dominated by S-type asteroids, and Tamara, dominated by low-albedo C-types. This object has recently become an interesting case for study after images obtained in late 2018 revealed that it was active and displaying a comet-like tail. Previous authors have proposed that the most likely scenarios to explain the observed activity on Gault were rotational excitation or merger of near-contact binaries. Here we use new photometric and spectroscopic data of Gault to determine its physical and compositional properties. Lightcurves derived from the photometric data showed little variation over three nights of observations, which prevented us from determining the rotation period of the asteroid. Using WISE observations of Gault and the near-Earth Asteroid Thermal Model (NEATM) we determined that this asteroid has a diameter <6 km. Near-infrared spectroscopic data obtained with the Infrared Telescope Facility showed a spectrum similar to that of S-complex asteroids, and a surface composition consistent with H chondrite meteorites. These results favor a compositional affinity between Gault and asteroid (25) Phocaea, and rules out a compositional link with the Tamara family. From the spectroscopic data we found no evidence of fresh material that could have been exposed during the outburst episodes.
Cognitive Correlates of Hippocampal Atrophy and Ventricular Enlargement in Adults with or without Mild Cognitive Impairment

We analyzed structural magnetic resonance imaging data from 58 cognitively normal and 101 mild cognitive impairment subjects. We used a general linear regression model to study the association between cognitive performance with hippocampal atrophy and ventricular enlargement using the radial distance method. Bilateral hippocampal atrophy was associated with baseline and longitudinal memory performance. Left hippocampal atrophy predicted longitudinal decline in visuospatial function. The multidomain ventricular analysis did not reveal any significant predictors.
Coherent quantum dynamics of systems with coupling-induced creation pathways

Many technologies emerging from quantum information science heavily rely upon the generation and manipulation of entangled quantum states. Here, we propose and demonstrate a new class of quantum interference phenomena that arise when states are created in and coherently converted between the propagating modes of an optical microcavity. The modal coupling introduces several new creation pathways to a nonlinear optical process within the device, which quantum mechanically interfere to drive the system between states in the time domain. The coherent conversion entangles the generated biphotons between propagation pathways, leading to cyclically evolving path-entanglement and the manifestation of coherent oscillations in second-order temporal correlations. Furthermore, the rich device physics is harnessed to tune properties of the quantum states. In particular, we show that the strength of interference between pathways can be coherently controlled, allowing for manipulation of the degree of entanglement, which can even be entirely quenched. The states can likewise be made to flip-flop between exhibiting initially correlated or uncorrelated behavior. The phenomena presented here open a route to creating higher dimensional entanglement and exotic multi-photon states. In the quantum revolution era, parallel and complementary efforts are deployed in the manipulation of quantum states and their entanglement. The authors theoretically and experimentally present a method using quantum interference in circular propagating modes of silicon microdisks to control quantum states produced by optical resonators, affording the possibility to creating higher dimensional entanglement and exotic multi-photon states.
Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPs

This paper establishes that optimistic algorithms attain gap-dependent and non-asymptotic logarithmic regret for episodic MDPs. In contrast to prior work, our bounds do not suffer a dependence on diameter-like quantities or ergodicity, and smoothly interpolate between the gap dependent logarithmic-regret, and the $\widetilde{\mathcal{O}}(\sqrt{HSAT})$-minimax rate. The key technique in our analysis is a novel ``clipped'' regret decomposition which applies to a broad family of recent optimistic algorithms for episodic MDPs.
Query processing on large graphs: Approaches to scalability and response time trade offs

Abstract Graphs, being an expressive data structure, have become increasingly important for modeling real-world applications, such as collaboration, different kinds of transactions, social networks, to name a few. With the advent of social networks and the web, the graph sizes have grown too large to fit in main memory precipitating the need for alternative approaches for an efficient, scalable evaluation of queries on graphs of any size. In this paper, we use the time-tested “divide and conquer” approach by partitioning a graph into desired number of partitions (and possibly with appropriate characteristics) and process queries over those partitions to obtain all or specified number of answers. This entails correctly computing answers that span multiple partitions or even need the same partition more than once. Given a set of partitions, there are a number of approaches using which a query can be evaluated: (i) One Partition At a Time (OPAT) approach, (ii) Traditional use of Multiple Processors (TraditionalMP), and (iii) using the Map/Reduce Multi-Processor approach (MapReduceMP) approach. The first approach, detailed in this paper, has established scalability through independent processing of partitions. The other two approaches address response time in addition to scalability. For the OPAT query evaluation approach, necessary minimal book keeping has been identified and its correctness established in this paper. Query answering on partitioned graphs also requires analyzing partitioning schemes for their impact on query processing and determining the number as well as the sequence in which partitions need to be loaded to reduce the response time for processing queries. We correlate query properties and partition characteristics to reduce query processing time in terms of the resources available. We also identify a set of quantitative metrics and use them for formulating heuristics to determine the order of loading partitions for efficient query processing. For OPAT approach, extensive experiments on large graphs (synthetic and real-world) using different partitioning schemes analyze the proposed heuristics on a variety of query types. The other two approaches are fleshed out, analyzed, and contrasted with the OPAT approach. An existing graph querying system has been extended to evaluate queries on partitioned graphs. Finally all three approaches are compared for their strengths and weaknesses.
Psychiatric genomics researchers' perspectives on best practices for returning results to individual participants.

Large-scale array-based and sequencing studies have advanced our understanding of the genetic architecture of psychiatric disorders, but also increased the potential to generate an exponentially larger amount of clinically relevant findings. As genomic testing becomes more widespread in psychiatry research, urgency grows to establish best practices for offering return of results (RoR) to individuals at risk or diagnosed with a psychiatric disorder. We interviewed an international sample (n = 39) of psychiatric genetics researchers to examine conceptualizations of “best practices” for RoR to individual research participants. While the vast majority of researchers do not offer RoR, most believed medically actionable findings (85%) and clinically valid but non–medically actionable findings (54%) should be offered. Researchers identified three main areas for improvement: interfacing with individual participants; interdisciplinary training, guidance, and integration; and quality planning and resource allocation for returning results. There are significant gaps between researchers’ visions for “best” versus “actual” RoR practices. While researchers call for participant-centered practices, including consent practices that consider any special needs of participants with psychiatric disorders, return of individually meaningful results, and effective follow-up and provisions for treatment, the current reality is that consent and RoR practices lack standardized and evidence-based norms.
Information-Guided Temporal Logic Inference with Prior Knowledge

This paper investigates the problem of inferring knowledge from data that is interpretable and informative to humans who have prior knowledge. Specifically, given a dataset as a collection of system trajectories, we infer parametric linear temporal logic (pLTL) formulas that are informative and satisfied by the trajectories in the dataset with high probability. The informativeness of the inferred formula is measured by the information gain with respect to given prior knowledge represented by a prior probability distribution. We first present two algorithms to compute the information gain with a focus on two types of prior probability distributions: stationary probability distributions and probability distributions governed by discrete time Markov chains. Then we provide a heuristic method to solve the inference problem for a subset of pLTL formulas with polynomial time complexity with respect to the number of Boolean connectives in the formula. We provide implementations of the proposed approach on explaining anomalous patterns, patterns changes and explaining the policies of Markov decision processes.
Model theory and ultraproducts

The article motivates recent work on saturation of ultrapowers from a general mathematical point of view.
Centros and Defensive Regulatory Competition: Some Thoughts and a Glimpse at the Data

This article looks at the phenomenon of ‘defensive regulatory competition’ in European corporate law following Centros, Uberseering and Inspire Art. In order to retain control over the corporate governing private limited entities operating within their territories and to prevent the proliferation of ‘foreign limited’ formations, Member States have modified some of the features of their laws that company founders consider to be the most unattractive, such as minimum capital and time-consuming incorporation procedures. The first part of the article analyzes the market for the law governing privately held firms, drawing from the debate in the United States. The US and Europe differ in that regulatory competition, as far as substantive law is concerned, focuses mainly on ex post mechanisms such as directors’ duties and veil piercing. By contrast, European competition seems to be driven by ex ante issues relating to firm formation, such as minimum capital. The second part of the article draws on an ongoing empirical research project that attempts to explore the effects of regulatory competition and uses reforms in Germany and Belgium as examples. Regression analysis suggests that at least the German 2008 reform had a minor effect on the number of UK private limited companies being set up to do business in Germany.
A Humanized Yeast Phenomic Model of Deoxycytidine Kinase to Predict Genetic Buffering of Nucleoside Analog Cytotoxicity

Knowledge about synthetic lethality can be applied to enhance the efficacy of anticancer therapies in individual patients harboring genetic alterations in their cancer that specifically render it vulnerable. We investigated the potential for high-resolution phenomic analysis in yeast to predict such genetic vulnerabilities by systematic, comprehensive, and quantitative assessment of drug–gene interaction for gemcitabine and cytarabine, substrates of deoxycytidine kinase that have similar molecular structures yet distinct antitumor efficacy. Human deoxycytidine kinase (dCK) was conditionally expressed in the Saccharomyces cerevisiae genomic library of knockout and knockdown (YKO/KD) strains, to globally and quantitatively characterize differential drug–gene interaction for gemcitabine and cytarabine. Pathway enrichment analysis revealed that autophagy, histone modification, chromatin remodeling, and apoptosis-related processes influence gemcitabine specifically, while drug–gene interaction specific to cytarabine was less enriched in gene ontology. Processes having influence over both drugs were DNA repair and integrity checkpoints and vesicle transport and fusion. Non-gene ontology (GO)-enriched genes were also informative. Yeast phenomic and cancer cell line pharmacogenomics data were integrated to identify yeast–human homologs with correlated differential gene expression and drug efficacy, thus providing a unique resource to predict whether differential gene expression observed in cancer genetic profiles are causal in tumor-specific responses to cytotoxic agents.
Multisite Internet data analysis

Summary form only given. In this presentation we describe the methods for characterizing network behavior from multiple collection points in the Internet. These methods combine non-linear dimension reduction, pattern matching, and change detection on a very large scale. Our results are illustrated on a combination of simulated and real data acquired from the Abilene network.
Graph Convolutional Neural Networks for Predicting Drug-Target Interactions.

Accurate determination of target-ligand interactions is crucial in the drug discovery process. In this paper, we propose a graph-convolutional (Graph-CNN) framework for predicting protein-ligand in...
Heterogeneous residential preferences among millennials and members of generation X in California: A latent-class approach

Abstract The millennial generation, the cohort born from 1981 to 1996, lives in large cities or denser parts of metropolitan areas more than preceding generations did at the same age. Studies have theorized that a combination of temporary economic hardship, long-term societal changes, and changing preferences and attitudes have been responsible for Millennials’ unique residential choices. This study examines a less-explored question about the presence and significance of heterogeneity in residential preferences across and within generations. In doing so, this study employs a latent-class choice model on a commuter subsample of Millennials and members of Generation X (n = 729) of the California Millennials Dataset, which collected a rich set of variables on various dimensions in Fall 2015. Using randomly-generated unlabeled choice sets at the US Census block group level, this study identifies three latent classes. The Younger, Pro-Urban Class (53% of our dataset; 66% of its millennial cases and 42% of its Gen Xers) behaves as the stereotypical Millennials in popular media, preferring urban amenities; the Affluent, Highly-Educated Class (32% of our dataset; 25% of its millennials and 38% of its Gen Xers) appears to pursue lifestyles and high socioeconomic status over homeownership or good school districts; and the Middle-Class Homeowner Class (15% of our dataset; 8% of its millennial cases and 21% of its Gen Xers) presents more traditional family-oriented suburban lifestyles. After the examination of shares of the three classes by age and neighborhood type, we provide suggestions for future research and effective planning responses.