A convex relaxation for weakly supervised classifiers

Armand Joulin, Francis R. Bach

Introduction

In many real-world machine learning scenarios, obtaining perfectly labeled data is prohibitively expensive or impossible. Instead, we often rely on weakly supervised data. For instance, in Multiple Instance Learning (MIL), data is grouped into "bags," and only the bag receives a label. In Semi-Supervised Learning (SSL), only a tiny fraction of the dataset is labeled.

The standard approach to these problems involves jointly estimating the "true" hidden labels and the classifier parameters. However, this creates a "chicken-and-egg" dependency that results in a non-convex optimization problem. Practitioners typically rely on greedy algorithms like Expectation-Maximization (EM), which are highly sensitive to initialization and prone to getting stuck in local minima. This paper introduces a robust, convex alternative that reformulates the latent label problem into a Semidefinite Program (SDP), guaranteeing a global optimum for the relaxed problem and providing a stable foundation for learning.

Methodology

The authors build their framework around the soft-max loss (logistic loss), selected for its twice-differentiable nature and similarity to the popular hinge loss. The core technical innovations include:

  • Semidefinite Relaxation: The discrete label assignment problem is transformed into a continuous optimization over a positive semidefinite matrix $Z$ (where $Z \approx zz^T$).
  • The Intercept Constraint: A major pitfall in previous convex relaxations is the omission of the intercept (bias) term. This paper explicitly includes the bias $b$ in the linear classifier, demonstrating that it requires a specific constraint on the dual variables and significantly improves classification accuracy on uncentered data.
  • Entropy Balancing: To prevent the model from trivially assigning the same label to every point (achieving "perfect" but useless separation), the authors incorporate an entropy-based penalty term that encourages a balanced distribution of labels.
  • Two-Loop Optimization: To efficiently solve the resulting SDP, they developed a dedicated algorithm. An inner loop handles the reparameterization of dual variables using proximal methods, while an outer loop optimizes over the "elliptope" (the set of symmetric matrices with ones on the diagonal).

A Unified Framework

One of the most elegant aspects of this approach is its universality. MIL, SSL, and discriminative clustering are all treated as the exact same mathematical problem. Adapting the model to a specific task simply requires changing the linear constraints applied to the $Z$ matrix. For example, in MIL, constraints are added to ensure that negative bags only contain negative instances.

Key Results

The authors evaluated their approach across three distinct domains, demonstrating strong performance:

  1. Multiple Instance Learning (MIL): The proposed method matched or outperformed state-of-the-art MIL-specific algorithms on standard benchmarks, achieving 87.7% accuracy on the Musk1 dataset, beating established methods like mi-SVM and EM-DD.
  2. Semi-Supervised Learning (SSL): The method proved particularly robust in low-label regimes. On the g241c dataset with only 10 provided labels, the linear model achieved 87.15% accuracy, significantly outperforming standard linear benchmarks (79.05%).
  3. Discriminative Clustering: In clustering tasks, the approach remained stable even as noise dimensions increased, a scenario where traditional k-means performance rapidly degrades.
Clustering results on 3 and 5 cluster toy datasets, illustrating the learned matrices.

Limitations and Future Directions

While the convex relaxation provides theoretical guarantees and strong empirical performance, it comes with computational trade-offs. The primary bottleneck is the $O(N^3)$ complexity of the outer optimization loop. While it scales to datasets of several thousand points, it is not yet suitable for massive "Big Data" applications.

Additionally, like all SDP relaxations, the final step requires "rounding" the continuous matrix back into discrete labels (often using k-means), which can result in a slight loss of information.

To mitigate the computational cost, the authors suggest a practical hybrid approach: using this convex method on a subset of the data to find a robust, "global" starting point, and then switching to a faster EM algorithm to refine the results. Future work may also explore low-rank decompositions of the kernel matrix to further accelerate the inner optimization loop.

Summary updated

Abstract

This paper introduces a general multi-class approach to weakly supervised classification. Inferring the labels and learning the parameters of the model is usually done jointly through a block-coordinate descent algorithm such as expectation-maximization (EM), which may lead to local minima. To avoid this problem, we propose a cost function based on a convex relaxation of the soft-max loss. We then propose an algorithm specifically designed to efficiently solve the corresponding semidefinite program (SDP). Empirically, our method compares favorably to standard ones on different datasets for multiple instance learning and semi-supervised learning, as well as on clustering tasks.
BibTeX
@inproceedings{joulin2012convex,
  author = {Armand Joulin and Francis R. Bach},
  title = {{A convex relaxation for weakly supervised classifiers}},
  booktitle = {International Conference on Machine Learning},
  year = {2012},
  doi = {10.48550/arxiv.1206.6413},
}
Figure