Data driven semi-supervised learning
Authors: Nina Balcan
Dravyansh Sharma
Venue: NeurIPS 2021 Oral (2021)
Keywords: Semi-supervised learning
learning theory

Abstract: We consider a novel data driven approach for designing semi-supervised learning algorithms that can effectively learn with only a small number of labeled examples. We focus on graph-based techniques, where the unlabeled examples are connected in a graph  under the implicit assumption that similar nodes likely have similar labels. Over the past two decades, several elegant graph-based semi-supervised learning algorithms for inferring the labels of the unlabeled examples given the graph and a few labeled examples have been proposed. However, the problem of how to create the graph (which impacts the practical usefulness of these methods significantly) has been relegated to heuristics and domain-specific art, and no general principles have been proposed. In this work we present a  novel data driven approach for learning the graph and provide strong formal guarantees in both the distributional and online learning formalizations. We show how to leverage problem instances coming from an underlying problem domain to learn the graph hyperparameters for commonly used parametric families of graphs that provably perform well on new instances from the same domain. We obtain low regret and efficient algorithms in the online setting, and generalization guarantees in the distributional setting. We also show how to combine several very different similarity metrics and learn multiple  hyperparameters, our results hold for large classes of problems. We expect some of the tools and techniques we develop along the way to be of independent interest, for data driven algorithms more generally.

Data driven semi-supervised learning
Maria-Florina Balcan School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 ninamfecs. cmu, edu
Dravyansh Sharma
Department of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213 dravyans@cs. cmu, edu
Abstract
We consider a novel data driven approach for designing semi-supervised learning algorithms that can effectively learn with only small number of labeled examples. We focus on graph-based techniques, where the unlabeled examples are connected in graph under the implicit assumption that similar nodes likely have similar labels. Over the past two decades, several elegant graph-based semi-supervised learning algorithms for inferring the labels of the unlabeled examples given the graph and a few labeled examples have been proposed. However, the problem of how to create the graph (which impacts the practical usefulness of these methods significantly) has been relegated to heuristics and Nomain-speciff art, and no general principles have been proposed. In this work we present novel data driven approach for learning the graph and provide strong formal guarantees in both the distributional and online learning formalizations. We show how to leverage problem instances coming from an underlying problem domain to learn the graph hyperparameters for commonly used parametric families of graphs that provably perform well on new instances from the same domain. We obtain low regret and efficient algorithms in the online setting, and generalization guarantees in the distributional setting. We also show how combine several very different similarity metrics and learn multiple hyperparameters, our results hold for large classes of problems. We expect some of the tools and techniques develop along the way be of independent interest, for data driven algorithms more generally.
Introduction
In recent years machine learning has found gainful application in diverse domains. major bottleneck of the currently used approaches is the heavy dependence on expensive labeled data. Advances in cheap computing and storage have made it relatively easier store and process large amounts of unlabeled data. Therefore, an important focus of the present research community is to develop general comman-independdeee methods to learn effectively from the unlabeled data, along with a small amount of labels. Achieving this goal would significantly elevate the state-of ofethe-art machine intelligence, which currently lags behind the human capability of learning from few labeled examples. Our work is a step in this direction, and provides algorithms and guarantees that enable fundamental techniques for semi-supervised learning to provably adapt to problem domains.
Graph-based approaches have been popular for learning from unlabeled data for the past two decades [Zhu and Goldberg 2009]. Labeled and unlabeled examples form the graph nodes and (possibly weighted) edges denote the feature similarity between examples. The graph therefore captures how each example is related to other examples, and by optimizing a suitably regularized objective over it one obtains an efficient discriminative, nonparametric method for learning the labels. There are several well-studied ways to define and regularize an objective on the graph [Chapelle al. 2010
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Table 1: Optimization objectives for graph-based SSL. Dij == -ii j &x Was L:= D-112(DD-
W) D-1/2 and the objective is ((f) = a (f yu) + (f. W + + 11f1
Algorithm
(.)
H(f.W),
Constraints on f
Mincut
(o0, 1.0)
F(D-W)f W)f
f (0,1)
Harmonic function
1,0)
FD
{E [0. 1
Normalized cut
1,0,
fT WW)
f 0, f = n n E = 10 f f [0, 1]"
Label propagation
(1.
and all yield comparable results which strongly depend on the graph used. A general formulation is described as follows, variations on which are noted under related work.
Problem formulation Given sets L and U of labeled and unlabeled examples respectively, and similarity metric d over the data, the goal is to use d to extrapolate labels in L to U. A graph G is constructed with U as the nodes and weighted edges W with w(u, v) = g(d(u, v)) for some g: R20 + Rzo. We seek labels f(-) for nodes of G which minimize a regularized loss function I(f) = ((f(v), yo) + BH W) + ? l[fl] under some constraints on f. The objective H captures the smoothness (regularization) induced by the graph (see Table for examples) and i(f()) ye)
) is the misclassification loss (computed here on labeled examples).
The graph G takes central position in this formulation. However, the majority of the research effort on this problem has focused on how to design and optimize the regularized loss function I(f). the effectiveness of which crucially depends on G. There is no known principled study on how to build G and prior work largely treats this as a domain-specific art [Chapelle et al.) 2010]. Is it possible to acquire the required domain expertise, without involving human experts? In this work we provide an affirmative answer by formulating graph selection as data-driven design. More precisely, we are required to solve not only one instance, but multiple instances of the underlying algorithmic problem that come from the same domain [Gupta and Roughgarden 2016) Balcan 2020). We show learning a near-optimal graph over commonly used infinite parameterized families possible in both online and distributional settings. In the process we generalize and extend data-driven learning techniques, and obtain practical methods to build the graphs with strong guarantees. In particular, we show how the techniques can learn several parameters at once, and also learn a broader class of parameters than previously known.
Our contributions and key challenges. We present first theoretically grounded work for graph- based learning from limited labeled data, while extending general data-driven design techniques.
Data-driven algorithm design. Firstly, for one dimensional loss functions, we show a novel structural result which applies when discontinuities (for loss as function of the algorithm parameter) occur along roots of exponential polynomials with random coefficients with bounded joint distributions (previously known only for algebraic polynomials in Balcan et al. (2020b)) This is crucial for showing learnability in the Gaussian graph kernels setting. Secondly, Balcan et al.) (2020b) only applies when the discontinuities occur along algebraic curves with random coefficients in just two dimensions. By novel algebraic and learning theoretic argument we are able to analyze higher (arbitrary constant number of) dimensions, making the technique much more generally applicable.
Semi-superrised learning. We examine commonly used parameterized graph families, denoted by general notation G(p), where P corresponds to a semi-supervised learning algorithm. We consider online and distributional settings, providing efficient algorithms to obtain low regret and low error re- spectively for learning p. Most previously studied settings involve polynomially many discontinuities for loss as function of the hyperparameter P fixed instance. implying efficient algorithms, which may not be the case for our setting. To resolve this, we describe efficient band-bandit implementa- tions, and in particular introduce a novel min-cut and flow recomputation algorithm on graphs with continuously changing edge weights which may be of independent interest. For the distributional setting, we provide asymptotically tight bounds on the pseudodimension of the parameter learning problem. Our lower bounds expose worst case challenges, and involve precise constructions of problem instances by setting node similarities which make assigning labels provably hard.

