summaries: Summary.  The paper is about the parameterized complexity of Bayesian Network Structure Learning. In particular, it is focused to analyze and develop previous contributions on superstructure of the input. The author/s show/s that changing the parametrization yields to achieve fixed-parameter tractability.  The paper also anallyzes how the complexity of structural learning of bayesian networks depends on the input representation, with specific reference to non-zero representation, and additive representation. Finally the paper shows how to extend the main contirbutions presented to the problem of Polytree Learning.

summaries: This paper contains a number of significant FPT results for BNSL, as well as providing a concise summary of existing FPT results. A key parameter considered is "local feedback edge number" which provides FPT. Results for when local scores are additively decomposable are given. The paper has many results and so many proofs are relegated to the supplementary material.

summaries: This is a paper about the parametrized complexity of BN structural learning. To achieve that the authors consider the learning task as a decision problem and distinguish tasks wrt the way the local scores are represented (non-zero, additive, additive with bound on the number of parents). Separately for each class, the authors discuss tractability wrt various parameters (and not only the treewidth) used to describe the superstructure. This in particular suggests a dynamic programming approach for the additive case that is fixed-parameter tractable wrt the treewidth. Those results are also specialized to the case of learning polytree-shaped models.

summaries: This paper investigates the fixed-parameter tractability of the Bayesian Network Structure Learning (BNSL) problem, according to new parameters related to the network superstructure. Namely, since the BNSL problem is known to be W[1]-hard for various vertex-related parameters, the authors concentrate on edge-related parameters, by showing that fixed-parameter tractability can indeed be achieved in some cases. In doing so, the authors consider two parameters, the feedback edge number (fen) and its “local” version (lfen), which are less restrictive than the tree-cut width (tcw). Orthogonally, the authors examine three families of scoring (function) representations: non-zero representations, additive representations, and bounded additive representations. Finally, the authors explore the fixed-parameter tractability of polytrees.

abstractText: We investigate the parameterized complexity of Bayesian Network Structure Learning (BNSL), a classical problem that has received significant attention in empirical but also purely theoretical studies. We follow up on previous works that have analyzed the complexity of BNSL w.r.t. the so-called superstructure of the input. While known results imply that BNSL is unlikely to be fixed-parameter tractable even when parameterized by the size of a vertex cover in the superstructure, here we show that a different kind of parameterization—notably by the size of a feedback edge set—yields fixed-parameter tractability. We proceed by showing that this result can be strengthened to a localized version of the feedback edge set, and provide corresponding lower bounds that complement previous results to provide a complexity classification of BNSL w.r.t. virtually all well-studied graph parameters. We then analyze how the complexity of BNSL depends on the representation of the input. In particular, while the bulk of past theoretical work on the topic assumed the use of the so-called non-zero representation, here we prove that if an additive representation can be used instead then BNSL becomes fixed-parameter tractable even under significantly milder restrictions to the superstructure, notably when parameterized by the treewidth alone. Last but not least, we show how our results can be extended to the closely related problem of Polytree Learning.

authors:
Matthias Bentert
Roman Haag
Christian Hofer
Tomohiro Koana
André Nichterlein

title: Parameterized complexity of min-power asymmetric connectivity

venue: Theory of Computing Systems,

authors:
Nadja Betzler
Robert Bredereck
Rolf Niedermeier
Johannes Uhlmann

title: On boundeddegree vertex deletion parameterized by treewidth

venue: Discret. Appl. Math.,

title: A linear-time algorithm for finding tree-decompositions of small treewidth

venue: SIAM J. Comput.,

title: Learning Bayesian networks is NP-complete. In Learning from data (Fort Lauderdale, FL, 1995), volume 112 of Lecture Notes in Statist., pages 121–130

title: Learning polytrees

venue: UAI ’99: Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence,

authors:
Camil Demetrescu
Irene Finocchi

title: Combinatorial algorithms for feedback problems in directed graphs

venue: Inf. Process. Lett.,

title: Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics

authors:
Rodney G. Downey
Michael R. Fellows

title: Fundamentals of Parameterized Complexity

venue: Texts in Computer Science. Springer,

authors:
Eduard Eiben
Robert Ganian
Iyad Kanj
Stefan Szeider

title: The parameterized complexity of cascading portfolio scheduling

venue: Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems

authors:
Gal Elidan
Stephen Gould

title: Learning bounded treewidth bayesian networks

venue: Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems,

authors:
Jirí Fiala
Petr A. Golovach
Jan Kratochvíl

title: Parameterized complexity of coloring problems: Treewidth versus vertex cover

venue: Theor. Comput. Sci.,

authors:
Robert Ganian
Iyad A. Kanj
Sebastian Ordyniak
Stefan Szeider

title: Parameterized algorithms for the matrix completion problem

venue: Proceedings of the 35th International Conference on Machine Learning,

authors:
Robert Ganian
Eun Jung Kim
Stefan Szeider

title: Algorithmic applications of tree-cut width

venue: Mathematical Foundations of Computer Science 2015 - 40th International Symposium,

authors:
Robert Ganian
Fabian Klute
Sebastian Ordyniak

title: On structural parameterizations of the bounded-degree vertex deletion

venue: problem. Algorithmica,

authors:
Robert Ganian
Sebastian Ordyniak

title: The complexity landscape of decompositional parameters for ILP

venue: Artif. Intell.,

title: The power of cut-based parameters for computing

venue: edge-disjoint paths. Algorithmica,

authors:
Robert Ganian
Sebastian Ordyniak
Ramanujan Sridharan

title: On structural parameterizations of the edge disjoint paths problem

authors:
Serge Gaspers
Mikko Koivisto
Mathieu Liedloff
Sebastian Ordyniak
Stefan Szeider

title: On finding optimal polytrees

title: Some np-complete problems on graphs

venue: In Proceedings of the 11th Conference on Information Sciences and Systems,

authors:
Niels Grüttemeier
Christian Komusiewicz
Nils Morawietz

title: On the parameterized complexity of polytree learning

venue: In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI-21),

authors:
Niels Grüttemeier
Christian Komusiewicz

title: Learning bayesian networks under sparsity constraints: A parameterized complexity analysis

venue: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence,

authors:
Haipeng Guo
William Hsu

title: A survey of algorithms for real-time bayesian network inference

venue: In Working Notes of the Joint AAAI/UAI/KDD Workshop on Real-Time Decision Support and Diagnosis Systems,

title: Treewidth: Computations and Approximations

authors:
Yasuaki Kobayashi
Hisao Tamaki

title: Treedepth parameterized by vertex cover number

venue: 11th International Symposium on Parameterized and Exact Computation, IPEC 2016,

authors:
Janne H. Korhonen
Pekka Parviainen

title: Exact learning of bounded tree-width bayesian networks

venue: In Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2013, Scottsdale, AZ,

title: Tractable bayesian network structure learning with bounded vertex cover number

venue: Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December

authors:
Dániel Marx
Paul Wollan

title: Immersions in highly edge connected graphs

venue: SIAM J. Discret. Math.,

title: Finding a path is harder than finding a tree

venue: J. Artif. Intell. Res.,

authors:
Jaroslav Nesetril
Patrice Ossona de Mendez

title: Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and Combinatorics

title: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications

authors:
Sebastian Ordyniak
Stefan Szeider

title: Parameterized complexity results for exact bayesian network structure learning

authors:
Sascha Ott
Seiya Imoto
Satoru Miyano

title: Finding optimal models for small gene networks

venue: Proceedings of the Pacific Symposium, Hawaii,

title: Probabilistic reasoning in intelligent systems - networks of plausible inference. Morgan Kaufmann series in representation and reasoning

authors:
Eric Perrier
Seiya Imoto
Satoru Miyano

title: Finding optimal bayesian network given a super-structure

venue: J. Mach. Learn. Res.,

authors:
Javad Safaei
Ján Manuch
Ladislav Stacho

title: Learning polytrees with constant number of roots from data

venue: AI 2013: Advances in Artificial Intelligence - 26th Australasian Joint Conference,

authors:
Mauro Scanagatta
Giorgio Corani
Cassio P. de Campos
Marco Zaffalon

title: Learning treewidth-bounded bayesian networks with thousands of variables

venue: Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems

authors:
Mauro Scanagatta
Cassio P. de Campos
Giorgio Corani
Marco Zaffalon

title: Learning bayesian networks with thousands of variables

authors:
Kirill Simonov
Fedor V. Fomin
Petr A. Golovach
Fahad Panolan

title: Refined complexity of PCA with outliers

venue: Proceedings of the 36th International Conference on Machine Learning,

authors:
Ioannis Tsamardinos
Laura E. Brown
Constantin F. Aliferis

title: The max-min hill-climbing bayesian network structure learning algorithm

venue: Mach. Learn.,

authors:
Johannes Uhlmann
Mathias Weller

title: Two-layer planarization parameterized by feedback edge set

authors:
René van Bevern
Till Fluschnik
Oxana Yu. Tsidulko

title: Parameterized algorithms and data reduction for the short secluded

venue: s-t-path problem. Networks,

title: The structure of graphs not admitting a fixed immersion

venue: J. Comb. Theory, Ser. B,

heading: 1 Introduction

