Estimation from Indirect Supervision with Linear Moments
This work addresses computational bottlenecks in structured prediction for scenarios with indirect supervision, such as privacy-constrained or annotation-limited settings, though it appears incremental as it builds on existing linear methods.
The paper tackles the computational challenges of maximum marginal likelihood in structured prediction with indirect supervision by introducing a method that solves a linear system to estimate sufficient statistics and then uses convex optimization for parameter estimation, showing effectiveness in learning with local privacy constraints and low-cost count-based annotations.
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.