Ryan Martin, Ph.D. - US grants

ABSTRACT

Principal Investigator: Axenovich, Maria
Co-Principal Investigator: Martin, Ryan
Proposal Number: DMS - 0901008
Institution: Iowa State University
Title: Extremal problems on hereditary properties and partitions of combinatorial structures

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).

The overarching theme of this proposal is the study of local substructures in combinatorial objects, primarily networks. To what degree is a given substructure unavoidable? Ramsey theory states that certain substructures are always unavoidable in large enough systems. Others could be avoided by local modifications such as, in graphs, edge deletion and addition. This proposal deals, in part, with the efficient modification of graphs, referred to as graph editing. Finding the edit distance from a graph to a hereditary property provides insight into the general structure of such properties and has many applications, such as property testing. The techniques proposed to address this problem include pseudorandom graphs, regular partitions, colored homomorphisms and optimization -- all of which promise to be useful in other facets of graph theory. In the study of unavoidable combinatorial structures, this proposal addresses a generalized Ramsey problem in which the substructures are not given explicitly but rather are determined by a set of parameters. For example, such a parameter can be the number of colors that are present on a given subgraph of an edge-colored graph. This explores, in particular, the balance between classical Ramsey and anti-Ramsey problems.

The PIs' research belongs to the discipline of graph theory, which is the study of networks and their properties and which has applications in a wide variety of other disciplines, including computer science, bioinformatics, operations research and economics. Graduate students and collaboration are integral parts of the PIs' research. The main objective of this proposal is to address two fundamental questions: "Which structures are unavoidable in large systems, such as networks?" and "How can one modify (edit) a network efficiently in order to satisfy desired properties?" Answers to these questions will bring a better understanding of networks, specifically those arising from scientific applications.

The investigators study prior-free probabilistic inference with "large p, small n" regression analysis. This is made possible in the new framework of Inferential Models (IMs) proposed recently by the investigators. Statistical results produced by IMs are probabilistic and have desirable frequency properties. In this study, the investigators develop IM-based methods for linear and certain non-linear regression analysis. A sequence of topics in the context of large-p-small-n regression to be investigated include (1) variable selection in Gaussian regression models; (2) robust Student-t regression; and (3) binary regression models.

Linear regression is one of the most commonly used methodologies in statistical applications. However, desirable prior-free and frequency-calibrated probabilistic inference, particularly in the important variable selection context, has not been available until the recent development of IMs. The IM framework provides a new and promising alternative to the well-known Bayesian and frequentist methods for various high-dimensional problems researchers currently face. In this study, the investigators develop new statistical methods and computing software, generating useful tools for applied statisticians and scientists who are challenged by very-high-dimensional data in carrying out regression analysis.

The Fall 2012 MIdwestern GrapH TheorY LIII (MIGHTY LIII) conference will be hosted at Iowa State University in Ames, Iowa on September 21-22, 2012. MIGHTY is a long-running conference series which draws graph theorists from across the country to one- or two-day conferences to disseminate new ideas in a wide variety of topics related to graph theory. Topics typically represented include chromatic graph theory, directed graphs, hypergraphs, and applications of graph theory (i.e., to biological and social networks).

This conference provides a rare opportunity to bring together a large number of researchers in graph theory from the Midwest. The broad appeal of the plenary speakers, Ron Graham and Persi Diaconis, will attract many participants including students and junior investigators. Most of the funds from this award will support the travel costs of such participants. More information about the conference is available at the conference website: http://www.math.iastate.edu/mighty2012/.

Statisticians frequently encounter problems that involve complicated models with high-dimensional parameters, particularly in "big data" settings. From a Bayesian perspective, it is imperative in these problems that the prior distribution be chosen to sit in a good position. Information about where is a good starting position can come from the data. There is a potential danger with this basic strategy, namely, that a double use of data might cause the model to track the data too closely, resulting on over fitting. To avoid this, the PIs introduce a regularization technique that suitably re-weights the likelihood, preventing the model from learning too quickly. This general "double empirical Bayes" strategy, where the prior is centered on the data and the likelihood is re-weighted, will be applied to several important and challenging high-dimensional problems, including estimation of sparse high-dimensional precision matrices, which is relevant to estimation of large complex networks.

In this project, the PIs will develop this new double empirical Bayes framework for inference on high-dimensional parameters with a relatively low "complexity" or "effective dimension". For example, in function estimation problems, posited smoothness on the function is a constraint on its complexity. The first step of the double empirical Bayes strategy is to use a prior, indexed by the complexity of the parameter, centered at a complexity-specific estimate of the parameter based on data. To prevent the posterior from tracking the data too closely, the second step is to re-weight the likelihood to be combined with the data-dependent prior. The result is a sort of posterior distribution on the parameter space, and the PIs will provide general conditions for this posterior to concentrate around the truth at optimal rates. An additional advantage of this new approach is that the complexity-specific priors, for suitable centering, can be taken of relatively simple form, which facilitates computation. The PIs will investigate the double empirical Bayes analysis of several important high-dimensional inference problems, including density and function estimation, variable selection problems in non-linear models, and estimation of sparse precision matrices. Software will be developed for each application.

