summaries: The author proposed an online learning setting where the true label is determined by which of k centers is the closest from the query point for a distance function.  The goal of the learner is to minimize the total distance from each query to the region corresponding to the correct label. The authors then propose learning algorithms for these settings and provide a theoretical analysis of the proposed algorithms. The authors also show interesting properties of this learning setting that could not be achieved in the traditional multiclass learning setting.

summaries: This paper proposes an online multiclass classifier that minimizes the distance between a point and the correct class partition for that point’s label. They argue that this loss function punishes more harshly points that are classified as extremely wrong versus almost correct. They propose an algorithm where in every round, their classifier predicts a point and suffers the distance based loss between their predicted point and the correct class region.

summaries: The paper considers the problem of online prediction of which region of a k-centred nearest-neighbour partition (where “nearest” is defined via a “distance” function) a point is in. The feedback on each trial is which region the point is in - as in standard online learning. However, instead of bounding the number of mistakes, this paper seeks to bound the total loss, where the loss on a trial is the “distance” of the point to the region predicted (see the main review for a confusion I have here). The paper considers two types of “distance” - the (negative of the) inner product and the p-norm. The paper gives loss bounds that are independent of the total number of trials and don’t have a “margin” term.

summaries: The work addresses an online learning problem, where the algorithm receives a sequence of points q_1,q_2,... in the d-dimensional unit ball, and must guess the label of each point among k possible labels {1,...,k}. The correct label corresponds to a nearest-neighbor partition of the ball, R_1,...,R_k determined by k unknown "centers" x_1,...,x_k. If the algorithm predicts that a point q has label i, it incurs a loss equal to the distance between q and the subset R_i of the points labelled as i. The goal is to minimize the total loss. The main result is a set of upper bounds on the loss in the form poly(d), or similar, but in any case independent of the length T of the sequence. The work considers also the special case k=2, the case of general convex classes (for which it gives lower bounds), as well as some other implications of the upper bounds.

abstractText: We consider the problem of multi-class classification, where a stream of adversarially chosen queries arrive and must be assigned a label online. Unlike traditional bounds which seek to minimize the misclassification rate, we minimize the total distance from each query to the region corresponding to its correct label. When the true labels are determined via a nearest neighbor partition – i.e. the label of a point is given by which of k centers it is closest to in Euclidean distance – we show that one can achieve a loss that is independent of the total number of queries. We complement this result by showing that learning general convex sets requires an almost linear loss per query. Our results build off of regret guarantees for the geometric problem of contextual search. In addition, we develop a novel reduction technique from multiclass classification to binary classification which may be of independent interest.

authors:
Aditya Bhaskara
Aravinda Kanchana Rwanpathirana

title: Robust algorithms for online k-means clustering

venue: In Algorithmic Learning Theory,

authors:
Koby Crammer
Ofer Dekel
Joseph Keshet
Shai Shalev-Shwartz
Yoram Singer

title: Online passive aggressive algorithms

authors:
Koby Crammer
Claudio Gentile

title: Multiclass classification with bandit feedback using adaptive regularization

venue: Machine learning,

authors:
Maxime C Cohen
Ilan Lobel
Renato Paes Leme

title: Feature-based dynamic pricing

venue: In Proceedings of the 2016 ACM Conference on Economics and Computation,

authors:
Koby Crammer
Yoram Singer

title: Ultraconservative online algorithms for multiclass problems

venue: Journal of Machine Learning Research,

authors:
Richard O Duda
Peter E Hart

title: Pattern classification and scene analysis, volume 3

authors:
Yoav Freund
Robert E Schapire

title: Large margin classification using the perceptron algorithm

authors:
Claudio Gentile
Shuai Li
Purushottam Kar
Alexandros Karatzoglou
Giovanni Zappella
Evans Etrue

title: On context-dependent clustering of bandits

venue: In International Conference on Machine Learning,

authors:
Claudio Gentile
Shuai Li
Giovanni Zappella

title: Online clustering of bandits

authors:
Geoffrey Hinton
Oriol Vinyals
Jeff Dean

title: Distilling the knowledge in a neural network

venue: arXiv preprint arXiv:1503.02531,

title: Separation properties of convex cones

venue: Proceedings of the American Mathematical Society,

authors:
Sham M Kakade
Shai Shalev-Shwartz
Ambuj Tewari

title: Efficient bandit algorithms for online multiclass prediction

venue: In Proceedings of the 25th international conference on Machine learning,

title: Concise formulas for the area and volume of a hyperspherical cap

venue: Asian Journal of Mathematics and Statistics,

authors:
Allen Liu
Renato Paes Leme
Jon Schneider

title: Optimal contextual pricing and extensions, 2020

authors:
Ilan Lobel
Renato Paes Leme
Adrian Vladu

title: Multidimensional binary search for contextual decision-making

venue: Operations Research,

authors:
Renato Paes Leme
Jon Schneider

title: Contextual search via intrinsic volumes

venue: IEEE Annual Symposium on Foundations of Computer Science,

authors:
Edo Liberty
Ram Sriharsha
Maxim Sviridenko

title: An algorithm for online k-means clustering

authors:
Jiri Matousek
Bernd Gärtner

title: Understanding and using linear programming

venue: Springer Science & Business Media,

authors:
Mehryar Mohri
Afshin Rostamizadeh

title: Perceptron mistake bounds

venue: arXiv preprint arXiv:1305.0208,

title: On convergence proofs for perceptrons

venue: Technical report, STANFORD RESEARCH INST MENLO PARK CA,

title: The perceptron: a probabilistic model for information storage and organization in the brain

venue: Psychological review,

authors:
Nathan Srebro
Shai Ben-David

title: Learning bounds for support vector machines with learned kernels

venue: In International Conference on Computational Learning Theory,

title: The nature of statistical learning theory

venue: Springer science & business media,

heading: 1 Introduction

text:
Online multiclass classification is a ubiquitous problem in machine learning. In this problem, a learning algorithm is presented with a stream of incoming query points and is tasked with assigning each query with a label from a fixed set. After choosing a label, the algorithm is told the true label of the query point. The goal of the algorithm is to learn over time how to label the query points as accurately as possible.
Traditionally, theoretical treatments of this problem are built around the notion of a margin γ. This margin represents the extent to which the input points are well-separated from the boundaries between different labels. For example, the analysis of the classic Perceptron algorithm [Nov63] guarantees that it makes at most O(1/γ2) mistakes when performing binary classification, as long as all query points are distance at least γ from a hyperplane separating the two classes. More sophisticated analyses and algorithms (relying on e.g. hinge loss) do not necessarily assume the classes are as well separated, but still inherently incorporate a margin γ (for example, the hinge loss associated with a point is positive unless it is γ-separated).
In this paper, we present an alternative to the traditional margin approaches. Our approach weights each mistake by how ambiguous the classification task is for that point, rather than penalizing all mistakes equally. More precisely, consider a partition of the space of all possible query points into k regions Ri, where Ri contains all query points whose true label is i. In our formulation assigning a query point q a label i incurs a loss of ℓ(q,Ri), where ℓ(q,Ri) should be thought of as the distance needed to move q so that it lies in Ri (i.e., for it to be labelled correctly). For example, in the case of
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
a linear classifier, ℓ(q,Ri) is zero if q is correctly classified, and the distance to the classifier if q is incorrectly classified. The goal of the algorithm is to minimize the total loss.
This notion of loss not only measures the rate of errors but also the degree of each error; choosing a wildly inaccurate label is punished more than selecting a label that is "almost" correct. This fine-grained approach to looking at errors has occurred in other areas of machine learning research as well. For example, the technique of knowledge distillation is based on training a smaller model on the logits produced by a larger model [HVD15]. Hinton et al. explain, “The relative probabilities of incorrect answers tell us a lot about how the cumbersome model tends to generalize. An image of a BMW, for example, may only have a very small chance of being mistaken for a garbage truck, but that mistake is still many times more probable than mistaking it for a carrot.” Rather than leaning on the power of a trained model, our framework differentiates between these different incorrect answers based on the geometry of the problem.

heading: 1.1 Our Results

heading: 1.1.1 Learning Linear Classifiers

text:
In this case we have a binary classification problem, where the two regions R1 and R2 are separated by an unknown d-dimensional hyperplane ⟨v, x⟩ = 0 (with ||v||2 = 1). Our loss function in this case is the function ℓ(q,Ri) = |⟨q, v⟩| · 1(q ̸∈ Ri). We prove the following result: Theorem 1 (Restatement of Corollary 3.1). There exists an efficient algorithm for learning a linear classifier that incurs a total loss of at most O(d log d).
Note that the total loss in Theorem 1 is independent of the time horizon (number of rounds) T . More importantly, note that this is stronger than the naive guarantee implied by the margin bounds for the Perceptron algorithm. Indeed, each mistake at a distance γ from the separating hyperplane is assigned loss O(γ) in our model. Since the Perceptron algorithm can make up to O(1/γ2) such mistakes, this only implies Perceptron incurs a total loss of at most O(1/γ) (which blows up as γ → 0). Indeed, our algorithm in Theorem 1 is not based off of the Perceptron algorithm or its relatives, but rather off of recently developed algorithms for a problem in online learning known as contextual search. In contextual search, a learner is similarly faced with a stream of incoming query points qt and wishes to learn a hidden vector v. However, instead of trying to predict the sign of ⟨v, qt⟩, in contextual search the goal is to guess the value of ⟨v, qt⟩. After the learner submits a guess, they are told whether or not their guess was higher or lower than the true value of ⟨v, qt⟩ (and pay a loss equal to the distance between their guess and the truth). The best known contextual search algorithms rely on techniques from integral geometry (bounding various intrinsic volumes of the allowable knowledge set), and are inherently different than existing Perceptron/SVM-style algorithms.
While it may seem like contextual search (which must predict the value of ⟨v, qt⟩ instead of just the sign) is strictly harder than our online binary classification problem, they are somewhat incomparable (for example, unlike in contextual search, we have no control over what feedback we learn about the hidden vector v). Nonetheless, in Theorem 8 we show a general reduction from our binary classification problem to contextual search. This allows us to use recent results of [LLS20] to obtain our O(d log d) bound in Theorem 1.

