Catalogue Search | MBRL
Are you sure you want to remove the book from the shelf?
{{itemTitle}}
62
result(s) for
"Ryder, Nick"
Sort by:
Compatibility of Real-Rooted Polynomials with Mixed Signs
We characterize compatible families of real-rooted polynomials, allowing both positive and negative leading coefficients. Our characterization naturally generalizes the same-sign characterization used by Chudnovsky and Seymour in their famous 2007 paper proving the real-rootedness of independence polynomials of claw-free graphs, thus fully settling a question left open in their paper. Our methods are generally speaking elementary, utilizing mainly linear algebra and the established theory of interlacing polynomials, with a bit of invariant theory.
Paper
Generalizations of the Matching Polynomial to the Multivariate Independence Polynomial
We generalize two main theorems of matching polynomials of undirected simple graphs, namely, real-rootedness and the Heilmann-Lieb root bound. Viewing the matching polynomial of a graph \\(G\\) as the independence polynomial of the line graph of \\(G\\), we determine conditions for the extension of these theorems to the independence polynomial of any graph. In particular, we show that a stability-like property of the multivariate independence polynomial characterizes claw-freeness. Finally, we give and extend multivariate versions of Godsil's theorems on the divisibility of matching polynomials of trees related to \\(G\\).
Paper
On the Further Structure of the Finite Free Convolutions
Since the celebrated resolution of Kadison-Singer (via the Paving Conjecture) by Marcus, Spielman, and Srivastava, much study has been devoted to further understanding and generalizing the techniques of their proof. Specifically, their barrier method was crucial to achieving the required polynomial root bounds on the finite free convolution. But unfortunately this method required individual analysis for each usage, and the existence of a larger encapsulating framework is an important open question. In this paper, we make steps toward such a framework by generalizing their root bound to all differential operators. We further conjecture a large class of root bounds, the resolution of which would require for more robust techniques. We further give an important counterexample to a very natural multivariate version of their bound, which if true would have implied tight bounds for the Paving Conjecture.
Paper
Connecting the q-Multiplicative Convolution and the Finite Difference Convolution
In a recent paper, Brändén, Krasikov, and Shapiro consider root location preservation properties of finite difference operators. To this end, the authors describe a natural polynomial convolution operator and conjecture that it preserves root mesh properties. We prove this conjecture using two methods. The first develops a novel connection between the additive (Walsh) and multiplicative (Grace-Szegö) convolutions, which can be generically used to transfer results from multiplicative to additive. We then use this to transfer an analogous result, due to Lamprecht, which demonstrates logarithmic root mesh preservation properties of a certain \\(q\\)-multiplicative convolution operator. The second method proves the result directly using a modification of Lamprecht's proof of the logarithmic root mesh result. We present his original argument in a streamlined fashion and then make the appropriate alterations to apply it to the additive case.
Paper
Bit Complexity of Jordan Normal Form and Spectral Factorization
We study the bit complexity of two related fundamental computational problems in linear algebra and control theory. Our results are: (1) An \\(O(n^+3a+n^4a^2+n^(1/))\\) time algorithm for finding an \\(-\\)approximation to the Jordan Normal form of an integer matrix with \\(a-\\)bit entries, where \\(\\) is the exponent of matrix multiplication. (2) An \\(O(n^6d^6a+n^4d^4a^2+n^3d^3(1/))\\) time algorithm for \\(\\)-approximately computing the spectral factorization \\(P(x)=Q^*(x)Q(x)\\) of a given monic \\(n n\\) rational matrix polynomial of degree \\(2d\\) with rational \\(a-\\)bit coefficients having \\(a-\\)bit common denominators, which satisfies \\(P(x) 0\\) for all real \\(x\\). The first algorithm is used as a subroutine in the second one. Despite its being of central importance, polynomial complexity bounds were not previously known for spectral factorization, and for Jordan form the best previous best running time was an unspecified polynomial in \\(n\\) of degree at least twelve cai1994computing. Our algorithms are simple and judiciously combine techniques from numerical and symbolic computation, yielding significant advantages over either approach by itself.
Paper
Asymmetric Random Projections
Random projections (RP) are a popular tool for reducing dimensionality while preserving local geometry. In many applications the data set to be projected is given to us in advance, yet the current RP techniques do not make use of information about the data. In this paper, we provide a computationally light way to extract statistics from the data that allows designing a data dependent RP with superior performance compared to data-oblivious RP. We tackle scenarios such as matrix multiplication and linear regression/classification in which we wish to estimate inner products between pairs of vectors from two possibly different sources. Our technique takes advantage of the difference between the sources and is provably superior to oblivious RPs. Additionally, we provide extensive experiments comparing RPs with our approach showing significant performance lifts in fast matrix multiplication, regression and classification problems.
Paper
First results of the deployment of a SoLid detector module at the SCK-CEN BR2 reactor
The SoLid experiment aims to resolve the reactor neutrino anomaly by searching for electron-to-sterile anti-neutrino oscillations. The search will be performed between 5.5 and 10 m from the highly enriched uranium core of the BR2 reactor at SCK-CEN. The experiment utilises a novel approach to anti-neutrino detection based on a highly segmented, composite scintillator detector design. High experimental sensitivity can be achieved using a combination of high neutron-gamma discrimination using 6 LiF:ZnS(Ag) and precise localisation of the inverse beta decay products. This compact detector system requires limited passive shielding as it relies on spacial topology to determine the different classes of backgrounds. The first full scale, 288 kg, detector module was deployed at the BR2 reactor in November 2014. A phased three tonne experimental deployment will begin in the second half of 2016, allowing a precise search for oscillations that will resolve the reactor anomaly using a three tonne detector running for three years. In this talk the novel detector design is explained and initial detector performance results from the module level deployment are presented along with an estimation of the physics reach of the next phase.
Paper
Real Stability Testing
We give a strongly polynomial time algorithm which determines whether or not a bivariate polynomial is real stable. As a corollary, this implies an algorithm for testing whether a given linear transformation on univariate polynomials preserves real-rootedness. The proof exploits properties of hyperbolic polynomials to reduce real stability testing to testing nonnegativity of a finite number of polynomials on an interval.
Paper
Tensor Programs V: Tuning Large Neural Networks via Zero-Shot Hyperparameter Transfer
Hyperparameter (HP) tuning in deep learning is an expensive process, prohibitively so for neural networks (NNs) with billions of parameters. We show that, in the recently discovered Maximal Update Parametrization (muP), many optimal HPs remain stable even as model size changes. This leads to a new HP tuning paradigm we call muTransfer: parametrize the target model in muP, tune the HP indirectly on a smaller model, and zero-shot transfer them to the full-sized model, i.e., without directly tuning the latter at all. We verify muTransfer on Transformer and ResNet. For example, 1) by transferring pretraining HPs from a model of 13M parameters, we outperform published numbers of BERT-large (350M parameters), with a total tuning cost equivalent to pretraining BERT-large once; 2) by transferring from 40M parameters, we outperform published numbers of the 6.7B GPT-3 model, with tuning cost only 7% of total pretraining cost. A Pytorch implementation of our technique can be found at github.com/microsoft/mup and installable via `pip install mup`.
Paper