- Award ID(s):
- 1816378
- PAR ID:
- 10169411
- Date Published:
- Journal Name:
- Stochastics and Partial Differential Equations: Analysis and Computations
- ISSN:
- 2194-0401
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
Mulzer, Wolfgang ; Phillips, Jeff M (Ed.)We consider two restricted cases of the planar dynamic convex hull problem with point insertions and deletions. We assume all updates are performed on a deque (double-ended queue) of points. The first case considers the monotonic path case, where all points are sorted in a given direction, say horizontally left-to-right, and only the leftmost and rightmost points can be inserted and deleted. The second case, which is more general, assumes that the points in the deque constitute a simple path. For both cases, we present solutions supporting deque insertions and deletions in worst-case constant time and standard queries on the convex hull of the points in O(log n) time, where n is the number of points in the current point set. The convex hull of the current point set can be reported in O(h+log n) time, where h is the number of edges of the convex hull. For the 1-sided monotone path case, where updates are only allowed on one side, the reporting time can be reduced to O(h), and queries on the convex hull are supported in O(log h) time. All our time bounds are worst case. In addition, we prove lower bounds that match these time bounds, and thus our results are optimal.more » « less
-
Quantifying the impact of parametric and model-form uncertainty on the predictions of stochastic models is a key challenge in many applications. Previous work has shown that the relative entropy rate is an effective tool for deriving path-space uncertainty quantification (UQ) bounds on ergodic averages. In this work we identify appropriate information-theoretic objects for a wider range of quantities of interest on path-space, such as hitting times and exponentially discounted observables, and develop the corresponding UQ bounds. In addition, our method yields tighter UQ bounds, even in cases where previous relative-entropy-based methods also apply, e.g. , for ergodic averages. We illustrate these results with examples from option pricing, non-reversible diffusion processes, stochastic control, semi-Markov queueing models, and expectations and distributions of hitting times.more » « less
-
Summary We propose a new algorithm, DASSO, for fitting the entire coefficient path of the Dantzig selector with a similar computational cost to the least angle regression algorithm that is used to compute the lasso. DASSO efficiently constructs a piecewise linear path through a sequential simplex-like algorithm, which is remarkably similar to the least angle regression algorithm. Comparison of the two algorithms sheds new light on the question of how the lasso and Dantzig selector are related. In addition, we provide theoretical conditions on the design matrix X under which the lasso and Dantzig selector coefficient estimates will be identical for certain tuning parameters. As a consequence, in many instances, we can extend the powerful non-asymptotic bounds that have been developed for the Dantzig selector to the lasso. Finally, through empirical studies of simulated and real world data sets we show that in practice, when the bounds hold for the Dantzig selector, they almost always also hold for the lasso.
-
A bstract Positivity bounds represent nontrivial limitations on effective field theories (EFTs) if those EFTs are to be completed into a Lorentz-invariant, causal, local, and unitary framework. While such positivity bounds have been applied in a wide array of physical contexts to obtain useful constraints, their application to inflationary EFTs is subtle since Lorentz invariance is spontaneously broken during cosmic inflation. One path forward is to employ a
Breit parameterization to ensure a crossing-symmetric and analytic S-matrix in theories with broken boosts. We extend this approach to a theory with multiple fields, and uncover a fundamental obstruction that arises unless all fields obey a dispersion relation that is approximately lightlike. We then apply the formalism to various classes of inflationary EFTs, with and without isocurvature perturbations, and employ this parameterization to derive new positivity bounds on such EFTs. For multifield inflation, we also consider bounds originating from the generalized optical theorem and demonstrate how these can give rise to stronger constraints on EFTs compared to constraints from traditional elastic positivity bounds alone. We compute various shapes of non-Gaussianity (NG), involving both adiabatic and isocurvature perturbations, and show how the observational parameter space controlling the strength of NG can be constrained by our bounds. -
There are many settings that extend the basic shortest-path search problem. In Bounded-Cost Search, we are given a constant bound, and the task is to find a solution within the bound. In Bi-Objective Search, each edge is associated with two costs (objectives), and the task is to minimize both objectives. In this paper, we combine both settings into a new setting of Bounded-Cost Bi-Objective Search. We are given two bounds, one for each objective, and the task is to find a solution within these bounds. We provide a scheme for normalizing the two objectives, introduce several algorithms for this new setting and compare them experimentally.more » « less