text:
Bayesian networks are among the most prominent graphical models for probability distributions. The key feature of Bayesian networks is that they represent conditional dependencies between random variables via a directed acyclic graph; the vertices of this graph are the variables, and an arc ab means that the distribution of variable b depends on the value of a. One beneficial property of Bayesian networks is that they can be used to infer the distribution of random variables in the network based on the values of the remaining variables.
The problem of constructing a Bayesian network with an optimal network structure is NP-hard, and remains NP-hard even on highly restricted instances [4]. This initial negative result has prompted an extensive investigation of the problem’s complexity, with the aim of identifying new tractable fragments as well as the boundaries of its intractability [26, 32, 27, 22, 11, 6, 19]. The problem— which we simply call BAYESIAN NETWORK STRUCTURE LEARNING (BNSL)—can be stated as follows: given a set of V of variables (represented as vertices), a family F of score functions which assign each variable v ∈ V a score based on its parents, and a target value `, determine if there exists a directed acyclic graph over V that achieves a total score of at least `1.
1Formal definitions are provided in Section 2. We consider the decision version of BNSL for complexitytheoretic reasons only; all of the provided algorithms are constructive and can output a network as a witness.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
To obtain a more refined understanding of the complexity of BNSL, past works have analyzed the problem not only in terms of classical complexity but also from the perspective of parameterized complexity [9, 5]. In parameterized complexity analysis, the tractability of problems is measured with respect to the input size n and additionally with respect to a specified numerical parameter k. In particular, a problem that is NP-hard in the classical sense may—depending on the parameterization used—be fixed-parameter tractable (FPT), which is the parameterized analogue of polynomial-time tractability and means that a solution can be found in time f(k) ·nO(1) for some computable function f , or W[1]-hard, which rules out fixed-parameter tractability under standard complexity assumptions. The use of parameterized complexity as a refinement of classical complexity is becoming increasingly common and has been employed not only for BNSL [26, 32, 27], but also for numerous other problems arising in the context of neural networks and artificial intelligence [13, 41, 10, 16].
Unfortunately, past complexity-theoretic works have shown that BNSL is a surprisingly difficult problem. In particular, not only is the problem NP-hard, but it remains NP-hard even when asking for the existence of extremely simple networks such as directed paths [29] and is W[1]-hard when parameterized by the vertex cover number of the network [27]. In an effort to circumvent these lower bounds, several works have proposed to instead consider restrictions to the so-called superstructure, which is a graph that, informally speaking, captures all potential dependencies between variables [42, 35]. Ordyniak and Szeider [32] studied the complexity of BNSL when parameterized by the structural properties of the superstructure, and showed that parameterizing by the treewidth [36] of the superstructure is sufficient to achieve a weaker notion of tractability called XP-tractability. However, they also proved that BNSL remains W[1]-hard when parameterized by the treewidth of the superstructure [32, Theorem 3].
Contribution. Up to now, no “implicit” restrictions of the superstructure were known to lead to a fixed-parameter algorithm for BNSL alone. More precisely, the only known fixed-parameter algorithms for the problem require that we place explicit restrictions on either the sought-after network or the parent sets on the input: BNSL is known to be fixed-parameter tractable when parameterized by the number of arcs in the target network [22], the treewidth of an “extended superstructure graph” which also bounds the maximum number of parents a variable can have [26], or the number of parent set candidates plus the treewidth of the superstructure [32]. Moreover, a closer analysis of the reduction given by Ordyniak and Szeider [32, Theorem 3] reveals that BNSL is also W[1]-hard when parameterized by the treedepth, pathwidth, and even the vertex cover number of the superstructure alone. The vertex cover number is equal to the vertex deletion distance to an edgeless graph, and hence their result essentially rules out the use of the vast majority of graph parameters; among others, any structural parameter based on vertex deletion distance.
As our first conceptual contribution, we show that a different kind of graph parameters—notably, parameters that are based on edge deletion distance—give rise to fixed-parameter algorithms for BNSL in its full generality, without requiring any further explicit restrictions on the target network or parent sets. Our first result in this direction concerns the feedback edge number (fen), which is the minimum number of edges that need to be deleted to achieve acyclicity. In Theorem 3 we show not only that BNSL is fixed-parameter tractable when parameterized by the fen of the superstructure, but also provide a polynomial-time preprocessing algorithm that reduces any instance of BNSL to an equivalent one whose number of variables is linear in the fen (i.e., a kernelization [9, 5]).
Since fen is a highly “restrictive” parameter—its value can be large even on simple superstructures such as collections of disjoint cycles—we proceed by asking whether it is possible to lift fixedparameter tractability to a more relaxed way of measuring distance to acyclicity. For our second result, we introduce the local feedback edge number (lfen), which intuitively measures the maximum edge deletion distance to acyclicity for cycles intersecting any particular vertex in the superstructure. In Theorem 6, we show that BNSL is also fixed-parameter tractable when prameterized by lfen; we also show that this comes at the cost of BNSL not admitting any polynomial-time preprocessing procedure akin to Theorem 3 when parameterized by lfen. We conclude our investigation in the direction of parameters based on edge deletion distance by showing that BNSL parameterized by treecut width [28, 45, 14], a recently discovered edge-cut based counterpart to treewidth, remains W[1]-hard (Theorem 9). An overview of these complexity-theoretic results is provided in Figure 1.
As our second conceptual contribution, we show that BNSL becomes significantly easier when one can use an additive representation of the scores rather than the non-zero representation that was considered in the vast majority of complexity-theoretic works on BNSL to date [26, 32, 27, 22, 11, 19].
The additive representation is inspired by known heuristics for BNSL [40, 39] and utilizes a succinct encoding of the score function which assumes that the scores for parent sets can be decomposed into a sum of the scores of individual variables in the parent set; a discussion and formal definitions are provided in Section 2. In Theorem 11, we show that if the additive representation can be used, BNSL becomes fixed-parameter tractable when parameterized by the treewidth of the superstructure (and hence under every parameterization depicted in Figure 1). Motivated by the empirical usage of the additive representation, we also consider the case where we additionally impose a bound q on the number of parents a vertex can accept; we show that the result of Theorem 11 also covers this case if q is taken as an additional parameter, and otherwise rule out fixed-parameter tractability using an intricate reduction (Theorem 12).
For our third and final conceptual contribution, we show how our results can be adapted for the emergent problem of POLYTREE LEARNING (PL), a variant of BNSL where we require that the network forms a polytree. The crucial advantage of such networks is that they allow for a more efficient solution of the inference task [34, 23], and the complexity of PL has been studied in several works [21, 19, 38]. We show that all our results for BNSL can be adapted to PL, albeit in some cases it is necessary to perform non-trivial modifications. Furthermore, we observe that unlike BNSL, PL becomes polynomial-time tractable when the additive representation is used (Observation 16); this matches the “naive” expectation that learning simple networks would be easier than BNSL in its full generality. As our concluding result, we show that this expectation is in fact not always validated: while PL was recently shown to be W[1]-hard when parameterized by the number of so-called dependent vertices [21], in Theorem 17 we prove that BNSL is fixed-parameter tractable under that same parameterization.

heading: 2 Preliminaries

