Estimation from Indirect Supervision with Linear Moments
In structured prediction problems where we have indirect supervision of the output, maximum marginal likelihood faces two computational obstacles: non-convexity of the objective and intractability of even a single gradient computation. In this paper, we bypass both obstacles for a class of what we call linear indirectly-supervised problems. Our approach is simple: we solve a linear system to estimate sufficient statistics of the model, which we then use to estimate parameters via convex optimization. We analyze the statistical properties of our approach and show empirically that it is effective in two settings: learning with local privacy constraints and learning from low-cost count-based annotations.
Code (1)
Tasks
Structured PredictionSimilar Papers 제목 키워드 기반
A Scrambled Method of Moments
Quasi-Monte Carlo (qMC) methods are a powerful alternative to classical Monte-Carlo (MC) integration. Under certain conditions, they can approximate the desired integral at a faster rate than the usual Central Limit Theo…
Time SeriesTime Series AnalysisMoment-Based Exact Uncertainty Propagation Through Nonlinear Stochastic Autonomous Systems
In this paper, we address the problem of uncertainty propagation through nonlinear stochastic dynamical systems. More precisely, given a discrete-time continuous-state probabilistic nonlinear dynamical system, we aim at …
The Exact Replica Threshold for Nonlinear Moments of Quantum States
Joint measurements on multiple copies of a quantum state provide access to nonlinear observables such as $\operatorname{tr}(ρ^t)$, but whether replica number marks a sharp information-theoretic resource boundary has rema…
Identification and Estimation of Categorical Random Coefficient Models
This paper proposes a linear categorical random coefficient model, in which the random coefficients follow parametric categorical distributions. The distributional parameters are identified based on a linear recurrence s…
Higher-Order Causal Message Passing for Experimentation with Complex Interference
Accurate estimation of treatment effects is essential for decision-making across various scientific fields. This task, however, becomes challenging in areas like social sciences and online marketplaces, where treating on…
Decision Making