---

Our techniques are extremely general and are shown to apply for nearly all combinations of optimiza- tion algorithms (Table and parametric graph families (Definition
Related work Semi-supervised learning is paradigm for learning from labeled and unlabeled data
(Zhu and Goldberg (009)) D. resembles human learning behavior more closely than fully supervised
and fully unsupervised models (Zhu et al. [2007], Gibson et al. (2013) ). A popular approach for semi-supervised learning is to optimize a graph- objective. Several methods have been proposed to predict labels given a graph including st- st-mincuts (Blum and Chawla [200T], soft mincuts that optimize a harmonic objective (Zhu et al. (2003) ), label propagation (Xiaojin and Zoubin| (0022), and many more (Shi and Malik| provided the graph G encodes the problem well [Zhu and Goldberg, 2009]. However, is not clear how to create the graph itself on which the extensive literature stands, barring some heuristics (Zhu jtt al. 2005). Zemel and Carreira-Perpiñán (2004). Sindhwani et al. [2005] construct warped kernels aligned with the data geometry, but the performance may vary strongly with warping and it is not clear how to optimize over it. We provide the first techniques that yield provably near-optimal graphs.
Belkin et al. (2006)). All algorithms have comparable performance
Gupta and Roughgarden (0166] 2017] define a formal learning framework for selecting algorithms from a laailly of heuristics or setting hyperparameters. It is further developed by BBleann et al. [017]] and noted as a fundamental algorithm design perspective [Blum] 2020]. It has been successfully applied to several combinatorial problems like integer programming and clustering (Balcan et al.. 2018a, 2019 2018c] and for giving powerful guarantees like adversarial robustness, adaptive learning and differential privacy [Balcan et al., 2018b 2020a [j Vitereik et al.) 2019, Balcan et al., 2020e d]. Balcan et al. [b 2020b] introduce general data-driven design techniques under some smoothness assumptions. We extend the techniques to significantly broader problem settings, and investigate the structure of graph-based label learning formulation to apply the new techniques.
2 Setup and definitions
We are given some unlabeled points U c. X' and labeled points L C X' x D. such that [L] |U| One constructs a graph G by placing (possibly weighted) edges w(u, v) between pairs of data points u, which are 'similar', and labels for the unlabeled examples are obtained by optimizing some graph- based score. We have an oracle O which on querying provides us the labeled and unlabeled examples, and we need to pick graph Gpp) from some family of graphs, parameterized using parameter E P. We commit to using some graph labeling algorithm A(G, L, U) (abbreviated as AG.L,)) which provides labels for examples in U, and we should pick a p such that A(G(p), L, U) results in small error in its predictions on U. More formally, for a loss function 1: y x y - [0, 1] and a target labeling : U + Y. we need find argmin (A(C(o)LLU) := Ev ((AG() (u),
We will now describe some graph familics G and algorithms AG,LUU We assume there is a feature based similarity function d X x X - R>o. metric which monotonically captures pairwise similarity. Commonly used parametric methods to build a graph using the similarity function follow.
Definition 1. Graph kernels !
a) Threshold graph, G(r). Parameterized by threshold r, we set w(u, v) = l[d(u, v) S r].
b) Polynomial kernel, G(ā). w(u,o) = (d(u, v) + a)d fixed degree d, parameterized by ā.
c) Gaussian RBF or exponential kernel, G(a). w(u, u) d(uu,)))) parameterized by a.
Remark 1. Another popular family of graphs used in practice is the k nearest neighbor graphs, where k E {0, 10.....,,7 n - 1}, n. is the number of nodes in the graph, is the parameter. Even though k-NN graphs may result in different graphs the ones considered in the paper, learning how to build an optimal graph over the algorithm family G(k) is much simpler. Online learning of the parameter k in this setting can be recognized as an instance of learning with experts advice for a finite hypothexis class (Section 1.1 of Shalev-Shwarts et al. (2011)), where an upper bound of O( log n) is known for the Weighted Majority algorithm. Online-to ticine-to-batt bathatch conversion provides generalization guarantees in the distributional setting (Section 5 of Shalev- Shaaare--Swwrz.e et al.) (2011y). We remark that our algorithm families need more sophisticated analysis due to continuous ranges of the algorithm parameters.
With some notational abuse, we have d the integer polynomial degree, and d(. as the similarity function. Common choices are setting d(u, v) the Euclidean norm and d(u, v) as the dot product when u, U E R".
3

---

The threshold graph adds (unweighted) edges to G only when the examples are closer than some r 2 We refer to this setting by the unweighted graph setting, and the others by the weighted graph setting. The similarity function d(uu, v) in Definitions pp increases monotonically with similarity of examples (as opposed to the other two). Once the graph constructed using one of the above kernlls, we can assign labels using some algorithm AG, A popular, effective approach is to optimize a quadratic objective z En,o w(u, ( f())), I may be discrete, [(u) E {0, 10 corresponds to finding a mincut separating the oppositely labeled vertices [Blum and Chawla 2001 or f E [o. 1]
may be continuous and we can round obtain the labels (Zhu et al.33 These correspond to the mincut and harmonic function algorithms respectively from Table
We also need some well-known definitions from prior work (Appendix A). In particular, we use dispersion from [Balcan et al.) 2020b]. The sequence of random loss functions l1, is 3-dispersed for the Lipschitz constant I. if, for all T and for all 2 T-8, E [max o.C.le- {t E (T) ((P) - leld) > L Llpp- -
hilp-p'll2] p'112]]] 5 Ö(T).
3 New general dispersion-based tools for data-driven design
We present new general tools for analyzing data-driven algorithms. Our new tools apply to a very broad class of algorithm design problems, for which we derive sufficient smoothness conditions to infer dispersion of a random sequence of problems, i.e. the algorithmic performance as a function of the algorithm parameters is dispersed. Recall that dispersion, roughly speaking, captures the rate at which discontinuities concentrate in any region of the domain. [Balcan et al. [2020b) provide general tool for verifying dispersion if non-Liischitzness occurs along roots of (algebraic) polynomials in one and two dimensions. We improve upon their results in two major ways.
Our first result is that dispersion for oie-dimensional loss functions follows when the points of discontinuity occur at the roots of exponential polynomials if the coefficients are random, lie within a finite range, and are drawn according to bounded joint distribution. The key idea is use algebraic arguments and Taylor series approximation to show that for any small interval containing roots of the random exponential polynomial, the corresponding sets of coefficients lie on n 1 dimensional linear subspaces with a probability measure proportional to the length of the interval (Appendix C.3).
Let 6(x) = Ei= arch" be a random function, such that coefficients og are real and of magnitude at most R. and distributed with joint density most Then for any interval I of width at most e, p(ó has a zero in 1)S Ö(e) (dependence on bi, n, K. R suppressed).
Theorem 2.
Proof Sketch. For n = 1 there are no roots, so assume n > 1. Suppose p is a root of Φ(z). Then a (a1..... an) is orthogonal to p(p) = (e'ip, eRPP) in R". For a fixed p. the set Sp of coefficients for which p is root of (ty) lie along an root in any interval I of length e, exactly when the coefficients lie on Sp for some E 1. The desired probability is therefore upper bounded by max, VOL(US, y E [p - e, + <)) ()L, y E R) which we will show to be Ō(e). The key idea is that if I p p'1 < e, then e(p) and e(p') are within a small angle pp.p/ = Ô(c) for small (the probability bound is vacuous for large c). But any point in Sp is at most O(8p.rr) from point in Spr, which implies the desired bound.
dimensional linear subspace of R", Now & has a
We further go beyond single-pant parameter discontinuties, which occur as points along a line to general small dimensional parameter spaces R", where discontinuties can occur along algebraic hypersurfaces. We employ tools from algebraic geometry to establish a bound on shattering of algebraic hypersurfaces by axis-aligned paths (Theorem 3 which implies dispersion using VC dimension based argument (Theorem 4. Our result is a first general sufficient condition for dispersion for any constant number p of parameters, and applies
broad class of algorithm families. Full proofs are in Appendix C.4
Theorem 3. There is constant ls depending only on d and p such that axis-al aligned line segments in IRP cannot shatter any collection of l algebraic hypersurfaces of degree at most d.
Proof Sketch. Let C denote a collection of algebraic hypersurfaces of degree at most RP. We say that subset of C is hit by a line segment if the subset is exactly the set of curves in C which intersect the segment. We can upper bound the subsets of C hit by line segments in a fixed axial direction in two steps. Along fixed line, Bezout's Theorem bounds the number of intersections

---

and therefore subsets hit by different line segments, Using the Murski-Seidenberg Theorem, the lines along x can be shown to belong to equivalence classes corresponding to cells in the cylindrical algebraic decomposition of the projection of the hypersurfaces, orthogonal to Finally, this extends to axis-aligned segments by noting they may hit only p times as many subsets.
Theorem 4. Let l,....,T= RRP R be independent piecewise J-Lipschiit,functions each having discontinuities specified by collection of at most K algebraic hypersurfuces of bounded degree. Let L denote the set of axis-aligned paths between pairs of points in WP, and for each s E L define D(T, s) {[1 I t S T le has discontinuity along s}{. Then we have Elsup D(T,s) S sup,eL (T, s)] + O( Oly/Tog(TK).
4 Learning the graph online
We will warm up this section with simple example demonstrating the need for and challenges posed by the problem of learning how to build a good graph from data. We consider the setting of learning thresholds for unweighted graphs (Definition [p)). We give simple demonstration that in a single instance any threshold may be optimal for labelings consistent with graph smoothness assumptions, therefore providing motivation for the learning our setting. Our construction (depicted in Figure IT captures the intuition that any unlabeled point may get weakly connected to examples from one class for small threshold but may get strongly connected to another class the threshold is increased to a larger value. Therefore depending on the unknown true label either threshold may be optimal or suboptimal, and makes sense learn the correct value through repeated problem instances.
Tmax
In
Ti
Yuii
Figure 1: G(r) connects to nodes in L1 for Tmin ST<r". |4, < [L2]
Theorem 5.
Let min denote the smallest value of threshold for which every unlabeled node of G(r)
reachable from some labeled node, and max be the smallest value of threshold r for which G(r) is the complete graph. There exists a data instance (L, U) such that for any rę {rmia (1 mmax for E (0,1), there exists set of labelings U of the unlabeled points such that for some Uc, Uc E u, re minimizes! L.G))) but not L.GG)))LL
4.1 Dispersion and online learning
We consider the problem of learning the graph online. In this setting, are presented with instances of the problem online and want to learn the best value of the parameter p while making predictions. For now, we assume get all the labels for past instances which may be used to determine the loss for any (full information). At time E [T] we predict Pt E P (the parameter space) based on labeled and unlabeled examples (I,, U.), i and past labels 7 (u) for each u E Uz. t and seek to minimize regret Ry == Σt= (A(G(p))
minpep ΣT= (((()))
A key difficulty in the online optimization for our settings is that the losses are discontinuous functions of the graph parameters p. We can efficiently solve this problem we can show that the loss functions are dispersed, in fact -dispersed functions may be learned with Ó /T) regret (Balcan et [2018b 2020cD). Algorithm[ [ddapts (adapts the general algorithm of Balcan et al. (018b) to data-dnven graph-based learning and achieves low regret for dispersed functions. Recall that dispersion roughly says that discontinuities in the loss function are not too concentrated. We will exploit an assumption that the
embeddings are approximate, so small random perturbations to the distance metric will likely not affect learning. This mild distributional assumption allows us show that Algorithm learns p.
5

---

Algorithm 1 Data-driven Graph-based SSL
1: Input: Graphs G2 with labeled and unlabeled nodes (L,, U2), node similarities d(u, v) Di 1yU
2: Hyperparameter: step size parameter À E (0. 1].
3: Output: Graph parameter Pr for times t = 1,2....,TT T.
4: Set w1(p) (p) = 1 for all p E Rzo.
5: for = 1, ..,....,T' do
6: Sample with probability Pc(p) = wa) W. output as Pe: where W₁ == Sc wr(d)dp. 7: Compute average loss function le(p) ाट. Enev (U,,,)).L..,,(1,,,7
8: For each p C, set (p) edve( we (p), where up(p) = 4(p) E [0, 1].
4.1.1 Dispersion of the loss functions.
We first show dispersion for the unweighted graph family, with threshold parameter Here dispersion follows from a simple assumption that the distance d(u, u) for any pair of nodes u, v follows a ni- bounded distribution and observing that discontinuities of the loss (as a function of r) must lie on the set of distances d(u, v) in the samples (for any optimization algorithm). Using a VC dimension argument on the loss sequence
show (Appendix C..I)
Theorem 6. Let II. I + R denote an independent sequence of losses as function of parameter r, when the graph is created using a threshold kernel w(u, v) = I[d(u,v) S r] and labeled by applying any algorithmm on the graph. If d((u, v) follows a r--ounded distribution for any u, the sequence 3-dispersed, and the regret of Algorithm 7 Ö(VT).
We also show dispersion for weighted graph kernels, but under slightly stronger assumptions. We assume that distances d(u, v) are jointly k--ouuded on closed and bounded support. The plan is show that if the similarity function is smooth, then the discontinuities lie along roots of polynomial with random finite coefficients with a w'-bounded joint distribution, and use results for dispersion analysis from Balcan et al. [2000)]. We establish the following theorem (proof in Appendix C.2).
Let 4,,...,4 LT IR + R denote an independent sequence of losses as a function of 5, for graph with edges wiu, w) = (d(u,, v) + a) labeled by optimizing the quadratic objective En, w(u, v)((()) f()))² If d(u, v) follows a r-bounded distribution with closed and bounded support, the sequence is 1 dispperedd, and the regret of Algorithmm 1 may be upper bounded by Ö(VT).
Theorem 7.
Proof Sketch. The solution of the quadratic objective is given by fo (Dou - The key technical challenge ā with degree at most nd, and coefficients that are jointly K KKk-bounded where K is constant that only depends on d and the support of d(u, v). Therefore the labeling, and consequently also the loss function, may only change when a root of one of [U]] polynomials of degree most dn. The dispersion result is now simple application of results from Balcan et al. [2020b].
show that for any u E U. f(u) 1/2 is a polynomial equation in
n
Remark 2. Theorem O applies to all objectives in Table ! and Theorem 7 extends to all except the mincut. We can also extend the analysis to obtain similar results when using the exponential kernel The results of Balcan et al. (2020b] no longer directly apply as the points of discontinuity are no longer roots of polynomials, and need to analyze points of discontimuities
w(u, = -I
of exponential polynomials, i.e. d(x)) = -Et agele (See Section 3 and Appendix C.3
Remark 3 (Extension to local and global classification Zhou et al. (2004]). Above results can be
extended to the classification algorithm used in Zhou et al. ad.120044 The key observation is that the
labels are given by a closed-form matrix, - ( a1)) 1/ 1/2W "WD 12/ or f'== (D W Y (for the two variants considered). For threshold graphs Grr), the regret bound in Theorem 6 applies to any classification algorithm. Extension to polynomial kernels G(ā) is described below. For fixed (in the notation of ohou et al. 22004), in expression for f above), ) the discontiniiiess in the loss as a function of the parameter lie along roots of polynomials in the parameter ā and therefore the same proof as Theorem 7 applies (essentially we get polynomial equations with slightly different but still
2 A density function| f R + R. bouuddee if max (x(()))))+)+))))))))))))))))){ S N a) is and bbounded for any μ.