heading: 1.1.2 Learning Nearest Neighbor Partitions

text:
One natural way to split a query space into multiple classes is via a nearest neighbor partition. In this setting, each label class i is associated with a “center” xi ∈ Rd, and each region Ri consists of the points which are “nearest” to xi. To define “nearest”, we introduce a similarity metric δ(x, y) representing the “distance” between points x and y in Rd. The two major classes of similarity metrics we consider are: a) the inner-product similarity δ(x, y) = −⟨x, y⟩ and b) the Lp similarity δ(x, y) = ||x− y||p. Given a fixed similarity metric δ, our loss function in this case is the function ℓ(q,Ri) = δ(q, xi)−mini∗ δ(q, xi∗); in other words, the difference between the similarity between q and xi with the similarity between q and its most similar center.
Theorem 2 (Restatement of Corollary 3.3). For inner-product similarity, there exists an efficient randomized algorithm for learning a nearest neighbors partition that incurs a total expected loss of at most O(k2d log d).
Like some other algorithms for multiclass classification, our algorithm in Theorem 2 works by running one instance of our binary classification algorithm (Theorem 1) for each pair of labels. Unlike some other “all-vs-all” methods in the multiclass classification literature, however, it does not suffice to run a simple majority vote over these instances. Instead, to prove Theorem 2, we solve a linear program to construct a probability distribution over centers that guarantees that our expected loss is bounded by an expected decrease in a total potential of all our ( k 2 ) sub-algorithms.
Our results for Lp similarity are as follows: Theorem 3 (Restatement of Theorems 12 and 13). For Lp similarity, when p is a positive even integer, there exists an efficient randomized algorithm for learning a nearest neighbors partition that incurs a total expected loss of at most O(k2poly(p, d)).
For an arbitrary p ≥ 2, if all k centers are ∆-separated in Lp distance, there exists an efficient randomized algorithm that incurs a total expected loss of
k2poly(p, d) ∆ · ( 1 p− 2 )2 .
When p is an even integer, it is possible to construct a polynomial kernel that exactly reduces this problem to the problem for inner-product similarity (albeit in the higher dimensional space Rd(p+1)). When p is not an even integer, it is no longer possible to perform an exact reduction to the innerproduct similarity problem. Instead, in parallel we perform a series of approximate reductions to inner-product similarity at multiple different scales (the full algorithm can be found in Appendix1 E). Surprisingly, this technique only gives T -independent bounds on the loss when p ≥ 2. It is an interesting open problem to develop algorithms for the case 1 ≤ p < 2 (and more generally, for arbitrary norms).

heading: 1.1.3 Learning General Convex Regions

text: Finally, we consider the case where the regions Ri are not defined in relation to hidden centers, but where they can be any convex subsets of Rd. Interestingly, in this case it is impossible to achieve total loss independent of T . Indeed, we prove a lower bound of Ω(T 1−O(1/d)) for the total loss of any algorithm for this setting, even when k = 2. Theorem 4. Any algorithm for learning general convex regions incurs a total loss of at least Ω ( T (d−4)/(d−2) ) , even when there are only two regions.

heading: 1.2 Mistake Bounds and Halving Algorithms

text:
As mentioned in the introduction, classical algorithms for multi-class classification generally try to minimize the mistake bound (the total number of classification errors the algorithm makes) under some margin guarantee γ. Even though our algorithms are designed to minimize the absolute loss and not a margin-dependent mistake bound, it is natural to ask whether our algorithms come with any natural mistake bound guarantees.
We show that our algorithms do in fact possess strong mistake bounds, matching the dependence on the margin γ of the best known halving algorithms. In particular, we show the following. Theorem 5 (Restatement of Theorem 16). If all query points qt are at least distance γ away from the separating hyperplane, our algorithm for learning linear classifiers (Theorem 1) makes at most O(d log(d/γ)) mistakes. Theorem 6 (Restatement of Theorem 17). If all query points qt are at least distance γ away from the boundary between any two regions, our algorithm for learning nearest neighbor partitions (Theorem 2) makes at most O(k2d log(d/γ)) mistakes.
In comparison, the best dimension-dependent classical bounds for this problem come from halving algorithms (efficiently implementable via linear programming) which have mistake bounds of O(d log(1/γ)) and O(kd log(1/γ)) respectively. In the first case, our mistake bound is nearly tight (losing only an additive O(d log d)). In the second case, our mistake bound is tight up to a multiplicative factor of k; it is an interesting open question whether it is possible to remove this factor of k in our techniques.
1All references to the appendix refer to the appendices of the Supplementary Material.
We additionally introduce a variant on the mistake bound that we call a robust mistake bound that is defined as follows. Normally, when we have a margin constraint of γ, we insist that all query points qt are distance at least γ away from any separating hyperplane. In our robust model, we remove this constraint, but only count mistakes when the query point qt lies at least γ away from the separating hyperplane.
Existing algorithms (both the Perceptron and halving algorithms) do not appear to give any non-trivial mistake bounds in the robust model – it is very important for the analysis of these algorithms that every query point is far from the separating hyperplane. On the other hand, it straightforwardly follows from our notion of loss that if we have an O(R)-loss algorithm for some problem, that algorithm simultaneously achieves an O(R/γ) robust mistake bound. In particular, we obtain robust mistake bounds of O((d log d)/γ) and O((k2d log d)/γ) for learning linear classifiers and learning nearest neighbor partitions respectively.
Related work The problem of online binary classification (and specifically, of online learning of a linear classifier) is one of the oldest problems in machine learning. The Perceptron algorithm was invented in [Ros58], and the first mistake bound analysis of the Perceptron algorithm appeared in [Nov63]. Since then, there has been a myriad of research on this problem, some of which is well-surveyed in [MR13]. Of note, the first mistake bounds for the non-separable case appear in [FS99]. We are not aware of any work on this problem that investigates the same loss we present in this paper.
Bounds for support vector machines (see [Vap13]) also result in the use of a margin to bound the number of mistakes. Choosing a suitable kernel can help create or improve the margin when viewing the data in the “kernel” space. We use a similar technique in proving bounds for generalized Lp norms. Our idea is to use differently-scaled kernels to produce increasingly accurate approximations. To the best of our knowledge, the technique we present is novel. There are other related techniques in the literature, e.g. [SBD06] attempt to learn the best kernel to improve classification error.
Similarly, there is a wealth of both theoretical and empirical research on multiclass classification. As far back as 1973, researchers were looking at generalizing binary classification algorithms to this setting (see e.g. Kesler’s construction in [DH+73]). One piece of relevant work is [CS03], which generalizes online binary classification Perceptron-style algorithms to solve online multiclass classification problems – in particular, the multiclass hypotheses they consider are same as the nearest neighbor partitions generated by the inner-product similarity metric (although as with the Perceptron, they only analyze the raw classification error). Since then, this work has been extended in many ways to a variety of settings (e.g. [CDK+06, CG13, KSST08]).
Another way of looking at the problem of multiclass classification is that we are learning how to cluster a sequence of input points into k pre-existing clusters. Indeed, the nearest neighbor partition with L2 similarity metric gives rise to exactly the same partitioning as a k-means clustering. There is an active area of research on learning how to cluster in an online fashion (e.g. [GLZ14, GLK+17, BR20]). Perhaps most relevantly, [LSS16] studies a setting where one must choose cluster labels for incoming points in an online fashion, and then at the end of the algorithm can choose the k centers (the goal being to minimize the total k-means loss of this eventual clustering).
The algorithms we develop in this paper are based off of algorithms for contextual search. Contextual search is a problem that originally arose in the online pricing community [CLPL16, LLV17]. The variant of contextual search we reference in this paper (with symmetric, absolute value loss) first appeared in [LS18]. The algorithms in this paper were later improved in [LLS20] (and it is these improved algorithms that we build off of in this paper).

heading: 2 Model

text:
Notation We will write Bd(c, r) to denote the d-dimensional ball in Rd centered at c with radius r. We write Bd in place of Bd(0, 1) to indicate the unit ball centered at the origin.
Given an x ∈ Rd, we will write ∥x∥p to denote the Lp norm of the vector x. In the case of p = 2, we will often omit the subscript and write ∥x∥ in place of ∥x∥2.

heading: 2.1 Online Multiclass Learning