Numerous scientific questions assume the form of inverse problems, in which an unknown input to a system under study gives rise to an observed noisy output, and the goal is to estimate the input from the output. An example of such a problem is calculating the density of the Earth from measurements of the local gravitational field. Only rarely can such inverse problems be solved analytically, and in general numerical approximations are required to find solutions. In this research project, the investigators aim to introduce a novel iterative algorithm for solving inverse problems, develop its theoretical and computational properties, and establish its performance in applications. It is anticipated that the new algorithm will be adaptable to a range of problems currently under investigation in applied and numerical mathematics, for example in solving a sparse system of linear equations, currently of great interest in areas including tomography, archaeology, astrophysics, and other sciences.

This research project explores a novel iterative algorithm for the solution of a class inverse problems that includes Fredholm integral equations of the first kind, Laplace transform inversion, mixing distribution estimation in statistics, and solving sparse systems of linear equations. The investigators plan to (i) introduce a novel iterative algorithm for solving inverse problems of these types, and perhaps others, (ii) develop its theoretical and computational properties, and (iii) establish its performance in applications. A motivation for the research is the statistical problem of estimating a mixing density in a nonparametric mixture model. To date, there are no general algorithms that produce globally consistent estimators of the mixing density, in the sense of almost sure convergence with respect to a strong metric; only weak convergence results are available. An important feature of the algorithm under development is that, if it is initialized at a smooth density function, then the estimator is necessarily also a smooth density function. Other algorithms designed by numerical analysts for solving these inverse problems do not have this closure property. The form of the novel iterative algorithm, along with the fact that it yields smooth density estimators, suggests that this open problem can be solved; the investigators aim to establish a general global consistency result and demonstrate rates of convergence.

The Rocky Mountain-Great Plains Graduate Research Workshop in Combinatorics (GRWC), will be held in Laramie, WY (2016), Denver, CO (2017) and Ames, IA (2018), building upon successful NSF-funded workshops in 2014 and 2015. Each workshop will involve approximately 39 graduate students and postdoctoral researchers, and 10 or more faculty members in an intense two-week collaborative research experience. Participants will work to solve important, relevant problems from graph theory, enumeration, combinatorial matrix theory, finite geometry, and other modern sub-disciplines of combinatorics. Students will prepare open problems prior to the workshop under the guidance of faculty mentors from the organizing committee, which consists of faculty from Iowa State University, the University of Colorado Denver, the University of Denver, the University of Nebraska Lincoln, and the University of Wyoming. These problems, presented at the workshop by their proposers or hosted on the workshop's secure problem wiki, will be worked on by small groups of participating students, postdocs, and faculty. For more information about the GRWC, including a detailed description of the workshop format, please see the workshop website at http://sites.google.com/site/rmgpgrwc

The goal of the collaborations at the heart of the GRWC is to produce high-quality, publishable research on a variety of topics. Another longer-term goal of the workshop is to help student participants expand their professional research networks. A strong research network is often a crucial part of building a generative and sustainable research program, and establishing these connections at an early career stage can have a long-term positive effect on the quality, impact, and depth of a professional's research portfolio. Participation in the GRWC will allow students to cultivate a large professional network of peers from the combinatorics community with whom they will be able to interact and collaborate throughout their careers. The GRWC will also offer professional development workshops to help students and postdocs prepare for job searches and future careers in academia, industry, or government.

Eighty percent of the U.S. population lives in urban areas. As hubs for economic powerhouses, urban communities generate around 85% of tthe U.S. GDP. Therefore, the sustainability of urban communities underpins the sustained prosperity of the Nation. Large urban cities across the U.S. are increasingly faced with the rapidly decaying infrastructure, critical maintenance and repair needs across city systems, and a need for modernization. Sustaining the urban infrastructures and their quality of service to the evolving climatic and socio-economic demands call for innovative strategies for their adaptations. This workshop will explore the potential of biological systems, which demonstrate amazing adaptation strategies to extreme climatic conditions, i.e., extreme cold, extreme hot, marsh, salinity, and drought, to provide a rich repository of information as source of inspiration for the smart adaptation of urban infrastructure. The outcome of the workshop will be to design a research and educational roadmap and to build a convergent research community to explore the frontier of bio-inspired adaptation of urban infrastructure systems.

The workshop on Bio-Inspired Adaptation for Urban Infrastructure Systems will leverage the intelligence and adaptation strategies of biological and ecological systems as sources of inspiration for creating new approaches to design and implementation of adaptive urban infrastructure systems. The workshop program will focus on four major thrust areas: adaptation in biological/ecological systems; bio-inspired adaptive infrastructure systems; bio-inspired adaptive decision and governance; and education and workforce planning for urban adaptation. The workshop will be a two-day event providing various opportunities for team-building, keynote speeches, panels, facilitated group discussions, and poster sessions. This program will facilitate transdisciplinary exchange among researchers, practitioners, community leaders, and decision-makers. The workshop will provide extensive opportunities for dynamic interactions among attendees who bring together transdisciplinary expertise, with the aim of advancing the science of the urban sustainability.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.