---

K-bounded coefficients). On the other hand, we consider as another graph parameter, we can still learn the kernel parameter together with a by applying Theorem 18 and Theorem (instead of Theorem 19 in the proof Theorem 7
4.1.2 Combining several similarity measures.
Multiple natural metrics often existin multimodal semi-supervised learning [Balcan et al. 2005 Different metries may have their own advantages and issues and often a weighted combination of metrics, say >; (.d;(..)), works better than any individual metric. The combination weights p; are additional graph hyperparameters. theoretically and empirically for linkage-based clustering [Balcan al. 2019]. However the argument therein crucially relies on the algorithm depending on relative distances and not the actual values, and therefore does not extend directly to our setting. We develop a first general tool for analyzing dispersion for multi-ddiensiionll parameters (Section B). which implics the multi-par aulti-parameter analogue of Theorem 7 stated below. See Appendix [.r proof details.
combination of metrics is known to boost performance
Theorem 8. Let l1,...,IT : IP + R denote an independent sequence of losses a func- tion of parameters Piç E [p], when the graph is created using a polynomial kernel w(u, v)
EE pid(u, w) + Pp)² and labeled by optimizing the quadratic objective En, w(u, (J(()) [w))). if follows a k-bounded distribution with a closed and bounded support, the sequence }/2 disppersd,, and the regret of Algorithm I may be upper bounded by Ö(VT).
4.1.3 Semi-bandit setting and efficient algorithms.
Online learning with full information is usually inefficient in practice since it involves computing and working with the entire domain of hyperparameters. For setting in particular this is computa- tionally infeasible for weighted graphs since the number pieces (in loss as a piecewise constant function of the parameter) may be exponential in the worst case (see Section [3. Fortunately a workaround provided by |alccan et al.) 2020b) where dispersion implies learning in a semi-bandit setting well. This setting differs from the full information online problem follows. In each round as we select the parameter Pi. we only observe losses for a single interval containing Pi (as opposed the entire domain). We call the set of these observable intervals the feedback set, and these provide a partition of the domain.
have
Algorithm 2 Efficient Data-driven Graph-based SSL
1: Input: Graphs G, with labeled and unlabeled nodes (L,, U.), node similarities d(u, v) L.
2: Hyperparameter: step size parameter À E (0, (0,1).
3: Output: Graph parameter Ar for times & = 1,2,.... T.
4: Set wi (p) = 1 for all p E C
5: for t = 1, 2, do
6: Sample with probability (p(p)
(p) W. output as Pe. where We == Sc we (p)dp..
7: Compute the feedback set (p) containing Pt.
For example, for the min-cut objective use Algorithm 3 (Appendix C.5.1 and set (p) =
DYNAMICMINCUTTG, Pt, 1/vT). For the quadratic objective use Algorithm (Appendix
Pr, 8: Compute average loss function 4((p) |o,1 Enev UAGG Lu, (w), r())).
C to set A = HARMONICFEDDDACKSTTTT 1,,CG,,,,,.IVII..... 1/VT).
9: For each p E C, set (p) = aa (p) wi (p), where le(p) Jato pe(e) h(().
For the case of learning the unweighted threshold graph, computing the feedback set containing given r is easy as we only need the next and previous thresholds from among the O(n?) values of pairwise distances where loss may be discontinuous in r. We present algorithms for computing the semi-bandit feedback sets (constant performance interval containing any a) for the weighted graph setting (Definition) Tb.. We propose novel hybrid combinatorial-contine objective (Algorithm 3 Appendix C.5.T) which re-computes the mineut graph with dynamic edge weights by flow decomposition and careful flow augmentation is varied until a new mincut
algorithm for the mincut
7

---

is detected. For the harmonic objective, we can obtain similar efficiency (Algorithm 4 Appendix p. We seek points where fu(o) 2 for some u E U closest to given on- For each we can find the local minima of (fu(o)- ) or simply the root of [u(a) &/2 using gradient descent or Newton's 's method. The gradient computation uses matrix inversion which can be computed in (nn)) time, and we can obtain quadratic convergence rates for finding the root. Formally, we establish Theorem (Appendix C.
Theorem 9. For the each objective in Table I and exponential kernel (Definition 7.. there exists an algorithm which outputs the interval containing in time (n
5 Distributional setting
In the distributional setting, we are presented with instances of the problem assumed to be drawn from an unknown distribution D and want to learn the best value of the graph parameter p.. that is one that minimizes loss L LA(G()) in expectation over the data distribution D. We show a divergence in the weighted and unweighted graph learning problems. We analyze and provide asymptotically tight bounds for the pseudodimension of the set of loss functions parameterized by the graph family parameter p. i.c. H, = (AAGG())LL.)) I E PJ. For learning the unweighted threshold graphs, the pseudodimension is Oloog n) which implies existence of an efficient algorithm with generalization guarantees in this setting. However, the pseudodimension is shown to be (n)) for the weighted graph setting, and therefore smoothness assumptions are necessary for learning over the algorithm family. Both these bounds are shown to be tight up to constant factors.
We also establish uniform convergence guarantees. For the unweighted graph setting, our pseudodi- mension bounds are sufficient for uniform convergence. We resort to bounding the Rademacher complexity in the weighted graph setting which allows us to prove distribution dependent gener- alization guarantees, that hold under distributional niceness assumptions of Section 4.1 (unlike pseudodimension which gives generalization guarantees that are worst-case over the distribution). The online learning results above only work for smoothed but adversarial instances, while the pseudodimension-bant based distributional learning sample complexity results work for any type (no smoothness needed) of independent and identically distributed instances. So these results are not superseded by the online learning results and provide new upper and lower bounds for the problem.
Pseudodimension bounds. We provide an upper bound on the pseudodimension of the set of loss functions for unweighted graphs H. = (AA(a())1.))) |05r r < oo), where G(r) is specified by Definition [T.. Our bounds hold for general quadratic objectives (Table [ and imply learnability with polynomially many samples. For the upper bound, we show that given any m instances we can partition the real line into O(mn²) intervals such that all values of behave identically for all instances within any fixed interval. We also show an asymptotically tight lower bound on the pseudodimension of Hy, by presenting a collection of graph thresholds and precisely designed labeling instances which are shattered by the thresholds. For full proof details see Appendix D
Theorem 10. The pseudo-dimensiag of H, is @log n),, where n is number of graph nodes.
Proof Sketch. Upper bound. As r is increased from 0 to infinity, at most (2) + 1 distinct graphs may be obtained. Thus given set S of m instances (A L(),, ), we can partition the real line into Omm)) intervals such that all values of r behave identically for all instances within any fixed interval. The loss function is a piecewise constant with only 0(mn²) pieces. Each piece can have a witness above or below it as r is varied for the corresponding interval, and so the binary labeling of S is fixed in that interval. The pseudo-dimension m satisfies 2m < Omm²²) and is therefore (log n). Lower bound: We have three labeled nodes, a1 with label 0 and 6,, b2 labeled 1, and n' (()) unlabeled nodes U {uI,.... u J. We can show that given a sequence (ri...., .xx) , of values of it is possible to construct an instance with suitable true labels of U such that the loss as function of r oscillates above and below some witness as r' moves along the sequence of intervals (re, T241) At the initial threshold ro. all unlabeled points have a single incident edge, connecting to 41, so all predicted labels are O. As the threshold is increased to r;, (the distances are set so that) u, gets connected to both nodes with label 1 and its predicted label changes to 1. If the sequence of nodes u; alternately labeled, the loss decreases and increases alternately as all the predicted labels turn to I as r is increased to rwy This oscillation between a high and low value can be achieved for any
8