text:
We will view the problem of online multiclass learning as follows. There are k disjoint regions in some domain, say Bd, labelled R1 through Rk. The region Ri contains the points in Bd that should be assigned the label i. The goal of the learner is to learn these subsets (and thus how to label points in Bd in an online manner). Every round t, the learner receives an adversarially chosen query point qt ∈ Bd. The learner must submit a prediction It ∈ [k] for which region RIt the point qt lies in. The learner then learns which region RI∗t the point actually belongs to, and suffers some loss ℓ(qt, RIt). This loss function should in some way represent how far qt was from lying in the region RIt chosen by the learner; for example, in the case where the learner chooses the correct region RI∗t , ℓ(qt, RI∗t ) should be zero.
In this paper, we will consider two specific cases of the above learning problem. In the first case, we wish to learn a nearest-neighbor partition. That is, the k regions are defined by k “centers” x1, x2, . . . , xk ∈ Bd. Region Ri then consists of all the points which are “nearest” to center xi according to some similarity metric δ(x, y) (where lower values of δ(x, y) mean that x and y are more similar; note that δ(x, y) does not need to be an actual metric obeying the triangle-inequality). Given a similarity metric δ(x, y), the loss our algorithm incurs when labelling query q with label i is given by ℓ(q,Ri) = δ(q, xi)− δ(q, xi∗), where Ri∗ is the region containing query q. We will examine several different possibilities for δ(x, y), including:
• δ(x, y) = −⟨x, y⟩. We refer to this as the inner-product similarity between x and y. Note that when k = 2, using this similarity metric reduces to the problem of learning a linear classifier. For k > 2, this results in similar partitions to those learned by multiclass perceptrons / SVMs [CS03, CDK+06]. • δ(x, y) = ||x− y||2; in other words, the Euclidean distance between x and y. When using this loss function, the k regions are given by the Voronoi diagram formed by the k centers xi. • For p ≥ 1, δ(x, y) = ||x− y||p; in other words, the Lp distance between x and y.
There is a straightforward reduction from the Euclidean distance similarity to the inner-product similarity (see Appendix C), so in Section 3 we will primarily concern ourselves with the innerproduct similarity. In Section 4 we will tackle this problem for the case of general Lp norms; for some cases (even integer p) it is possible to perform a similar reduction to the inner product similarity, but in general it is not and we will need to rely on other techniques.
In the second case, we wish to learn general convex sets. In particular, there are k disjoint convex sets R1, . . . , Rk ⊆ Bd (not necessarily a partition). Each round t, we receive a query point qt ∈ ⋃k i=1 Ri, guess a region i ∈ [k], and are penalized against the loss function ℓ(qt, Ri) ≜ minx∈Ri ∥qt − x∥2. In other words, we are penalized the minimum distance from qt to the predicted region Ri, which is zero if our guess was correct. In Section 5 we will show that (even in the case of k = 2), there is no low-loss learning algorithm for learning general convex sets (in contrast to learning nearest neighbors).
Finally, for any α > 0 and existing loss function ℓ(g,Ri), we can consider the modified loss function ℓ′(q,Ri) = ℓ(q,Ri)
α. Note that this does not change the division of Bd into regions, but it can change the total loss incurred by our algorithm (and will be useful for some of our reductions). If in any result we do not specify an α, that means we are taking α = 1 (i.e. the unmodified loss function).

heading: 2.2 Contextual Search

text:
One of the main tools we will rely on is an existing algorithm for a problem in online learning known as contextual search. For our purposes, the problem of contextual search can be defined as follows. There is a hidden point p ∈ Bd, unknown to the learner. Every round t (for T rounds) an adversary provides the learner with a query vector xt ∈ Bd. The learner must then submit a guess gt for the value of the inner product ⟨xt, p⟩. The learner then learns whether their guess was too high or too low. At the end of the game, the learner incurs loss ℓ(gt, ⟨xt, p⟩) = |gt − ⟨xt, p⟩| for each of their guesses. The learner’s goal is to minimize their total loss.
Interestingly, there exist algorithms for contextual search with total loss polynomial in the ambient dimension d and independent of the time horizon T . The first such algorithms were given in [LS18]
and used techniques from integral geometry to obtain a total regret of O(d4). More recently, these algorithms were improved in [LLS20] to achieve a regret bound of O(d log d). We will rely on a slightly strengthened variant of the result from [LLS20] to work when the loss function raised to an arbitrary power. Theorem 7. Let α > 0. There exists an algorithm for contextual search with loss function ℓ(gt, ⟨xt, p⟩) = |gt − ⟨xt, p⟩|α that incurs a total loss of at most O(α−2d log d).
In particular, Theorem 7 is satisfied by the algorithm from [LLS20]. For completeness, we include a description of the algorithm (along with the proof of Theorem 7) in Appendix A.

heading: 3 Learning Nearest Neighbor Partitions

heading: 3.1 The Two-Point Case: Learning a Hyperplane

text:
To begin, we will discuss how to solve the k = 2 variant of the problem of learning nearest neighbor partitions for the inner-product similarity function δ(q, x) = −⟨q, x⟩. Recall that in this setting we have two unknown centers x1 and x2 belonging to Bd. Each round t we are given a query point qt ∈ Bd, and asked to choose a label It ∈ {1, 2} of the center that we think is most similar to qt (i.e., that maximizes δ(qt, x)). Letting yt = xIt and x ∗ t = argmaxxi δ(q, xi), our loss in round t is zero if we guess correctly (yt = x∗t ) and is δ(q, x ∗ t ) − δ(q, yt) if we guess incorrectly (we will also be able to deal with the case when the loss is |δ(q, x∗t )− δ(q, yt)| α for some α > 0). Afterwards, we are told the identity (but not the location) of x∗t .
Note that the optimal strategy in this game (for an agent who knows the hidden centers x1 and x2) is to guess It = 1 whenever ⟨q, x1⟩ > ⟨q, x2⟩, and to guess It = 2 otherwise. Rewriting this, we want to guess It = 1 exactly when ⟨q, x1 − x2⟩ > 0. If we let w = x1 − x2, we can think of goal as learning the hyperplane ⟨q, w⟩ = 0. More specifically, each round we are given a point q and asked which side of the hyperplane q lies on. If we guess correctly, we suffer no loss; if we guess incorrectly, we suffer loss equal to the distance from q to this hyperplane. In either case, we learn afterwards which side of the hyperplane q lies on.

heading: 3.1.1 Reducing to Contextual Search

text:
We will show that we can solve this online learning problem with total loss O(poly(d)), independent of the number of rounds T in the time-horizon. As mentioned earlier, our primary tool will be existing algorithms for a problem in online learning known as contextual search.
Recall that in contextual search there is a hidden vector v ∈ Bd, and each round we are given a vector qt ∈ Bd. However, unlike in our problem (where we only care about the sign of the inner product ⟨qt, v⟩), the goal in contextual search is to submit a guess gt for the value of the inner product ⟨qt, v⟩. We then incur loss equal to the absolute distance |⟨qt, vt⟩ − gt| between our guess and the truth, and are then told whether our guess gt was too high or too low.
As mentioned earlier in Section 2.2, there exist algorithms for contextual search with O(d log d) total loss. Via a simple reduction, we will show that we can apply these algorithms in our setting. Theorem 8. Fix α > 0. Assume there exists an algorithm A for contextual search with loss function ℓ(gt, ⟨xt, p⟩) = |gt − ⟨xt, p⟩|α that incurs regret at most R(d, T ). Then there exists an algorithm A′ that incurs regret at most R(d, T ) for the k = 2 case of learning nearest neighbor partitions with similarity metric δ(x, y) = −⟨x, y⟩ and loss raised to the power α. Corollary 3.1. Fix an α > 0. When k = 2, there exists an algorithm for learning nearest neighbor partitions with similarity metric δ(x, y) = −⟨x, y⟩ and loss raised to the power α that incurs total loss at most O(α−2d log d).

heading: 3.1.2 Potential-Based Algorithms

