Collaborative and Privacy-Preserving Machine Teaching via Consensus Optimization

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

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 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. The 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.

Introduction

Machine Teaching is a paradigm where a teacher identifies an optimal training set to guide a learner toward a target model $\theta^*$. A specific instance, "Super Teaching," involves selecting a subset of data that yields better performance than the full dataset. Despite its potential, Super Teaching faces three critical challenges: scalability issues due to the complexity of Mixed-Integer Non-Linear Programming (MINLP), privacy concerns regarding siloed data, and the need for communication-efficient collaboration among distributed teachers.

Methodology

The authors propose a decentralized framework for Collaborative Super Teaching based on consensus optimization.

Regularized Dual Learning

To overcome the limitations of MINLP, the framework utilizes the dual form of the learner's optimization problem. An adaptive $l_1$-norm penalty is employed to enforce sparsity, effectively identifying the most informative data points—those with non-zero dual variables.

Consensus Optimization via Block-Coordinate Descent (BCD)

The problem is formulated as a consensus optimization task solved using Block-Coordinate Descent (BCD). Teachers perform local optimization on their private data and share only aggregated summaries with a central server. This ensures privacy as raw data never leaves local storage.

Theoretical Guarantees

The method is shown to possess the "Oracle property," asymptotically matching the performance of an ideal teacher. Furthermore, the authors demonstrate that collaboration is necessary; independent or "oblivious" teaching fails to guarantee optimal subset selection.

Experimental Evaluation

The framework was evaluated on synthetic datasets and two large-scale real-world benchmarks: the Higgs dataset (1,000,000 instances) and the Superconduct dataset (21,263 instances).

The "Goldilocks" Zone of Data Selection

A significant insight from the experiments is the existence of an optimal subset size. As illustrated in Figure 1, the teaching risk decreases as informative samples are added but begins to increase once the subset exceeds a certain threshold (approximately 15% for Higgs and 25% for Superconduct). This confirms that "less is more" when data is carefully selected.

Teaching Risk vs. Subset Size for Higgs and Superconduct Datasets

Results and Discussion

The proposed method significantly outperforms the state-of-the-art MINLP approach in both speed and scalability.

Efficiency and Convergence

The consensus optimization process is highly efficient. Figure 2 shows the rapid convergence of the "Colluding Teaching Loss" for both datasets. In practice, the method achieved speedups of over 95% compared to the MINLP baseline and successfully handled datasets 100 times larger than the baseline's limit.

Convergence of Colluding Teaching Loss over Iterations

Accuracy and Sparsity

The collaborative approach consistently achieved lower teaching risk than non-collaborative methods. For the Higgs dataset, the learner achieved 99% consistency with the target model using only 15% of the original data.

Conclusion

This paper presents a scalable and privacy-preserving approach to collaborative machine teaching. By leveraging consensus optimization and dual learning, the framework enables distributed teachers to effectively coordinate data selection. Future research will explore extensions to non-convex models and alternative performance metrics like AUC.

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 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. The 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},
}
Figure