text:
For an integer i, we let [i] = {1, 2, . . . , i} and [i]0 = [i] ∪ {0}. We denote by N the set of natural numbers, by N0 the set N ∪ {0}. We refer to the handbook by Diestel [8] for standard terminology on directed as well as undirected graphs. The skeleton (sometimes called the underlying undirected graph) of a directed graph (a digraph) D = (V,A) is the undirected graph G′ = (V,E) such that vw ∈ E if vw ∈ A or wv ∈ A. A digraph is a polytree if its skeleton is a forest. When comparing two numerical parameters α, β of graphs, we say that α is more restrictive than β if there exists a function f such that β(G) ≤ f(α(G)) holds for every graph G. We refer to the standard sources for the fundamentals of parameterized complexity, including the definitions of fixed-parameter tractability, parameterized reductions, W[1]-hardness and treewidth [5, 9, 31].
Problem Definitions. Let V be a set of vertices and F = { fv : 2V \{v} → N0 | v ∈ V } be a family of local score functions. For a digraph D = (V,A), we define its score as follows: score(D) = ∑ v∈V fv(PD(v)), where PD(v) is the set of vertices of D with an outgoing arc to v (i.e., the parent set of v in D). We can now formalize our problem of interest [32, 22].
BAYESIAN NETWORK STRUCTURE LEARNING (BNSL)
Input: A set V of vertices, a family F of local score functions, and an integer `. Question: Does there exist an acyclic digraph D = (V,A) such that score(D) ≥ `?
POLYTREE LEARNING (PL) is defined analogously, with the only difference that there D is additionally required to be a polytree [21]. We call D a solution for the given instance.
Since both V and F are assumed to be given on the input of our problems, an issue that arises here is that an explicit representation of F would be exponentially larger than |V |. A common way to potentially circumvent this is to use a non-zero representation of the family F , i.e., where we only store values for fv(P ) that are different than zero. This model has been used in the vast majority of works studying the complexity of BNSL and PL [26, 32, 27, 22, 19, 21]. Let Γf (v) be the collection of candidate parents of v which yield a non-zero score; formally, Γf (v) = {Z | fv(Z) 6= 0 }, and the input size |I| of an instance I = (V,F , `) is simply defined as |V |+ `+ ∑ v∈V,P∈Γf (v) |P | 2.
A natural way to think about and exploit the structure of inter-variable dependencies of an instance I is to consider its superstructure graph GI = (V,E), where ab ∈ E if a occurs in at least one candidate set in Γf (b) (or vice-versa). An example is provided in Figure 2.
Naturally, families of local score functions may be exponentially larger than |V | even when stored using the non-zero representation. In this paper, we also consider a second representation of F which is guaranteed to be polynomial in |V |: in the additive representation, we require that for every vertex v ∈ V and set Q = {q1, . . . , qm} ⊆ V \ {v}, fv(Q) = fv({q1}) + · · · + fv({qm}). Hence, each cost function fv can be fully characterized by storing at most |V |-many entries of the form fv(x) := fv({x}) for each x ∈ V \ {v}. To avoid overfitting, one may optionally impose an additional constraint: an upper bound q on the size of any parent set in the solution.
While not every family of local score functions admits an additive representation, the additive model is similar in spirit to the models used by some practical algorithms for BNSL. For instance, the algorithms of Scanagatta, de Campos, Corani and Zaffalon [40, 39], which can process BNSL instances with up to thousands of variables, approximate the real score functions by adding up the known score functions for two parts of the parent set and applying a small, logarithmic correction. Both of these algorithms also use the aforementioned bound q for the parent set size. In spite of this connection to practice and the representation’s streamlined nature, we are not aware of any prior works that considered the additive representation in complexity-theoretic studies of BNSL and PL. The superstructure graph for the additive representation can be defined in an analogous way as for the non-zero representation: an edge uv simply captures a “suspected dependencey’ between variables u and v (i.e., one receives a positive score for depending on the other).
To distinguish between these models, we use BNSL 6=0, BNSL+, and BNSL+≤to denote BAYESIAN NETWORK STRUCTURE LEARNING with the non-zero representation, the additive representation, and the additive representation and the parent set size bound q, respectively (and analogously for PL).
In our algorithmic results, we will often use G = (V,E) to denote the superstructure graph of the input instance I. Without any loss of generality, we will also assume that G is connected. Graph Parameters Based on Edge Cuts. Traditionally, the bulk of graph-theoretic research on structural parameters has focused on parameters that guarantee the existence of small vertex separators in the graph; these are inherently tied to the theory of graph minors [37, 36] and the vertex deletion
2We remark that the non-zero representation could be strengthened even further by omitting each parent set Z of v which contains a proper subset Z′ such that fv(Z) ≤ fv(Z′). This preprocessing step, however, does not have an impact on any of the results presented in this paper.
distance. This approach gives rise not only to the classical notion of treewidth, but also to its well-known restrictions and refinements such as pathwidth [37], treedepth [30] and the vertex cover number [12, 25]. The vertex cover number is the most restrictive parameter in this hierarchy.
However, there are numerous problems of interest that remain intractable even when parameterized by the vertex cover number. A recent approach developed for attacking such problems has been to consider parameters that guarantee the existence of small edge cuts in the graph; these are typically based on the edge deletion distance or, more broadly, tied to the theory of graph immersions [45, 28]. The parameter of choice for the latter is treecut width (tcw) [45, 28, 14, 15], a counterpart to treewidth which has been successfully used to tackle some problems that remained intractable when parameterized by the vertex cover number [17].
On the other hand, the by far most prominent parameter based on edge deletion distance is the feedback edge number of a connected graph G = (V,E), which is the minimum cardinality of a set F ⊆ E of edges (called the feedback edge set) such that G− F is acyclic. The feedback edge number can be computed in quadratic time and has primarily been used to obtain fixed-parameter algorithms and polynomial kernels for problems where other parameterizations failed [17, 2, 1, 44].
Up to now, these were the only two edge-cut based graph parameters that have been considered in the broader context of algorithm design. This situation could be seen as rather unstisfactory in view of the large gap between the complexity of the richer class of graphs of bounded treecut width, and the significantly simpler class of graphs of bounded feedback edge number—for instance, the latter class is not even closed under disjoint union. Here, we propose a new parameter that lies “between” the feedback edge number and treecut width, and which can be seen as a localized relaxation of the feedback edge number: instead of measuring the total size of the feedback edge set, it only measures how many feedback edges can “locally interfere with” any particular part of the graph.
Formally, for a connected graph G = (V,E) and a spanning tree T of G, let the local feedback edge set at v ∈ V be ETloc(v) = {uw ∈ E \ E(T ) | the unique path between u and w in T contains v}. The local feedback edge number of (G,T ) (denoted lfen(G,T )) is then equal to maxv∈V |ETloc(v)|, and the local feedback edge number of G is simply the smallest local feedback edge number among all possible spanning trees of G, i.e., lfen(G) = minT is a spanning tree ofG lfen(G,T ).
It is not difficult to show that the local feedback edge number is “sandwiched” between the feedback edge number and treecut width. We also show that computing it is FPT. Proposition 1. For every graph G, tcw(G) ≤ lfen(G) + 1 and lfen(G) ≤ fen(G). Theorem 2. The problem of determining whether lfen(G) ≤ k for an input graph G parameterized by an integer k is fixed-parameter tractable. Moreover, if the answer is positive, we may also output a spanning tree T such that lfen(G,T ) ≤ k as a witness.
3 Solving BNSL 6=0 with Parameters Based on Edge Cuts.
In this section we provide tractability and lower-bound results for BNSL 6=0 from the viewpoint of superstructure parameters based on edge cuts. Together with the previous lower bound that rules out fixed-parameter algorithms based on all vertex-separator parameters [32, Theorem 3], the results presented here provide a comprehensive picture of the complexity of BNSL 6=0 with respect to superstructure parameterizations.
Using the Feedback Edge Number for BNSL 6=0. We say that two instances I, I ′ of BNSL are equivalent if (1) they are either both Yes-instances or both No-instances, and furthermore (2) a solution to one instance can be transformed into a solution to the other instance in polynomial time. Our aim here is to prove the following theorem: Theorem 3. There is an algorithm which takes as input an instance I of BNSL 6=0 whose superstructure has fen k, runs in time O(|I|2), and outputs an equivalent instance I ′ = (V ′,F ′, `′) of BNSL 6=0 such that |V ′| ≤ 16k.
In parameterized complexity theory, such data reduction algorithms with performance guarantees are called kernelization algorithms [9, 5]. These may be applied as a polynomial-time preprocessing step before, e.g., more computationally expensive methods are used. The fixed-parameter tractability of BNSL 6=0 when parameterized by the fen of the superstructure follows as an immediate corollary of Theorem 3 (one may solve I by, e.g., exhaustively looping over all possible DAGs on V ′ via a
brute-force procedure). We also note that even though the number of variables of the output instance is polynomial in the parameter k, the instance I ′ need not have size polynomial in k. We begin our path towards a proof of Theorem 3 by computing a feedback edge set EF of G of size k in timeO(|I|2) by, e.g., Prim’s algorithm. Let T be the spanning tree ofG, EF = E(G)\E(T ). The algorithm will proceed by the recursive application of certain reduction rules, which are polynomialtime operations that alter (“simplify”) the input instance in a certain way. A reduction rule is safe if it outputs an instance which is equivalent to the input instance. We start by describing a rule that will be used to prune T until all leaves are incident to at least one edge in EF .
Reduction Rule 1. Let v ∈ V be a vertex and let Q be the set of neighbors of v with degree 1 in G. We construct a new instance I ′ = (V ′,F ′, `) by setting: 1. V ′ := V \ Q; 2. Γf ′(v) := {∅} ∪ { (P \ Q) | P ∈ Γf (v) }; 3. for all w ∈ V ′ \ {v}, f ′w = fw; 4. for every P ′ ∈ Γf ′(v):
f ′v(P ′) := max
P :P\Q=P ′
( fv(P ) + ∑ vin∈P∩Q fvin(∅) + ∑ vout∈Q\P max(fvout(∅), fvout(v)) ) .
Lemma 4. Reduction Rule 1 is safe.
Observe that the superstructure graph G′ obtained after applying one step of Reduction Rule 1 is simply G−Q; after its exhaustive application we obtain an instance I such that all the leaves of the tree T are endpoints of EF . Our next step is to get rid of long paths in G whose internal vertices have degree 2. We note that this step is more complicated than in typical kernelization results using feedback edge set as the parameter, since a directed path Q in G can serve multiple “roles” in a hypothetical solution D and our reduction gadget needs to account for all of these. Intuitively, Q may or may not appear as a directed path in D (which impacts what other arcs can be used in D due to acyclicity), and in addition the total score achieved by D on the internal vertices of Q needs to be preserved while taking into account whether the endpoints of Q have a neighbor in the path or not. Because of this (and unlike in many other kernelization results of this kind [17, 43, 15]), we will not be replacing Q merely by a shorter path, but by a more involved gadget. An illustration is provided in Figure 3.
Reduction Rule 2. Let a, b1, . . . , bm, c be a path in G such that for each i ∈ [m], bi has degree precisely 2, and let P = {b1, . . . , bm}. We construct a new instance I ′ = (V ′,F ′, `) as follows:
1. V ′ := V ∪ {b} \ {b2...bm−1};
2. Γf ′(b) = {B ∪ {b1, bm}|B ⊆ {a, c}} where f ′b(B ∪ {b1, bm}) is equal to the maximum score that can be achieved by P if B are used as parents;
3. The scores for a and c are obtained from F by simply adding b to any parent set containing either b1 or bm;
4. Γf ′(b1) contains only {a, b, bm} with score equal to the maximum score that can be achieved by P if a is used as a parent but there is no path from a to bm via P ;
5. Γf ′(bm) contains only {c, b, b1} with score equal to the maximum score that can be achieved by P if c is used as a parent but there is no path from c to b1 via P ;
6. for all w ∈ V ′ \ {a, b1, b, bm, c}, f ′w = fw.
Lemma 5. Reduction Rule 2 is safe.
Proof of Theorem 3. We begin by exhaustively applying Reduction Rule 1 on an instance whose superstructure graph has a feedback edge set of size k, which results in an instance with the same feedback edge set but whose spanning tree T has at most 2k leaves. It follows that there are at most 2k vertices with a degree greater than 2 in T .
Let us now “mark” all the vertices that either are endpoints of the edges inEF or have a degree greater then 2 in T ; the total number of marked vertices is upper-bounded by 4k. We now proceed to the exhaustive application of Reduction Rule 2, which will only be triggered for sufficiently long paths in T that connect two marked vertices but contain no marked vertices on its internal vertices; there are at most 4k such paths due to the tree structure of T . Reduction Rule 2 will replace each such path with
a set of 3 vertices, and therefore after its exhaustive application we obtain an equivalent instance with at most 4k + 4k · 3 = 16k vertices, as desired. Correctness follows from the safeness of Reduction Rules 1, 2, and the runtime bound follows by observing that the total number of applications of each rule as well as the runtime of each rule are upper-bounded by a linear function of the input size.
As an immediate corollary of Theorem 3, we can apply a standard brute-force branching procedure [33] to solve BNSL in time nO(1) + 2O(k).
Fixed-Parameter Tractability of BNSL 6=0 using the Local Feedback Edge Number. Our aim here will be to lift the fixed-parameter tractability of BNSL 6=0 established by Theorem 3 by relaxing the parameterization to lfen. In particular, we will prove:
Theorem 6. BNSL 6=0 is fixed-parameter tractable when parameterized by the local feedback edge number of the superstructure.
Since fen is a more restrictive parameter than lfen, this results in a strictly larger class of instances being identified as tractable. However, the means we will use to establish Theorem 6 will be fundamentally different: we will not use a polynomial-time data reduction algorithm as the one provided in Theorem 3, but instead apply a dynamic programming approach. Since the kernels constructed by Theorem 3 contain only polynomially-many variables w.r.t. fen, that result is incomparable to Theorem 6. In fact one can use standard techniques to prove that, under well-established complexity assumptions, a data reduction result such as the one provided in Theorem 3 cannot exist for lfen.
Theorem 7. Unless NP ⊆ co-NP/poly, there is no polynomial-time algorithm which takes as input an instance I of BNSL 6=0 whose superstructure has lfen k and outputs an equivalent instance I ′ = (V ′,F ′, `′) of BNSL 6=0 such that |V ′| ∈ kO(1). In particular, BNSL 6=0 does not admit a polynomial kernel when parameterized by lfen.
Towards proving Theorem 6, assume that we are given an instance I = (V,F , `) of BNSL 6=0 with connected superstructure graph G = (V,E). Let T be a fixed rooted spanning tree of G such that lfen(G,T ) = lfen(G) = k, denote the root by r. For v ∈ V (T ), let Tv be the subtree of T rooted at v, let Vv = V (Tv), and let V̄v = NG(Vv) ∪ Vv. We define the boundary δ(v) of v to be the set of endpoints of all edges in G with precisely one endpoint in Vv (observe that the boundary can never have a size of 1). Notice that |δ(v)| ≤ 2k + 2. We can now proceed to a definition of the records that will be used in our dynamic program. Intuitively, these records will be computed in a leaf-to-root fashion and will store at each vertex v information about the best score that can be achieved by a partial solution that intersects the subtree rooted at v.
Let R be a binary relation on δ(v) and s an integer. For s ∈ Z, we say that (R : s) is a record for a vertex v if and only if there exists a DAG D on V̄v such that (1) w ∈ Vv for each arc uw ∈ A(D), (2) ab ∈ R if there exists an a-b path in D, and (3) s is the total score achieved by D on vertices in Vv.
The records (R, s) where s is maximal for fixed R are called valid. Denote the set of all valid records for v byR(v), and note that |R(v)| ≤ 2O(k2). Observe that if vi is a closed child of v, thenR(vi) consists of precisely two valid records: one for R = ∅ and one for R = {vvi}. Moreover, the root r of T has only a single valid record (∅ : sI), where sI is the maximum score that can be achieved by a solution in I. The following lemma lies at the heart of our result and shows how we can compute our records in a leaf-to-root fashion along T . Lemma 8. Let v ∈ V (G) have m children in T where m > 0, and assume we have computedR(vi) for each child vi of v. ThenR(v) can be computed in time at most m · |Γf (v)| · 2O(k 3).
To prove Theorem 6, we start by invoking Theorem 2 to obtain a spanning tree T and then compute the recordsR(v) for each leaf of T via exhaustive branching. We then apply Lemma 8 to propagate our record sets towards the root r of T ; once we obtainR(r), we can output a solution in constant time. The runtime of the dynamic programming procedure used in the proof of Theorem 6 is upper-bounded by |I|3 · 2O(k3). For our final result for this section, recall that lfen lies between fen and treecut width in the parameter hierarchy (see Proposition 1). Since BNSL 6=0 is FPT when parameterized by lfen, the next step would be to ask whether this tractability result can be lifted to treecut width. Below, we answer this question negatively via a reduction from the W[1]-hard MULTICOLORED CLIQUE problem [9, 5]. Theorem 9. BNSL 6=0is W[1]-hard when parameterized by the treecut width of the superstructure.

heading: 4 Additive Scores and Treewidth

text:
While the previous section focused on the complexity of BNSL when the non-zero representation was used (i.e., BNSL 6=0), here we turn our attention to the complexity of the problem with respect to the additive representation. Recall from Subsection 2 that there are two variants of interest for this representation: BNSL+ and BNSL+≤. We begin by showing that, unsurprisingly, both of these are NP-hard. We do so by reducing from the classical MINIMUM FEEDBACK ARC SET problem [20, 7]. Theorem 10. BNSL+ is NP-hard. Moreover, BNSL+≤ is NP-hard for every q ≥ 3.
While the use of the additive representation did not affect the classical complexity of BNSL, it makes a significant difference in terms of parameterized complexity. Indeed, in contrast to BNSL 6=0: Theorem 11. BNSL+ is FPT when parameterized by the treewidth of the superstructure. Moreover, BNSL+≤ is FPT when parameterized by q plus the treewidth of the superstructure.
Proof Sketch. As noted in the preliminaries, due to space constraints we refer to the usual books for a definition of treewidth and nice tree-decompositions [9, 5]. We begin by applying Bodlaender’s algorithm [3, 24] to compute a nice tree-decomposition (T , χ) of GI of width k = tw(GI), whose vertices are called nodes. To prove the theorem, we will design a leaf-to-root dynamic programming algorithm which will compute and store a set of records at each node of T , whereas once we ascertain the records for r we will have the information required to output a correct answer. Intuitively, the records will store all information about each possible set of arcs between vertices in each bag, along with relevant connectivity information provided by arcs between all vertices that are either in the current bag t or in some descendant of t (we denote the set of these vertices χ↓t ), and information about the partial score. When solving BNSL+≤, the records will also keep track of parent set sizes.
Formally, the records will have the following structure. For a node t, let S(t) = {(loc, con, inn) | loc, con ⊆ Aχ(t), inn : χ(t)→ [q]0} be the set of snapshots of t. The record Rt of t is then a mapping from S(t) to N0 ∪ {⊥}. Observe that |S(t)| ≤ 4k 2
(q + 1)k. To introduce the semantics of our records, let Υt be the set of all directed acyclic graphs over the vertex set χ ↓ t with maximal in-degree at most q, and let Dt = (χ ↓ t , A) be a directed acyclic graph in Υt. We say that the snapshot of Dt in t is the tuple (α, β, p) where α = A ∩ Aχ(t), β = Con(χ(t), Dt) and p (which is only used for BNSL+≤) specifies numbers of parents of vertices from χ(t) in D, i.e., p(v) = |{w ∈ χ↓t |wv ∈ A}|, v ∈ χ(t). Now, for each snapshot (loc, con, inn) ∈ S(t) we set Rt(loc, con, inn) = ⊥ if there exists no DAG in Υt with (loc, con, inn) as its snapshot, and otherwise we setRt(loc, con, inn) to the highest score that can be achieved by such a DAG.
The algorithm computes these records in a leaf-to-root fashion while traversing T , which can be achieved in time at most 2O(k
2) · qO(k) · n, where n is the input size. Once we reach the root node r, we use the fact that χ(r) = ∅ by the definition of nice tree-decompositions to simply check if Rr(∅, ∅, ∅) ≥ `; the algorithm then outputs “Yes” if and only if this is the case.
This completely resolves the parameterized complexity of BNSL+ w.r.t. all parameters depicted on Figure 1. However, the same is not true for BNSL+≤: while a careful analysis of the algorithm provided in the proof of Theorem 11 reveals that BNSL+≤ is XP-tractable when parameterized by the treewidth of the superstructure alone, it is not yet clear whether it is FPT—in other words, do we need to parameterize by both q and treewidth to achieve fixed-parameter tractability? We conclude this section by answering this question affirmatively via an involved two-step reduction from a variant of the W[1]-hard MULTIDIMENSIONAL SUBSET SUM problem [18, 15].
Theorem 12. BNSL+≤ is W[1]-hard when parameterized by the treewidth of the superstructure.

heading: 5 Implications for Polytree Learning

text:
Here, we discuss how the results of Sections 3 and 4 can be adapted to POLYTREE LEARNING (PL).
Theorem 3: Data Reduction. Recall that the proof of Theorem 3 used two data reduction rules. While Reduction Rule 1 carries over to PL 6=0, Reduction Rule 2 has to be completely redesigned to preserve the (non-)existence of undirected paths between a and c. By doing so, we obtain: Theorem 13. There is an algorithm which takes as input an instance I of PL 6=0 whose superstructure has feedback edge number k, runs in time O(|I|2), and outputs an equivalent instance I ′ = (V ′,F ′, `′) of PL 6=0 such that |V ′| ≤ 24k.
Theorem 6: Fixed-parameter tractability. Analagously to BNSL 6=0 a data reduction procedure as the one provided in Theorem 13 does not exist for PL 6=0 parametrized by lfen unless NP ⊆ co-NP/poly, since the lower-bound result provided in Theorem 7 can be straightforwardly adapted to PL 6=0. But similarly as for BNSL we can provide an FPT algorithm using the same ideas as in the proof of Theorem 6. The algorithm proceeds by dynamic programming on the spanning tree T of G with lfen(G,T ) = lfen(G) = k. The records will, however, need to be modified: for each vertex v, instead of the path-connectivity relation on δ(v), we store connected components of the inner boundary δ(v) ∩ Vv and incoming arcs to Tv . This yields: Theorem 14. PL 6=0 is fixed-parameter tractable when parameterized by the local feedback edge number of the superstructure.
As for treecut width, we remark that a recent reduction for PL 6=0 [21, Theorem 4.2] immediately implies that the problem is W[1]-hard when parameterized by the treecut width.
Theorem 11: Additive Representation. We remark that, like BNSL+ and BNSL+≤, a simple reduction shows that PL+≤ is NP-hard for a fixed value of q, in this case q = 1. Moreover, the dynamic programming algorithm for BNSL+≤ parameterized by treewidth and q can be adapted to also solve PL+≤. The algorithm runs in time at most 2 O(k2) · qO(k) · |I|.
Theorem 15. PL+≤ is FPT when parameterized by q plus the treewidth of the superstructure.
The situation is, however, completely different for PL+: unlike BNSL+, this problem is in fact polynomial-time tractable. Indeed, it admits a simple reduction to the classical minimum edgeweighted spanning tree problem. Observation 16. PL+ is polynomial-time tractable.
This coincides with the intuitive expectation that learning simple, more restricted networks could be easier than learning general networks. We conclude our exposition with an example showcasing that this is not true in general when comparing PL to BNSL. Grüttemeier et al. [21] recently showed that PL 6=0 is W[1]-hard when parameterized by the number of dependent vertices, which are vertices with non-empty sets of candidate parents in the non-zero representation. For BNSL 6=0 we can show:
Theorem 17. BNSL 6=0 is fixed-parameter tractable when parameterized by the number of dependent vertices.

heading: 6 Concluding Remarks

text:
Our results provide a new set of tractability results that counterbalance the previously established algorithmic lower bounds for BAYESIAN NETWORK STRUCTURE LEARNING and POLYTREE LEARNING on “simple” superstructures. In particular, even though the problems remain W[1]-hard when parameterized by the vertex cover number of the superstructure [32, 21], we obtained fixedparameter tractability and a data reduction procedure using the feedback edge number and its localized version. Together with our lower-bound result for treecut width, this completes the complexity map for BNSL w.r.t. virtually all commonly considered graph parameters of the superstructure. Moreover, we showed that if the input is provided with an additive representation instead of the non-zero representation considered in previous theoretical works, the problems admit a dynamic programming algorithm which guarantees fixed-parameter tractability w.r.t. the treewidth of the superstructure. We remark that all of our results assume that the score functions are provided explicitly; future work could also consider the behavior of the problem when these functions are supplied by a suitably defined oracle.
This theoretical work follows up on previous complexity studies of the considered problems, and as such we do not claim any immediate practical applications of the results. That being said, it would be interesting to see if the polynomial-time data reduction procedure introduced in Theorem 3 could be adapted and streamlined to allow for a speedup of previously introduced heuristics for the problem [40, 39], at least for some sets of instances. Finally, we believe that the local feedback edge number can be used to push the boundaries of tractability for other problems of interest as well.
Acknowledgments. The authors acknowledge support by the Austrian Science Fund (FWF, projects P31336 and Y1329).
Funding Transparency Statement. Funding in direct support of this work: FWF Project P31336, FWF Project Y1329.
Declaration of Competing Interests. None of the authors have financial relationships with entities that could potentially be perceived to influence the content of the submitted work.

title: The Complexity of Bayesian Network Learning: Revisiting the Superstructure


summaries: This paper focuses on stream-based (online) active learning for training classifiers in the binary classification setting. In particular, the authors propose a strategy, the so-called ALPS*, that trains classifiers by optimizing a surrogate loss over both the labeled instances and sequentially predicted data points by the learner. Theoretical guarantees on label complexity and error of the returned model are provided, and are shown to be competitive with the existing bounds. A set of experiments are conducted on datasets using multi-layer perceptrons as classification models, where the performance of ALPS is illustrated to have good performance with small labeling cost.   *Actively Learning over Pseudo-labels for Surrogate losses

summaries: This paper studies the problem of online active learning for classification. In order to learn a classification algorithm, the paper proposes to employ surrogate loss function. The error of the proposed method is analyzed and some empirical results are presented.

summaries: The authors propose an active learning algorithm in the streaming setting for binary classification tasks. The algorithm leverages weak labels to minimize the number of label requests and trains a model to optimize a surrogate loss on a resulting set of labeled and weak-labeled points. The paper contains a number of theoretical results and supporting empirical results. Overall, its a very strong paper.

summaries: This paper presents Actively Learning over Pseudo-Labels for Surrogate Losses (ALPS), an active learning algorithm for binary classification with surrogate losses in the streaming setting. The main idea is to generate pseudo-labels for points whose labels are not requested and train on the union of data points with ground-truth labels and those with pseudo-labels. Since the pseudo-labels may not be accurate, the authors propose requestor functions that have a final say in whether a pseudo-label is used, and in effect, enable control over the noise generated by erroneous pseudo-labeling. Under an assumption involving the requestor function class, the authors prove bounds on the generalization error and label complexity of ALPS that are roughly on the same order of prior work (e.g., IWAL).

abstractText: We derive a novel active learning algorithm in the streaming setting for binary classification tasks. The algorithm leverages weak labels to minimize the number of label requests, and trains a model to optimize a surrogate loss on a resulting set of labeled and weak-labeled points. Our algorithm jointly admits two crucial properties: theoretical guarantees in the general agnostic setting and a strong empirical performance. Our theoretical analysis shows that the algorithm attains favorable generalization and label complexity bounds, while our empirical study on 18 real-world datasets demonstrate that the algorithm outperforms standard baselines, including the Margin Algorithm, or Uncertainty Sampling, a highperforming active learning algorithm favored by practitioners.

authors:
Kareem Amin
Giulia DeSalvo
Afshin Rostamizadeh

title: Understanding the effects of batching in online active learning

venue: In Proceedings of AISTATs,

authors:
Jordan Ash
Chicheng Zhang
Akshay Krishnamurthy
John Langford
Alekh Agarwal

title: Deep batch active learning by diverse, uncertain gradient lower bounds

venue: In Proceedings of ICLR,

authors:
Pranjal Awasthi
Maria Florina Balcan
Philip M Long

title: The power of localization for efficiently learning linear separators with noise

venue: In Proceedings of STOC,

authors:
Pranjal Awasthi
Maria-Florina Balcan
Nika Haghtalab
Ruth Urner

title: Efficient learning of linear separators under bounded noise

venue: In Proceedings of COLT,

authors:
Maria-Florina Balcan
Phil Long

title: Active and passive learning of linear separators under logconcave distributions

authors:
Maria-Florina Balcan
Andrei Broder
Tong Zhang

title: Margin based active learning

venue: In Proceeedings of COLT,

authors:
Peter Bartlett
Michael Jordan
Jon McAuliffe

title: Convexity, classification, and risk bounds

venue: Journal of the American Statistical Association,

authors:
Alina Beygelzimer
Sanjoy Dasgupta
John Langford

title: Importance weighted active learning

venue: In Proceedings of ICML,

title: Incorporating diversity in active learning with support vector machines

authors:
Rui Castro
Robert Nowak

title: Minimax bounds for active learning

venue: IEEE Transactions on Information Theory,

authors:
Nicolò Cesa-Bianchi
Claudio Gentile

title: Improved risk tail bounds for on-line algorithms

authors:
Chih-Chung Chang
Chih-Jen Lin

title: Libsvm : a library for support vector machines

venue: ACM Transactions on Intelligent Systems and Technology,

authors:
Galen Chuang
Giulia DeSalvo
Lazarus Karydas
Jean-francois Kagy
Afshin Rostamizadeh
A Theeraphol

title: Active learning empirical study

venue: In NeurIPS2019 LIRE Workshop,

authors:
Corinna Cortes
Spencer Greenberg
Mehryar Mohri

title: Relative deviation learning bounds and generalization with unbounded loss functions

authors:
Corinna Cortes
Giulia DeSalvo
Mehryar Mohri

title: Learning with rejection

venue: In Proceedings of ALT,

authors:
Corinna Cortes
Giulia DeSalvo
Claudio Gentile
Mehryar Mohri
Ningshan Zhang

title: Active learning with disagreement graphs

title: Regionbased active learning

venue: In Proceedings of AISTATS,

title: Adaptive region-based active learning

authors:
Aron Culotta
Andrew McCallum

title: Reducing labeling effort for structured prediction tasks

venue: In Proceedings of AAAI,

authors:
Sanjoy Dasgupta
Adam Tauman Kalai
Claire Monteleoni

title: Analysis of perceptron-based active learning

authors:
Sanjoy Dasgupta
Daniel Hsu
Claire Monteleoni

title: A general agnostic active learning algorithm

venue: In Proceedings of NeurIPS,

authors:
Ofer Dekel
Claudio Gentile
Karthik Sridharan

title: Selective sampling and active learning from single and multiple teachers

venue: Journal of Machine Learning Research,

authors:
Melanie Ducoffe
Frederic Precioso

title: Adversarial active learning for deep networks: a margin based approach

venue: In arXiv,

authors:
Yarin Gal
Riashat Islam
Zoubin. Ghahramani

title: Deep bayesian active learning with image data

authors:
Yonatan Geifman
Ran El-Yaniv

title: Deep active learning over the long tail

title: A bound on the label complexity of agnostic active learning

title: Rates of convergence in active learning

venue: The Annals of Statistics,

authors:
Steve Henneke
Liu Yang

title: Surrogate losses in passive and active learning

venue: In Electronic Journal of Statistics,

authors:
Ajay Joshi
Fatih Porikli
Nikolaos Papanikolopoulos

title: Multi-class active learning for image classification

venue: In Proceedings of CVPR,

authors:
Sham Kakade
Ambuj Tewari

title: On the generalization ability of online strongly convex programming algorithms

title: Local rademacher complexities and oracle inequalities in risk minimization

title: Rademacher complexities and bounding the excess risk in active learning

title: Learning multiple layers of features from tiny images

venue: Tech Report,

authors: Corinna Cortes. MNIST handwritten digit database.

title: URL http://yann

authors:
David Lewis
William Gale

title: A sequential algorithmfor training text classifiers

venue: In Proceedings of SIGIR,

authors:
Enno Mammen
Alexandre Tsybakov

title: Smooth discrimination analysis

authors:
Pascal Massart
Elodie Nedelec

title: Risk bounds for statistical learning

authors:
Jooyoung Moon
Jiho Kim
Younghak Shin
Sangheum Hwan

title: Confidence aware learning for deep neural networks

authors:
Stephen Mussmann
Percy Liang

title: Uncertainty sampling is preconditioned stochastic gradient descent on zero-one loss

authors:
F. Pedregosa
G. Varoquaux
A. Gramfort
V. Michel
B. Thirion
O. Grisel
M. Blondel
P. Prettenhofer
R. Weiss
V. Dubourg
J. Vanderplas
A. Passos
D. Cournapeau
M. Brucher
M. Perrot
E. Duchesnay

title: Scikit-learn: Machine learning in Python

authors:
Silvio Savarese
Ozan Sener
Zoubin. Ghahramani

title: Active learning for neural network a core set approach

authors:
Greg Schohn
David Cohn

title: Less is more: Active learning with support vector machines

venue: Proceeedings of ICML,

authors:
Christopher Schroder
Andreas

title: Niekler. A survey of active learning for text classification for deep neural networks

authors:
Simon Tong
Daphne Koller

title: Support vector machine active learning with applications to text classification

title: Optimal aggregation of classifiers in statistical learning

authors:
Tim Van Erven
Peter Grunwald
Nishant Mehta
Mark Reid
Robert Williamson

title: Fast rates in statistical and online learning

authors:
Joaquin Vanschoren
Jan N. van Rijn
Bernd Bischl
Luis Torgo

title: Openml: Networked science in machine learning

venue: SIGKDD Explorations,

authors:
Yazhou Yang
Marco Loog

title: A benchmark and comparison of active learning for logistic regression

authors:
Chicheng Zhang
Jie Shen
Pranjal Awasthi

title: Efficient active learning of sparse halfspaces with arbitrary bounded noise

title: Statistical behavior and consistency of classification methods based on convex risk minimization

venue: Annals of Statistics,

heading: 1 Introduction

text:
While unlabeled data is generated at increasing rates, supervised learning often requires large portions of this data to be annotated by human raters, which carry significant costs. Active learning seeks to significantly alleviate this problem through algorithms that attain comparable performance to passive learning (i.e., to full supervision) while using considerably fewer labels. Because of the ever increasing use of labeled data in modern machine learning approaches, this calls for the development of more and more effective active learning techniques.
In this paper, we are specifically interested in binary classification problems in the so-called streaming (or online) setting of active learning. In this setting, learning proceeds in a sequence of rounds, where in each round an unlabeled sample is received, and the learner decides on-the-fly whether or not to observe the associated binary label. Now, it is common practice, in active learning or machine learning in general, that even for binary classification problems, the loss used both for training and for evaluating statistical performance is not the zero-one loss, but some surrogate function thereof. This results in more tractable (e.g. convex) optimization problems in the training phase, but also in more calibrated metrics in the evaluation phase. For instance, we may be compelled to output estimates of class probabilities, say, the success rate of a given set of decisions, and thus deploy a maximum posterior probability estimator for such probabilities. Then, given a training set with labels y ∈ {±1} and if p̂(x) is an estimate of the conditional class probability P [y = 1 |x], a standard goal is to minimize the log-loss 1+y2 log 1 p̂(x) + 1−y 2 log 1 1−p̂(x) . In these cases, the logistic link function p̂(x) = 1 1+e−h(x)
is often adopted to model conditional class probabilities where h is some (unknown) function in a given hypothesis class. In this and many other situations that arise in practice, it is thus advisable to resort to surrogate loss functions for both training and evaluation.
The online active learning literature contains a number of proposed algorithms that admit theoretical guarantees for both generalization error and label complexity, that is, the expected number of label requests. The theoretical analyses found in these works are either tailored to the zero-one loss or to general surrogate losses, with much more emphasis historically placed on the former. The papers that
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
analyze zero-one loss introduce novel ideas tackling important theoretical questions in active learning, but the theory does not easily extend to general loss functions – see discussion in Henneke and Yang [2019]. Nevertheless, the algorithmic solutions we propose borrow several ideas from one such work, namely [Dasgupta et al., 2008]. In the agnostic setting, Dasgupta et al. [2008] developed an algorithm for the zero-one loss based on the disagreement between functions, that carefully constructs pseudo-labels, that is, weak labels generated by the algorithm itself. We call this algorithm DHM, after the name of the three authors.
For general surrogate losses, Beygelzimer et al. [2009] designed an algorithm based on constructing importance weighted predictors with theoretical guarantees in the agnostic setting. Cortes et al. [2019a,b, 2020] further developed these importance-weighted algorithms enhancing their guarantees and used them as building blocks for meta-algorithms. We refer to these algorithms as IWAL (Importance Weighted Active Learning).
On a different line of work, Henneke and Yang [2019] presents a theoretical analysis of an active learning algorithm that uses surrogate loss functions for binary classification. Among the theoreticallyoriented contributions in active learning, this work appears to be the closest reference to our paper when it comes to motivations. Yet, it is fair to say that the authors make the very strong assumption that the Bayes optimal function for the surrogate loss at hand lies in the hypothesis class used for learning, and they explicitly state that this realizability condition cannot be relaxed without resorting to a significantly different approach. Moreover, unlike our work and that of IWAL-based algorithms, Henneke and Yang [2019] are only focusing on deriving bounds on the zero-one risk. And finally, their algorithm operates in a pool-based setting of active learning, where the whole set of unlabeled points is available to the learner, which is more flexible than the streaming setting analyzed here.
In practice, the Margin Algorithm, or Uncertainty Sampling, of Lewis and Gale [1994] attains a substantial performance improvement compared to passive learning as well as other active learning algorithms, and is thus often favored by practitioners (e.g. Schohn and Cohn [2000], Tong and Koller [2001], Brinker [2003], Culotta and McCallum [2005], Joshi et al. [2009], Mussmann and Liang [2018]). Moreover, the margin algorithm is flexible in that it can be used in both the pool and streaming setting. In the pool setting, several papers have recently tailored active learning algorithms to neural networks, always comparing their algorithm’s empirical performance to that of the margin algorithm [Geifman and El-Yaniv, 2017, Gal et al., 2017, Savarese et al., 2018, Ducoffe and Precioso, 2018, Ash et al., 2020, Moon et al., 2020, Schroder and Niekler, 2020]. Overall, the margin algorithm is often found to be a competitive contender to this new collection of practical active learning algorithms. Additionally, two extensive empirical studies found that the margin algorithm outperforms many recent active learning algorithms [Yang and Loog, 2016, Chuang et al., 2019]. On the theoretical side, several authors developed active learning algorithms with theoretical guarantees for specific classes of functions (e.g., linear separators) based on sampling along the margin [Dasgupta et al., 2005, Balcan et al., 2007, Balcan and Long, 2013, Awasthi et al., 2014, 2015, Zhang, 2018, Zhang et al., 2020], but the guarantees of these margin-based algorithms only hold under strong assumptions on the realizability of the problem. Our goal is thus to derive an algorithm that admits theoretical guarantees without relying on realizability assumptions and that, at the same time, attains in practice a performance that is better than that of the margin algorithm in the streaming setting.

heading: 1.1 Contributions

text:
In this paper, we introduce a novel active learning algorithm, called ALPS (Actively Learning over Pseudo-labels for Surrogate losses), in the streaming setting for binary classification tasks that trains a model by optimizing a surrogate loss on the joint set of labeled and self-constructed pseudo-labeled points (Section 3). Crucially, we prove that ALPS admits theoretical guarantees with respect to the surrogate loss in the general agnostic setting while at the same time surpassing the training performance of the margin algorithm as well as other baselines.
More concretely, we prove theoretical guarantees for ALPS in terms of both generalization and label complexity, under assumptions on the interplay between the function class and the data distribution which are not captured by traditional low noise assumptions often formulated in active learning (Section 4). We show that ALPS is able to leverage pseudo-labels in a principled manner even though the loss function of interest is not the zero-one loss, but a surrogate loss thereof. We then complement our theoretical findings with a thorough experimental investigation on 18 real-world
datasets using a class of neural networks, Multi-layer Perceptrons. We test our algorithm against the IWAL algorithm of Beygelzimer et al. [2009] since it admits theoretical guarantees for general loss functions, and against passive learning since we want to quantify the improvement over supervised methods. Additionally, we generate as competitors a pool of margin-based uncertainty samplers by varying their label request threshold, and show that on almost all datasets our algorithm outperforms the ex-post best among such algorithms (Section 5).
This paper follows the general research agenda of reducing the gap between theory and practice, which has been widening at a faster rate in the recent active learning literature. As outlined above, we try to bridge this disconnect by deriving an algorithm that not only works well in practice, but also admits solid theoretical guarantees. In doing so, we also introduce novel algorithmic ideas, which could independently lead to new directions of research.

heading: 1.2 Main Ideas

text:
The main mechanism behind ALPS is to query the label of the current instance based on the disagreement between hypotheses and to construct pseudo-labels for the non-queried instances. The algorithm then trains a model on the joint set of labeled and pseudo-labeled data. The sample used for training will be unbiased with respect to marginal distribution on the instance space, but label noise will be introduced whenever the pseudo-label differs from the true (unrevealed) label. This noise affects both the generalization ability of the algorithm and its label complexity. Controlling this noise is not only crucial, but also quite challenging, for it relies on assessing the expected reliability of the pseudo-labels.
In order to control this noise, we introduce the novel idea of using requester functions: ALPS learns to query labels on instances with unreliable (that is, potentially noisy) pseudo-labels by using a requester function chosen to minimize an importance-weighted estimate of the noise. For the sake of our results, the requester functions are assumed to lie in some generic function class. One natural example of this class is that of margin-based functions, meaning functions that request along the margin of a given prediction model. In this case, our algorithm is related to the margin algorithm but, unlike the theoretical guarantees for the margin algorithm (e.g. Balcan et al. [2007]), we do not rely on specific distributional assumptions on the instance space. The requester functions are reminiscent of the abstention functions introduced in Cortes et al. [2016], but serve an entirely different purpose in active learning.
ALPS can be seen as an extension of the DHM algorithm [Dasgupta et al., 2008] to surrogate loss functions, which seeks to address the open question posed by Dasgupta et al. [2008] of whether there are active learning algorithms that only require solving tractable optimization problems in agnostic scenarios. At the same time, these two algorithms differ on how they treat the label noise introduced by pseudo-labeling. In DHM, the label noise can be easily bypassed by a simple property of the zero-one loss. In contrast, for general surrogate loss functions, this noise is unavoidable, and if not controlled as is done in the ALPS algorithm, the learned hypothesis can be arbitrarily far from the best-in-class.

heading: 2 Preliminaries and Notation

text:
We consider an active learning framework in the streaming setting for binary classification. Learning proceeds in a sequence of rounds. In each round n, the learner receives from the environment an instance (or feature vector) xn from an instance (or feature) space X. Based on what has been observed so far, the learner can then decide whether or not to request the true label yn associated with xn. Label yn is assumed to lie in the output space Y = {±1}. The pairs (x1, y1), (x2, y2), . . . are drawn i.i.d. from a joint distribution D over X× Y. In order to evaluate the statistical performance of the learner, we consider any bounded surrogate loss function ` : R × Y → [0, B] that upper bounds the zero-one loss, and let `B(·, ·) = `(·, ·)/B be a [0, 1]-normalized version of this loss.
Let H denote a hypothesis class of functions h : X→ R. For simplicity of exposition, we assume that H is a finite class, but our analysis can be extended to classes with finite VC dimension by standard covering arguments. The true (expected) risk of hypothesis h ∈ H is defined as err(h) = E(x,y)∼D[`(h(x), y)] and h∗ = argminh∈H err(h) denotes the best-in-class hypothesis.
Moreover, we denote by err(h, Z) = 1n ∑
(x,y)∈Z `(h(x), y) the empirical risk of h over a training set Z = {(x1, y1), (x2, y2), . . . , (xn, yn)}. Given round n ≥ 1, we denote by Tn the set of labeled data points {(xs, ys)} from rounds s ∈ [n] := {1, . . . , n} where the label was requested by the learning algorithm, and denote by Sn its complement, that is, the set of labeled data points {(xs, ys)} from rounds s ∈ [n] where the label was not requested. Unlike Tn, the set Sn is not fully known to the learner. On those rounds, the learner replaces the true unobserved label ys by pseudo-label ŷs, which is a suitable proxy to ys generated by the learner itself. We denote by Ŝn the set containing data points {(xs, ŷs)} from rounds s ∈ [n] where the label is not requested, and the true label gets replaced by the corresponding pseudo-label.
For notational convenience (and unless otherwise specified), we set ŷs = ys in rounds s where the true label is known to the learner. Then the following two short-hands are used for empirical risk up to round n using ground-truth labels and the empirical risk up to round n using pseudo-labels:
err n
(h) = err(h, Sn ∪ Tn) = 1
n n∑ s=1 `(h(xs), ys) ; êrr n (h) = err(h, Ŝn ∪ Tn) = 1 n n∑ s=1 `(h(xs), ŷs) .
In the sequel, we will also need the following definition of consistency of hypothesis h ∈ H . Definition 1. We say that h ∈ H is consistent with a labeled data point (x, y) ∈ X×Y if sgn(h(x)) = y and, by extension, that h is consistent with a set of labeled data points Z if it is consistent with all data points in Z. Two hypotheses h, h′ ∈ H are consistent with one another on a set of (unlabeled) points if sgn(h(x)) = sgn(h′(x)) for all x in that set of points.
At each round n, the learner is compelled to output a hypothesis hn ∈ H , and we seek to bound its true risk, err(hn), in terms of the true risk, err(h∗), of the best-in-class hypothesis h∗, as a function of the total number of streamed points n thus far. In addition, we want a bound on the label complexity of the learner, that is, the number of labels requested by the learner during the course of training. This bound should be provably smaller than n, which is the label complexity of a passive learner observing all labels. Further ancillary definitions will be introduced in later sections.

heading: 3 The ALPS Algorithm

text:
At a high level, ALPS either requests the label of an instance vector xn or assigns it a pseudo-label at each round n. The algorithm then selects a model hn that is consistent on the pseudo-labeled points, Ŝn, and that minimizes the empirical estimate of the risk, êrrn(h), which is defined in terms of pseudo-labeled and labeled points, Ŝn ∪ Tn, processed thus far. See pseudo-code in Algorithm 1.
More concretely, the learned hypothesis at round n is hn = LEARN(Ŝn, Ŝn ∪ Tn) where: Definition 2. For sets of labeled data points S and Z, LEARN(S,Z) returns a hypothesis in H that minimizes the empirical risk êrr(h, Z) on the second argument Z, and is consistent with all labeled data points in the first argument S, where consistency is defined in Definition 1. LEARN raises a flag if no such hypothesis is found.
In the LEARN procedure, we only need to consider hypotheses consistent with pseudo-labeled points, Ŝn, because we can show that with high probability, the sign of the best-in-class, h∗ = argminh∈H err(h), matches the sign of the pseudo-labeled points.
In order to decide whether to query the label of xn, ALPS leverages the disagreements between hypotheses, h+1, h−1 ∈ H returned by the LEARN procedure, where the label of the current instance xn is assumed to be either +1 for learning hypothesis h+1 and -1 for learning hypothesis h−1. Ideally, the algorithm would use the empirical difference errn(h+1) − errn(h−1) based on ground-truth labels to assess this disagreement, but because not all labels at time n have been disclosed to the algorithm, it instead uses the pseudo-labeled version êrrn(h+1)− êrrn(h−1), which is indeed observable. The algorithm compares this difference to a slack term, ∆̃n, derived from our theoretical analysis. See Appendix A for all slack term definitions. If the loss difference is smaller than the
1The sign of the pseudo-label ŷ is determined by the condition êrrn−1(h−ŷ)− êrrn−1(hŷ) > ∆̃n−1 and whether h−ŷ exist for ŷ ∈ ±1. E.g., ŷ = +1 if êrrn−1(h−1)− êrrn−1(h+1) > ∆̃n−1 or if h−1 does not exist.
Algorithm 1: Actively Learning over Pseudo-labels for Surrogate losses (ALPS) Input: LEARN(S,Z), Hypothesis class H , requester class R, and slack terms ∆̃n,∆′n. Ŝ0 = ∅;T0 = ∅; F1 = H ×R; for n = 1, 2, . . . , N do
Receive feature vector xn; For ŷ = ±1, let hŷ = LEARN(Ŝn−1 ∪ {(xn, ŷ)}, Ŝn−1 ∪ {(xn, ŷ)} ∪ Tn−1); Define version space Fn and bias pn:
Fn = {(h, r) ∈ Fn−1 : min (h′,r′)∈Fn−1
ln−1(h ′, r′) ≥ ln−1(h, r)−∆′n−1}
pn = max (h,r),(h′,r′)∈Fn max y∈Y
`B(y, h(xn))I{r(xn) ≤ 0} − `B(y, h′(xn))I{r′(xn) ≤ 0}
Qn ∼ Bernoulli(pn); if êrrn−1(h−ŷ)− êrrn−1(hŷ) > ∆̃n−1(or if no such h−ŷ is found) for some ŷ ∈ {±1} AND Qn = 0 then rn = argminr∈Rn E[I{r(x) > 0}], where
Rn = {r : (h, r) ∈ Fn and h consistent with Ŝn−1 ∪ {(xn, ŷ)}}
if rn(xn) > 0 then Request yn and update Ŝn = Ŝn−1, Tn = Tn−1 ∪ {(xn, yn)}; else Do not request yn and use1pseudo-label ŷ to update Ŝn = Ŝn−1 ∪ {(xn, ŷ)}, Tn = Tn−1;
end if else
Request yn and update Ŝn = Ŝn−1, Tn = Tn−1 ∪ {(xn, yn)}; end if hn = LEARN(Ŝn, Ŝn ∪ Tn);
end for Output hN = LEARN(ŜN , ŜN ∪ TN );
slack, then the label is requested because the sign of best-in-class h∗ cannot be inferred. Otherwise, a pseudo-label is constructed. In more detail, the sign of the pseudo-label ŷ is determined by the condition êrrn−1(h−ŷ)− êrrn−1(hŷ) > ∆̃n−1 and whether h−ŷ exist for ŷ ∈ ±1. Note that by this construction, the LEARN procedure can always return a consistent hypothesis on all pseudo-labeled points.
To understand the next steps in the ALPS algorithm, we relate the ground-truth empirical difference errn(h)− errn(h′) to its the pseudo-labeled counterpart êrrn(h)− êrrn(h′). To this effect, we define the difference of difference of losses An(h, h′) between two hypotheses h, h′ ∈ H at time n as
An(h, h ′) := err
n (h)− err n (h′)− ( êrr n (h)− êrr n (h′) ) .
This idea is also adopted by Dasgupta et al. [2008] in their analysis of the DHM algorithm. Yet, because they only deal with zero-one loss, in their case An(h, h′) = 0 for consistent h, h′ even when the true label does not match the pseudo-label. This easily follows from the fact that if sgn(h) and sgn(h′) agree on instance x, then2 I{sgn(h(x)) 6= y} − I{sgn(h′(x)) 6= y} = I{sgn(h(x)) 6= ŷ} − I{sgn(h′(x)) 6= ŷ}, irregardless of whether y = ŷ or not. In the surrogate loss setting analyzed here, whenever the pseudo-labels do not match their corresponding true labels, the term An(h, h′) is typically non-zero even for consistent h, h′. As a consequence, the magnitude of An(h, h′) must be carefully controlled since, otherwise, it would break both generalization and label complexity bounds as well as the guarantee that the best-in-class h∗ is consistent with Ŝn. In the sequel, we call An the noise term, as it captures the noise introduced during training due to the discrepancy between pseudo-labels and true labels.
2Throughout, I{·} is the indicator function of its argument.
To control the noise term, we introduce the idea of using requester functions. Specifically, we consider a set R of functions r : X → R, where r(x) > 0 means that the label of x is requested by r, and otherwise it is not requested. At each round n, the algorithm picks a requester function rn out of the set R, and the algorithm’s final condition of whether or not to request the label is decided by the sign of rn(xn). The requester function rn thus works as the final gatekeeper of whether to use the pseudo-label.
Notice that by definition the noise term An is non-zero when the true labels do not match the pseudolabels, ys 6= ŷs for some s ∈ [n]. By construction, since the final condition of whether to use a pseudo-label in round s is determined by rs, it follows that I{ys 6= ŷs} = I{ys 6= ŷs}I{rs(xs) ≤ 0}. In addition, for any h consistent with Ŝs, it holds that ŷs = sgn(h(xs)), and since the surrogate loss ` upper bounds the zero-one loss, we have that for any h consistent with Ŝs,
I{ys 6= ŷs}I{rs(xs) ≤ 0} ≤ `(h(xs), ys)I{rs(xs) ≤ 0} = B`B(h(xs), ys)I{rs(xs) ≤ 0} . (1) The above can thus be used as an upper bound of the noise.
To estimate this upper bound of An, the algorithm constructs an unbiased importance-weighted estimate, ln(h, r), of E[`B(h(x), y)I{r(x) ≤ 0}] as follows:
ln(h, r) = 1
n n∑ s=1 Qs ps(xs) `B(h(xs), ys)I{r(xs) ≤ 0} ,
where Qs is a Bernoulli random variable with bias ps(xs) and where ps(·) is a (random) function only depending on the past history {(xs′ , ys′), Qs′}s−1s′=1. The algorithm will request the label ys whenever Qs = 1 to construct this unbiased estimate. In order not to request the label (Qs = 1) too frequently, ps(·) is based on a shrinking version space Fn that contains only the pairs (h, r) whose empirical estimate ln(h, r) is close to the smallest one.
Given these estimates of E[`B(h(x), y)I{r(x) ≤ 0}], the algorithm chooses a requester function rn with the smallest request rate E[I{r(x) > 0}] from a set of requester functions in the version space Fn. In this way, the algorithm ensures that the noise term An is kept small. This is due to the fact that the version space Fn contains pairs of function (h, r) that are provably close to those minimizing E[`B(h(x), y)I{r(x) ≤ 0}], combined with the fact that `B(h(xn), yn)I{rn(xn) ≤ 0} is an upper bound on the noise at round n via (1).
Putting the above together, ALPS will request the label of xn whenever one of the following three conditions hold: 1) the loss differences of h+ and h− is smaller than the slack term, in which case the revealed label is used as we cannot infer the sign of h∗ and cannot construct a pseudo-label 2) Qn = 1, in which case the revealed label is used for the empirical estimates ln(h, r), 3) rn(xn) > 0, in which case the revealed label is used to control the noise term, An, introduced by pseudo-labeling. In all cases, the revealed labels are used in LEARN to find the best model at each round n.
Notice that, for the sake of argument, we have assumed in the above description to have access to a large unlabeled pool of examples x so as to construct a convenient set of requester functions, that is, to estimate E[I{r(x) > 0}] accurately. Yet, our algorithm and its associated analysis can be generalized straightforwardly to the case when such a pool is available only in a streaming way. Moreover, in our experiments in Section 5, we do not use an unlabeled pool to generate requester functions or to estimate the requesting rate. Instead, we define the set of requester functions to be margin-based functions with varying thresholds, and then estimate the requesting rate based on the data processed thus far. See Section 5 for details.