text:
In order to generalize this to k > 2 labels, we will need to open the black box that is our contextual search algorithm slightly. In particular, the argument in the following section requires our algorithm for the k = 2 case to be a potential-based algorithm.
Before defining exactly what a potential-based algorithm is, it will be useful to define the notion of a knowledge set. For the problem we are considering in this section – the k = 2 variant of our problem
for inner-product similarity – we will define the knowledge set Kt at time t to be the set of possible values for w = x1 − x2 that are consistent with all known information thus far. Note that since x1 and x2 start as arbitrary points in Bd, the knowledge set K0 is simply the set Bd −Bd = 2Bd. As the algorithm gets more feedback about w, the knowledge set shrinks; however, since this feedback is always of the form of a linear constraint (e.g. ⟨qt, w⟩ ≥ 0), the knowledge set Kt is always a convex subset of Rd. Let St be the history of all feedback the algorithm has seen up to (but not including) round t; that is St = {(q1, I∗1 ), (q2, I∗2 ), . . . , (qt−1, I∗t−1)}. Let St denote the set of possible values for St, and let S = ⋃ t St. We can think of St as capturing the state of a deterministic algorithm at time t. For now, it is fine to think of St as interchangeable with Kt; i.e., the knowledge set Kt captures all relevant details about all feedback the algorithm has observed thus far. (Later, when looking at Lp similarity metrics, we will want to keep track of separate knowledge sets at different scales, and thus will want a more nuanced notion of potential-based algorithm). Definition 9. A deterministic algorithm A (for k = 2 and α > 0) is a potential-based algorithm if there exists a potential function Φ from S to R≥0 and a “loss bound” function L from S × Bd to R≥0 that satisfy:
• For all rounds t, Φ(St+1) ≤ Φ(St). • Let qt be the query point in round t. Then L(St, qt) is an upper bound on the loss incurred
by any guess. In other words, L(St, qt) must satisfy
L(St, qt) ≥ maxx1,x2 consistent with St |δ(qt, x1)− δ(qt, x2)|α .
• Again, let qt be the query point in round t. IfA guesses the label incorrectly in round t, then Φ(St)− Φ(St+1) ≥ L(St, qt).
For the case of inner-product similarity, we will set the loss bound function L(St, qt) equal to the width of the knowledge set Kt in the direction qt. Importantly, this choice of L is an efficiently computable (in terms of qt and the knowledge set Kt) upper-bound on the loss, which will prove important in the following section (in general, we will want both Φ and L to be efficiently computable in order to efficiently carry out the reduction in Section 3.2).
Note also that such a potential immediately gives a way to bound the total loss of an algorithm independently of T ; in particular, summing the inequality Φ(St)− Φ(St+1) ≥ L(St, qt) over all t gives that the total loss is at most Φ(S0). We call the value Φ(S0) the initial potential of the algorithm A. Similar potential-based arguments are used in [LLS20] and [LS18] to give T -independent total loss bounds for the problem of contextual search. Unsurprisingly, these arguments can be extended (via Theorem 8) to apply to the problem of learning nearest neighbors as well. Theorem 10. Fix an α > 0. When k = 2, there exists a potential-based algorithm for learning nearest neighbor partitions under the similarity metric δ(x, y) = −⟨x, y⟩ that incurs total loss at most O(α−2d log d) (independent of the time horizon T ).
The proof of Theorem 10 can be found in Appendix B.

heading: 3.2 From Two to Many Centers

text:
We will now show how to use any potential-based algorithm for learning nearest neighbor partitions with two centers to construct an algorithm that can learn nearest neighbor partitions with any number of centers.
Our main result is the following: Theorem 11. Let A be a potential-based algorithm for learning nearest neighbor partitions with two centers that has an initial potential (and thus a total loss) of at most R. Then there exists a randomized algorithmA′ for learning nearest neighbor partitions for any k ≥ 2 whose total expected loss is at most O(k2R).
Similar to many existing methods for multiclass classification (“all-to-all” methods), we will accomplish this by running one instance of our two-center algorithm A for each of the ( k 2 ) pairs of centers.
However, instead of using a simple majority voting scheme to choose our eventual label, we will use the potentials of these ( k 2 ) algorithms to construct a distribution over centers that we will sample from.
More specifically, our algorithm will work as follows. As mentioned, each round, based on the current query qt and the potentials of the ( k 2 ) sub-algorithms, we will construct a distribution v ∈ ∆([k]) over the k centers (we will describe how we do this shortly). We then sample a label i from this distribution v and guess it as the label of qt. If we then learn that the correct label was in fact j, we update the sub-algorithm for the pair (i, j) with this information. We do not update any of the other sub-algorithms (in particular, if we guess the label correctly, we do not update any of the sub-algorithms).
To construct our distribution v, we will choose a distribution v that has the property that our expected loss in each round is at most the expected decrease in the total potential over all ( k 2 ) sub-algorithms. This will guarantee that the total expected loss of our algorithm is bounded above by the total starting potential of all our ( k 2 ) sub-algorithms. To be more precise, define the following variables:
1. Let Aij denote the two-center sub-algorithm for the labels i and j. Let S(t)ij be the state of Aij at round t, and let Φ(t)ij = Φ(S (t) ij ) be the potential of Aij at round t. Define
Φ(t) = ∑
(i,j) Φ (t) ij to be the total of all the potentials belonging to sub-algorithms Aij .
2. As in Definition 9, let L(t)ij = L(S (t) ij , qt) denote an upper-bound on the loss incurred by the
algorithm Aij in round t. 3. Let D(t)ij denote the reduction in the potential of Aij when i is the correct label. In other
words, D(t)ij = Φ (t) ij −Φ (t+1) ij when I ∗ t = i. Note that D (t) ij is not equal to D (t) ji ; it is possible for the potential of Aij to decrease a lot more upon learning that a point qt has label i than learning it has label j (geometrically, this corresponds to different halves of the knowledge set being maintained by Aij).
4. Finally, define M (t) ≜ D(t) − 12 · L (t), where here we are treating M (t) and L(t) as n-by-n
matrices. Observe that we can efficiently compute the values L(t)ij and D (t) ij and hence the value of M (t)ij from qt and the knowledge set of Aij at the beginning of round t.
From here on, we will fix a round t and suppress all associated superscripts. Assume that in this round the correct label for the query point is r. Now, if we sample a label from a distribution v, then note that the expected loss we sustain is ∑ i Lrivi = e T r Lv. Similarly, the expected decrease in Φ is∑
i Drivi = e T r Dv. If it was guaranteed to be the case that e T r Dv ≥ eTr Lv, then this would in turn
guarantee that our total expected loss is at most the total starting potential.
It follows that if we can find a distribution v that satisfies Mv ≥ 0, we are in luck. If such a distribution exists, we can find it by solving an LP. This is in fact how we find the distribution v, and this concludes the description of the algorithm. To prove correctness of the algorithm, it suffices to show that such a distribution always exists.
To do so, note that from the third point in Definition 9, we know that for each pair of labels (i, j),
Dij +Dji ≥ Lij (P1)
(In fact, Definition 9 tells us that max(Dij , Dji) ≥ Lij , since if Aij predicts j, we have that Dij ≥ Lij , and likewise if Aij predicts i, we have that Dji ≥ Lij). We can rewrite (P1) in the form M +MT ≥ 0. The following lemma shows that if M +MT ≥ 0, then there must exist a distribution v satisfying Mv ≥ 0, whose proof we defer to the appendix. Lemma 3.2. Given any matrix M ∈ Rn×n such that M +MT ≥ 0, there exists a point v ∈ ∆n such that Mv ≥ 0.
With this, it is straightforward to finish off the proof of Theorem 11.
Proof of Theorem 11. By Lemma 3.2, we know that each round we can find a distribution v ∈ ∆([k]) satisfying Mv ≥ 0. By the previous discussion, it follows that if we always sample from this
distribution, the total expected loss will be at most twice the starting total potential, 2Φ(1). But note that Φ(1) is just the sum of the starting potentials Φ(1)ij of all the sub-algorithms, and is thus at most( k 2 ) R. It follows that the total loss of our new algorithm is at most O(k2R).
Corollary 3.3. Fix an α > 0. There exists a randomized algorithm for learning nearest neighbor partitions with the inner-product similarity metric that incurs total loss at most O(α−2k2d log d).
Remark 3.4. Why do simple algorithms (such as a majority voting scheme) fail to work in our setting? In fact, it is possible to get a simple majority vote (breaking ties arbitrarily) to work if we are given additional feedback from the algorithm – specifically, the ranking of all k distances δ(qt, xi). With this information, it is possible to update all ( k 2 ) sub-instances each round, and charge any regret we sustain to an appropriate sub-instance. But if we only receive the true label of qt, we no longer have the information to update every sub-instance, and instead have to do the more subtle amortization described above.

heading: 4 Learning Nearest Neighbor Partitions Under Lp Similarity

text:
In this section, we will discuss generalizations of our previous results for the inner-product similarity metric to general Lp spaces. We will primarily deal with the case when there are only two unknown points (k = 2) as the general reduction in Section 3.2 will allow us to reduce from the k-point case to the 2-point case.
The general approach for the algorithms in this section is to apply some sort of kernel mapping so that inequalities of the form ∥X − x1∥p ≤ ∥X − x2∥p become linear constraints. Once we linearize the problem, we can apply our earlier algorithms for the inner-product similarity along with tools from [LLS20].
Similar to the previous sections, we will assume that the hidden points x1, x2 are in the L2 unit ball Bd. This is equivalent to assuming that the hidden points are in the Lp unit ball (which may be a more natural setting since we are working with Lp distances) up to a √ d factor since we can simply rescale the L2-ball to contain the Lp-ball.
4.1 p-Norms for Even Integers p
When p is an even integer, there is a kernel mapping that exactly linearizes the problem. To see this, note that |(x− a)|p = (x− a)p which is a polynomial in x so it suffices to consider the polynomial kernel (1, x, . . . , xp). In d dimensions, we can simply apply this kernel map coordinate-wise. After applying these kernel maps, we will be able to apply Corollary 3.3. Our main theorem for even integer p is stated below. Theorem 12. For even integer p, there is an algorithm for learning nearest neighbor partitions under the Lp similarity metric that incurs expected total loss at most O(p4d(p+1)/pk2 log d) = O(k2 · poly(p, d)).
The details of the proof are deferred to Appendix E.2. Remark 4.1. For the special case of p = 2, the reduction is even more immediate (the kernel map needs only add a single dimension), and obtains a slightly tighter bound of O(k2d log d). The reduction for this special case is summarized in Appendix C.
4.2 General p-Norms
Now we discuss how to deal with general Lp norms. The main difficulty here is that there is no kernel map that exactly linearizes the problem so instead we will have multiple kernel maps. These kernel maps approximately linearize the problem at different scales, i.e. they have different output dimensions and as the output dimension grows, the problem can be more closely approximated by a linear one. When we are given a query point, we choose the scale of approximation that we use based on estimating the maximum possible loss that we can incur. By balancing the dimensionality and the approximation error to be at the same scale as the maximum possible loss, we may ensure that whenever we guess the label incorrectly, a certain potential function must decrease by an amount comparable to the loss that we incur. Our main theorem is stated below.
Theorem 13. Fix a p > 2. If all k unknown centers are ∆-separated in Lp distance, there exists an algorithm for learning nearest neighbor partitions under the Lp similarity metric that incurs total loss
k2poly(d, p) ∆ · ( 1 p− 2 )2 .
The full proof is more complicated than the algorithms in previous sections and requires opening the contextual search black-box and redoing parts of the analysis. Note that in the above theorem, we need the assumption that the unknown centers are ∆-separated, an assumption that was not necessary for even integer p. This is due to the fact that when the true centers are too close together, the dimensionality of the kernels that we need to achieve the necessary approximations are large. Nevertheless, we believe that the separated centers assumption is realistic for classification problems in practice. The details of the proof of Theorem 13 are deferred to Appendix E.3 of the Supplementary Material.

