More Like this

1. Partial Identifiability in Discrete Data with Measurement Error

   Noam Finkelstein; Roy Adams; Suchi Saria; Ilya Shpitser (July 2021, Proceedings of the Thirty Seventh Conference on Uncertainty in Artificial Intelligence)

   Cassio de Campos; Marloes H. Maathuis (Ed.)

   When data contains measurement errors, it is necessary to make modeling assumptions relating the error-prone measurements to the unobserved true values. Work on measurement error has largely focused on models that fully identify the parameter of interest. As a result, many practically useful models that result in bounds on the target parameter -- known as partial identification -- have been neglected. In this work, we present a method for partial identification in a class of measurement error models involving discrete variables. We focus on models that impose linear constraints on the tar- get parameter, allowing us to compute partial identification bounds using off-the-shelf LP solvers. We show how several common measurement error assumptions can be composed with an extended class of instrumental variable-type models to create such linear constraint sets. We further show how this approach can be used to bound causal parameters, such as the average treatment effect, when treatment or outcome variables are measured with error. Using data from the Oregon Health Insurance Experiment, we apply this method to estimate bounds on the effect Medicaid enrollment has on depression when depression is measured with error. 

   more » « less
2. SVAR Identification from Higher Moments: Has the Simultaneous Causality Problem Been Solved?

   https://doi.org/10.1257/pandp.20221047  

   Montiel Olea, José Luis; Plagborg-Møller, Mikkel; Qian, Eric (May 2022, AEA Papers and Proceedings)

   Two recent strands of the structural vector autoregression literature use higher moments for identification, exploiting either non-Gaussianity or heteroskedasticity. These approaches achieve point identification without exclusion or sign restrictions. We review this work critically and contrast its goals with the separate research program that has pushed for macroeconometrics to rely more heavily on credible economic restrictions. Identification from higher moments imposes stronger assumptions on the shock process than second-order methods do. We recommend that these assumptions be tested. Since inference from higher moments places high demands on a finite sample, weak identification issues should be given priority by applied users. 

   more » « less
3. Recursive rules with aggregation: a simple unified semantics

   https://doi.org/10.1093/logcom/exac072  

   Liu, Yanhong A; Stoller, Scott D (November 2022, Journal of Logic and Computation)

   Abstract Complex reasoning problems are most clearly and easily specified using logical rules, but require recursive rules with aggregation such as count and sum for practical applications. Unfortunately, the meaning of such rules has been a significant challenge, leading to many disagreeing semantics. This paper describes a unified semantics for recursive rules with aggregation, extending the unified founded semantics and constraint semantics for recursive rules with negation. The key idea is to support simple expression of the different assumptions underlying different semantics, and orthogonally interpret aggregation operations using their simple usual meaning. We present a formal definition of the semantics, prove important properties of the semantics and compare with prior semantics. In particular, we present an efficient inference over aggregation that gives precise answers to all examples we have studied from the literature. We also apply our semantics to a wide range of challenging examples, and show that our semantics is simple and matches the desired results in all cases. Finally, we describe experiments on the most challenging examples, exhibiting unexpectedly superior performance over well-known systems when they can compute correct answers. 

   more » « less
4. Level constrained first order methods for function constrained optimization

   https://doi.org/10.1007/s10107-024-02057-4  

   Boob, Digvijay; Deng, Qi; Lan, Guanghui (March 2024, Mathematical Programming)

   Abstract We present a new feasible proximal gradient method for constrained optimization where both the objective and constraint functions are given by summation of a smooth, possibly nonconvex function and a convex simple function. The algorithm converts the original problem into a sequence of convex subproblems. Formulating those subproblems requires the evaluation of at most one gradient-value of the original objective and constraint functions. Either exact or approximate subproblems solutions can be computed efficiently in many cases. An important feature of the algorithm is the constraint level parameter. By carefully increasing this level for each subproblem, we provide a simple solution to overcome the challenge of bounding the Lagrangian multipliers and show that the algorithm follows a strictly feasible solution path till convergence to the stationary point. We develop a simple, proximal gradient descent type analysis, showing that the complexity bound of this new algorithm is comparable to gradient descent for the unconstrained setting which is new in the literature. Exploiting this new design and analysis technique, we extend our algorithms to some more challenging constrained optimization problems where (1) the objective is a stochastic or finite-sum function, and (2) structured nonsmooth functions replace smooth components of both objective and constraint functions. Complexity results for these problems also seem to be new in the literature. Finally, our method can also be applied to convex function constrained problems where we show complexities similar to the proximal gradient method. 

   more » « less
5. Connecting Hamilton-Jacobi Partial Differential Equations with Maximum a Posteriori and Posterior Mean Estimators for Some Non-convex Priors.

   https://doi.org/10.1007/978-3-030-03009-4_56-1  

   Darbon, J.; Langlois, G.P.; Meng, T. (May 2021, Handbook of Mathematical Models and Algorithms in Computer Vision and Imaging. Springer,)

   null; null; null; null (Ed.)

   Many imaging problems can be formulated as inverse problems expressed as finite-dimensional optimization problems. These optimization problems generally consist of minimizing the sum of a data fidelity and regularization terms. In Darbon (SIAM J. Imag. Sci. 8:2268–2293, 2015), Darbon and Meng, (On decomposition models in imaging sciences and multi-time Hamilton-Jacobi partial differential equations, arXiv preprint arXiv:1906.09502, 2019), connections between these optimization problems and (multi-time) Hamilton-Jacobi partial differential equations have been proposed under the convexity assumptions of both the data fidelity and regularization terms. In particular, under these convexity assumptions, some representation formulas for a minimizer can be obtained. From a Bayesian perspective, such a minimizer can be seen as a maximum a posteriori estimator. In this chapter, we consider a certain class of non-convex regularizations and show that similar representation formulas for the minimizer can also be obtained. This is achieved by leveraging min-plus algebra techniques that have been originally developed for solving certain Hamilton-Jacobi partial differential equations arising in optimal control. Note that connections between viscous Hamilton-Jacobi partial differential equations and Bayesian posterior mean estimators with Gaussian data fidelity terms and log-concave priors have been highlighted in Darbon and Langlois, (On Bayesian posterior mean estimators in imaging sciences and Hamilton-Jacobi partial differential equations, arXiv preprint arXiv:2003.05572, 2020). We also present similar results for certain Bayesian posterior mean estimators with Gaussian data fidelity and certain non-log-concave priors using an analogue of min-plus algebra techniques. 

   more » « less