An official website of the United States government
We present CausalSim, a causal framework for unbiased trace-driven simulation. Current trace-driven simulators assume that the interventions being simulated (e.g., a new algorithm) would not affect the validity of the traces. However, real-world traces are often biased by the choices algorithms make during trace collection, and hence replaying traces under an intervention may lead to incorrect results. CausalSim addresses this challenge by learning a causal model of the system dynamics and latent factors capturing the underlying system conditions during trace collection. It learns these models using an initial randomized control trial (RCT) under a fixed set of algorithms, and then applies them to remove biases from trace data when simulating new algorithms. Key to CausalSim is mapping unbiased trace-driven simulation to a tensor completion problem with extremely sparse observations. By exploiting a basic distributional invariance property present in RCT data, CausalSim enables a novel tensor completion method despite the sparsity of observations. Our extensive evaluation of CausalSim on both real and synthetic datasets, including more than ten months of real data from the Puffer video streaming system shows it improves simulation accuracy, reducing errors by 53% and 61% on average compared to expert-designed and supervised learning baselines. Moreover, CausalSim provides markedly different insights about ABR algorithms compared to the biased baseline simulator, which we validate with a real deployment
more »
« less
Sparse trace tests
We establish how the coefficients of a sparse polynomial system influence the sum (or the trace) of its zeros. As an application, we develop numerical tests for verifying whether a set of solutions to a sparse system is complete. These algorithms extend the classical trace test in numerical algebraic geometry. Our results rely on both the analysis of the structure of sparse resultants as well as an extension of Esterov’s results on monodromy groups of sparse systems.
more »
« less
- Award ID(s):
- 1913119
- PAR ID:
- 10513580
- Publisher / Repository:
- American Mathematical Society
- Date Published:
- Journal Name:
- Mathematics of Computation
- Volume:
- 92
- Issue:
- 344
- ISSN:
- 0025-5718
- Page Range / eLocation ID:
- 2893 to 2922
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We consider the finite element approximation of a coupled fluid‐structure interaction (FSI) system, which comprises a three‐dimensional (3D) Stokes flow and a two‐dimensional (2D) fourth‐order Euler–Bernoulli or Kirchhoff plate. The interaction of these parabolic and hyperbolic partial differential equations (PDE) occurs at the boundary interface which is assumed to be fixed. The vertical displacement of the plate dynamics evolves on the flat portion of the boundary where the coupling conditions are implemented via the matching velocities of the plate and fluid flow, as well as the Dirichlet boundary trace of the pressure. This pressure term also acts as a coupling agent, since it appears as a forcing term on the flat, elastic plate domain. Our main focus in this work is to generate some numerical results concerning the approximate solutions to the FSI model. For this, we propose a numerical algorithm that sequentially solves the fluid and plate subsystems through an effective decoupling approach. Numerical results of test problems are presented to illustrate the performance of the proposed method.more » « less
-
The minimum-gain eigenvalue assignment/pole placement problem (MGEAP) is a classical problem in LTI systems with static state feedback. In this paper, we study the MGEAP when the state feedback has arbitrary sparsity constraints. We formulate the sparse MGEAP problem as an equality-constrained optimization problem and present an analytical characterization of its locally optimal solution in terms of eigenvector matrices of the closed loop system. This result is used to provide a geometric interpretation of the solution of the non-sparse MGEAP, thereby providing additional insights for this classical problem. Further, we develop an iterative projected gradient descent algorithm to obtain local solutions for the sparse MGEAP using a parametrization based on the Sylvester equation. We present a heuristic algorithm to compute the projections, which also provides a novel method to solve the sparse EAP. Also, a relaxed version of the sparse MGEAP is presented and an algorithm is developed to obtain approximately sparse local solutions to the MGEAP. Finally, numerical studies are presented to compare the properties of the algorithms, which suggest that the proposed projecmore » « less
-
Abstract Standing meanders are a key component of the Antarctic Circumpolar Current (ACC) circulation system, and numerical studies have shown that these features may locally enhance subduction, upwelling, as well as lateral and vertical tracer transport. Yet, observational data from these regions remain sparse. Here, we present results based on measurements made by a group of autonomous platforms sampling an ACC standing meander formed due to the interaction of the Polar Front with the Southwest Indian Ridge. Two Seagliders were deployed alongside a Biogeochemical‐Argo float that was advected through the standing meander. In the high eddy kinetic energy region of the standing meander, the glider observations reveal enhanced submesoscale frontal gradients as well as heightened tracer variability at depth, as compared to the more quiescent region further downstream. Vertical gradients in spice and apparent oxygen utilization are reduced in the standing meander despite similarities in the large‐scale vertical stratification, suggesting greater ventilation of the surface ocean. These observations are consistent with numerical studies that highlight standing meanders as hotspots for ventilation and subduction due to enhanced mesoscale stirring and submesoscale vertical velocities. Our results emphasize the need to account for spatial heterogeneity in processes influencing air‐sea exchange, carbon export, and biogeochemical cycling in the Southern Ocean.more » « less
-
Sparse principal component analysis and sparse canonical correlation analysis are two essential techniques from high-dimensional statistics and machine learning for analyzing large-scale data. Both problems can be formulated as an optimization problem with nonsmooth objective and nonconvex constraints. Because nonsmoothness and nonconvexity bring numerical difficulties, most algorithms suggested in the literature either solve some relaxations of them or are heuristic and lack convergence guarantees. In this paper, we propose a new alternating manifold proximal gradient method to solve these two high-dimensional problems and provide a unified convergence analysis. Numerical experimental results are reported to demonstrate the advantages of our algorithm.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1090/mcom/3849