heading: 5 Learning General Convex Regions: Lower Bound

text: In this section, we consider the task of learning general convex regions, and present a construction which shows that any learning algorithm incurs Ω(T (d−4)/(d−2)) error over T rounds, even for only k = 2 regions. We give the full proof in Appendix F. Theorem 4. Any algorithm for learning general convex regions incurs a total loss of at least Ω ( T (d−4)/(d−2) ) , even when there are only two regions.

title: Margin-Independent Online Multiclass Learning via Convex Geometry


summaries: This paper proposes a new loss terms to encourage Transformer-based models perform "explicit reasoning", which is beneficial for transferring knowledge from oracle-trained VQA models to deployable ones. Specifically, the novel loss is similar with the one commonly used in modular network (e.g. converting questions to executable program/functions), but instead of relying on the predicted programs to assemble executable programs during inference, in this paper this loss is only used during training as an auxiliary regularization on top of regular Transformer-based VQA models. The authors provide theoretical proof about the benefits of using the additional loss, and empirically evaluated the advantage on GQA dataset (including out-of-distribution evaluation on GQA-OOD). The proposed system demonstrates not the best but still competitive performance especially considering the model size and training efficiency (without using extra data).  ========================================================================================  Thanks for the response from the authors. I've updated my rating after reading the rebuttal as well as the comments from other reviewers.

summaries: The paper studies the problem of training VQA models on noisy/imperfect visual input (e.g., representations from existing object detectors). It proposes using program supervision as an additional task to assist in transferring reasoning patterns learned through clean/oracle visual inputs to the imperfect inputs. The experiments are performed on the GQA/GQA-OOD benchmarks, and the empirical results show gains on both frequent (head) and infrequent (tail) classes, showing improvement in reasoning skills. Furthermore, the work theoretically shows that predicting programs can reduce sample complexity.

summaries: This paper targets on the application problem of visual question answering, whose recent state of the art was set by attention (typically transformer) - based deep neural networks. This work propose to use program supervision to introduce extra loss terms in the training of these transformer based models, arguing that the guidance from these signals improve the model's robustness against noise and fluctuations in the visual input during transfer learning. Theoretical analysis and experimental evaluations are conducted on program supervision, leading to plausible findings and results.

summaries: This paper describes a novel approach for doing more robust VQA that doesn’t just learn to exploit the biases in the data. They build on previous work which demonstrated that training a model on oracle visual data makes it less susceptible to learning biases in the data. While the previous work showed that the better reasoning skills learnt by the models trained on oracle visuals decline when transferred to the noisier visuals extracted by pre-trained vision models, here the authors demonstrate that adding the additional supervision step of making the model predict the reasoning program alongside the VQA answer makes it more robust to such distributional shifts.

abstractText: Methods for Visual Question Anwering (VQA) are notorious for leveraging dataset biases rather than performing reasoning, hindering generalization. It has been recently shown that better reasoning patterns emerge in attention layers of a stateof-the-art VQA model when they are trained on perfect (oracle) visual inputs. This provides evidence that deep neural networks can learn to reason when training conditions are favorable enough. However, transferring this learned knowledge to deployable models is a challenge, as much of it is lost during the transfer. We propose a method for knowledge transfer based on a regularization term in our loss function, supervising the sequence of required reasoning operations. We provide a theoretical analysis based on PAC-learning, showing that such program prediction can lead to decreased sample complexity under mild hypotheses. We also demonstrate the effectiveness of this approach experimentally on the GQA dataset and show its complementarity to BERT-like self-supervised pre-training.

authors:
Aishwarya Agrawal
Dhruv Batra
Devi Parikh
Aniruddha Kembhavi

title: Don’t just assume; look and answer: Overcoming priors for visual question answering

authors:
Peter Anderson
Xiaodong He
Chris Buehler
Damien Teney
Mark Johnson
Stephen Gould
Lei Zhang

title: Bottom-up and top-down attention for image captioning and visual question answering

venue: In CVPR,

authors:
Jacob Andreas
Marcus Rohrbach
Trevor Darrell
Dan Klein

title: Neural module networks

authors:
Stanislaw Antol
Aishwarya Agrawal
Jiasen Lu
Margaret Mitchell
Dhruv Batra
C Lawrence Zitnick
Devi Parikh

title: Vqa: Visual question answering

venue: In ICCV,

authors:
Hedi Ben-Younes
Rémi Cadene
Matthieu Cord
Nicolas Thome

title: Mutan: Multimodal tucker fusion for visual question answering

authors:
Wenhu Chen
Zhe Gan
Linjie Li
Yu Cheng
William Wang
Jingjing Liu

title: Meta module network for compositional visual reasoning

venue: In WACV,

authors:
Kyunghyun Cho
Bart van Merrienboer
Çaglar Gülçehre
Dzmitry Bahdanau
Fethi Bougares
Holger Schwenk
Yoshua Bengio

title: Learning phrase representations using rnn encoder-decoder for statistical machine translation

venue: In EMNLP,

authors:
Corentin Dancette
Remi Cadene
Damien Teney
Matthieu Cord

title: Beyond question-based biases: Assessing multimodal shortcut learning in visual question answering

venue: arXiv preprint arXiv:2104.03149,

authors:
Abhishek Das
Harsh Agrawal
C. Lawrence Zitnick
Devi Parikh
Dhruv Batra

title: Human Attention in Visual Question Answering: Do Humans and Deep Networks Look at the Same Regions

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova

title: Bert: Pre-training of deep bidirectional transformers for language understanding

venue: In Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,

authors:
Robert Geirhos
Jörn-Henrik Jacobsen
Claudio Michaelis
Richard Zemel
Wieland Brendel
Matthias Bethge
Felix A Wichmann

title: Shortcut learning in deep neural networks

venue: Nature Machine Intelligence,

authors:
Yash Goyal
Tejas Khot
Douglas Summers-Stay
Dhruv Batra
Devi Parikh

title: Making the v in vqa matter: Elevating the role of image understanding in visual question answering

authors:
Ronghang Hu
Jacob Andreas
Marcus Rohrbach
Trevor Darrell
Kate Saenko

title: Learning to reason: End-to-end module networks for visual question answering

venue: In Proceedings of the IEEE International Conference on Computer Vision,

authors:
Drew Hudson
Christopher D Manning

title: Learning by abstraction: The neural state machine

venue: In Advances in Neural Information Processing Systems,

authors:
Drew A Hudson
Christopher D Manning

title: Gqa: A new dataset for real-world visual reasoning and compositional question answering

authors:
Justin Johnson
Bharath Hariharan
Laurens van der Maaten
Li Fei-Fei
C Lawrence Zitnick
Ross Girshick

title: Clevr: A diagnostic dataset for compositional language and elementary visual reasoning

authors:
Justin Johnson
Bharath Hariharan
Laurens Van Der Maaten
Judy Hoffman
Li Fei-Fei
C Lawrence Zitnick
Ross Girshick

title: Inferring and executing programs for visual reasoning

authors:
C. Kervadec
G. Antipov
M. Baccouche
C. Wolf

title: Roses Are Red, Violets Are Blue.

venue: Should VQA Expect Them To? Pre-print: arxiv:2006.05121,

authors:
Corentin Kervadec
Grigory Antipov
Moez Baccouche
Christian Wolf

title: Weak supervision helps emergence of word-object alignment and improves vision-language tasks

venue: In European Conference on Artificial Intelligence,

title: Roses are red, violets are blue... but should vqa expect them to

authors:
Corentin Kervadec
Theo Jaunet
Grigory Antipov
Moez Baccouche
Romain Vuillemot
Christian Wolf

title: How transferable are reasoning patterns in vqa

authors:
Jin-Hwa Kim
Jaehyun Jun
Byoung-Tak Zhang

title: Bilinear attention networks

authors:
Jiayuan Mao
Chuang Gan
Pushmeet Kohli
Joshua B. Tenenbaum
Jiajun Wu

title: The Neuro-Symbolic Concept Learner: Interpreting Scenes, Words, and Sentences From Natural Supervision

venue: In International Conference on Learning Representations,

