Collaborative and Privacy-Preserving Machine Teaching via Consensus Optimization

Yufei Han, Yuzhe Ma, Christopher Gates, Kevin A. Roundy, Yun Shen

TL;DR

This paper introduces a decentralized, privacy-preserving framework for "Super Teaching," where multiple distributed teachers collaborate to select the most informative subset of data to train a learner. By formulating the problem as a consensus optimization task using block-coordinate descent, the authors achieve massive speedups (over 95% faster than traditional methods) and better teaching accuracy without ever sharing raw local data.

What Problem Does This Paper Address?

In the field of Machine Teaching, a "teacher" knows a specific target model ($\theta^*$) and wants to find the smallest, most effective training set to help a "student" (a machine learning algorithm) reach that model. Super Teaching is a specific subset of this where the teacher trims down an existing large dataset to a "super" subset that actually performs better than the full i.i.d. dataset.

Until now, super teaching faced three major hurdles:

  1. Scalability: Existing methods rely on Mixed-Integer Non-Linear Programming (MINLP), which is computationally "undecidable" in theory and prohibitively slow for large datasets.
  2. Privacy: Most methods assume a single teacher has access to all data. In the real world, data is often stuck in silos (e.g., different hospitals or banks) that cannot be shared due to privacy regulations.
  3. Collaboration Efficiency: It wasn't clear how distributed teachers could coordinate their data selection without massive communication overhead or "oblivious" (independent) teaching, which often leads to poor results.

Methods

The authors propose a Collaborative Super Teaching paradigm based on consensus optimization.

  • Regularized Dual Learning: Instead of solving the hard MINLP problem, they look at the dual form of the learner's optimization problem. They use an adaptive $l_1$-norm penalty (similar to the Adaptive Lasso) to enforce sparsity. This naturally identifies the most "useful" data points—those with non-zero dual variables.
  • Consensus Optimization via BCD: They use Block-Coordinate Descent (BCD). Each teacher optimizes their own local data subset selection in parallel. They then send a small, aggregated summary (not raw data) to a central server, which broadcasts a global update back to the teachers.
  • The Oracle Property: The authors theoretically prove that their method enjoys the "Oracle property," meaning it can asymptotically perform as well as if the teacher knew exactly which data points were the "true" informative ones beforehand.
  • Privacy Preservation: Because only aggregated dual variables are shared, the raw, private data never leaves the local teacher's device.

Datasets

The researchers evaluated their approach on both synthetic and real-world benchmarks:

  • Synthetic Data: Generated classification and regression datasets ranging from 5,000 to 500,000 instances.
  • Higgs Dataset: A massive physics dataset with 1,000,000 instances and 28 features (used for Logistic Regression).
  • Superconduct Dataset: A regression dataset with 21,263 instances and 81 features (used for Ridge Regression).

Key Insights and Ideas

  • Collaboration is Mandatory: The authors prove (Theorem 1) that "oblivious teaching"—where teachers pick data independently—doesn't guarantee better results. Information sharing is the "secret sauce" that allows distributed teachers to collectively find a better training set than any one could find alone.
  • The "Goldilocks" Zone of Data: Their experiments on the Higgs and Superconduct datasets revealed a "turning point." Teaching risk decreases as you add more selected data, but only up to a point (around 15-25% of the data). Adding too much data after that actually increases the teaching risk, confirming that "less is more" in machine teaching.
  • Communication Efficiency: The communication cost is $O(TKd)$, where $d$ is the number of features. This is highly efficient compared to transferring raw datasets.

Key Results

  • Massive Speedup: The proposed method is significantly faster than the state-of-the-art MINLP approach. In many tests, it took less than 5% of the time required by the baseline.
  • Scalability: While the MINLP baseline failed to produce results for datasets larger than 10,000 instances, the collaborative method easily handled 1,000,000 instances.
  • Accuracy: The collaborative approach consistently achieved lower "teaching risk" (the distance between the learned model and the target model) compared to independent, non-collaborative teaching.
  • Sparsity: The model successfully taught the learner using only a small fraction of the original data (e.g., 15% of the Higgs dataset) while maintaining 99% consistency with the target model.

Limitations and Future Work

  • Target Model Assumption: The current framework assumes the teacher already knows the exact target model ($\theta^*$). In some real-world scenarios, the teacher might only have a general goal rather than a specific parameter vector.
  • Learner Complexity: The study focused on relatively simple learners like Logistic Regression and Ridge Regression. Extending this to complex non-convex models like Deep Neural Networks remains a challenge.
  • Future Directions: The authors suggest exploring different teaching goals, such as optimizing for AUC (Area Under the Curve) rather than standard classification risk, to make the framework more applicable to practical, imbalanced data scenarios.

Summary updated

Abstract

In this work, we define a collaborative and privacy-preserving machine teaching paradigm with multiple distributed teachers. We focus on consensus super teaching. It aims at organizing distributed teachers to jointly select a compact while informative training subset from data hosted by the teachers to make a learner learn better. The challenges arise from three perspectives. First, the state-of-the-art pool-based super teaching method applies mixed-integer non-linear programming (MINLP) which does not scale well to very large data sets. Second, it is desirable to restrict data access of the teachers to only their own data during the collaboration stage to mitigate privacy leaks. Finally, the teaching collaboration should be communication-efficient since large communication overheads can cause synchronization delays between teachers. To address these challenges, we formulate the collaborative teaching as a consensus and privacy-preserving optimization process to minimize teaching risk. We theoretically demonstrate the necessity of collaboration between teachers for improving the learner's learning. Furthermore, we show that the proposed method enjoys a similar property as the Oracle property of adaptive Lasso. Empirical study illustrates that our teaching method can deliver significantly more accurate teaching results with high speed, while the non-collaborative MINLP-based super teaching becomes prohibitively expensive to compute.
BibTeX
@inproceedings{han2019collaborative,
  author = {Yufei Han and Yuzhe Ma and Christopher Gates and Kevin A. Roundy and Yun Shen},
  title = {{Collaborative and Privacy-Preserving Machine Teaching via Consensus Optimization}},
  booktitle = {IJCNN},
  year = {2019},
  url = {https://openreview.net/forum?id=XCoxQyidWBs},
}

Loading related content...

Figure