---

03
(a) MNIST
(b) Omniglot
(c) CIFAR-10
Figure Multiple instances of the same problem, loss function of a.
subsequence distances r... Tw', and a witness may be set as a loss value between the oscillation limits. By precisely choosing the subsequences so that the oscillations align with the bit flips in the binary digit sequence, we can construct m instances which satisfy the 2nd shattering constraints. C
For learning weighted graphs G(o), we can show a (n) bound on the pseudodimension of the set co). The lower bound consists of inductively
of loss functions Ho (LA(G(O),E.U) LLU) 0 S constructed graphs with carefully set edges in a precisely designed sequence (Appendix D
Theorem 11. The pseudo-dimensee of H. is ((n).
Uniform convergence. Our results above implies a uniform convergence guarantee for the offline distributional setting, for both weighted and unweighted graph families. For the unweighted case, we can use the pseudodimension bounds above, and for the weighted case we use dispersion guarantees from section 4.1 For either case it suffices to bound the empirical Rademacher complexity. We will need the following theorem (slightly rephrased) from Balcan et al. [2018b].
Theorem 12. [Balcan et al. 2018b] Let == (fo :ffo:d X - 10.11.p0 C C Rd) be parametereized family of functiins, where C lies in ball of radius R. For any set suppose the functions Ux (p) [p(x;) for i E (T) are piecewise L-Lipschitz and ß-dispersed. Then R(F,8) < Ommin (d/TT) log RT + LT-3, (Pdim(F)/TT).
) X,
Now, using classic results from learning theory, conclude that ERM has good generalization.
Theorem 13. For both weighted and unweighted graph w(u, u) defined above, with probability at least 1 - 8, the average loss on any sample 21,..., IT ~ D". the loss suffered w.r.t. to any
parameter p Rd satisfies 1 +E to(xz) ExwDl(()) 50
(V dlog T log 1/6
Experiments
In this section we evaluate the performance of our learning procedures when finding application- specific semi-supervised learning algorithms (i.e. graph parameters). Our experiments demonstrate that the best parameter for different applications varies greatly, and that the techniques presented in this paper can lead to large gains. We look at image classification based on standard pixel embedding.
Setup: We consider the task of semi-supervised classfication image datasets. We restrict attention to binary classification and pick two classes (labels 0 or 1) for each dataset. We then draw random subsets of the dataset (with class restriction) of size 100 and randomly select J. examples for labeling. For any data subset S, we measure distance between any pairs of images using the L2 distance between their pixel intensities. We would like determine data-specific good values for o, when predictions are made by optimizing the harmonic objective (Table IT). We use three popular benchmark datasets MNIST [LeCun al., 1998). Omniglot [Lake al. 2015) and CIFAR- 10 [Szegedy et al.) [2015]. We generate a random semi-supervised learning instance from the data by sampling 100 random examples and further sampling L random examples from the subset for labeling.
L == 10 for MNIST, while I, 20 for Omniglot and CIFAR-10.
Code: https://drive. http::/aww..g.....o.......eeeeea

---

0.6
0.175
0.5
0.150
Average regret
Average ragret
0.4
Average regnet
0.125
0.12
0.3
0475
0.30
0.500
Time
Time
Time
(a) MNIST
(b) Omniglot
(c) CIFAR-10 10
Figure 3: Average regret for online learning of parameter
Resudts and discussion: For the MNIST dataset get optimal parameters with near-perfect classifi- cation even with small values of L. while for other datasets the error of the optimal parameter is over 0.1 even with larger values of L, indicating differences in the inherent difficulties of the classification tasks (like label noise and how well separated the classes are). We examine the full variation of performance of graph- semi- cumi-supervised learning for all possible graphs G( for a E [0, 10]. The losses are piecewise constant and can have large discontinuities in some cases. The optimal parameter values vary with the dataset, but we observe at least 10%, and up 80%, absolute gaps in performance between optimal and suboptimal values within the same dataset.
Another interesting observation is the variation of optima across data subsets, indicating transductively optimal parameters may not generalize well. We plot the variation of loss with parameter a for several subsets of the same size N 100 for MNIST and Omniglot datasets Figure In MNIST we have two optimal ranges in most subsets but only one shared optimum (around o 2) across different subsets. This indicates that local search based techniques that estimate the optimal parameter values on given data instance may lead to very poor performance on unseen instances. The CIFAR-10 example further shows that the optimal algorithm may not be easy empirically discern.
We also implement our online algorithms and compute the average regret for finding the optimal graph parameter a for the different datasets. To obtain smooth curves plot the average 50 iterations for learning from 50 problem instances each (T 50, Figure 3). We observe fast convergence the optimal parameter regret for all the datasets considered. The starting part of these curves (T' = 0) indicates regret for randomly setting the graph parameters, averaged over iterations, which is strongly outperformed by our learning algorithms as they learn from problem instances.
Ethics and broader impact
This work takes step in making cumi-supereised learning techniques domain independent and more practically effective. The resulting automation reduces dependence on human labelers and domain experts needed in current approaches. Dataset bias and ethics of applications will need be individually considered when applying our approach to real world problems.
8
Acknowledgments
This material is based on work supported by the National Science Foundation under grants CCF- 1535967, CCF-1910321, IIS-1618714, IIS-190140; and SES- 1919453; the Defense Advanced Research Projects Agency under cooperative agreement HR001 12020003; AWS Machine Learning Research Award; an Amazon Research Award: a Bloomberg Research Grant; Microsoft Research Faculty Fellowship. The views expressed in this work do not necessarily reflect the position the policy of the Government and no official endorsement should be inferred.
References
Doug Altner and Ozlem Ergun. Rapidly solving an online sequence of maximum flow problems. Integration of and OR Techniques Constraint Programming for Combinatorial Optimization Problems (L. Michel, ed.) (SSpinn,, pages 283-287, 2008.
10

---

Maria-Florina Balcan. Data- Driven Algorithm Design. In Tim Roughgarden, editor, Beyond Worst Case Analysis of Algorithms. Cambridge University Press, 2020.
Maria-Florina Balcan, Avrim Blum, Patrick Pakyan Choi, John Lafferty, Brian Pantano, Mu- gizi Robert Rwebangira, and Xiaojin Zhu. Person identification in webcam images: An application of semi-supervised learning. In ICML 2005 Workshop on Learning with Partially Classified Training Data, volume 2. page 6. 2005.
Maria-Flos Foria-Floriiaa Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. Learning theoretic -chreii- foundations of algorithm configuration for combinatorial partitioning problems. In Conference on Learning Theory, pages 213-274. PMLR, 2017.
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. In International conference on muchine learning, pages 344-353. PMLR, 2018a.
Maria-Flonee Firia--Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 604-614. IEEE, 2018b.
Maria-Florina Balcan, Travis Dick, and Manuel Lang. Learning to link. In International Conference on Learning Representations, 2019.
Maria-Florina Balcan, Avrim Blum, Dravyansh Sharma, and Hongyang Zhang, On the power of abstention and data-driven decision making for adversarial robustness. arXiv preprint arXiv:2010.06154, 2020a.
Maria-Florina Balcan, Travis Dick, and Wesley Pegden. Semi-bandit optimization in the dispersed setting. In Conference on Uncertainty in Artificial Intelligence, pages 909-918. PMLR, 2020b.
Maria-Florina Balcan, Travis Dick, and Dravyansh Sharma. Learning piecewise Lipschitz functions in changing environments. In International Conference on Artificial Intelligence and Statistics, pages 3567-3577. PMLR, 2020c.
Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Learning to optimize computational resources: Frugal training with generalization guarantees. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3227-3234, 2020d.
Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Refined bounds for algorithm config- uration: The knife-edge of dual class approximability. In International Conference on Machine Learning, pages 580-590. PMLR, 2020e.
Maria-Florina F Balcan, Travis Dick, and Colin White. Data-driven clustering via parameterized lloyd's families. Advances in Neural Information Processing Systems, 31:106411-0651, 2018c.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
Mikhail Belkin, Partha Niyogi. and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of machine learning research, (Nov):2399-24342 2006.
Avrim Blum. Technical perspective: Algorithm selection as a learning problem. Communications of the ACM, 63(6):86-86) 06, 2020.
Avrim Blum and Shuchi Chawla. Learning from labeled and unlabeled data using graph mincuts, In ICML, 2001.
Olivier Chapelle, Bernhard Schlkopf. and Alexander Zien. Semi-Supervised Learning. The MIT Press, 1st edition, 2010. ISBN 0262514125.
Matthew England and James H Davenport. The complexity of cylindrical algebraic decomposition with respect to polynomial degree. In International Workshop on Computer Algebra Scientific Computing, pages 172-192. Springer, 2016.

---

Bryan R Gibson, Timothy T Rogers, and Xiaojin Zhu. Human semi-supervised learning, Topics in cognitive science, 5(1):132-172, 2013.
Rishi Gupta and Tim Roughgarden. A PAC approach to application-speeifie algorithm selection. In Proceedings of the 7th Innovations Theoretical Computer Science Conference, 2016.
Rishi Gupta and Tim Roughgarden. A PAC approach to application-specifie algorithm selection.
SIAM Journal on Computing, 46(3):922-1017, 2017.
Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning 33056266):133--33388 through probabilistic program induction. Science, 350(6266): 1332-1338, 2015.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-22 2324, 1998.
David Pollard. Convergence of stochastic processes. Springer Science & Business Media, 2012.
Shai Shalev-Shwartz et Online learning and online convex optimization. Foundations and trends in Machine Learning, 1(7):107-194, 2011.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888- 888-9888-90 2000.
Vikas Sindhwani, Partha Niyogi, and Mikhail Belkin. Beyond the point cloud: from transductive to semi-supervised learning. In Proceedings of the 22nd international conference Machine learning, pages 824-831, 2005.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Du- mitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1-9, 2015.
Ellen Vitercik, compatibility. In ACM Conference on Economics and Computation, 2019.
Balcan, and Tuomas Sandholm. Estimating approximate incentive
Zhu Xiaojin and Ghahramani Zoubin. Learning from labeled and unlabeled data with label propaga- tion. Tech. Rep., Technical Report CMU-CALD-02-107, Carnegie Mellon University, 2002.
Richard Zemel and Miguel Carreira-Perpinán. Proximity graphs for clustering and manifold learning. Advances in neural information processing systems, 17:225-255 2004.
Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. Advances in neural information processing systems, 16(16):321-328. 2004.
Xiaojin Zhu and Andrew B Goldberg. Introduction to semi-supervised learning. Synthesis lectures on artificial intelligence and machine learning, 3(1):1-130, 2009.
Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi-super learning using Gaussian fields and harmonic functions. In Proceedings of the 20th International conference Machine learning (ICML-03), pages 912-919, 2003.
Xiaojin Zhu, John Lafferty, and Ronald Rosenfeld. Semi-supervised learning with graphs. PhD thesis, Carnegie Mellon University, Language Technologies Institute, 2005.
Xiaojin Zhu, Timothy Rogers, Ruichen Qian, and Chuck Kalish. Humans perform semi-supervised classification too. In AAAI, volume 2007, pages 864-870 164-870, 2007.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you deseribe the limitations of your work? [Yes] Remarked with results as
applicable, c.g. Theorem 7 does extend to mincut objective.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] URL.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A] Can be reproduced on personal computers within reasonable time (16GB, 2.3 GHz Dual-Core).
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "q7RaxGnS5kf", "reviewer": "Reviewer_YqaQ", "summary": "This paper proposes a data driven approach to construct graph for graph-based semi-supervised classification task. The authors realize the graph quality is important to learning performance and they aim to update the hyper-parameter when new samples come. They present the algorithms for two cases, online and distributional settings.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The task of updating hyper-parameter for creating graph is new. The method seems an extension of Balcan's work, but shows some novelty as focusing on different tasks. The related works are properly cited and major contributions are nicely stated.\n \nQuality: I have some concerns by reading this paper.\n1. If the number of data (L+U) is already large at time of t, the necessity of updating the hyper-parameter for the same domain instances are reduced? So I would like to know if the same domain indicates that data are drew from the identical distribution. If so, it strictly not online learning.\n2. It is observed that a target labeling tau is used for computing the loss l_A (line 111).  What is target labeling? Is it side-information compared to the regularized loss (line 43)? Because I have found tau is used in algorithm (step 7 in Alg 1)\n3. For the online setting, it seems every time a new sample comes the whole graph will be updated. Is it practical in real case? How about updating a small fraction of entries of w?\n4. I am new to regret loss. Is regret estimated from hindsight?\n5. Can we say regret in Fig 3(b) converges to the optimal parameter within 50 iterations?\n6. Some equations and symbols. Check inequality line 131; rho \\in P (line 108) but rho \\in C (line 131); definition of \\bar{U} (line 191), etc.\n7. I think it is better to say \"graph-based SSL\" in title.\n\nClarity: The submission clearly written except some typos.\n\nSignificance: As graph based semi-supervised learning is not popular for today's research due to its intrinsic limitations, the extension of the main theory from Balcan et al. for this task is not very interesting for me. But this paper is still valuable for some readers in the community. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have pointed out one limitation of this work (line 460). ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5h"}, "extra_text": {}}, {"review_id": "jMGVQ1v2Dy0", "reviewer": "Reviewer_HLTa", "summary": "This work presents novel theoretical tools for data-driven algorithm design. In particular, the authors generalise a dispersion-based analysis from intervals to axis-aligned paths of arbitrary dimension. \n\nUsing these new results, the authors study graph-based semi-supervised learning from a data-driven perspective and achieve strong bounds in the online and PAC setting. Their goal is to perform well on a fixed distribution of semi-supervised problem instances (or minimising the regret in the online setting) by selecting the most appropriate graph from a parametrised graph family (in particular: threshold graphs and graphs with edge weights given by the polynomial or RBF kernel). Many additional results, such as first experiments and lower bounds, are discussed.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a very interesting and important work studying semi-supervised learning from a data-driven perspective. It opens up many interesting follow-up questions and makes one interested in reading more on that topic. It is an important contribution to the problem of learning / constructing the graph for semi-supervised learning. \n\nEven though some parts (section 1, 2 and the first paragraph of section 4 with Theorem 5) are very well-written, the main technical sections of this work are quite dense and sometimes hard to follow. Notation and concepts are sometimes not well introduced and discussed. E.g., the $G(r)$ (and related) are not formally introduced. \n\nAlso, the proposed algorithms are only very briefly described. The notation and details are not really clear. Algorithm 2 is not referenced from the main text.\n\nSome more related previous papers could be discussed in more depth, in particular previous theoretical results on graph construction such as\n* Maier, Markus, Ulrike Von Luxburg, and Matthias Hein. \"Influence of graph construction on graph-based clustering measures.\" NIPS. Vol. 1025. 2008.\n\nand, for example, the discussions in:\n* Liu, Wei, Junfeng He, and Shih-Fu Chang. \"Large graph construction for scalable semi-supervised learning.\" ICML. 2010.\n* Jebara, Tony, Jun Wang, and Shih-Fu Chang. \"Graph construction and b-matching for semi-supervised learning.\" Proceedings of the 26th annual international conference on machine learning. 2009.\n\nSome additional minor comments:\n\n* line 41: $L+U$, why not use the common notation $L\\cup U$.\n* line 69: $G(\\rho)$ where $\\rho$ corresponds to a semi-supervised learning (SSL) algorithm. However later the authors rather use e.g., $G(r)$ or $G(\\sigma)$ to denote the parameter to construct the graph and not the SSL algorithm itself. This is a little bit confusing. It would also help a lot to properly define $G(r)$, $G(\\sigma)$, and $G(\\tilde{\\alpha})$,e.g., in Def. 1.\n* line 103: Is it allowed to have the same examples in $L$ and $U$?\n* In line 113, the authors call $d$ a similarity function (which would be large for similar examples), but seem to use it rather as a distance/metric (small for similar examples)\n* line 116: Why not use the more commonly used term $\\varepsilon$-neighbourhood graph ($\\varepsilon$-NN) instead of \"threshold graphs\". The name threshold graphs is also used to describe a particular unweighted graph family.\n* line 206: What embeddings do the authors mean here?\n* The set $C$ used in algorithm 1 and 2 is not defined nor described. Algorithm 1: Two dots \"..\" in line 6. Missing \"dp\" in line 9.\n* line 237: typo in \"existin\", -> \"exist in\"\n* line 408: reference: missing \"ö\" in Schölkopf. Also: the year seems to be wrong, the book was published in 2006, and is the ISBN really required?\n* a conclusion paragraph would be nice.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not discuss any limitations. In my opinion, there are some topics, which the authors might address:\n* Is it possible to get similar bounds for (one of the most commonly used similarity graph) $k$-nearest neighbour graphs ($k$-NNs)? Why do the authors have restricted their results to the other three types (threshold, polynomial, RBF)?\n* Do the results still hold when using other classification algorithms, e.g., learning with local and global (Zhou, et al. 2004) or GCNs?\n* This work mostly focuses on setting the edge-weights (or filtering edges) of the graph given feature-based distances. There might be scenarios where restricting the whole graph family (e.g., to trees) is more reasonable than just setting the weights. \n* The double exponential dependence on $p$ in Theorem 3 seems to be problematic. Please, discuss why this is theoretically / asymptotically not an issue. Also mention this in the main text, instead of hiding the \"constant\" in the $O(\\cdot)$. It seems to severely limit the practicability of these bounds. \n\n\nThe authors only briefly discuss societal impact. However, this is completely fine for such a conceptual and theoretical work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "dXIA2NW0OTf", "reviewer": "Reviewer_Evc7", "summary": "The authors suggest using repeated problem instances to learn input graphs for graph-based semi-supervised algorithms. They extend the concept of dispersion of one-dimensional algebraic polynomials to an arbitrary number of dimensions in order to provide uniform convergence guarantees for the gaussian graph kernel in unweighted offline training and a generalization bound for weighted graphs. They also offer a threshold graph approach for online training under the dispersity assumption that includes assurances in the form of a constraint on the algorithm's regret across repetitions. Finally, they show that the suggested offline technique leads to minimal regret across a large number of repetitions T.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written however there are a number of issues making that the paper is not ready for publication:", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Overall remarks:\n*Theorem3 is not self-content.\n* There are no comments on Theorem4's inequality: What does this outcome (inequality) imply?\n* The argument over how to test the dispersion assumption in the sequence of high-dimensional loss functions of graph parameters in practice is unclear.\n* The dataset size, n, is maintained relatively modest (n=100) compared to the size of the benchmark datasets that were utilized, most likely due to the high time complexity of the optimization process for learning the graph parameters (MNIST, CIFAR, Omnigot).\n* The low generalization of the optimal parameter values determined via transductive training, as shown in the experimental part, might be explained by the limited sample size used in training.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "PkFigWcdNh2", "reviewer": "Reviewer_vHeJ", "summary": "The authors propose to learn the underlying graphs for graph-based semi-supervised learning problems. So far, graph-based SSL usually grounds on KNN-like graphs where distances are computed according to some measure. The present paper now learns the parameters of the measures (kernels) as well as a threshold to determine whether an edge is present or not. ", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is a very interesting paper that introduces solid theoretical results that may have an impact in domains different from SSL. The derivations heavily build on different results by Balcan and colleagues and render the technical contribution very strong and convincing, including novel regret bound, algorithms, as well as generalization guarantees in probabilistic scenarios. The appendix is very helpful and gives many additional insights. \n\nI appreciate the authors response. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes in terms of limitations, there are no societal aspects. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers generally consider this a strong theoretical submission that should be accepted despite a few shortcomings in the experiments. The author feedback clarified a few open questions and should be incorporated in the final version. The reviewers appreciated the solid theoretical work with impact to graph-based semi-supervised learning and beyond.
Decision: Accept (Oral)