authors:
Hubert Ramsauer
Bernhard Schäfl
Johannes Lehner
Philipp Seidl
Michael Widrich
Lukas Gruber
Markus Holzleitner
Milena Pavlović
Geir Kjetil Sandve
Victor Greiff

title: Hopfield networks is all you need

authors:
Shaoqing Ren
Kaiming He
Ross Girshick
Jian Sun

title: Faster r-cnn: Towards real-time object detection with region proposal networks. In Advances in neural information processing

authors:
S.S. Du S. Arora
W. Hu
Z. Li
R. Wang

title: Fine-grained Analysis of optimization and generalization for overparametrized two-layer neural networks

authors:
Shai S. Shalev-Shwart
S. Ben-David

title: Understanding Machine Learning - From Theory to Algorithms

authors:
Robik Shrestha
Kushal Kafle
Christopher Kanan

title: A negative case analysis of visual grounding methods for vqa

venue: In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics,

title: An investigation of critical issues in bias mitigation techniques

venue: arXiv preprint arXiv:2104.00170,

authors:
Hao Tan
Mohit Bansal

title: Lxmert: Learning cross-modality encoder representations from transformers

authors:
Damien Teney
Ehsan Abbasnejad
Kushal Kafle
Robik Shrestha
Christopher Kanan
Anton van den Hengel

title: On the value of out-of-distribution testing: An example of goodhart's law

venue: NeurIPS,

title: A theory of the learnable

venue: In Communications of the ACM,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

venue: In Advances in neural information processing systems,

authors:
K. Xu
J. Li
M. Zhang
S.S. Du
K.-I. K
S. Jegelka

title: What can Neural Networks Reason About

venue: In ICLR,

authors:
Kexin Yi
Jiajun Wu
Chuang Gan
Antonio Torralba
Pushmeet Kohli
Joshua B Tenenbaum

title: Neural- Symbolic VQA: Disentangling Reasoning from Vision and Language Understanding

venue: In Advances in Neural Information Processing Systems (NIPS),

authors:
Zhou Yu
Jun Yu
Yuhao Cui
Dacheng Tao
Qi Tian

title: Deep modular co-attention networks for visual question answering

authors:
C. Zhang
S. Bengio
M. Hardt
B. Recht
O. Vinyals

title: Understanding deep learning requires rethinking generalization

heading: 1 Introduction

text:
Reasoning over images is the main goal of Visual Question Anwering (VQA), a task where a model is asked to answer questions over images. This problem is a test bed for the creation of agents capable of high-level reasoning, as it involves multi-modal and high-dimensional data as well as complex decision functions requiring latent representations and multiple hops. State-of-the-art models are notorious for leveraging dataset biases and shortcuts in learning rather than performing reasoning, leading to lack of generalization, as evidenced by extensive recent work on bias oriented benchmarks for vision-and-language reasoning [1, 20, 21, 31]. Even large-scale semi-supervised pre-training methods, which successfully managed to increase overall VQA performance, still struggle to address questions whose answers are rare given a context [20].
It has been recently shown that reasoning patterns emerge in attention layers of a SOTA VQA model when trained on perfect (oracle) visual inputs, which provides evidence that deep neural networks can learn to reason, when training conditions are favorable enough [21]. In particular, uncertainty and noise in visual inputs seems to be a major cause for shortcut learning in VQA. While this kind of methods provide strong empirical results and insights on the bottlenecks in problems involving learning to reason, they still suffer from significant loss in reasoning capabilities during the transfer phase, when the model is required to adapt from perfectly clean visual input to the noisy input it will encounter after deployment. We conjecture, that reasoning on noisy data involves additional functional components not necessary in the clean case due to different types of domain shifts: (1) a presence shift, caused by imperfect object detectors, leading to missing visual objects necessary for
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
reasoning, or to multiple (duplicate) detections; (2) an appearance shift causing variations in object embeddings (descriptors) for the same class of objects due to different appearance.
In this paper, we propose a new method for transferring reasoning patterns from models learned on perfect visual input to models trained on noisy visual representations. Key to the success is a regularization term minimizing loss of the reasoning capabilities during transfer. In particular, we address this problem through program prediction as an additional auxiliary loss, i.e. supervision of the sequence of reasoning operations along with their textual and/or visual arguments. To maintain a strong link between the learned function and its objective during the knowledge transfer phase, when inputs are switched from clean oracle inputs to noisy input, the neural model is required to continue to predict complex reasoning programs from different types of inputs.
As a second justification, we claim that program supervision in itself leads to a simpler learning problem, as the underlying reasoning function is decomposed into a set of tasks, each of which is easier to learn individually than the full joint decision function. We backup this claim through a theoretical analysis showing decreased sample complexity under mild hypotheses.
As a summary, we present the following contributions: (i) we propose a new program supervision module added on top of vision-language transformer models; (ii) we provide a theoretical analysis of the benefit of supervising program prediction in VQA deriving bounds on sample complexity; (iii) we experimentally demonstrate the efficiency of program supervision and show that it increases VQA performance on both in- and out-of-distribution sets, even when combined with BERT-like pre-training [30, 10], and that it improves the quality of oracle transfer initially proposed by [21].

heading: 2 Related Work

text:
Transformers in VQA — VQA as a task was introduced in various datasets [4, 12, 16], including GQA [15] which is automatically-generated from real-world images. This growing amount of diverse datasets has been accompanied by the development of more and more sophisticated VQA models. While their exhaustive survey is out of the scope of this paper, one can mention some foundational categories of approaches, e.g. those based on object-level attention [2] and tensor decomposition [5]. In this work, we focus on VQA models which are based on Transformers [33], due to their wide adoption and their impressive results in several tasks (including VQA). In particular, we rely on the combination of Transformers with a large-scale BERT [10]-like pretraining which was shown to be beneficial for VQA in recent works [19, 30]. More recently, [21] focused on the study of so-called reasoning patterns in such Transformer-based VQA models. The authors analyzed how various VQA tasks are encoded in different attention heads, by applying an energy-based analysis inspired by [24]. The analysis was performed using a perfect-sighted oracle Transformer model (which is trained with near-to-perfect visual information, and thus, is much less prone to exploit dataset biases) in order to identify which patterns lead to better reasoning. Then, the authors showed that these reasoning patterns can be transferred from the oracle to a Transformer-based VQA model, thus improving both overall accuracy and accuracy on infrequent answers. In this work, we argue that using program prediction as an additional supervision signal is a catalyst for the transfer of these reasoning patterns.
Biases and shortcut learning in VQA — In addition to the popular VQA datasets mentioned above, other benchmarks were proposed to evaluate specific reasoning capabilities of VQA systems. In particular, they address the issue of shortcut learning [11] in deep learning, where models learn decision rules which are ineffective when tested on a domain or distribution different from the training one. For instance, VQA-CP [1] explicitly inverts the answer distribution between train and test splits. To cope with recent criticisms regarding these evaluations [31, 28], the GQA-OOD dataset [18] introduced a new split of GQA focusing on rare (Out-Of-Distribution / OOD) question-answer pairs, and showed that many VQA models strongly rely on dataset biases. Following this work, the VQA-CE dataset [8] introduced a new evaluation approach related to the VQA v2 dataset. By studying the multi-modal shortcuts in the training set and mining some trivial predictive rules (e.g. co-occurrences of words and visual objects), the evaluation set is generated using questions where these mined rules lead to incorrect answers. As for GQA-OOD, this dataset demonstrated that SOTA models do not perform well when they can’t rely on shortcuts, even models which use bias-reduction techniques. Based on these benchmarks, several methods have been conceived to reduce shortcut learning in VQA (see [31, 29] for a comprehensive study of the different techniques). However none of them achieve significant performance improvement on GQA-OOD [18] or VQA-CE [8].
Connections with symbolic VQA — Our work is also related to neuro-symbolic reasoning [35, 23] and neural module networks (NMN) [3, 13], which generally encode a set of pre-defined functions into unique neural modules, then dynamically compose them to execute question-related programs. Several improvements of standard NMNs have been proposed to make them end-to-end trainable through reinforcement learning [17] or, more recently, to enhance their scalability and generalizability [6]. However, the common point of all these works is that they are generally based on the prediction of reasoning programs whose elementary functions are learned jointly with program prediction itself, through program supervision. In contrast to this work, our approach uses program supervision to enrich its internal representations instead of inferring program’s execution.
Measuring complexity of learning problems — and thus generalization, has been a goal of theoretical machine learning since the early days, with a large body of work based on PAC-Learning [32, 27]. Traditionally, bounds have been provided ignoring data distributions and focusing uniquely on hypothesis classes (network structures in neural network language), e.g. as measured by VCdimension. Surprising experimental results on training networks on random samples have seemingly contradicted learning theory [37], in particular Rademacher Complexity. Recently, building on statistics of gradient descent, bounds have been proposed which take into account data distributions, notably [26]. Algorithmic alignment between neural network structures and the decomposition of underlying reasoning functions has been studied in [34], with a focus on algorithms based on dynamic programming. Our theoretical contribution in section 4 builds on the latter two methodologies and extends this type of analysis to intermediate supervision of reasoning programs.

heading: 3 Knowledge transfer and program supervision