heading: 4 Theoretical Guarantees

text:
We now present generalization and label complexity guarantees of our algorithm. These bounds will be in terms of the best-in-class hypothesis, h∗, whose risk err(h∗) will be denoted by ν. For these guarantees, we consider a class R of requester functions that satisfies the following: Assumption 1. There exists r∗ ∈ R and a constant C ≥ 0 such that E[`(y, h∗(x))I{r∗(x) ≤ 0}] = 0 and E[I{r∗(x) > 0}] ≤ Cν.
If given access to a large unlabeled pool of data, we can always construct a function r such that E[`(y, h(x))I{r(x) ≤ 0}] = 0 for any h, since r can always be augmented in such a way to request
more frequently (that is, making r(x) > 0 for most x). Moreover below, we will further relax the first constraint to E[`(y, h(x))I{r(x) ≤ 0}] ≤ for some ≥ 0. However, unless more information about the structure of the problem is known, proving that there exists a function r∗ in the set R such that E[I{r∗(x) > 0}] ≤ Cν holds with a favorable (i.e., reasonably small) value of C is more difficult. Nevertheless, unfavorable C values, just like unfavorable disagreement coefficients, only impact the label complexity bound and not the generalization guarantee. After the theorems below, we present several natural examples of favorable C values.
Note that Assumumption 1 does not dictate conditions on the true conditional class probability, η(x) = P[y = 1 |x]. Hence, we are not relying on low-noise assumptions often adopted in active learning in realizable scenarios. Specifically, our assumption cannot be viewed as a surrogate loss counterpart to the Tsybakov [Mammen and Tsybakov, 1999, Tsybakov, 2004] low noise condition in the realizable setting [Castro and Nowak, 2008, Hanneke, 2011, Koltchinskii, 2010, Dekel et al., 2012] nor as an incarnation of the Bernstein condition, often invoked in statistical learning settings to achieve fast rates in both passive and active learning [Massart and Nedelec, 2006, Bartlett et al., 2006, Koltchinskii, 2006, Van Erven et al., 2015, Henneke and Yang, 2019].
In general, the richer the R class is, the easier Assumption 1 is satisfied with a small C. At the same time, since ALPS is learning over H and R simultaneously, the complexity of R affects both generalization bound and label complexity, as per usual in learning guarantees. Below, we first present the generalization bound of the ALPS algorithm. Here and in Theorem 2, the Õ notation is hiding logarithmic factors in n, 1/δ, and |H ×R|. Theorem 1. Under Assumption 1, for any δ > 0, with probability at least 1− δ, for any n > 0,
err(hn) ≤ ν + Õ (√ ν n + 1 n ) ,
where hn is the hypothesis computed by ALPS in round n.
This guarantee states that the risk of the hypothesis returned by the algorithm converges to the best-in-class hypothesis at a rate that matches that of standard supervised learning, despite the fact that ALPS uses less labeled points. The analysis used to derive this theorem proves that the noise introduced by the pseudo-labels is, in fact, controlled by the learned requester function so that the above bound can be attained. In passing, we observe that if the loss ` is convex and the Bayes optimal hypothesis is in the class H , then by using standard consistency techniques [Zhang, 2004, Bartlett et al., 2006] in conjunction with Theorem 1 above, we could also attain a bound on the excess risk of the zero-one loss.
The next theorem shows a bound on the expected number of labels the algorithm requests. This bound will be in terms of a notion of disagreement coefficient derived from the one in [Hanneke, 2007]. Define a metric ρ on the space of hypotheses H as ρ(h, h′) := E(x,y)∼D [ |`(h(x), y)− `(h(x), y)| ] . Using this metric, we consider the γ-ball around the best-in-class: Bγ(h∗) = {h : ρ(h, h∗) ≤ γ} . Then, let θ := supγ>0 {Px[∃h ∈ Bγ(h∗) : sgn(h(x)) 6= sgn(h∗(x))]/γ} be the disagreement coefficient of H (for the given distribution D over X× Y). Theorem 2. Under Assumption 1, for any δ > 0, with probability 1− δ, the label complexity of the ALPS algorithm at time n > 0 is bounded as Õ (nν(θ + C)) .
Disregarding constants θ and C, the above bound is Õ(nν). This label complexity guarantee of ALPS in conjunction with its generalization bound matches the known lower bound Ω(nν) from Beygelzimer et al. [2009] up to constants and is therefore optimal.
In Assumption 1, we considered the case when E[`(y, h∗(x))I{r∗(x) ≤ 0}] = 0 which is easy to satisfy if we have a rich enough class R with functions that request more frequently. Nevertheless, we can relax this assumption if desired as follows: Assumption 2. There exists r∗ ∈ R and constants C ≥ 0 and ≥ 0 such that E[`(y, h∗(x))I{r∗(x) ≤ 0}] ≤ and E[I{r∗(x) > 0}] ≤ Cν.
Under this assumption, the label complexity guarantee in Theorem 2 remains unchanged while an term is added to the generalization bound in Theorem 1 when ALPS is run with slack ∆̃n−1 + . By definition, is at most ν and if ν, then this term has basically no effect on generalization. There are several natural instances where the condition stated in Assumption 1 and Assumption 2 are satisfied with favorable C values. Consider for example a scenario where along the margin of the
best-in-class hypothesis, there are hard-to-classify examples, while further away the best-in-class hypothesis mostly classifies the examples correctly. See Figure 1 for an illustration where there is such a margin γ∗ around the best-in-class h∗. This example is often used to explain why the popular margin algorithm works since this algorithm queries the label of points close to the classification surface. In our case, letting r∗(x) = γ∗ − |h∗(x)|, it holds that E[`(y, h∗(x))I{|h∗(x)| ≥ γ∗}] ≤ for a small and E[I{|h∗(x)| < γ∗}] = νE[`(y,h∗(x)) | |h∗(x)|<γ∗] . If the expected loss of h
∗ conditioned on the margin region is high, say ≥ 1/2, then it follows that E[I{r∗(x) > 0}] = E[I{|h∗(x)| < γ∗}] ≤ 2ν, so that Assumption 2 is satisfied with C = 2. Specifically, in Figure 1, it holds that C = 2 and = 2/50.
When h∗ performs well outside the margin, then Assumption 2 holds with a small while if it correctly classifies all points outside the margin, then = 0 and Assumption 1 holds. The = 0 case is easily satisfied by generalized linear models, P[y = 1|x] = σ(h∗(x)), where σ is a tapered sigmoid function. Note that Assumption 1 is not placing specific restrictions on the marginal distribution over X, other than E[I{|h∗(x)| < γ∗}] = 2ν. This does not imply conditions on η(x) when x falls in the region |h∗(x)| < γ∗ and hence we are not relying on realizability assumptions. With any given class of hypotheses H , one can always associate the margin-based requester function class R = {r : r(x) = γ − |h(x)| , γ ≥ 0, h ∈ H}. In this case, ALPS can be seen as trying to simultaneously approximate h∗ and the best threshold γ∗. The resulting algorithm turns out to be related to margin-based approaches since ALPS will seek to query the label of these more difficult points along the margin, but ALPS finds this optimal pair by using a different approach.
At the same time, we would like to stress that, in our framework, the function class R need not be restricted to margin-based requesters: if there exists a small region, {x ∈ X : r∗(x) > 0}, for some function r∗ : X→ R such that most of the loss incurred by the best-in-class h∗ is coming from this region, and R is rich enough to contain such function r∗, then Assumption 1 and Assumption 2 hold. For an illustration of this situation, see Figure 1 on the right.

heading: 4.1 Comparisons to IWAL and DHM

text:
The IWAL algorithm of Beygelzimer et al. [2009] constructs importance weighted estimates of the expected loss and uses them to select the prediction function. In contrast, ALPS leverages importance weighted estimators to select requester functions that minimize the noise term. Thus, even though both algorithms construct importance weighted estimators, they serve entirely different purposes. Both IWAL and ALPS attain generalization and label complexity bounds that are effectively of the same order, but our empirical results show that IWAL considerably underperforms compared to other active learning algorithm on all 18 datasets we tested. These empirical results are consistent with other authors’ findings (e.g., Figure 2 in Cortes et al. [2019b] and Figure 3 in Cortes et al. [2020]).
Even though ALPS can be seen as a generalization of DHM [Dasgupta et al., 2008] to surrogate loss functions, there are several key differences. The noise introduced by the pseudo-labels does not affect DHM since by definitionAn(h, h′) = 0 for the zero-one loss. Thus, DHM does not resort to requester functions or other techniques to deal with unreliable pseudo-labels. Moreover, unlike in DHM, the second argument in the LEARN(·, ·) subroutine over which ALPS minimizes error is Ŝn ∪ Tn, not just Tn. For the zero-one loss, minimizing the error over Ŝn ∪ Tn or only Tn is equivalent since hypothesis consistent on Ŝn admit zero loss over the points in Ŝn. Note that ALPS’s pseudo-code
reduces to DHM’s when ` is the zero-one loss and R is set to include only the never-requesting function, that is, r(x) = 0 for all x, in which case the importance-weighted estimates ln(h, r) are not constructed. We then attain the same guarantees as DHM’s without resorting to Assumption 1 or Assumption 2.

heading: 5 Empirical Results

text:
In this section, we present our experimental results in the streaming active learning setting that test the ALPS algorithm, the IWAL algorithm, the margin algorithm (or uncertainty sampling), and a passive learning algorithm, which requests the label of all points and finds the hypothesis that attains the smallest empirical loss. We compare to IWAL since it is a principled algorithm in the general agnostic scenario with strong theoretical guarantees. We test the margin algorithm since even though its theoretical guarantees do not hold in general, it admits a strong performance in practice. We run a passive learning algorithm to demonstrate the benefit of ALPS over standard supervised learning.
We tested these algorithms on 18 publicly available datasets where we used the logistic loss as the surrogate loss ` and used feedforward artificial neural networks as our model class. Specifically, we used the Multi-layer Perceptron algorithm in the scikit-learn library and ran two diverse network architectures, one with 3-layers and another with 4-layers. For each type of neural network, we constructed a diverse finite set of hypotheses by pre-training on small random subsets while varying the l2 regularization parameter and initial weights. For each experiment, we randomly shuffled the dataset, generated the finite hypothesis set, and ran all the algorithms. We repeated the experiment 50 times and averaged the results. See Appendix D for details on the datasets and model class settings.
Recall that the margin algorithm in the streaming setting first selects the hypothesis h ∈ H with the smallest empirical loss and then requests the label of a point x if |Ph[y = +1|x]−Ph[y = −1|x]| ≤ γ, where Ph[y = ±1|x] is the model h’s (estimated) conditional probability of labeling the given point x either +1 or −1. We ran nine instances of the margin algorithm for all thresholds γ ∈ Γm where the set of thresholds Γm was chosen as a result of a tuning procedure that consisted of a standard grid search and zooming in. For ALPS, the requester class R is also defined by margin-based functions as r(x) = I{|Ph[y = +1|x]− Ph[y = −1|x]| ≤ γ} for each hypothesis h ∈ H and each γ ∈ Γr. Note that we run ALPS with = 0 for this class R. Unlike Γm, the set Γr was not tuned since ALPS learns the best threshold in Γr. For details on Γm and Γr, please see Appendix D.
To evaluate the algorithm performance, both accuracy and logistic loss are of interest in different applications as explained in the introduction. Thus, Figure 2 shows the accuracy and logistic loss on
the test set of the model returned by each algorithm at each round n. Figure 2 also plots the number of points labeled by each algorithm as a function of the number of unlabeled points (or rounds) n.
Notice, in particular, that for the passive learning algorithm, since the data is streamed in a random order the value of the curves at time step n can be interpreted as running the algorithm up until we gather n queries on randomly drawn points. So, for instance, at round n = 200 of the passive curve (orange line) for the ijcnn dataset, we effectively randomly sample and reveal the label of 200 points out of the training set, choose a model that corresponds to an empirical risk minimizer over these 200 points, and evaluate this model’s accuracy on the test set. The passive learning curve is then used as a baseline comparator of the active learning algorithms. That is, the best performing active learning algorithm is the one that attains an accuracy and logistic loss curve that is on par or better than that of passive learning while requesting the fewest number of labels.
Figure 2 on the right shows that the accuracy and logistic loss curves of the margin algorithm varies with the threshold. In almost all datasets, there exists thresholds whose corresponding margin algorithm admits an accuracy curve that is below that of passive learning and as the threshold increases, the accuracy curve improves eventually matching that of passive learning. This indicates that a good set of threshold values was tested, since we seek an algorithm that requests the fewest number of points (i.e. having a small threshold) with an accuracy curve on par to that of passive learning. We then pick the ex-post best margin algorithm with smallest threshold that admits an learning curve area with respect to accuracy that is within one standard error of the passive learning curve area. If no algorithm admits such a curve, we pick the margin algorithm with the largest learning curve area. Choosing the ex-post best margin algorithm in this way and tuning of Γm gives the margin algorithm an unfair advantage, since both of these processes use the learning curves based on the revealed labels. Nevertheless, it provides an upper bound on the best performance of these uncertainty samplers.
The left-most plots of Figure 2 show that, for both cifar and ijcnn datasets, the ALPS algorithm performs better than all baseline methods since out of the algorithms that attain the accuracy and logistic loss curve close to that of passive learning, it requests the fewest number of points. In Appendix D, we report these figures for all 18 datasets.
Overall for the 3-layer networks, our results show that the ALPS algorithm outperforms the ex-post best margin algorithm on all but one dataset. Similarly, for the 4-layer networks, ALPS performs better than the margin algorithm on all but two dataset. Thus, despite the advantage given by the ex-post tuning of the margin algorithm, ALPS attains a better performance. Moreover, ALPS outperforms both passive learning and IWAL on all datasets. On average across all datasets, ALPS requests only a mere 28% of the processed points. Since ALPS was run with = 0, these experiments suggest that Assumption 1 holding with favorable C values often happens in practice or that Assumption 1 is simply an artifact of our analysis.
Additionally, the ex-post best margin algorithm outperforms IWAL on the majority of the datasets, which is consistent with previous studies [Cortes et al., 2020]. IWAL attains a higher variance across the trials for some datasets, and overall it performs better than passive learning. In general, the same empirical conclusions about the relative performance of the active learning algorithms hold for logistic loss and accuracy curves for all algorithms except for the margin algorithm. On a few datasets, the margin algorithm attains a logistic loss curve that is worse than that of passive learning while admitting an accuracy curve that is on par to that of passive learning (e.g., ijcnn).

heading: 6 Conclusion

text:
We designed an active learning algorithm, called ALPS, for general loss functions that learns to leverage pseudo-labels by using requester functions in order to train a model over a joint set of pseudolabel and labeled points. ALPS operates in the general agnostic setting; its model is guaranteed to converge to the best-in-class prediction model at the same rate as passive learning, while achieving favorable label complexity guarantees under a mild assumption on the class of requester functions. Our comprehensive empirical study on 18 datasets shows that ALPS outperforms relevant baselines, including the margin algorithm often used in practice. As a next step, we will investigate how to extend our algorithm and its associated analysis to multi-class classification setting.
Acknowledgments. Most of this research was done while the Tobias Sommer Thune was visiting Google Research in New York. Tobias Sommer Thune further acknowledges partial support by the Independent Research Fund Denmark, grant number 9040-00361B. We thank the NeurIPS anonymous reviewers whose comments helped us improve the presentation of this paper.

title: Online Active Learning with Surrogate Loss Functions