Learning from Complementary Labels
Collecting labeled data is costly and thus a critical bottleneck in real-world classification tasks. To mitigate this problem, we propose a novel setting, namely learning from complementary labels for multi-class classification. A complementary label specifies a class that a pattern does not belong to. Collecting complementary labels would be less laborious than collecting ordinary labels, since users do not have to carefully choose the correct class from a long list of candidate classes. However, complementary labels are less informative than ordinary labels and thus a suitable approach is needed to better learn from them. In this paper, we show that an unbiased estimator to the classification risk can be obtained only from complementarily labeled data, if a loss function satisfies a particular symmetric condition. We derive estimation error bounds for the proposed method and prove that the optimal parametric convergence rate is achieved. We further show that learning from complementary labels can be easily combined with learning from ordinary labels (i.e., ordinary supervised learning), providing a highly practical implementation of the proposed method. Finally, we experimentally demonstrate the usefulness of the proposed methods.
This paper proposes a novel problem setting and algorithm for learning from complementary labels. It shows an unbiased estimator of the classification risk can be obtained only from complementary labels, if a loss function satisfies a particular symmetric condition. The paper also provides estimation error bounds for the proposed method. Experiments show the approach can produce results similar to standard learning with ordinary labels on some datasets.
The idea and the theoretical results are interesting. But I question the usefulness of the proposed learning problem.  Though using complementary labels can be less laborious than ordinary labels, complementary labels are less informative than ordinary labels. If using N training instances with complementary labels cannot perform better (this is almost certain) than learning with N/(K-1) training instances with ordinary labels,  why should one use complementary labels? Moreover, based on the theoretical results, learning with complementary labels are restricted to a limited number of loss functions, while there are many state-of-the-art effective learning methods with ordinary labels. 
The paper only suggests in the conclusion section that such complementary label learning can be useful in the context of privacy-aware machine learning. Then why not put this study within the privacy-aware learning setting and compare to the privacy-aware learning techniques?
For section 3: (1) On line 51, it says “ that incurs a large loss for large z”.  Shouldn’t be “that incurs a large loss for small z”?  (2) It is not clear how the derivation on Line 79-80 was conducted.  Why should \sum_{y\not= \bar{y}}\ell(g_y(x))/(K-1) =  \ell(g_{\bar{y}}(x)) ?
The experiments are very basic. In the benchmark experiments, it only compares to a self-constructed ML formulation and a one-hidden-layer neural network with ordinary labels. The way of translating the complementary labels to multi-labels is not proper since it actually brings much wrong information into the labels. The one-hidden-layer neural network is far from being a state-of-the-art multi-label classification model.  It is better to just compare with the standard learning with ordinary labels using the same PC with sigmoid loss. 
Another issue is: why not use the whole datasets instead of part of them? It would also be interesting to see the comparison between complementary label learning with ordinary label learning with a range of different number of classes on the same datasets.