text:
We propose a method for transferring reasoning patterns from models learned on perfect visual inputs to models trained on noisy visual representations. In the lines of oracle transfer [21], we first pre-train a model on ground-truth visual data and then fine-tune on standard visual embeddings extracted with an object detector. The underlying hypothesis is that the noise and uncertainty in visual input prevents the model from learning to reason and leads to learning shortcuts.
To minimize the loss of reasoning capabilities during the transfer over the presence shift between oracle and noisy visual objects, we propose a regularization technique, which supervises the prediction of reasoning steps required to answer the question. We therefore assume the existence of the following ground truth annotation of reasoning programs. A given data sample consists of a sequence {qi} of input question word embeddings, a set {vi} of input visual objects, the ground truth answer class y∗ as well as the groundtruth reasoning program, which is structured as a tree involving operations and arguments. Operations {o∗i } are elements of a predefined set {choose color, filter size, ...}. The arguments of these operations may be taken from (i) all question words, (ii) all visual objects, (iii) all operations — when an operation takes as argument the result of another operation. Hence, arguments are annotated as many-to-many relationships. In the question “Is there a motorbike or a plane?”, for instance, the operation “or” depends on the result of the two operations checking the existence of a specific object in the image. This is denoted as aq∗ij ∈{0, 1} where a q∗ ij =1 means that
operation i is associated with question word j as argument and, similarly, av∗ij =1 indicating a visual argument and ad∗ij =1 an operation result argument.
We propose to apply the regularization on top of the VL-Transformer architecture proposed in [30], based on sequences of self- and cross-modality attention. For this purpose, we define a trainable module for program generation (program decoder), added to the output of the VL-Transformer model as shown in Fig. 2 — an adaptation to other architectures would be straightforward.
Program decoder — In the lines of [6], the program decoder has been designed in a coarse-to-fine fashion. It first generates À a coarse sketch of the program consisting only of the operations, which are then Á refined by predicting textual and visual arguments and dependencies between operations.
À Coarse: operation — this module only predicts the sequence of operations {oi}i∈[0,n−1] using a recurrent neural network (RNN / GRU) [7] variant, whose initial hidden state is initialized with the yCLS token embedding of the VQA transformer — the same embedding from which classically the final answer y is predicted, cf. Figure 2. Inference is stopped when the special “STOP” operation is predicted. At each GRU time step i, a new hidden state hi is computed, from which the operation oi is classified with a linear projection. It is supervised with a cross-entropy loss Lop = ∑ iLCE(oi,o∗i ).
Á Fine: input arguments — the coarse program is then refined by predicting the operations’ arguments. We first deal with textual and visual arguments only. Affinity scores aqij between each operation’s hidden hi and token qj embeddings are computed with a 2-layer feed-forward network from concatenated embeddings. They represent the probability of the word qj to belong to the argument set of operation oi. Similar scores avij are computed for operations and visual objects. They are supervised with BCE losses Lqarg = ∑ ijLBCE(a q ij ,a q∗ ij ) and Lvarg = ∑ ijLBCE(avij ,av∗ij ).
Fine: op arguments — next the dependencies are predicted, i.e. arguments which correspond to results of other operations, and which structure the program into a tree. We deal with these arguments differently, and compute the set of dependency arguments for each operation oi with another GRU, whose hidden state is initialized with the hidden state hi of the operation. The argument index adij is a linear projection of the hidden state and supervised with BCE: Ldep = ∑ ijLBCE(adij ,ad∗ij ).
Program supervision — The coarse-to-fine program decoder is trained with the four additional losses weighted by hyperparameters α, β, γ, δ.
L = Lvqa︸︷︷︸ VQA +α.Lop + β.Ldep + γ.Lqarg + δ.Lvarg︸ ︷︷ ︸ Program supervision , (1)
Ground truth programs — We use ground truth information from the GQA [15] dataset, whose questions have been automatically generated from real images. Each sample contains a program describing the operations and arguments required to derive the answer for each question. However, the GT programs have been created for GT visual arguments (GT objects), which do not exactly
match the visual input of an object detector used during training and inference [2]. We therefore construct a soft target, by computing intersection-over-union (IoU) between GT and detected objects.
Oracle transfer — Our method uses program supervision to regularize knowledge transfer from a visual oracle to noisy input, as introduced in [21]. Oracle transfer consists in pretraining the VLTransformer model on ground-truth one-hot visual inputs before performing BERT-like pre-training. It offers training conditions which are more favorable for learning reasoning capabilities. We perform the following steps: (1) Oracle pre-training on GT visual input on the GQA dataset; (2) (optionally) BERT-like pre-training on data from GQA unbalanced; (3) Finetuning on the final VQA-objective on the GQA dataset. Each one of these steps are regularized using program supervision.

heading: 4 Sample complexity of program supervision

text:
We provide a theoretical analysis indicating that the prediction and supervision of reasoning programs can improve learnability in vision and language reasoning under some assumptions. In what follows, we denote with g “true” (but unknown) underlying reasoning functions, and by f functions approximating them, implemented as neural networks. The goal is to learn a function g able to predict a distribution y over answer classes given an input question and an input image, see Fig 1a. While in the experimental part we use state-of-the-art tranformer based models, in this theoretical analysis, we consider a simplified model, which takes as input the two vectorial embeddings q and v corresponding to, respectively, the question and the visual information (image), for instance generated by a language model and a convolutional neural network, and produces answers y∗ = g(q,v).
We restrict this analysis to two-layer MLPs, as they are easier to handle theoretically than modern attention based models. The reasoning function g is approximated by neural network f parametrized by a vector θ and which predicts output answers y = f(q,v, θ).
Our analysis uses PAC-learning [32] and builds on recent results providing bounds on sample complexity taking into account the data distribution itself. We here briefly reproduce Theorem 3.5. from paper [34], which, as an extension of a result in [26], provides a bound for sample complexity of overparametrized MLPs with vectorial outputs, i.e. MLPs with sufficient capacity for learning a given task:
Theorem 4.1 (Sample complexity for overparametrized MLPs). Let A be an overparametrized and randomly initialized two-layer MLP trained with gradient descent for a sufficient number of iterations. Suppose g : Rd → Rm with components g(x)(i) = ∑ j α (i) j (β (i)T j x) p (i) j , where β(i)j ∈ Rd, α(i) ∈ R, and p(i)j = 1 or p (i) j = 2l, l ∈ N+. The sample complexity CA(g, , δ) is
CA(g, , δ) = O maxi∑j p(i)j |α(i)j |·||β(i)j ||p(i)j2 + log(mδ ) ( /m)2  (2) We use the following Ansatz: since each possible input question requires a potentially different form of reasoning over the visual content, our analysis is based on the following assumption.
Assumption 1. The unknown reasoning function g() is a mixture model which decomposes as follows y∗ = ∑ r πrhr = ∑ r πrgr(v), (3)
where the different mixture components r correspond to different forms of reasoning related to different questions. The mixture components can reason on the visual input only, and the mixture weights are determined by the question q, i.e. the weights π depend on the question q, e.g. π = gπ(q).
We call gπ(.) the reasoning mode estimator. One hypothesis underlying this analysis is that learning to predict reasoning programs allows the model to more easily decompose into this form (3), i.e. that the network structure closely mimicks this decomposition, as information on the different reasoning modes r is likely to be available in the activations of intermediate layers, cf. Figure 1. This will be formalized in assumption 3 and justified further below.
Considering the supposed “true” reasoning function y∗ = g(q,v) and its decomposition given in (3), we suppose that each individual reasoning module gr can be approximated with a multi-variate
polynomial, in particular each component h(i)r of the vector hr, as h(i)r = gr(v) = ∑ j α (i) r,j(β (i)T r,j v) p (i) r,j with parameters ω = { α (i) r,j , β (i) r,j , p (i) r,j . }
(4)
A trivial lower bound on the complexity of the reasoning mode estimator gπ(.) is the complexity of the identity function, which is obtained in the highly unlikely case where the question embeddings q contain the 1-in-K encoding of the choice of reasoning mode r. We adopt a more realistic case as the following assumption. Assumption 2. The input question embeddings q are separated into clusters according to reasoning modes r, such that the underlying reasoning mode estimator gπ can be realized as a NN classifier with dot-product similarity in this embedding space.
Under this assumption, the reasoning mode estimator can be expressed as a generalized linear model, i.e. a linear function followed by a soft-max σ,
π = gπ(q) = σ ([ γT0 q, γ T 1 q, ... ]) , (5)
where the different γr are the cluster centers of the different reasoning modes r in the question embedding space. As the softmax is a monotonic non-linear function, its removal will not decrease sample complexity1, and the complexity can be bounded by the logits πr = γTr q. Plugging this into (3) we obtain that each component y∗(i) of the answer is expressed as the following function:
y∗(i) = ∑ r ( γTr q )∑ j α (i) r,j(β (i)T r,j v) p (i) r,j (6)
We can reparametrize this function by concatenating the question q and the visual input v into a single input vector x, which are then masked by two different binary masks, which can be subsumed into the parameters γr and β (i) r,j , respectively, giving
y∗(i) = ∑ r ∑ j (γTr x)α (i) r,j(β (i)T r,j x) p (i) r,j (7)
Extending Theorem 3.5. from [34], we can give our main theoretical result as the sample complexity of this function expressed as the following theorem. Theorem 4.2 (Sample complexity for multi-mode reasoning functions). Let A be an overparametrized and randomly initialized two-layer MLP trained with gradient descent for a sufficient number of iterations. Suppose g : Rd → Rm with components g(x)(i) =∑ r ∑ j(γ T r x)α (i) r,j(β (i)T r,j x) p (i) r,j where γr ∈ Rd, β(i)r,j ∈ Rd, α (i) r,j ∈ R, and p (i) r,j = 1 or p (i) r,j = 2l, l ∈ N+. The sample complexity CA(g, , δ) is
CA(g, , δ) = O maxi∑r∑j πp(i)r,j |α|·||γr||2·||βr,j ||p(i)r,j2 + log(m/δ) ( /m)2  . The proof of this theorem is given in the supplementary material (Appendix A).
Theorem 4.2 provides the sample complexity of the reasoning function g() under classical training. In the case of program supervision, our analysis is based on the following assumption (see also Fig. 1b): Assumption 3. Supervising reasoning programs encodes the choice of reasoning modes r into the hidden activations of the network f . Therefore, learning is separated into several different processes,
(a) learning of the reasoning mode estimator gπ() approximated as a network branch fπ() connected to the program output;
(b) learning of the the different reasoning modules gr() approximated as network branches fr() connected to the different answer classes yr; each one of these modules is learned independently.
1In principle, there should exist special degenerate cases, where an additional softmax could reduce sample complexity; however, in our case it is applied to a linear function and thus generates a non-linear function.
We justify Assumption 3.a through supervision directly, which separates gπ() from the rest of the reasoning process. We justify Assumption 3.b by the fact, that different reasoning modes r will lead to different hidden activations of the network. Later layers will therefore see different inputs for different modes r, and selector neurons can identify responsible inputs for each branch fr(), effectively switching off irrelevant input.
We can see that these complexities are lower than the sample complexity of the full reasoning function given in theorem 4.2, since for a given combination of i, r, j, the term ||γr||2·||βr,j || p (i) r,j 2 dominates the corresponding term ||βr,j || p (i) r,j
2 . Recalling that the vectors γ correspond to the cluster centers of reasoning modes in language embedding space. Under the assumption that the embeddings q have been created with batch normalization, a standard technique in deep learning, each value γ(i)r follows a normal distribution N (0, 1). Dropping indices i, r, j to ease notation, we can then compare the expectation of the term ||γ||2·||β||p2 over the distribution of γ and derive the following relationship:
Eγ(i)∼N(0,1)||γ||2·||β|| p 2 = C||β|| p 2 =
√ 2 Γ(m2 + 1 2 )
Γ(m2 ) ||β||p2 (8)
where Γ is the Gamma special function and m is the dimension of the language embedding γ. We provide a proof for this equality in the supplementary material (Appendix A).
Discussion and validity of our claims — the difference in sample complexity is determined by the factor C in equation (8), which monotonically grows with the size of the embedding space m, which is typically in the hundreds. For the order of m=512 to m=768 used for state-of-the-art LXMERT models [30], complexity grows by a factor of around ∼20. We would like to point out that this analysis very probably under-estimates the difference in complexity, as the difference highly depends on the complexity of the reasoning estimator π, which we have simplified as a linear function in equation (5). Taking into account just the necessary soft-max alone would probably better appreciate the difference in complexity between the two methods, which we leave for future work. Our analysis is also based on several assumptions, among which is the simplified model (an over-parametrized MLP instead of an attention based network), as well as assumptions of Theorem 4.2 from [34] and [26], on which our analysis is based. Lastly, we would like to comment on the fact that we compare two different bounds: (i) the one on sample complexity for learning the full multi-modal reasoning given in Theorem 4.2, and (ii) the one for learning a single reasoning mode given by Theorem 4.1. While comparing bounds does not provide definitive answers on the order of models, both bounds have been derived by the same algebraic manipulations and we claim that they are comparable.

heading: 5 Experimental results

text:
Setup + architecture: — we perform our experiments with a compact version of the VisionLanguage (VL)-Tansformer used in [30] (cf. Fig. 2), with a hidden embedding size of d=128 and h=4 heads per layer (only 26M trainable parameters). Dataset: our models are trained on the balanced GQA [15] training set (∼1M question-answer pairs). However, LXMERT pretraining is done on the unbalanced training set (∼15M question-answer pairs). The latter contains more questions and programs, but the same number of images (∼100K images). Evaluation: is performed on GQA [15]
and GQA-OOD [18] test sets. GQA is a dataset with question-answer pairs automatically generated from real images, and is particularly well suited for evaluating a large variety of reasoning skills. GQA-OOD is a benchmark dedicated to the out-of-domain VQA evaluation, and gives information on the generalization capabilities of the model. Hyper-parameters are selected either on the testdev (for GQA) or validation (for GQA-OOD) sets. When specified (with ±) we provide the average accuracy and standard deviation computed on three runs with different random seeds. Visual input: following [2], we use bottom-up visual features extracted using a pre-trained object detector (we keep its parameters frozen during the training). If not specified, we use faster-RCNN [25] with 36 objects per-images. In addition to that, we experiment with designed objects, and also with the VinVL [38] features which (unlike faster-RCNN ones) are conceived specifically for vision-language tasks.
Program supervision improves visual reasoning — Tab. 1 reports the effectiveness of program prediction when combined with oracle and BERT-like pretraining on the GQA dataset and corroborates the results found in the theoretical analysis. In addition, when using both program supervision and LXMERT [30] but without oracle transfer, we achieve an accuracy of 58.8 on the testdev set of GQA. This is lower than oracle transfer’s accuracy, demonstrating the complementary of the two methods. We note that the majority of the gain is achieved on the more challenging open questions. In addition, results on GQA-OOD (acc-tail and acc-head) suggest that the gains are obtained in, both, out- and in-distribution settings. However, as already observed in [21], LXMERT pre-training tends to decrease the acc-tail gains brought by oracle transfer plus program supervision. We evaluate the program prediction performance by measuring the area under the ROC curve (AUC) on the visual argument prediction with an IoU treshold of 23=0.66. Models (c) and (e) achieve, respectively, 97.1 and 96.4 AUC scores, demonstrating the effectiveness of the program decoder.
Program supervision decreases sample complexity — as shown in Fig. 3. We vary the amount of training data from 5% to 100% and observe that adding program supervision allows to reach an accuracy similar to the baseline while using less data (no oracle transfer, no LXMERT pretraining).
Visual arguments are the key — We study the impact of different types of program supervision in Tab. 2. We can see the importance of supervising arguments, in (4) and (5). The supervision of visual arguments (5) contributes most to the gain in performance, again corroborating that visual uncertainty is the main bottleneck for reasoning.
Program supervision enhances cross-modal interactions — In Tab. 3, we study how the inputs of the program prediction module influence the VQA accuracy. In particular, we test two settings: (7) uni-modal, where the programs are predicted from the vision and language em-
beddings right after the uni-modal layers (language and vision only in Fig. 2); and (8) cross-modal, where the programs are predicted after the cross-modal layers (as shown in Fig. 2). We observe that, contrary to the latter, the former does not improve the baseline ((7) vs (6) in Tab. 3). This highlights the fact that the program supervision mainly impacts the operations in the cross modal layers, where the most complex reasoning operations are performed.
Program supervision allows to take advantage of the improved visual inputs — We analyse the impact of using our method with a better input image representation. Increasing the number of objects from 36 to 100 per image ((g) and (h) in Tab. 4), allows to further increase the gains brought by our method. On the contrary, the score of the baseline model remains unchanged, showing that the program supervision allows to take advantage of a bigger number of object proposals. Similarly, replacing the faster-RCNN features by the more recent and more accurate VinVL ones ((i)-(l) in Tab. 4) results in better performances.
Comparison with SOTA — We report in Tab. 5 the results obtained by our approach compared to the current SOTA on the GQA and GQA-OOD datasets. In order to ensure a fair comparison, we also provide, for each method, information regarding the amount of data (images and sentences) used during training. As shown in Tab. 5, our approach compares favourably with SOTA since it obtains the second best accuracy (with a 0.2 points gap) on the GQA test-std set among the approaches which not use extra training data. The results also remain competitive when comparing to the OSCAR+VinVL [38], while being trained with 50 times less images. On GQA-OOD, our approach obtains the second best acc-tail score (and the best acc-head one) with a much less complex architecture than current SOTA (26M vs 212M trainable parameters compared to LXMERT [30]).

heading: 6 Conclusion

text:
We have demonstrated that it is possible to improve the reasoning abilities of VQA models when providing additional supervision of program annotations. In particular, our method is designed to improve the transfer of reasoning patterns from models learned on perfect visual input to models trained on noisy visual representations. Our experiments are supported by a theoretical analysis, demonstrating that program supervision can decrease sample complexity under reasonable hypothesis. The proposed method relies on the availability of reasoning program annotations, which are costly to annotate, especially when dealing with human generated questions. Recent work has already managed to gather such kind of annotations [9]. The next step will be to extend the method to configurations where the program annotation is rare or incomplete. Another promising research path could be explicitly conditioning the VQA system’s answer by the program prediction module, following the recent work of Chen et al. [6], instead of using it as catalyst for knowledge transfer.
Acknowledgment — C. Wolf acknowledges support from ANR through grant “Remember” (ANR20-CHIA-0018).

title: Supervising the Transfer of Reasoning Patterns in VQA