# Data driven semi-supervised learning

Maria-Florina Balcan
School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213
<EMAIL_ADDRESS>
&Dravyansh Sharma
Department of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213
<EMAIL_ADDRESS>
###### Abstract

We consider a novel data driven approach for designing learning algorithms
that can effectively learn with only a small number of labeled examples. This
is crucial for modern machine learning applications where labels are scarce or
expensive to obtain. 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 decades, several elegant
graph-based semi-supervised learning algorithms for how to infer 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
domain-specific art and heuristics 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 from commonly used parametric
families of graphs that perform well on new instances coming 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, providing general techniques to apply to large classes of
problems. We expect some of the tools and techniques we develop along the way
to be of interest beyond semi-supervised learning, for data driven algorithms
for combinatorial problems more generally.

##  1 Introduction

In recent years machine learning techniques have found gainful application in
diverse settings including textual, visual, or acoustic data. A major
bottleneck of the currently used approaches is the heavy dependence on
expensive labeled data. At the same time advances in cheap computing and
storage have made it relatively easier to store and process large amounts of
unlabeled data. Therefore, an important focus of the present research
community is to develop general (domain-independent) methods to learn
effectively from the unlabeled data, along with a small amount of labels.
Achieving this goal would significantly elevate the state-of-the-art machine
intelligence, which currently lags behind the human capability of learning
from a few labeled examples. Our work is a step in this direction, and
provides algorithms and guarantees that enable fundamental techniques for
learning from limited labeled data to provably adapt to problem domains.

Graph-based approaches have been popular for learning from unlabeled data for
the past two decades [38]. Labeled and unlabeled examples form the graph nodes
and (possibly weighted) edges denote the feature similarity between examples.
The implicit modeling assumption needed to make semi-supervised learning
possible is that the likelihood of having a particular label increases with
closeness to nodes of that label (Balcan and Blum [3]). 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
[18, 38], and all yield comparable results which strongly depend on the graph
used. A general formulation is described as follows, variations on which are
briefly discussed under related work.

Problem formulation: Given sets $L$ and $U$ of labeled and unlabeled examples
respectively, and a 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 $L+U$
as the nodes and weighted edges $W$ with $w(u,v)=g(d(u,v))$ for some
$g:\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$. We seek labels
$f(\cdot)$ for nodes $u$ of $G$ which minimize a regularized loss function
$l(f)=\alpha\sum_{v\in L}\hat{l}(f(v),y_{v})+\beta H(f,W)+\gamma\left\lVert
f\right\rVert^{2}$, under some constraints on $f$. The objective $H$ captures
the smoothness (regularization) induced by the graph (see Table 1 for
examples) and $\hat{l}(f(v),y_{v})$ is the misclassification loss (computed
here on labeled examples).

The graph $G$ takes a 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 $l(f)$, the effectiveness of which
crucially depends on $G$. Indeed the graph $G$ is expected to reflect a deep
understanding of the problem structure and how the unlabeled data is expected
to help. Despite the central role of $G$ in the semi-supervised learning
process, only some heuristics are known for setting the graph hyperparameters
[41]. There is no known principled study on how to do this and prior work
largely treats this as a domain-specific art. Is it possible to acquire the
required domain expertise, without involving human experts?

In this work we provide an affirmative answer by introducing data-driven
algorithms for building the graphs, that is techniques which learn a provably
good problem-specific graph from instances of a learning problem. More
precisely, we are required to solve not only one instance of the problem, but
multiple instances of the underlying algorithmic problem that come from the
same domain [2, 5, 23]. This approach allows us to model the problem of
identifying a good algorithm from data as an online or statistical learning
problem. We formulate the problem of creating the learning graph as a data-
specific decision problem, where we select the graph from well-known infinite
families of candidates which capture a range of ways to encode example
similarity. We show learning a near-optimal graph over these families is
possible in both online and distributional settings. In the process we
generalize and extend results developed in the context of other data-driven
learning problems, and obtain practical methods to build the graphs with
strong guarantees. In particular, we show that the approach may be used for
learning several parameters at once, and it is useful for learning a broader
class of parameters than previously known.

###  1.1 Our results

Semi-supervised learning: We consider common ways of creating the graph $G$
and formulating the regularized loss $l(f)$ as families of algorithms to learn
over, and by learning over these families determine the most suitable semi-
supervised learning method for any given problem domain. The graph is created
by setting the edge weights according to some (monotonic) function $g$ of the
similarity metric $d$, and is parameterized by $\rho$. We denote this graph by
$G(\rho)$ (omitting $d$ for conciseness). Note that each value of $\rho$
corresponds to a semi-supervised learning algorithm, where labels for the
unlabeled examples are predicted by optimizing over the graph $G(\rho)$ (i.e.,
similar nodes according to $G(\rho)$ get similar labels). We consider online
and distributional settings and provide efficient algorithms to obtain low
regret and low error respectively for learning $\rho$.

In the online setting, we receive problem instances $L_{i},U_{i}$ sequentially
and must predict labels $f_{i}$ for the $i$th instance before receiving the
next by optimizing over some graph $G(\rho_{i})$. We also observe the loss
$l(f)$ for prediction according to $G(\rho)$ for all $\rho$ (full information
setting) or some interval containing $\rho_{i}$ after our prediction (semi-
bandit setting). The performance is measured by the regret of our predictions
using $G(\rho_{i})$ relative to the optimal graph $G(\rho^{*})$ in hindsight.
Our key insight is to note that the loss is a piecewise constant function of
the parameter $\rho$ with dispersed discontinuities (Definition 4) under mild
smoothness assumptions on the similarity function, that the metric is not
exact and small perturbations to the similarities does not affect learning.
Roughly speaking, dispersion means that the discontinuities are not
concentrated in a small region, across instances. The full information setting
however can be computationally inefficient, since it involves computing the
loss for each of potentially prohibitively many constant performance “pieces”.
This is overcome by Algorithm 2 in the semi-bandit setting, where it is
sufficient to compute the loss for a small number of pieces contained in an
efficiently computable feedback set. Our implementation involves a novel min-
cut and flow recomputation algorithm on a graph with continuously changing
edge-weights, and may be of independent interest to the broader theory
community.

In the distributional setting, the problem instances are assumed to be sampled
according to some underlying distribution, and we would like to show PAC
bounds for learning with low error with a high confidence. We provide
asymptotically tight upper and lower bounds on the pseudodimension of learning
the best parameter from a parameterized family of semi-supervised learning
algorithms, each algorithm corresponding to a graph $G(\rho)$. We consider
both unweighted and weighted graph families. Our bounds imply efficient
algorithms with PAC guarantees for the unweighted setting, and hardness of
efficient learning of worst case instances of weighted graphs. For commonly
used approaches to create a weighted graph from a similarity metric, we show
efficient learning is still possible under the mild smoothness assumptions
used in the online setting above. The lower bounds are fairly technical and
involve constructing a family of graph instances while setting the distances
between graph nodes in a precise correlated manner to ensure that the loss as
a function of the parameter oscillates highly and at carefully determined
points in the domain.

Compared to known heuristics to build graphs which consider a fixed problem
instance, our approach may be viewed as building graphs by learning over
subsets of the full dataset (which previous approaches have not considered to
the best of our knowledge) and doing learning with these instances as examples
for the hyperparameter learning problem. The setting however is more general
and captures batches of partially labeled data arriving online or according to
some distribution.

Multiple metrics: In practice, we might have several natural, but very
different types of metrics for our problem. The Euclidean distance metric
$d(u,v)$ over the representation (embedding) of the examples alone may not
best capture the similarity measure between node pairs. When learning over
multiple channels or modes simultaneously, for example in detecting people or
activities from video footages, one needs to combine information from several
natural similarity metrics [4]. We can view this as a graph with multiple
hyperparameters $G(\rho_{1},\rho_{2},\dots)$, where the additional parameters
indicate relative importance of the different metrics. We show how to select a
provably good interpolation by generalizing results from [10] to multiple
parameters. We use tools from algebraic geometry including the
Tarski–Seidenberg theorem and properties of the cylindrical algebraic
decomposition to accomplish this.

Data-driven algorithm design: This work employs and extends powerful general
techniques and results for selecting algorithms from a parameterized family in
a data-driven way i.e. from several problem instances. Dispersion is a
property of problem sequences (observed online, or drawn from a distribution)
which has been shown to be necessary and sufficient for provably learning
optimal parameters for combinatorial algorithms [7, 11]. Algorithms for
learning dispersed instances are known for both full information and semi-
bandit online settings [7, 10]. We study data driven algorithm design for a
completely new setting, learning the graph for graph based semi-supervised
learning techniques, and undertake the technical work needed to understand the
underlying structure of the induced loss functions in these new settings. In
the process we extend general tools for deducing dispersion for general
algorithm design problems. Firstly, for one dimensional loss functions, we
show a novel structural result for proving dispersion when discontinuities
(for loss as function of the algorithm parameter) occur along roots of
exponential polynomials with random coefficients with bounded joint
distributions (previously shown only for algebraic polynomials [10]). This is
crucial for showing learnability in the Gaussian graph kernels setting.
Secondly, prior work [10] was only able to prove dispersion when the
discontinuities occur along algebraic curves with random coefficients in just
two dimensions. By a novel algebraic and learning theoretic argument we are
able to analyze higher dimensions, and show dispersion for an arbitrary
constant number of parameters, making it much more generally applicable.

Key challenges: We present the first theoretically grounded work outlining how
to create good graphs for learning from unlabeled data. Graph-based semi-
supervised learning literature has largely been focused on learning approaches
given a graph and very little progress made on the arguably more significant
problem of designing good graphs. The problem was noted by [41] and has
remained largely open for two decades. We use a data-driven algorithm design
perspective [7, 10] and take steps towards resolving this problem. We remark
that our techniques are very general and they apply simultaneously for
learning the graph when we do prediction by optimizing various quadratic
objectives with hard or soft labels (Table 1).

Online learning in our setting poses some interesting challenges. The loss
function is a non-Lipschitz function of the parameter, so usual gradient-based
approaches do not work. We use mild perturbation invariance assumptions to
show dispersion of the non-Lipschitzness which is necessary to overcome the
worst case lower bounds. Furthermore, most previously studied settings for
dispersion involve polynomially many discontinuities, so efficient algorithms
are immediate, which may not be the case for our setting. Instead we crucially
rely on semi-bandit algorithms to ensure that the parameters may be learned
efficiently, which involve development of careful local search techniques in
the parameter space. For weighted graphs and combinatorial optimizations, the
challenge of computing changing mincuts with continuously varying graph
weights requires a novel algorithm with combinatorial and continuous elements.
In the distributional setting, we provide lower bounds for the pseudo-
dimension of learning the algorithm, which require technical constructed
instances. In particular we seek to show instances with highly oscillating
loss functions at carefully determined points as the graph parameter is
varied, which is especially difficult for the weighted graph families. We note
that even for single-parameter families the lower bound is superconstant (for
example $\Omega(\log n)$ and even $\Omega(n)$).

Another key challenge we overcome is to show how the results may be extended
to tuning several graph hyperparameters at the same time, making our results
much more powerful. Similar results are known for linkage-based clustering [8]
but they crucially rely on the algorithm depending on relative distances and
not the actual values, and therefore do not extend to our setting. The problem
is significantly more complex than the one-dimensional problem as non-
Lipschitzness now occurs along high-dimensional surfaces instead of just
points of discontinuity for which learnability may be deduced by arguing about
the concentration of these points in intervals. For algebraic curves (learning
two parameters) one may use a bound on the number of local extrema and curve
intersections in a fixed direction [10], but we need a careful projection
argument and tools from algebraic geometry to generalize to higher dimensions.

Extension to active learning: We also consider an active learning setting
where we learn the graph for the graph-based active learning procedure for a
fixed constant label budget. We consider data-driven construction of the graph
family, where the labels used for semi-supervised learning are obtained by the
greedy active learning algorithm from [40]. The procedure selects the next
node which minimizes the expected estimated risk after querying the node. We
show how to learn a graph for which the budgeted active learning procedure,
followed by semi-supervised label predictions, results in provably near-
minimum loss.

###  1.2 Related work

Algorithm | $(\alpha,\beta,\gamma)$ | $H(f,W),\left\lVert\cdot\right\rVert$ | Constraints on $f$
---|---|---|---
A. Mincut (Blum and Chawla [16]) | $(\infty,1,0)$ | $f^{T}(D-W)f$ | $f\in\\{0,1\\}^{n}$
B. Harmonic functions (Zhu et al. [39]) | $(\infty,1,0)$ | $f^{T}(D-W)f$ | $f\in[0,1]^{n}$
C. Normalized cut (Shi and Malik [29]) | $(\infty,1,0)$ | $f^{T}(D-W)f$ | $f^{T}\mathbf{1}=0,f^{T}f=n^{2},$
|  |  | $f\in[0,1]^{n}$
D. Label propagation (Zhou et al. [37]) | $(1,\mu,1)$ |  $f^{T}\mathcal{L}f$, $\left\lVert\cdot\right\rVert_{2}$ | $f\in[0,1]^{n}$

Table 1:

Optimization using a quadratic objective involved in some prominent algorithms
for graph-based semi-supervised learning. Here
$D_{ij}:=\mathbb{I}[i=j]\sum_{k}W_{ik},\mathcal{L}:=D^{-1/2}(D-W)D^{-1/2}$ and
the objective is $l(f)=\alpha\sum_{u\in L}(f(u)-y_{u})^{2}+\beta
H(f,W)+\gamma\left\lVert f\right\rVert^{2}$.

Semi-supervised learning is a paradigm for learning from both labeled and
unlabeled data (Zhu and Goldberg [38]). It resembles human learning behavior
more closely than fully supervised and fully unsupervised models (Gibson et
al. [22], Zhu et al. [42]). Learning from unlabeled data may be possible due
to implicit compatibility between the target concept and the underlying data
distribution (Balcan and Blum [3]). A semi-supervised learning method makes a
particular compatibility assumption and provides a procedure to determine a
predictor which fits the labeled data well and has high compatibility.

Graph-based methods: A prominent and effective approach widely used in
practice for semi-supervised learning is to optimize a graph-based objective.
Here the compatibility assumption is that the labels are smooth over the
graph, and as such the performance is highly sensitive to the graph structure
and the edge weights. Since labels partition the graph, we seek a (possibly
soft) graph cut as the predictor. Several methods have been proposed to obtain
predictors given a graph including $st$-mincuts (Blum and Chawla [16]), soft
mincuts that optimize a quadratic energy objective (Zhu et al. [39]), label
propagation (Xiaojin and Zoubin [34]), and many more (Blum et al. [17], Belkin
et al. [14]). Table 1 summarizes the optimization involved in some prominent
algorithms. $\alpha=\infty$ corresponds to forcing labels of labeled examples
$L$.

However, it is not clear how to create the graph itself on which the extensive
literature stands, although some heuristics are known (Zhu et al. [41]). Zemel
and Carreira-Perpiñán [35] discuss how to create a robust graph by considering
an ensemble of minimum spanning trees for several data perturbations and
randomly retaining edges which appear often. The algorithm however uses a
parameter $t$ for expected graph density and it is unclear how to set it for
any given problem instance, and no theoretical guarantees are provided.
Sindhwani et al. [30] construct warped kernels more aligned with the data
geometry, but the performance may vary strongly with warping and it is not
clear how to optimize over it. To the best of our knowledge, we provide the
first techniques that yield provably near-optimal graphs. Prior art largely
compares semi-supervised graph learning in terms of assumption generality and
experimental evidence.

Data-driven design and dispersion: Gupta and Roughgarden [23] define a formal
learning framework for selecting algorithms from a family of heuristics or a
range of hyperparameters. The framework is further developed by Balcan et al.
[5] and its usefulness as a fundamental algorithm design perspective has been
noted [2, 15]. It has been successfully applied to several combinatorial
problems like integer programming and clustering [6, 8, 12] and for giving
powerful guarantees like adversarial robustness, adaptive learning and
differential privacy [7, 9, 11, 33]. Balcan [2] provides a simple introduction
to and a comprehensive survey on this rapidly expanding research direction.

Balcan et al. [7] introduce dispersion, a useful property of the problem
instances with respect to an algorithm family, which, if satisfied,
intuitively allows it to be efficiently learned in full information online as
well as distributional settings. Full information may be expensive to compute
and work with, and a semi-bandit algorithm is introduced by Balcan et al.
[10]. The same work also presents a general technique for analyzing dispersion
which is used to show dispersion when the non-Lipschitzness occurs along roots
of polynomials with random coefficients, for up to two parameters. We apply
dispersion in a new problem setting, and show how to learn algorithms for
semi-supervised learning of labels by carefully studying the properties of
these problems. We also extend the technique, and prove that dispersion holds
for a broader setting involving non-polynomial discontinuities and employ
tools from algebraic geometry to extend the theory to an arbitrary constant
number of parameters.

##  2 Notation and definitions

We are given some labeled points $L$ and unlabeled points $U$. One constructs
a graph $G$ by placing (possibly weighted) edges $w(u,v)$ between pairs of
data points $u,v$ 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 $G$ from some family $\mathcal{G}$ of graphs. We commit to using some
algorithm $A(G,L,U)$ (abbreviated as $A_{G,L,U}$) which provides labels for
examples in $U$, and we should pick a $G$ such that $A(G,L,U)$ results in
small error in its predictions on $U$. To summarize more formally,

Problem statement: Given data space $\mathcal{X}$, label space $\mathcal{Y}$
and an oracle $O$ which yields a number of labeled examples
$L\subset\mathcal{X}\times\mathcal{Y}$ and some unlabeled examples
$U\subset\mathcal{X}$ such that $|L|+|U|=n$. We are further given a
parameterized family of graph construction procedures over parameter space
$\mathcal{P}$,
$\mathcal{G}:\mathcal{P}\rightarrow(\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}_{\geq
0})$, graph labeling algorithm
$A:(\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}_{\geq 0})\times
2^{\mathcal{X}\times(\mathcal{Y}\cup\\{\perp\\})}\rightarrow(\mathcal{X}\rightarrow\mathcal{Y})$,
a loss function $l:\mathcal{Y}\times\mathcal{Y}\rightarrow[0,1]$ and a target
labeling $\tau:U\rightarrow\mathcal{Y}$. We need to select
$\rho\in\mathcal{P}$ such that corresponding graph $G(\rho)$ minimizes
$\sum_{U}l(A_{G(\rho),L,U}(u),\tau(u))$ w.r.t. $\rho$.

We will consider online and distributional settings of the above problem. In
the online setting we make no distributional assumptions about the data and
simply seek to minimize the regret, i.e. the loss suffered in an arbitrary
online sequence of oracle queries $O$ relative to that endured by the best
parameter $\rho^{*}$ in hindsight. In the distributional setting we will
assume that the data and labels supplied by $O$ come from an underlying
distribution $\mathcal{D}$ and we would like to minimize the expected loss
suffered on test examples drawn from the distribution with high probability.
We will present further details and notations for the respective settings in
the subsequent sections.

We will now describe graph families $\mathcal{G}$ and algorithms $A_{G,L,U}$
considered in this work. We assume there is a feature based similarity
function $d:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}_{\geq 0}$, a
metric which monotonically captures similarity between the examples. In
section 4.2.2, we will consider creating graphs with several similarity
functions, but for now assume we have a single $d$. Definition 1 summarizes
commonly used parametric methods to build a graph using the similarity
function.

In this work, we will consider three parametric families of graph construction
algorithms defined below. $\mathbb{I}[\cdot]$ is the indicator function taking
values in $\\{0,1\\}$.

######  Definition 1.

Graph kernels.

  1. a)

Threshold graph, $G(r)$. Parameterized by a threshold $r$, we set
$w(u,v)=\mathbb{I}[d(u,v)\leq r]$.

  2. b)

Polynomial kernel, $G(\tilde{\alpha})$.
$w(u,v)=(\tilde{d}(u,v)+\tilde{\alpha})^{d}$ for fixed degree $d$,
parameterized by $\tilde{\alpha}$.111With some notational abuse here, we have
$d$ as the integer degree of the polynomial, and $\tilde{d}(\cdot,\cdot)$ as
the similarity function.

  3. c)

Gaussian RBF or exponential kernel, $G(\sigma)$.
$w(u,v)=e^{-d(u,v)^{2}/\sigma^{2}}$, parameterized by $\sigma$.

######  Remark 1.

Another popular family of graphs used in practice is the $k$ nearest neighbor
graphs, where $k\in\\{0,1,\dots,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 hypothesis class (Section 3.1 of [28]), where
an upper bound of $O(\sqrt{T\log n})$ is known for the Weighted Majority
algorithm. Online-to-batch conversion provides generalization guarantees in
the distributional setting (Section 5 of [28]). We remark that our algorithm
families need more sophisticated analysis due to continuous ranges of the
algorithm parameters.

The threshold graph adds (unweighted) edges to $G$ only when the examples are
closer than some $r\in\mathbb{R}_{\geq 0}$, i.e. a step function of the
distance. Polynomial and exponential kernels add (weighted) edges to the
graph, with weights varying polynomially and exponentially (respectively) with
the similarity. Note that similarity function $\tilde{d}(u,v)$ in the
definition for polynomial kernels increases monotonically with similarity of
examples, as opposed to the other two222Common choices are setting $d(u,v)$ as
the Euclidean norm and $\tilde{d}(u,v)$ as the dot product when
$u,v\in\mathbb{R}^{n}$. Usually the threshold graph setting (Definition 1a)
will be easier to optimize over, but it is also a small parameter family often
with relatively weaker performance in practice. In the following, we will
refer to this setting by the unweighted graph setting, and the other two
settings (Definitions 1b and 1c) by the weighted graph setting. Often we will
discuss just the Gaussian RBF setting since it is more technically challenging
and more commonly used in practice for building graphs. However, in some
instances working through the polynomial kernel setting can provide useful
insights.

Once the graph is constructed using one of the above kernels, we can assign
labels using a suitable algorithm $A_{G,L,U}$. A popular and effective
approach is by optimizing a quadratic objective
$\frac{1}{2}\sum_{u,v}w(u,v)(f(u)-f(v))^{2}=f^{T}(D-W)f$. Here $f$ may either
be discrete $f(u)\in\\{0,1\\}$ which corresponds to finding a graph mincut
separating the oppositely labeled vertices [16], or $f$ may be continuous,
i.e. $f\in[0,1]$, and we can round $f$ to obtain the labels [39]. These
correspond to algorithms A and B respectively from Table 1. It is noted that
all algorithms have comparable performance provided the graph $G$ encodes the
problem well [38]. We restrict our attention to these two algorithms for
simplicity of presentation, although our algorithms and proofs may be extended
to any quadratic objective based algorithm in Table 1333Specifically by
extending arguments for algorithm B since the optimization is similar. In
contrast, Algorithm A is combinatorial and the reasoning diverges somewhat..

Finally we note definitions of some useful learning theoretic complexity
measures. First recall the definitions of pseudodimension and Rademacher
complexity, well-known measures for hypothesis-space complexity in statistical
learning theory. Bounding these quantities implies immediate bounds on
learning error using classic learning theoretic results. In Section 4.3 we
will bound the pseudodimension and Rademacher complexity for the problems of
learning unweighted and weighted graphs.

######  Definition 2.

Pseudo-dimension [27]. Let $\mathcal{H}$ be a set of real valued functions
from input space $\mathcal{X}$. We say that
$C=(x_{1},\dots,x_{m})\in\mathcal{X}^{m}$ is pseudo-shattered by $\mathcal{H}$
if there exists a vector $r=(r_{1},\dots,r_{m})\in\mathbb{R}^{m}$ (called
“witness”) such that for all $b=(b_{1},\dots,b_{m})\in\\{\pm 1\\}^{m}$ there
exists $h_{b}\in\mathcal{H}$ such that
$\text{sign}(h_{b}(x_{i})-r_{i})=b_{i}$. Pseudo-dimension of $\mathcal{H}$ is
the cardinality of the largest set pseudo-shattered by $\mathcal{H}$.

######  Definition 3.

Rademacher complexity [13]. Let
$\mathcal{F}=\\{f_{\rho}:\mathcal{X}\rightarrow[0,1],\rho\in\mathcal{C}\subset\mathbb{R}^{d}\\}$
be a parameterized family of functions, and sample
$\mathcal{S}=\\{x_{i},\dots,x_{T}\\}\subseteq\mathcal{X}$. The empirical
Rademacher complexity of $\mathcal{F}$ with respect to $\mathcal{S}$ is
defined as
$\hat{R}(\mathcal{F},\mathcal{S})=\mathbb{E}_{\mathbf{\sigma}}\left[\sup_{f\in\mathcal{F}}\frac{1}{T}\sum_{i=1}^{T}\sigma_{i}f(x_{i})\right]$,
where $\sigma_{i}\sim U(\\{-1,1\\})$ are Rademacher variables.

We will also need the definition of dispersion which, informally speaking,
captures how amenable a non-Lipschitz function is to online learning. As noted
in [7, 11], dispersion is necessary and sufficient for learning piecewise
Lipschitz functions.

######  Definition 4.

Dispersion [10]. The sequence of random loss functions $l_{1},\dots,l_{T}$ is
$\beta$-dispersed for the Lipschitz constant $L$ if, for all $T$ and for all
$\epsilon\geq T^{-\beta}$, we have that, in expectation, at most
$\tilde{O}(\epsilon T)$ functions (the soft-O notation suppresses dependence
on quantities beside $\epsilon,T$ and $\beta$, as well as logarithmic terms)
are not $L$-Lipschitz for any pair of points at distance $\epsilon$ in the
domain $\mathcal{C}$. That is, for all $T$ and for all $\epsilon\geq
T^{-\beta}$,

$\displaystyle\mathbb{E}\left[\max_{\begin{subarray}{c}\rho,\rho^{\prime}\in\mathcal{C}\\\
\left\lVert\rho-\rho^{\prime}\right\rVert_{2}\leq\epsilon\end{subarray}}\big{\lvert}\\{t\in[T]\mid
l_{t}(\rho)-l_{t}(\rho^{\prime})>L\left\lVert\rho-\rho^{\prime}\right\rVert_{2}\\}\big{\rvert}\right]\leq\tilde{O}(\epsilon
T).$

##  3 New general dispersion-based tools for data-driven design

We present new techniques and generalize known tools for analyzing data-driven
algorithms [7, 10]. 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. Balcan et al. [10]
provide a general tool for verifying dispersion if non-Lipschitzness occurs
along roots of (algebraic) polynomials in one and two dimensions. We improve
the results in the following two ways.

Our first result is that dispersion for one-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 a bounded joint distribution. In addition to generalizing prior
results, we present a new simpler proof. The full proof appears in Appendix
A.2.

######  Theorem 5.

Let $\phi(x)=\sum_{i=1}^{n}a_{i}e^{b_{i}x}$ be a random function, such that
coefficients $a_{i}$ are real and of magnitude at most $R$, and distributed
with joint density at most $\kappa$. Then for any interval $I$ of width at
most $\epsilon$, P($\phi$ has a zero in $I$)$\leq\tilde{O}(\epsilon)$
(dependence on $b_{i},n,\kappa,R$ suppressed).

###### Proof Sketch.

For $n=1$ there are no roots, so assume $n>1$. Suppose $\rho$ is a root of
$\phi(x)$. Then $\mathbf{a}=(a_{1},\dots,a_{n})$ is orthogonal to
$\varrho(\rho)=(e^{b_{1}\rho},\dots,e^{b_{n}\rho})$ in $\mathbb{R}^{n}$. For a
fixed $\rho$, the set $S_{\rho}$ of coefficients $\mathbf{a}$ for which $\rho$
is a root of $\phi(y)$ lie along an $n-1$ dimensional linear subspace of
$\mathbb{R}^{n}$. Now $\phi$ has a root in any interval $I$ of length
$\epsilon$, exactly when the coefficients lie on $S_{\rho}$ for some $\rho\in
I$. The desired probability is therefore upper bounded by
$\max_{\rho}\textsc{Vol}(\cup S_{y}\mid
y\in[\rho-\epsilon,\rho+\epsilon])/\textsc{Vol}(S_{y}\mid y\in\mathbb{R})$
which we will show to be $\tilde{O}(\epsilon)$. The key idea is that if
$|\rho-\rho^{\prime}|<\epsilon$, then $\varrho(\rho)$ and
$\varrho(\rho^{\prime})$ are within a small angle
$\theta_{\rho,\rho^{\prime}}=\tilde{O}(\epsilon)$ for small $\epsilon$ (the
probability bound is vacuous for large $\epsilon$). But any point in
$S_{\rho}$ is at most $\tilde{O}(\theta_{\rho,\rho^{\prime}})$ from a point in
$S_{\rho^{\prime}}$, which implies the desired bound.∎

We further go beyond single-parameter discontinuties, which occur as points
along a line to general small dimensional parameter spaces $\mathbb{R}^{p}$,
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 6), which implies dispersion
using a VC dimension based argument (Theorem 7). Our result is the first of
its kind, a general sufficient condition for dispersion for any constant
number $p$ of parameters, and applies to a broad class of algorithm families.
Full proofs may be found in Appendix A.3.

######  Theorem 6.

There is a constant $k$ depending only on $d$ and $p$ such that axis-aligned
line segments in $\mathbb{R}^{p}$ cannot shatter any collection of $k$
algebraic hypersurfaces of degree at most $d$.

###### Proof Sketch.

Let $\mathcal{C}$ denote a collection of $k$ algebraic hypersurfaces of degree
at most $d$ in $\mathbb{R}^{p}$. We say that a subset of $\mathcal{C}$ is hit
by a line segment if the subset is exactly the set of curves in $\mathcal{C}$
which intersect the segment, and hit by a line if some segment of the line
hits the subset. We can upper bound the subsets of $\mathcal{C}$ by line
segments in a fixed axial direction $x$ in two steps. Along a fixed line,
Bezout’s theorem bounds the number of intersections and therefore subsets hit
by different line segments. The lines along $x$ can further be shown to belong
to equivalence classes corresponding to cells in the cylindrical algebraic
decomposition of the projection of the hypersurfaces, orthogonal to $x$.
Finally, we can extend this to axis-aligned segments by noting they may hit
only $p$ times as many subsets. ∎

######  Theorem 7.

Let $l_{1},\dots,l_{T}:\mathbb{R}^{p}\rightarrow\mathbb{R}$ be independent
piecewise $\mathcal{L}$-Lipschitz functions, each having discontinuities
specified by a collection of at most $K$ algebraic hypersurfaces of bounded
degree. Let $L$ denote the set of axis-aligned paths between pairs of points
in $\mathbb{R}^{p}$, and for each $s\in L$ define $D(T,s)=|\\{1\leq t\leq
T\mid l_{t}\text{ has a discontinuity along }s\\}|$. Then we have
$\mathbb{E}[\sup_{s\in L}D(T,s)]\leq\sup_{s\in
L}\mathbb{E}[D(T,s)]+O(\sqrt{T\log(TK)})$.

###### Proof Sketch.

We relate the number of ways line segments can label vectors of $K$ algebraic
hypersurfaces of degree $d$ to the VC-dimension of line segments (when
labeling algebraic hypersurfaces), which from Theorem 6 is constant. To verify
dispersion, we need a uniform-convergence bound on the number of Lipschitz
failures between the worst pair of points $\rho,\rho^{\prime}$ at distance
$\leq\epsilon$, but the definition allows us to bound the worst rate of
discontinuties along any path between $\rho,\rho^{\prime}$ of our choice. We
can bound the VC dimension of axis aligned segments against bounded-degree
algebraic hypersurfaces, which will allow us to establish dispersion by
considering piecewise axis-aligned paths between points $\rho$ and
$\rho^{\prime}$. ∎

##  4 Data-driven semi-supervised learning

We will warm up this section with a simple example demonstrating the need for
and challenges posed by the problem of learning how to build a good graph from
data. We will then consider online and distributional settings in sections 4.2
and 4.3 respectively. For online learning we show how to employ and extend
dispersion based analysis to our setting, and obtain algorithms which learn
good graphs with low regret and are efficient to implement, under mild
assumptions on data niceness. For the distributional setting, we analyze the
pseudodimension and Rademacher complexity of our learning problems which imply
generalization guarantees for learning the graph parameters.

Transductive and inductive aspects: For semi-supervised learning, we may
distinguish the transductive setting where predictions are evaluated only on
provided unlabeled examples $U$, with the inductive setting where we also care
about new unseen examples coming from the same distribution. Graph-based
methods were originally introduced as transductive learning approaches [16,
34], but may be used in either setting. For induction we may recompute the
graph, or use a fixed subgraph (and assume that new points do not affect the
transductive labels) for more efficient prediction [20]. Our setting has an
inductive aspect since we learn a graph (by learning graph parameter values)
which we expect to use for unseen problem instances.

###  4.1 Any threshold may be optimal

We consider the setting of learning thresholds for unweighted graphs
(Definition 1a). We give a 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 in our setting.
The example below captures the intuition that any unlabeled point may get
weakly connected to examples from one class for a small threshold but may get
strongly connected to another class as the threshold is increased to a larger
value. Therefore depending on the unknown true label either threshold may be
optimal or suboptimal, and it makes sense to learn the correct value through
repeated problem instances.

######  Theorem 8.

Let $r_{\min}$ denote the smallest value of threshold $r$ for which every
unlabeled node of $G(r)$ is reachable from some labeled node, and $r_{\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_{\zeta}=\zeta
r_{\min}+(1-\zeta)r_{\max}$ for $\zeta\in(0,1)$, there exists a set of
labelings $\mathcal{U}$ of the unlabeled points such that for some
$U_{\zeta},\bar{U}_{\zeta}\in\mathcal{U}$, $r_{\zeta}$ minimizes
$l_{A(G(r),L,U_{\zeta})}$ but not $l_{A(G(r),L,\bar{U}_{\zeta})}$.

$\displaystyle L_{1}$$\displaystyle L_{2}$$\displaystyle a$$\displaystyle
r_{\min}={\textstyle\frac{r^{*}}{2}}$$\displaystyle r^{*}$$\displaystyle
r_{\max}$ Figure 1: $G(r)$ connects $a$ to nodes in $L_{1}$ for $r_{\min}\leq
r<r^{*}$.

###### Proof.

Note that for any $r<r_{\min}$, there is no graph similarity information for
at least one node, and therefore all labels cannot be predicted. Also, the
graph is unchanged for all $r\geq r_{\max}$. Therefore,
$r\in[r_{\min},r_{\max}]$ captures all graphs of interest on a given data
instance.

Intuitively the statement claims that any threshold $r$ (modulo the scaling
factors for the data embedding) may be optimal or suboptimal for some data
labeling for a given constructed instance. Therefore it is useful to consider
several problem instances and learn the optimal value of $r$ for the data
distribution. We will present an example where an unlabeled point is closest
to some labeled point of one class but closer to more points of another class
on average. So for small thresholds it may be labeled as the first class and
for larger thresholds as the second class.

Let $L=L_{1}\cup L_{2}$ with $|L_{1}|<|L_{2}|$ and $d(u,v)=0$ for $u,v\in
L_{i},i\in\\{1,2\\}$, $d(u,v)=3r^{*}/2$ for $u\in L_{i},v\in L_{j},i\neq j$,
where $r^{*}$ is a positive real. Further let $U=\\{a\\}$ such that
$d(a,u_{i})=ir^{*}/2$ for each $u_{i}\in L_{i}$. It is straightforward to
verify that the triangle inequality is satisfied. Further note that
$r_{\min}=r^{*}/2$ and $r_{\max}=3r^{*}/2$. Our set of labelings $\mathcal{U}$
will include one that labels $a$ according to each class. Now we have two
cases

  1. 1.

$\zeta\in(0,\frac{1}{2})$: $r_{\min}\leq r<r^{*}$, $G(r_{\zeta})$ connects $a$
to $L_{1}$ but not $L_{2}$ and we have that the loss is minimized exactly for
the labeling where $a$ matches $L_{1}$.

  2. 2.

$\zeta\in[\frac{1}{2},1)$: $r^{*}\leq r\leq r_{\max}$, $G(r_{\zeta})$ connects
$a$ to both $L_{1}$ and $L_{2}$. But since $|L_{1}|<|L_{2}|$, we predict that
the label of $a$ matches that of $L_{2}$.

Finally we note that $d(u,v)$ may not be exactly zero when $u\neq v$ for a
metric. This is easily fixed by making tiny perturbations to the labeled
points, for any given $r_{\zeta}$. ∎

The example presented above captures some essential challenges of our setting
in the following sense. Firstly, we see that the loss function may be non-
Lipschitz (as a function of the parameter $r$), which makes the optimization
problem more challenging. More importantly, it highlights that graph
similarity only approximately corresponds to label similarity, and how the
accuracy of this correspondence is strongly influenced by the graph
parameters. In this sense, it may not be possible to learn from a single
instance, and considering a data-driven setting is crucial.

###  4.2 Dispersion and online learning

We consider the problem of learning the graph online. In the online setting,
we are presented with instances of the problem and want to learn the best
value of the parameter $\rho$ while making predictions. We also assume we get
all the labels for past instances which may be used to determine the loss for
any $\rho$ (full information)444We can think of each problem instance to be of
a small size, so we do not need too many labels if we can learn with a
reasonable number of problem instances. We improve on the label requirement
further in the semi-bandit setting.. A choice of $\rho$ uniquely determines
the graph $G(\rho)$ (for example in single parameter families in Definition 1)
and we use some algorithm $A_{G(\rho),L,U}$ to make predictions (e.g.
minimizing the quadratic penalty score above) and suffer loss
$l_{A(G(\rho),L,U)}:=\sum_{u\in U}l(A_{G(\rho),L,U}(u),\tau(u))$ which we seek
to minimize relative to the best fixed choice of $\rho$ in hindsight.
Formally, at time $t\in[T]$ we predict $p_{t}\in\mathcal{P}$ (the parameter
space) based on labeled and unlabeled examples $(L_{i},U_{i}),i\in[t]$ and
past labels $\tau(u)$ for each $u\in U_{j},j<t$ and seek to minimize

$R_{T}:=\sum_{t=1}^{T}l_{A(G(\rho_{t}),L_{t},U_{t})}-\min_{\rho\in\mathcal{P}}\sum_{t=1}^{T}l_{A(G(\rho),L_{t},U_{t})}$

A key difficulty in the online optimization for our settings is that the
losses, as noted above, are discontinuous functions of the graph parameters
$\rho$. We can efficiently solve this problem if we can show that the loss
functions are dispersed, in fact $\frac{1}{2}$-dispersed functions may be
learned with $\tilde{O}(\sqrt{T})$ regret ([7, 11]). Algorithm 1 adapts the
general algorithm of [7] to data-driven graph-based learning and achieves low
regret for dispersed functions. Recall that dispersion roughly says that the
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 to show dispersion, and therefore
learnability. For further background and additional proofs and details from
this section, see Appendix A.

1: Input: Graphs $G_{t}$ with labeled and unlabeled nodes $(L_{t},U_{t})$ and
node similarities $d(u,v)_{u,v\in L_{t}\cup U_{t}}$.

2: Hyperparameter: step size parameter $\lambda\in(0,1]$.

3: Output: Graph parameter $\rho_{t}$ for times $t=1,2,\dots,T$.

4: Set $w_{1}(\rho)=1$ for all $\rho\in\mathbb{R}_{\geq 0}$.

5: for $t=1,2,\dots,T$ do

6: $W_{t}:=\int_{C}w_{t}(\rho)d\rho$.

7: Sample $\rho$ with probability $p_{t}(\rho)=\frac{w_{t}(\rho)}{W_{t}}$,
output as $\rho_{t}$.

8: Compute average loss function $l_{t}(\rho)=\frac{1}{|U_{t}|}\sum_{u\in
U}l(A_{G_{t}(\rho),L_{t},U_{t}}(u),\tau(u))$.

9: Set $u_{t}(\rho)=1-l_{t}(\rho)$ (loss is converted to utility function,
$u_{t}(\rho)\in[0,1]$).

10: For each $\rho\in C,\text{ set }w_{t+1}(\rho)=e^{\lambda
u_{t}(\rho)}w_{t}(\rho)$.

Algorithm 1 Data-driven Graph-based SSL ($\lambda$)

####  4.2.1 Dispersion of the loss functions

We start with showing dispersion for the unweighted graph family, with
threshold parameter $r$. Here dispersion follows from a simple assumption that
the distance $d(u,v)$ for any pair of nodes $u,v$ follows a $\kappa$-bounded
distribution555A density function $f:\mathbb{R}\rightarrow\mathbb{R}$
corresponds to a $\kappa$-bounded distribution if
$\max_{x\in\mathbb{R}}\\{f(x)\\}\leq\kappa$. For example,
$\mathcal{N}(\mu,\sigma)$ is $\frac{1}{2\pi\sigma}$-bounded for any $\mu$.,
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).

######  Lemma 9.

Let $\bar{l}(r)=l_{A(G(r),L,U)}$ be the loss function for graph $G(r)$ created
using the threshold kernel $w(u,v)=\mathbb{I}[d(u,v)\leq r]$. Then
$\bar{l}(r)$ is piecewise constant and any discontinuity occurs at
$r^{*}=d(u,v)$ for some graph nodes $u,v$.

###### Proof.

This essentially follows from the observation that as $r$ is increased, the
graph gets a new edge only for some $r^{*}=d(u,v)$. Therefore no matter what
the optimization algorithm is used to predict labels to minimize the loss, the
loss is fixed given the graph, and has discontinuities potentially only when
new edges are added. ∎

We can use it to show the following theorem.

######  Theorem 10.

Let $l_{1},\dots,l_{T}:\mathbb{R}\rightarrow\mathbb{R}$ denote an
independent666Note that the problems arriving online are adversarial. The
adversary is smoothed [31] in the sense it has a distribution which it can
choose as long as it has bounded density over the parameters, independent
samples are drawn from adversary’s distribution. sequence of losses as a
function of parameter $r$, when the graph is created using a threshold kernel
$w(u,v)=\mathbb{I}[d(u,v)\leq r]$ and labeled by applying any algorithm on the
graph. If $d(u,v)$ follows a $\kappa$-bounded distribution for any $u,v$, the
sequence is $\frac{1}{2}$-dispersed, and there is an algorithm (Algorithm 1)
for setting $r$ with regret upper bounded by $\tilde{O}(\sqrt{T})$.

###### Proof.

Assume a fixed but arbitrary ordering of nodes in each $V_{t}=L_{t}\cup U_{t}$
denoted by $V_{t}^{(i)},i\in[n]$. Define $d_{i,j}=\\{d(u,v)\mid
u=V_{t}^{(i)},v=V_{t}^{(j)},t\in[T]\\}$. Since $d_{i,j}$ is $\kappa$-bounded,
the probability that it falls in any interval of length $\epsilon$ is
$O(\kappa\epsilon)$. Since different problem instances are independent and
using the fact that the VC dimension of intervals is 2, with probability at
least $1-\delta/D$, every interval of width $\epsilon$ contains at most
$O\left(\kappa\epsilon T+\sqrt{T\log D/\delta}\right)$ discontinuities from
each $d_{i,j}$ (using Lemma 9). Now a union bound over the failure modes for
$d_{i,j}$ for different $i,j$ gives $O\left(n^{2}\kappa\epsilon
T+n^{2}\sqrt{T\log n/\delta}\right)$ discontinuities with probability at least
$1-\delta$ for any $\epsilon$-interval. Setting $\delta=1/\sqrt{T}$, for each
$\epsilon\geq 1/\sqrt{T}$ the maximum number of discontinuities in any
$\epsilon$-interval is at most $(1-\delta)O\left(\kappa n^{2}\sqrt{T\log
n\sqrt{T}}\right)+\delta T=\tilde{O}(\epsilon T)$, in expectation, proving
$\frac{1}{2}$-dispersion. ∎

We can show dispersion for weighted graph kernels as well, but under stronger
assumptions than before. We assume that distances $d(u,v)$ are jointly
$\kappa$-bounded on a closed and bounded support. The plan is to use results
for dispersion analysis from [10] (summarized in Appendix A.1), which implies
that roots of a random polynomial are dispersed provided it has finite
coefficients distributed jointly with a $\kappa$-bounded distribution. We
establish the following for learning polynomial kernels (full proof in
Appendix A.1).

######  Theorem 11.

Let $l_{1},\dots,l_{T}:\mathbb{R}\rightarrow\mathbb{R}$ denote an independent
sequence of losses as a function of parameter $\tilde{\alpha}$, when the graph
is created using a polynomial kernel
$w(u,v)=(\tilde{d}(u,v)+\tilde{\alpha})^{d}$ and labeled by optimizing the
quadratic objective $\sum_{u,v}w(u,v)(f(u)-f(v))^{2}$. If $\tilde{d}(u,v)$
follows a $\kappa$-bounded distribution with a closed and bounded support, the
sequence is $\frac{1}{2}$-dispersed, and the regret of Algorithm 1 may be
upper bounded by $\tilde{O}(\sqrt{T})$.

###### Proof Sketch.

$w(u,v)$ is a polynomial in $\tilde{\alpha}$ of degree $d$ and the
coefficients are $K\kappa$-bounded, where $K$ is a constant that only depends
on $d$ and the support of $\tilde{d}(u,v)$. Consider the harmonic solution of
the quadratic objective [39] which is given by
$f_{U}=(D_{UU}-W_{UU})^{-1}W_{UL}f_{L}$. For any $u\in U$, $f(u)=1/2$ is a
polynomial equation in $\tilde{\alpha}$ with degree at most $nd$. Therefore
the labeling, and consequently also the loss function, may only change when
$\tilde{\alpha}$ is a root of one of $|U|$ polynomials of degree at most $dn$.
The dispersion result is now a simple application of results from [10] (noted
as Theorems 22 and 23 in Appendix A.1). The regret bound is implied by Theorem
2 of [10].∎

######  Remark 2 (Extension to exponential kernel).

We can also extend the analysis to obtain similar results when using the
exponential kernel $w(u,v)=e^{-||u-v||^{2}/\sigma^{2}}$. The results of [10]
no longer directly apply as the points of discontinuity are no longer roots of
polynomials, and we need to analyze points of discontinuities of exponential
polynomials, i.e. $\phi(x)=\sum_{i=1}^{k}a_{i}e^{b_{i}x}$ (See Section 3 and
Appendix A.2). The number of discontinuities may be exponentially high in this
case. Indeed, solving the quadratic objective shows that discontinuities lie
at zeros of exponential polynomials with $k=O(|U|^{n})$ terms.

######  Remark 3 (Extension to local and global classification [37]).

Above results can be extended to the classification algorithm used in [37].
The key observation is that the labels are given by a closed-form matrix,
$f^{*}=(I-\alpha D^{-1/2}WD^{1/2})Y$ or $f^{*}=(D-\alpha W)Y$ (for the two
variants considered). For threshold graphs $G(r)$, the regret bound in Theorem
10 applies to any classification algorithm. Extension to polynomial kernels
$G(\tilde{\alpha})$ is described below. For fixed $\alpha$ (in the notation of
[37], in expression for $f^{*}$ above), the discontinuities in the loss as a
function of the parameter $\tilde{\alpha}$ lie along roots of polynomials in
the parameter $\tilde{\alpha}$ and therefore the same proof as Theorem 11
applies (essentially we get polynomial equations with slightly different but
still $K$-bounded coefficients). On the other hand, if we consider $\alpha$ as
another graph parameter, we can still learn the kernel parameter
$\tilde{\alpha}$ together with $\alpha$ by applying Theorem 22 and Theorem 7
(instead of Theorem 23) in the proof of Theorem 11.

####  4.2.2 Combining several similarity measures

Often the distance metric used for measuring similarity between the data
points is a heuristic, and we can have multiple reasonable metrics. Different
metrics may have their own advantages and issues and often a weighted
combination of metrics, say $\sum_{i}{\rho_{i}}d_{i}(\cdot,\cdot)$, works
better than any individual metric. This has been observed in practice for
semi-supervised learning [4]. The combination weights $\rho_{i}$ are
additional graph hyperparameters. A combination of metrics has been shown to
boost performance theoretically and empirically for linkage-based clustering
[8]. 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-dimensional parameters (Section 3), which implies the
multi-parameter analogue of Theorem 11, stated as follows. See Appendix A.3
for proof details.

######  Theorem 12.

Let $l_{1},\dots,l_{T}:\mathbb{R}^{p}\rightarrow\mathbb{R}$ denote an
independent sequence of losses as a function of parameters $\rho_{i},i\in[p]$,
when the graph is created using a polynomial kernel
$w(u,v)=(\sum_{i=1}^{p-1}\rho_{i}\tilde{d}(u,v)+\rho_{p})^{d}$ and labeled by
optimizing the quadratic objective $\sum_{u,v}w(u,v)(f(u)-f(v))^{2}$. If
$\tilde{d}(u,v)$ follows a $\kappa$-bounded distribution with a closed and
bounded support, the sequence is $\frac{1}{2}$-dispersed, and the regret may
be upper bounded by $\tilde{O}(\sqrt{T})$.

####  4.2.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 our setting in particular this is computationally infeasible for weighted
graphs since the number of pieces (in loss as a piecewise constant function of
the parameter) may be exponential in the worst case (see section 4.3.1).
Fortunately we have a workaround provided by Balcan et al. [10] where
dispersion implies learning in a semi-bandit setting as well. This setting
differs from the full information online problem as follows. In each round as
we select the parameter $\rho_{i}$, we only observe losses for a single
interval containing $\rho_{i}$ (as opposed to the entire domain). We call the
set of these observable intervals the feedback set, and these provide a
partition of the domain. The trade-off is slightly slower convergence, the
regret bound for these approaches is weaker (it is $O(\sqrt{K})$ in the size
$K$ of the feedback set instead of $O(\sqrt{\log K})$) but still converges to
optimum as $\tilde{O}(1/\sqrt{T})$.

1: Input: Graphs $G_{t}$ with labeled and unlabeled nodes $(L_{t},U_{t})$ and
node similarities $d(u,v)_{u,v\in L_{t}\cup U_{t}}$.

2: Hyperparameter: step size parameter $\lambda\in(0,1]$.

3: Output: Graph parameter $\rho_{t}$ for times $t=1,2,\dots,T$.

4: Set $w_{1}(\rho)=1$ for all $\rho\in C$

5: for $t=1,2,\dots,T$ do

6: $W_{t}:=\int_{C}w_{t}(\rho)d\rho$.

7: Sample $\rho$ with probability $p_{t}(\rho)=\frac{w_{t}(\rho)}{W_{t}}$,
output as $\rho_{t}$.

8: Compute the feedback set $A^{(t)}(\rho)$ containing $\rho_{t}$. For
example, for the min-cut objective use Algorithm 3 to set
$A^{(t)}(\rho)=\textsc{DynamicMinCut}(G_{t},\rho_{t},1/\sqrt{T})$, similarly
for the harmonic objective use Algorithm 4.

9: Compute average loss function $l_{t}(\rho)=\frac{1}{|U_{t}|}\sum_{u\in
U}l(A_{G_{t}(\rho),L_{t},U_{t}}(u),\tau(u))$.

10: Set $\hat{l}_{t}(\rho)=\frac{\mathbb{I}[\rho\in
A^{(t)}(\rho)]}{\int_{A^{(t)}(\rho)}p_{t}(\rho)}l_{t}(\rho)$.

11: For each $\rho\in C,\text{ set
}w_{t+1}(\rho)=e^{\lambda\hat{l}_{t}(\rho)}w_{t}(\rho)$.

Algorithm 2 Efficient Data-driven Graph-based SSL ($\lambda$)

For the case of learning the unweighted threshold graph, computing the
feedback set containing a given $r$ is easy as we only need the next and
previous thresholds from among the $O(n^{2})$ 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
$\sigma$) for the weighted graph setting (we will use Definition 1c for
concreteness, but the algorithms easily extend to Definition 1b). We propose a
hybrid combinatorial-continuous algorithm for the min cut objective and use
continuous optimization for the harmonic objective (recall objectives from
Table 1). See Appendix A.4 for background on the flow-cut terminology in
Algorithm 3, and for a complete proof of its correctness.

1: Input: Graph $G$ with unlabeled nodes, query parameter $\sigma_{0}$, error
tolerance $\epsilon$.

2: Output: Piecewise constant interval containing $\sigma_{0}$.

3: Use a max-flow algorithm to compute max-flow and min-cut $\mathcal{C}$ for
$G(\sigma)$, $\sigma_{h}=\sigma_{0}$.

4: Compute the flow decomposition of the max-flow, $\mathcal{F}$.

5: Let $f_{e}$ be a unique path flow (i.e. along an $st$-path, Definition 31)
through $e\in\mathcal{C}$.

6: Say $e$ is augmentable if flow $f_{e}$ can be increased by amount
$w_{e}(\sigma)-w_{e}(\sigma_{h})$ for some $\sigma>\sigma_{h}$. $e$ acts as
the bottleneck for increasing the flow $f_{e}$.

7: Initialize $S$ to $\mathcal{C}$ (a set of saturated edges).

8: while All edges $e\in S$ are augmentable, do

9: Increase flow in all $f_{e}$ for $e\in S$ to keep $e$ saturated.

10: Find first saturating edge $e_{1}\notin S$ for some $f_{e^{\prime}}$
($e^{\prime}\in S$) and $\sigma^{\prime}$ to within $\epsilon$.

11: Reassociate flow through $e_{1},e^{\prime}$ as $f_{e_{1}}$.
$f_{e^{\prime}}$ will now be along an alternate path in the residual
capacities graph (Definition 32).

12: Add $e_{1}$ to $S$.

13: Set $\sigma_{h}=\sigma^{\prime}$.

14: Similarly find the start of the interval $\sigma_{l}$ by detecting
saturation while reducing flows.

15: return $[\sigma_{l},\sigma_{h}]$.

Algorithm 3 $\textsc{DynamicMinCut}(G,\sigma_{0},\epsilon)$

######  Theorem 13.

For the mincut objective and exponential kernel (Definition 1c), Algorithm 3
outputs the interval containing $\sigma$ in time $O(n^{3}K(n,\epsilon))$,
where $K(n,\epsilon)$ is the complexity of solving an exponential equation
$\phi(y)=\sum_{i=1}^{n}a_{i}y^{b_{i}}=0$ to within error $\epsilon$ (for
example $K(n,\epsilon)=O(n\log\log\frac{1}{\epsilon})$ using Newton’s method
with quadratic convergence).

###### Proof Sketch.

Let $L_{1}$ and $L_{2}$ denote the labeled points $L$ of different classes. To
obtain the labels for $U$, we seek the smallest cut $(V_{1},V\setminus V_{1})$
of $G$ separating the nodes in $L_{1}$ and $L_{2}$. If $L_{i}\subseteq V_{1}$,
label exactly the nodes in $V_{1}$ with label $i$. The loss function,
$l(\sigma)$ gives the fraction of labels this procedure gets right for the
unlabeled set $U$.

It is easy to see, if the min-cut is the same for two values of $\sigma$, then
so is the loss function $l(\sigma)$. So we seek the smallest amount of change
in $\sigma$ so that the mincut changes. Consider a fixed value of
$\sigma=\sigma_{0}$ and the corresponding graph $G(\sigma_{0})$. We can
compute the max-flow on $G(\sigma)$, and simultaneously obtain a min-cut
$(V_{1},V\setminus V_{1})$ in time $O(n^{3})$. Clearly, all the edges in
$\partial V_{1}$ are saturated by the flow. For each $e_{i}\in\partial V_{1}$,
let $f_{i}$ denote the flow that saturated $e_{i}$. Note that the $f_{i}$ are
distinct. Now as $\sigma$ is increased, we increment each $f_{i}$ by the
additional capacity in the corresponding edge $e_{i}$, until an edge in
$E\setminus\partial V_{1}$ saturates (at a faster rate than the flow through
it). We now increment flows while keeping this edge saturated. The procedure
stops when we can no longer find an alternate path for some flow among the
unsaturated edges, which implies the existence of a new min-cut. This gives us
a new critical value of $\sigma$.

Finally note that each time we perform step 10 of the algorithm, a new
saturated edge stays saturated for all further $\sigma$ until the new cut is
found. So we can do this at most $O(n^{2})$ times. In each loop we need to
obtain the saturation condition for $O(n)$ edges. ∎

For the harmonic objective, we can obtain similar efficiency (Algorithm 4). We
seek points where $f_{u}(\sigma)=\frac{1}{2}$ for some $u\in U$ closest to
given $\sigma_{0}$. For each $u$ we can find the local minima of
$\left(f_{u}(\sigma)-\frac{1}{2}\right)^{2}$ or simply the root of
$f_{u}(\sigma)-\frac{1}{2}$ using gradient descent or Newton’s method. The
gradient computation requires $O(n^{3})$ time for matrix inversion, and we can
obtain quadratic convergence rates for finding the root.

######  Theorem 14.

For the harmonic function objective (Table 1) and exponential kernel
(Definition 1c), Algorithm 4 outputs the interval containing $\sigma$ within
accuracy $\epsilon$ in time $O(n^{4}K_{1}(\epsilon))$, where $K_{1}(\epsilon)$
is the complexity of convergence for Newton’s method
($K_{1}(\epsilon)=O(\log\log\frac{1}{\epsilon})$ under standard assumptions).

###### Proof.

The key observation is that any boundary point $\sigma^{\prime}$ of a piece
(where the loss function is constant) has $f_{u}(\sigma^{\prime})=\frac{1}{2}$
for some $u\in U$. This follows from continuity of $f_{u}(\sigma)$ (it is in
fact differentiable). Algorithm 4 simply estimates the locations of these
$\sigma^{\prime}$ closest to $\sigma_{0}$ for each $u$ (by using Newton’s
method) to find the root of $g_{u}(\sigma)=(f_{u}(\sigma)-\frac{1}{2})^{2}$.
For each of $O(n)$ nodes, Algorithm 4 computes the gradient and function value
of $g_{u}(\sigma)$ in $O(n^{3})$ time for different values of $\sigma$ until
convergence, which gives the bound on time complexity. ∎

1: Input: Graph $G$ with unlabeled nodes, query parameter $\sigma_{0}$, error
tolerance $\epsilon$.

2: Output: Piecewise constant interval containing $\sigma_{0}$.

3: Let $f_{U}=(D_{UU}-W_{UU})^{-1}W_{UL}f_{L}$ denote the harmonic objective
minimizer, where $D_{ij}:=\mathbb{I}[i=j]\sum_{k}W_{ik}$.

4: for all $u\in U$ do

5: Let $g_{u}(\sigma)=(f_{u}(\sigma)-\frac{1}{2})^{2}$.

6:
$\sigma_{1}=\sigma_{0}-\frac{g_{u}(\sigma_{0})}{g^{\prime}_{u}(\sigma_{0})}$,
where $g^{\prime}_{u}(\sigma)$ is given by  $\displaystyle\frac{\partial
g_{u}}{\partial\sigma}$
$\displaystyle=2\left(f_{u}(\sigma)-\frac{1}{2}\right)\frac{\partial
f_{u}}{\partial\sigma},$ $\displaystyle\frac{\partial f}{\partial\sigma}$
$\displaystyle=(I-P_{UU}^{-1})\left(\frac{\partial
P_{UU}}{\partial\sigma}f_{U}-\frac{\partial
P_{UL}}{\partial\sigma}f_{L}\right),$ $\displaystyle\frac{\partial
P_{ij}}{\partial\sigma}$ $\displaystyle=\frac{\frac{\partial
w(i,j)}{\partial\sigma}-P_{ij}\sum_{k\in L+U}\frac{\partial
w(i,k)}{\partial\sigma}}{\sum_{k\in L+U}w(i,k)},$ $\displaystyle\frac{\partial
w(i,j)}{\partial\sigma}$ $\displaystyle=\frac{2w(i,j)d(i,j)^{2}}{\sigma^{3}},$
where $P=D^{-1}W$.

7: $n=0$

8: while $|\sigma_{n+1}-\sigma_{n}|\geq\epsilon$ do

9: $n\leftarrow n+1$

10:
$\sigma_{n+1}=\sigma_{n}-\frac{g_{u}(\sigma_{n})}{g^{\prime}_{u}(\sigma_{n})}$

11: $\sigma_{u}=\sigma_{n+1}$

12: $\sigma_{l}=\max_{u}\\{\sigma_{u}\mid\sigma_{u}<\sigma_{0}\\}$,
$\sigma_{h}=\min_{u}\\{\sigma_{u}\mid\sigma_{u}>\sigma_{0}\\}$

13: return $[\sigma_{l},\sigma_{h}]$.

Algorithm 4 $\textsc{HarmonicFeedbackSet}(G,\sigma_{0},\epsilon)$

###  4.3 Distributional setting

In the distributional setting, we are presented with instances of the problem
assumed to be drawn from an unknown distribution $\mathcal{D}$ and want to
learn the best value of the graph parameter $\rho$. We also assume we get all
the labels for past instances (full information). A choice of $\rho$ uniquely
determines the graph $G(\rho)$ and we use some algorithm $A_{G(\rho),L,U}$ to
make predictions (e.g. minimizing the quadratic penalty score above) and
suffers loss $l_{A(G(\rho),L,U)}:=\sum_{U}l(A_{G(\rho),L,U}(u),\tau(u))$ which
we seek to minimize relative to smallest possible loss by some graph in the
hypothesis space, in expectation over the data distribution $\mathcal{D}$.

We will 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 (composed with the graph creation
algorithm family and the optimization algorithm for predicting labels)
prarmeterized by the graph family parameter $\rho$, i.e.
$\mathcal{H}_{\rho}=\\{l_{A(G(\rho),L,U)}\mid\rho\in\mathcal{P}\\}$. For
learning the unweighted threshold graphs, the pseudodimension is $O(\log n)$
which implies existence of an efficient algorithm with generalization
guarantees in this setting. However, the pseudodimension is shown to be
$\Omega(n)$ for the weighted graph setting, and therefore the smoothness
assumptions are necessary for learning over the algorithm family. Both these
bounds are shown to be tight up to constant factors (Section 4.3.1).

We establish uniform convergence guarantees in Section 4.3.2. For the
unweighted graph setting, our pseudodimension 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
generalization guarantees, that hold under distributional niceness assumptions
of Section 4.2.1 (unlike pseudodimension which gives generalization guarantees
that are worst-case over the distribution). These guarantees are derived by
extending our results in the dispersion setting, and follow under the same
perturbation invariance assumptions. Additional proofs and details from this
section may be found in Appendix B.

The online learning results above only work for smoothed but adversarial
instances, while the distributional learning sample complexity results based
on pseudodimension work for any types (no smoothness needed) of independent
and identically distributed instances. So these results are not superseded by
the online learning results, the settings are strictly speaking incomparable,
and the pseudodimension results in the distributional setting provide new
upper and lower bounds for the problem.

####  4.3.1 Pseudodimension bounds

We can efficiently learn the unweighted graph with polynomially many samples.
We show this by providing a bound on the pseudodimension of the set of loss
functions $\mathcal{H}_{r}=\\{l_{A(G(r),L,U)}\mid 0\leq r<\infty\\}$, where
$G(r)$ is specified by Definition 1a. Our bounds hold for both the min-cut and
quadratic objectives (Table 1).

######  Theorem 15.

The pseudo-dimension of $\mathcal{H}_{r}$ is $O(\log n)$, where $n$ is the
total number of (labeled and unlabeled) data points.

###### Proof.

There are at most ${\binom{n}{2}}$ distinct distances between pairs of data
points. As $r$ is increased from 0 to infinity, the graph changes only when
$r$ corresponds to one of these distances, and so at most $\binom{n}{2}+1$
distinct graphs may be obtained.
Thus given set $\mathcal{S}$ of $m$ instances $(A^{(i)},L^{(i)})$, we can
partition the real line into $O(mn^{2})$ intervals such that all values of $r$
behave identically for all instances within any fixed interval. Since $A$ and
therefore its loss is deterministic once $G$ is fixed, the loss function is a
piecewise constant with only $O(n^{2})$ 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 $\mathcal{S}$ is fixed in that interval. The pseudo-
dimension $m$ satisfies $2^{m}\leq O(mn^{2})$ and is therefore $O(\log n)$. ∎

We can also show an asymptotically tight lower bound on the pseudodimension of
$\mathcal{H}_{r}$. We do this by presenting a collection of graph thresholds
and well-designed labeling instances which are shattered by the thresholds. An
intuitive simplified sketch for the proof is included below, for full details
see Appendix B.

######  Theorem 16.

The pseudo-dimension of $\mathcal{H}_{r}$ is $\Omega(\log n)$.

###### Proof Sketch.

We have three labeled nodes, $a_{1}$ with label 0 and $b_{1},b_{2}$ labeled 1,
and $n^{\prime}=O(n)$ unlabeled nodes $U=\\{u_{1},\dots,u_{n^{\prime}}\\}$. We
can show that given a sequence $\\{r_{1},\dots,r_{n^{\prime}}\\}$ of values of
$r$, it is possible to construct an instance with suitable true labels of $U$
such that the loss as a function of $r$ oscillates above and below some
witness as $r$ moves along the sequence of intervals $(r_{i},r_{i+1})_{i\geq
0}$.

---

(a) $G(r_{i})$

(b) Loss oscillations in shattered instances

Figure 2: Graphs $G(r)$ as $r$ is varied, for lower bound construction for
pseudodimension of $\mathcal{H}_{r}$. Labels are set in the instances to match
bit flips in the sequence of binary numbers as shown.

At the initial threshold $r_{0}$, all unlabeled points have a single incident
edge, connecting to $a_{1}$, so all predicted labels are 0. As the threshold
is increased to $r_{i}$, (the distances are set so that) $u_{i}$ gets
connected to both nodes with label 1 and therefore its predicted label changes
to 1. If the sequence of nodes $u_{i}$ is alternately labeled, the loss
decreases and increases alternately as all the predicted labels turn to 1 as
$r$ is increased to $r_{n^{\prime}}$. This oscillation between a high and a
low value can be achieved for any subsequence of distances
$r_{1},\dots,r_{n^{\prime}}$, 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 $2^{m}$ shattering constraints. ∎

For learning weighted graphs, we can show a $\Theta(n)$ bound on the
pseudodimension of the set of loss functions. We show this for the loss
functions for learning graphs with exponential kernels,
$\mathcal{H}_{\sigma}=\\{l_{A(G(\sigma),L,U)}\mid 0\leq\sigma<\infty\\}$,
where $G(\sigma)$ is specified by Definition 1c. For simplicity of
presentation, the lower bound will be shown for the min-cut objective.

######  Theorem 17.

The pseudo-dimension of $\mathcal{H}_{\sigma}$ is $O(n)$, where $n$ is the
total number of (labeled and unlabeled) data points.

###### Proof.

This bound trivially follows by noting that we have $n$ vertices and therefore
only $2^{n}$ possible labelings in an instance. Thus, for $m$ problems,
$2^{m}\leq m2^{n}$ gives $m=O(n)$. ∎

######  Theorem 18.

The pseudo-dimension of $\mathcal{H}_{\sigma}$ is $\Omega(n)$.

###### Proof Sketch.

We first show that we can carefully set the distances between the examples so
that we have at least $2^{\Omega(n)}$ intervals of $\sigma$ such that
$G(\sigma)$ has distinct vertex sets as min-cuts in each interval. We start
with a pair of labeled nodes of each class, and a pair of unlabeled nodes
which may be assigned either label depending on $\sigma$. We then build the
graph in $N=(n-4)/2$ stages, adding two new nodes at each step with
meticulously chosen distances from existing nodes. Before adding the $i$th
pair $x_{i},y_{i}$ of nodes, there will be $2^{i-1}$ intervals of $\sigma$
such that the intervals correspond to distinct min-cuts which result in all
possible labelings of $\\{x_{1},\dots,x_{i-1}\\}$. Moreover, $y_{j}$ will be
labeled differently from $x_{j}$ in each of these intervals. The edges to the
new nodes will ensure that the cuts that differ exactly in $x_{i}$ will divide
each of these intervals giving us $2^{i}$ intervals where distinct mincuts
give all labelings of $\\{x_{1},\dots,x_{i}\\}$, and allowing an inductive
proof. The challenge is that we only get to set $O(i)$ edges in round $i$ but
seek properties about $2^{i}$ cuts, so we must do this carefully. The full
construction and proof is presented in Appendix B.

Finally, we use this construction to generate a set of $\Theta(n)$ instances
that correspond to cost functions that oscillate in a manner that helps us
pick $2^{\Omega(n)}$ values of $\sigma$ that shatter the samples. ∎

####  4.3.2 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 from section 4.3.1,
and for the weighted case we use dispersion guarantees from section 4.2. For
either case it suffices to bound the empirical Rademacher complexity. We will
need the following theorem (slightly rephrased) from [7].

######  Theorem 19.

Let
$\mathcal{F}=\\{f_{\rho}:\mathcal{X}\rightarrow[0,1],\rho\in\mathcal{C}\subset\mathbb{R}^{d}\\}$
be a parametereized family of functions, where $\mathcal{C}$ lies in a ball of
radius $R$. For any set
$\mathcal{S}=\\{x_{i},\dots,x_{T}\\}\subseteq\mathcal{X}$, suppose the
functions $u_{x_{i}}(\rho)=f_{\rho}(x_{i})$ for $i\in[T]$ are piecewise
L-Lipschitz and $\beta$-dispersed. Then $\hat{R}(\mathcal{F},\mathcal{S})\leq
O(\min\\{\sqrt{(d/T)\log RT}+LT^{-\beta},\sqrt{Pdim(\mathcal{F})/T}\\})$.

Now, using classic results from learning theory, we can conclude that
Empirical Risk Minimization has good generalization under the distribution.

######  Theorem 20.

For both weighted and unweighted graph $w(u,v)$ defined above, with
probability at least $1-\delta$, the average loss on any sample
$x_{1},\dots,x_{T}\sim D^{T}$, the loss suffered w.r.t. to any parameter
$\rho\in\mathbb{R}^{d}$ satisfies
$|\frac{1}{T}\sum_{i=1}^{T}l_{\rho}(x_{i})-\mathbb{E}_{x\sim
D}l_{\rho}(x)|\leq O\left(\sqrt{\frac{d\log T\log 1/\delta}{T}}\right)$.

##  5 Extension to active learning

So far we have considered an oracle which gives labeled and unlabeled points,
where the labels of the unlabeled points possibly revealed later but it does
not allow us to select a subset of the unlabeled points for which we obtain
the labels. A natural question to ask is if we can further reduce the need for
labels by active learning. The S2 algorithm of [19] allows efficient active
learning given the graph, but we would like to learn the graph itself. We will
present an algorithm which extends the approach of [40] to do data-driven
active learning with a constant budget $L$ of labels in a general (non-
realizable) setting.

We have the same problem setup as before (Section 2), except we will now learn
the set of labeled examples $L$ via an active learning procedure $A^{\prime}$.
We set $\ell:=|L|$ as the budget for the active learning which we will think
of as a small constant. $A^{\prime}$ takes as input the graph $G$, the budget
$\ell$ and outputs a set of nodes $L$ with $|L|=\ell$ to query labels for. In
our budgeted active learning setup we provide all the queries in a single
batch, we consider sequential querying in the next section. Let
$A^{\prime}(G,\ell)$ denote the set $L$ of labeled examples obtained using
$A^{\prime}$. In addition, we assume we are given a set of initially labeled
points $L_{0}$ (not included in the budget) consisting of some example from
each class of labels. This is needed for known graph-based active learning
procedures to work [40], our results in the next section imply upper bounds on
the size of $L_{0}$ for a purely unsupervised initialization. As with the
semi-supervised learning above, the effectiveness of the active learning also
heavily depends on how well the graph captures the label similarity.

We are interested in learning the graph parameter $\rho$ which minimizes the
loss $l_{A(G(\rho),L_{0}\cup A^{\prime}(G(\rho),\ell),U)}$ where $U$ is the
set of nodes not selected for querying by $A^{\prime}$. That is, we seek the
graph that works best with the combined active semi-supervised procedure for
predicting the labels (by learning over multiple problem instances). We will
consider the harmonic objective minimization as the semi-supervised algorithm
$A$. Several reasonable heuristics for $A^{\prime}$ may be considered, we will
restrict our attention to Algorithm 5 which adapts the greedy algorithm of
[40] to our budgeted setting. Our main contribution in this section is to
prove dispersion for the sequence of loss functions, which implies
learnability of the graph for the composite active semi-supervised procedure.
The loss function is piecewise constant in the parameter $\rho$, with
discontinuities corresponding to changes in algorithmic decisions in selecting
the labeling set $L$ and subsequent predictions for the unlabeled examples.
The following theorem establishes this for polynomial kernels, extensions to
other kernels may be made as before.

######  Theorem 21.

Let $l_{1},\dots,l_{T}:\mathbb{R}\rightarrow\mathbb{R}$ denote an independent
sequence of losses as a function of parameter $\tilde{\alpha}$, when the graph
is created using a polynomial kernel
$w(u,v)=(\tilde{d}(u,v)+\tilde{\alpha})^{d}$ and labeled by Algorithm 5
followed by predicting the remaining labels by optimizing the quadratic
objective $\sum_{u,v}w(u,v)(f(u)-f(v))^{2}$. If $\tilde{d}(u,v)$ follows a
$\kappa$-bounded distribution with a closed and bounded support, the sequence
is $\frac{1}{2}$-dispersed.

###### Proof Sketch.

The proof reuses ideas from the proof of Theorem 11 with additional insights
to handle the dependence of the loss functions on the budgeted active learning
procedure. Discontinuities in the loss function may only occur when the label
set from the active procedure changes (which only happens if $u^{S}=u^{T}$ for
some candidate subsets $S\neq T$ in Algorithm 5) or when the semi-supervised
prediction changes ($f(u)=1/2$ for the soft labeling using the full labeled
set after active learning). We show that both kinds of discontinuities lie
along roots of polynomials with bounded discontinuities and are therefore
dispersed. Detailed argument appears in Appendix C∎

1: Input: Graph $G$ with unlabeled nodes, initial labels $L_{0}$, label budget
$\ell$.

2: Output: Nodes for label query $L$, $|L|=\ell$.

3: Compute soft labeling $f$ to minimize the harmonic objective $f^{T}(D-W)f$
using initial labels $L_{0}$.

4: for each subset $S$ of unlabeled nodes, $|S|=\ell$ do

5: for each labeling $L_{S}\in\\{0,1\\}^{\ell}$ of $S$ do

6: Estimate probability of $L_{S}$, $p^{L_{S}}=\Pi_{s\in
S}[L_{S}(s)f_{s}+(1-L_{S}(s))(1-f_{s})]$.

7: Compute soft labels $f^{L_{S}}$, by minimizing the harmonic objective with
labels $L_{S}$ for $S$ (in addition to $L_{0}$).

8: Estimate uncertainty as
$u^{L_{S}}=\sum_{i}\frac{1}{2}-\lvert\frac{1}{2}-f^{L_{S}}_{i}\rvert$.

9: Return $\operatorname*{arg\,min}_{S}u^{S}$ where
$u^{S}:=\sum_{L_{S}}p^{L_{S}}u^{L_{S}}$.

Algorithm 5 $\textsc{BudgetedActiveLearning}(G,\ell)$

We remark that while we have only considered learning the graph family with
the active learning procedure of [40], but it would be interesting to extend
our results to other similar active learning algorithms [26, 36].

##  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 will look at image classification based on
standard pixel embedding for different datasets.

(a) MNIST

(b) Omniglot

(c) CIFAR-10

Figure 3: Loss for different unweighted graphs as a function of the threshold
$r$.

(a) MNIST

(b) Omniglot

(c) CIFAR-10

Figure 4: Loss for different weighted graphs as a function of the parameter
$\sigma$.

Setup: We consider the task of semi-supervised classfication on image
datasets. We restrict our attention to binary classification and pick two
classes for each data set. We then draw random subsets of the dataset (with
class restriction) of size $n=100$ and randomly select $L$ ($10\leq L\leq 20$)
examples for labeling. For any data subset $S$, we measure distance between
any pairs of images using the $L_{2}$ distance between their pixel
intensities. We would like to determine data-specific parameters $r$ and
$\sigma$ which lead to good weighted and unweighted graphs for semi-supervised
learning on the datasets. We will optimize the harmonic function objective
(Table 1) and round the fractional labels $f$ to make our predictions.

Data sets: We use three popular benchmark datasets — MNIST, Omniglot and
CIFAR-10. The MNIST dataset [25] contains images of hand-written digits from 0
to 9 as $28\times 28$ binary images, with 5000 training examples for each
class. We consider examples with labels 0 or 1. We generate a random semi-
supervised learning instance from this data by sampling $100$ random examples
and further sampling $L=10$ random examples from the subset for labeling.
Omniglot [24] has $105\times 105$ binary images of handwritten characters
across 30 alphabets with 19,280 examples. We consider the task of
distinguishing alphabets 0 and 1, and set $L=20$ in this setting. CIFAR-10
[32] has $32\times 32$ color images (an integer value in $[0,255]$ for each of
three colors) for object recognition among 10 classes. Again we consider
objects 0 and 1 and set $L=20$.

Results and discussion: For the MNIST dataset we get optimal parameters with
near-perfect classification even with small values of $L$, while the error of
the optimal parameter is $\sim 0.2-0.3$ 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-based semi-supervised learning for
all possible graphs $G(r)$ ($r_{\min}<r<r_{\max}$) and $G(\sigma)$ for
$\sigma\in[0,10]$ (Figures 3, 4). 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% gap in performance between
optimal and suboptimal values within the same dataset.

Another interesting observation is the variation of optima across subsets,
indicating transductively optimal parameters may not generalize well. We plot
the variation of loss with graph parameter $\sigma$ for several subsets of the
same size $N=100$ for MNIST and Omniglot datasets in Figure 5. In MNIST we
have two optimal ranges in most subsets but only one shared optimum (around
$\sigma=2$) across different subsets. This indicates that local search based
techniques that estimate the optimal parameter values on a 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 to empirically
discern.

(a) MNIST

(b) Omniglot

(c) CIFAR-10

Figure 5: Comparing different subsets of the same problem.

(a) MNIST

(b) Omniglot

(c) CIFAR-10

Figure 6: Average regret vs. $T$ for online learning of parameter $\sigma$

We also implement our online algorithms and compute the average regret (i.e.
excess error in predicting labels of unlabeled examples over the best
parameter in hindsight) for finding the optimal graph parameter $\sigma$ for
the different datasets. To obtain smooth curves we plot the average over 50
iterations for learning from 50 problem instances each ($T=50$, Figure 6). We
observe fast convergence to 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.

##  7 Acknowledgments

This material is based on work supported by the National Science Foundation
under grants CCF-1535967, CCF-1910321, IIS-1618714, IIS-1901403, and
SES-1919453; the Defense Advanced Research Projects Agency under cooperative
agreement HR00112020003; an AWS Machine Learning Research Award; an Amazon
Research Award; a Bloomberg Research Grant; a Microsoft Research Faculty
Fellowship. The views expressed in this work do not necessarily reflect the
position or the policy of the Government and no official endorsement should be
inferred.

## References

  * Altner and Ergun [2008] Doug Altner and Ozlem Ergun.  Rapidly solving an online sequence of maximum flow problems.  _Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (L. Michel, ed.),(Spain)_ , pages 283–287, 2008.
  * Balcan [2020] Maria-Florina Balcan.  Book chapter Data-Driven Algorithm Design.  In _Beyond Worst Case Analysis of Algorithms, T. Roughgarden (Ed)_. Cambridge University Press, 2020.
  * Balcan and Blum [2010] Maria-Florina Balcan and Avrim Blum.  A discriminative model for semi-supervised learning.  _Journal of the ACM (JACM)_ , 57(3):1–46, 2010\.
  * Balcan et al. [2005] Maria-Florina Balcan, Avrim Blum, Patrick Pakyan Choi, John Lafferty, Brian Pantano, Mugizi 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.
  * Balcan et al. [2017] Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White.  Learning-theoretic foundations of algorithm configuration for combinatorial partitioning problems.  In _Conference on Learning Theory_ , pages 213–274. PMLR, 2017.
  * Balcan et al. [2018a] Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik.  Learning to branch.  In _International conference on machine learning_ , pages 344–353. PMLR, 2018a.
  * Balcan et al. [2018b] Maria-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 603–614. IEEE, 2018b.
  * Balcan et al. [2019] Maria-Florina Balcan, Travis Dick, and Manuel Lang.  Learning to link.  In _International Conference on Learning Representations_ , 2019.
  * Balcan et al. [2020a] 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.
  * Balcan et al. [2020b] 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.
  * Balcan et al. [2020c] 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.
  * Balcan et al. [2018c] Maria-Florina F Balcan, Travis Dick, and Colin White.  Data-driven clustering via parameterized lloyd’s families.  _Advances in Neural Information Processing Systems_ , 31:10641–10651, 2018c.
  * Bartlett and Mendelson [2002] 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.
  * Belkin et al. [2006] Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani.  Manifold regularization: A geometric framework for learning from labeled and unlabeled examples.  _Journal of machine learning research_ , 7(Nov):2399–2434, 2006.
  * Blum [2020] Avrim Blum.  Technical perspective: Algorithm selection as a learning problem.  _Communications of the ACM_ , 63(6):86–86, 2020\.
  * Blum and Chawla [2001] Avrim Blum and Shuchi Chawla.  Learning from labeled and unlabeled data using graph mincuts.  In _ICML_ , 2001.
  * Blum et al. [2004] Avrim Blum, John Lafferty, Mugizi Robert Rwebangira, and Rajashekar Reddy.  Semi-supervised learning using randomized mincuts.  In _Proceedings of the twenty-first international conference on Machine learning_ , page 13, 2004.
  * Chapelle et al. [2010] Olivier Chapelle, Bernhard Schlkopf, and Alexander Zien.  _Semi-Supervised Learning_.  The MIT Press, 1st edition, 2010.  ISBN 0262514125.
  * Dasarathy et al. [2015] Gautam Dasarathy, Robert Nowak, and Xiaojin Zhu.  S2: An efficient graph based active learning algorithm with application to nonparametric classification.  In _Conference on Learning Theory_ , pages 503–522, 2015.
  * Delalleau et al. [2005] Olivier Delalleau, Yoshua Bengio, and Nicolas Le Roux.  Efficient non-parametric function induction in semi-supervised learning.  In _AISTATS_ , volume 27, page 100, 2005.
  * England and Davenport [2016] Matthew England and James H Davenport.  The complexity of cylindrical algebraic decomposition with respect to polynomial degree.  In _International Workshop on Computer Algebra in Scientific Computing_ , pages 172–192. Springer, 2016.
  * Gibson et al. [2013] Bryan R Gibson, Timothy T Rogers, and Xiaojin Zhu.  Human semi-supervised learning.  _Topics in cognitive science_ , 5(1):132–172, 2013.
  * Gupta and Roughgarden [2017] Rishi Gupta and Tim Roughgarden.  A PAC approach to application-specific algorithm selection.  _SIAM Journal on Computing_ , 46(3):992–1017, 2017.
  * Lake et al. [2015] Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum.  Human-level concept learning through probabilistic program induction.  _Science_ , 350(6266):1332–1338, 2015.
  * LeCun et al. [1998] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Long et al. [2008] Jun Long, Jianping Yin, Wentao Zhao, and En Zhu.  Graph-based active learning based on label propagation.  In _International Conference on Modeling Decisions for Artificial Intelligence_ , pages 179–190. Springer, 2008.
  * Pollard [2012] David Pollard.  _Convergence of stochastic processes_.  Springer Science & Business Media, 2012.
  * Shalev-Shwartz et al. [2011] Shai Shalev-Shwartz et al.  Online learning and online convex optimization.  _Foundations and trends in Machine Learning_ , 4(2):107–194, 2011.
  * Shi and Malik [2000] Jianbo Shi and Jitendra Malik.  Normalized cuts and image segmentation.  _IEEE Transactions on pattern analysis and machine intelligence_ , 22(8):888–905, 2000.
  * Sindhwani et al. [2005] Vikas Sindhwani, Partha Niyogi, and Mikhail Belkin.  Beyond the point cloud: from transductive to semi-supervised learning.  In _Proceedings of the 22nd international conference on Machine learning_ , pages 824–831, 2005.
  * Spielman and Teng [2004] Daniel A Spielman and Shang-Hua Teng.  Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time.  _Journal of the ACM (JACM)_ , 51(3):385–463, 2004\.
  * Szegedy et al. [2015] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru 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.
  * Vitercik et al. [2019] Ellen Vitercik, Maria-Florina Balcan, and Tuomas Sandholm.  Estimating approximate incentive compatibility.  In _ACM Conference on Economics and Computation_ , 2019.
  * Xiaojin and Zoubin [2002] Zhu Xiaojin and Ghahramani Zoubin.  Learning from labeled and unlabeled data with label propagation.  _Tech. Rep., Technical Report CMU-CALD-02–107, Carnegie Mellon University_ , 2002.
  * Zemel and Carreira-Perpiñán [2004] Richard Zemel and Miguel Carreira-Perpiñán.  Proximity graphs for clustering and manifold learning.  _Advances in neural information processing systems_ , 17:225–232, 2004.
  * Zhao et al. [2008] Wentao Zhao, Jun Long, En Zhu, and Yun Liu.  A scalable algorithm for graph-based active learning.  _Frontiers in Algorithmics_ , page 311, 2008.
  * Zhou et al. [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.
  * Zhu and Goldberg [2009] Xiaojin Zhu and Andrew B Goldberg.  Introduction to semi-supervised learning.  _Synthesis lectures on artificial intelligence and machine learning_ , 3(1):1–130, 2009.
  * Zhu et al. [2003a] Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty.  Semi-supervised learning using Gaussian fields and harmonic functions.  In _Proceedings of the 20th International conference on Machine learning (ICML-03)_ , pages 912–919, 2003a.
  * Zhu et al. [2003b] Xiaojin Zhu, John Lafferty, and Zoubin Ghahramani.  Combining active learning and semi-supervised learning using gaussian fields and harmonic functions.  In _ICML 2003 workshop on the continuum from labeled to unlabeled data in machine learning and data mining_ , page Vol. 3, 2003b.
  * Zhu et al. [2005] Xiaojin Zhu, John Lafferty, and Ronald Rosenfeld.  _Semi-supervised learning with graphs_.  PhD thesis, Carnegie Mellon University, Language Technologies Institute, 2005.
  * Zhu et al. [2007] Xiaojin Zhu, Timothy Rogers, Ruichen Qian, and Chuck Kalish.  Humans perform semi-supervised classification too.  In _AAAI_ , volume 2007, pages 864–870, 2007.

## Appendix

##  Appendix A Dispersion and Online learning

In this appendix we include details of proofs and algorithms from section 4.2.

###  A.1 A general tool for analyzing dispersion

If the weights of the graph are given by a polynomial kernel
$w(u,v)=(\tilde{d}(u,v)+\tilde{\alpha})^{d}$, we can apply the general tool
developed by Balcan et al. [10] to learn $\tilde{\alpha}$, which we summarize
below.

  1. 1.

Bound the probability density of the random set of discontinuities of the loss
functions.

  2. 2.

Use a VC-dimension based uniform convergence argument to transform this into a
bound on the dispersion of the loss functions.

Formally, we have the following theorems from [10], which show how to use this
technique when the discontinuities are roots of a random polynomial.

######  Theorem 22 ([10]).

Consider a random degree $d$ polynomial $\phi$ with leading coefficient 1 and
subsequent coefficients which are real of absolute value at most $R$, whose
joint density is at most $\kappa$. There is an absolute constant $K$ depending
only on $d$ and $R$ such that every interval $I$ of length $\leq\epsilon$
satisfies Pr($\phi$ has a root in $I$) $\leq\kappa\epsilon/K$.

######  Theorem 23 ([10]).

Let $l_{1},\dots,l_{T}:\mathbb{R}\rightarrow\mathbb{R}$ be independent
piecewise $L$-Lipschitz functions, each having at most $K$ discontinuities.
Let $D(T,\epsilon,\rho)=|\\{1\leq t\leq T\mid l_{t}\text{ is not
}L\text{-Lipschitz on }[\rho-\epsilon,\rho+\epsilon]\\}|$ be the number of
functions that are not $L$-Lipschitz on the ball
$[\rho-\epsilon,\rho+\epsilon]$. Then we have
$E[\max_{\rho\in\mathbb{R}}D(T,\epsilon,\rho)]\leq\max_{\rho\in\mathbb{R}}E[D(T,\epsilon,\rho)]+O(\sqrt{T\log(TK)})$.

We will now use Theorems 22 and 23 to establish dispersion in our setting. We
first need a simple lemma about $\kappa$-bounded distributions. We remark that
similar properties have been proved in [7, 10], in other problem contexts.
Specifically, [7] show the lemma for a ratio of random variables, $Z=X/Y$, and
[10] establish it for the sum $Z=X+Y$ but for independent variables $X,Y$.

######  Lemma 24.

Suppose $X$ and $Y$ are real-valued random variables taking values in
$[m,m+M]$ and $[m^{\prime},m^{\prime}+M^{\prime}]$ for some
$m,m^{\prime},M,M^{\prime}\in\mathbb{R}^{+}$ and suppose that their joint
distribution is $\kappa$-bounded. Then,

  1. (i)

$Z=X+Y$ is drawn from a $K_{1}\kappa$-bounded distribution, where
$K_{1}\leq\min\\{M,M^{\prime}\\}$.

  2. (ii)

$Z=XY$ is drawn from a $K_{2}\kappa$-bounded distribution, where
$K_{2}\leq\min\\{M/m,M^{\prime}/m^{\prime}\\}$.

###### Proof.

Let $f_{X,Y}(x,y)$ denote the joint density of $X,Y$.

  1. (i)

The case where $X,Y$ are independent has been studied (Lemma 25 in [10]), the
following is slightly more involved. The cumulative density function for $Z$
is given by

$\displaystyle F_{Z}(z)$ $\displaystyle=\text{Pr}(Z\leq z)=\text{Pr}(X+Y\leq
z)=\text{Pr}(X\leq z-Y)$
$\displaystyle=\int_{m^{\prime}}^{m^{\prime}+M^{\prime}}\int_{m}^{z-y}f_{X,Y}(x,y)dxdy.$

The density function for $Z$ can be obtained using Leibniz’s rule as

$\displaystyle f_{Z}(z)=\frac{d}{dz}F_{Z}(z)$
$\displaystyle=\frac{d}{dz}\int_{m^{\prime}}^{m^{\prime}+M^{\prime}}\int_{m}^{z-y}f_{X,Y}(x,y)dxdy$
$\displaystyle=\int_{m^{\prime}}^{m^{\prime}+M^{\prime}}\left(\frac{d}{dz}\int_{m}^{z-y}f_{X,Y}(x,y)dx\right)dy$
$\displaystyle=\int_{m^{\prime}}^{m^{\prime}+M^{\prime}}f_{X,Y}(z-y,y)dy$
$\displaystyle\leq M^{\prime}\kappa.$

A symmetric argument shows that $f_{Z}(z)\leq M\kappa$, together with above
this completes the proof.

  2. (ii)

The cumulative density function for $Z$ is given by

$\displaystyle F_{Z}(z)$ $\displaystyle=\text{Pr}(Z\leq z)=\text{Pr}(XY\leq
z)=\text{Pr}(X\leq z/Y)$
$\displaystyle=\int_{m^{\prime}}^{m^{\prime}+M^{\prime}}\int_{m}^{z/y}f_{X,Y}(x,y)dxdy.$

The density function for $Z$ can be obtained using Leibniz’s rule as

$\displaystyle f_{Z}(z)=\frac{d}{dz}F_{Z}(z)$
$\displaystyle=\frac{d}{dz}\int_{m^{\prime}}^{m^{\prime}+M^{\prime}}\int_{m}^{z/y}f_{X,Y}(x,y)dxdy$
$\displaystyle=\int_{m^{\prime}}^{m^{\prime}+M^{\prime}}\left(\frac{d}{dz}\int_{m}^{z/y}f_{X,Y}(x,y)dx\right)dy$
$\displaystyle=\int_{m^{\prime}}^{m^{\prime}+M^{\prime}}\frac{1}{y}f_{X,Y}(z/y,y)dy$
$\displaystyle\leq\int_{m^{\prime}}^{m^{\prime}+M^{\prime}}\frac{1}{m^{\prime}}f_{X,Y}(z/y,y)dy$
$\displaystyle\leq\frac{M^{\prime}}{m^{\prime}}\kappa.$

Similarly we can show that $f_{Z}(z)\leq M\kappa/m$, together with above this
completes the proof.

∎

See 11

###### Proof.

$w(u,v)$ is a polynomial in $\tilde{\alpha}$ of degree $d$ with coefficient of
$\tilde{\alpha}^{i}$ given by $c_{i}=D_{d,i}\tilde{d}(u,v)^{E_{d,i}}$ for
$i\in[d]$. Since the support of $\tilde{d}(u,v)$ is closed and bounded, we
have $m\leq\tilde{d}(u,v)\leq M$ with probability 1 for some $M>1,m>0$ (since
$\tilde{d}(u,v)$ is a metric, $\tilde{d}(u,v)>0$ for $u\neq v$).

To apply Theorem 22, we note that we have an upper bound on the coefficients,
$R<(dM)^{d}$. Moreover, if $f(x)$ denotes the probability density of $d(u,v)$
and $F(x)$ its cumulative density,

$\displaystyle\text{Pr}(c_{i}\leq
x_{i})=\text{Pr}\left(D_{d,i}\tilde{d}(u,v)^{E_{d,i}}\leq
x_{i}\right)=\text{Pr}\left(\tilde{d}(u,v)\leq\left(\frac{x_{i}}{D_{d,i}}\right)^{1/E_{d,i}}\right)=F\left(\left(\frac{x_{i}}{D_{d,i}}\right)^{1/E_{d,i}}\right).$

Thus,

$\text{Pr}(c_{i}\leq x_{i}\text{ for each
}i\in[d])=F\left(\min_{i}\left(\frac{x_{i}}{D_{d,i}}\right)^{1/E_{d,i}}\right).$

The joint density of the coefficients is therefore $K\kappa$-bounded where $K$
only depends on $d,m$.
($K\leq\max_{i}{D_{d,i}}^{-1/E_{d,i}}m^{-1+1/E_{d,i}}$).

Consider the harmonic solution of the quadratic objective [39] which is given
by $f_{U}=(D_{UU}-W_{UU})^{-1}W_{UL}f_{L}$. For any $u\in U$, $f(u)=1/2$ is a
polynomial equation in $\tilde{\alpha}$ with degree at most $nd$. The
coefficients of these polynomials are formed by multiplying sets of weights
$w(u,v)$ of size up to $n$ and adding the products, and are also bounded
density on a bounded support (using above observation in conjunction with
Lemma 24). The dispersion result now follows by an application of Theorems 22
and 23. The regret bound is implied by results from [7, 11]. ∎

###  A.2 Dispersion for roots of exponential polynomials

In this section we will extend the applicability of the dispersion analysis
technique from Appendix A.1 to exponential polynomials, i.e. functions of the
form $\phi(x)=\sum_{i=1}^{n}a_{i}e^{b_{i}x}$. We will now extend the analysis
to obtain similar results when using the exponential kernel
$w(u,v)=e^{-||u-v||^{2}/\sigma^{2}}$. The results of Balcan et al. [10] no
longer directly apply as the points of discontinuity are no longer roots of
polynomials. To this end, we extend and generalize arguments from [10] below.
We need to generalize Theorem 22 to exponential polynomials below.

######  Theorem 25.

Let $\phi(x)=\sum_{i=1}^{n}a_{i}e^{b_{i}x}$ be a random function, such that
coefficients $a_{i}$ are real and of magnitude at most $R$, and distributed
with joint density at most $\kappa$. Then for any interval $I$ of width at
most $\epsilon$, P($\phi$ has a zero in $I$)$\leq\tilde{O}(\epsilon)$
(dependence on $b_{i},n,\kappa,R$ suppressed).

###### Proof.

For $n=1$ there are no roots, so assume $n>1$. Suppose $\rho$ is a root of
$\phi(x)$. Then $\mathbf{a}=(a_{1},\dots,a_{n})$ is orthogonal to
$\varrho(\rho)=(e^{b_{1}\rho},\dots,e^{b_{n}\rho})$ in $\mathbb{R}^{n}$. For a
fixed $\rho$, the set $S_{\rho}$ of coefficients $\mathbf{a}$ for which $\rho$
is a root of $\phi(y)$ lie along an $n-1$ dimensional linear subspace of
$\mathbb{R}^{n}$. Now $\phi$ has a root in any interval $I$ of length
$\epsilon$, exactly when the coefficients lie on $S_{\rho}$ for some $\rho\in
I$. The desired probability is therefore upper bounded by
$\max_{\rho}\textsc{Vol}(\cup S_{y}\mid
y\in[\rho-\epsilon,\rho+\epsilon])/\textsc{Vol}(S_{y}\mid y\in\mathbb{R})$
which we will show to be $\tilde{O}(\epsilon)$. The key idea is that if
$|\rho-\rho^{\prime}|<\epsilon$, then $\varrho(\rho)$ and
$\varrho(\rho^{\prime})$ are within a small angle
$\theta_{\rho,\rho^{\prime}}=\tilde{O}(\epsilon)$ for small $\epsilon$ (the
probability bound is vacuous for large $\epsilon$). But any point in
$S_{\rho}$ is at most $\tilde{O}(\theta_{\rho,\rho^{\prime}})$ from a point in
$S_{\rho^{\prime}}$, which implies the desired bound (similar arguments to
Theorem 22).

We will now flesh out the above sketch. Indeed,

$\displaystyle\sin\theta_{\rho,\rho^{\prime}}=\sqrt{1-\frac{\left(\langle\varrho(\rho),\varrho(\rho^{\prime})\rangle\right)^{2}}{\left\lVert\varrho(\rho)\right\rVert\left\lVert\varrho(\rho^{\prime})\right\rVert}}=\sqrt{1-\frac{\left(\sum_{i}e^{b_{i}\rho}e^{b_{i}\rho^{\prime}}\right)^{2}}{\sum_{i}e^{2b_{i}\rho}\sum_{i}e^{2b_{i}\rho^{\prime}}}}=\sqrt{\frac{\sum_{i\neq
j}e^{2(b_{i}\rho+b_{j}\rho^{\prime})}-e^{(b_{i}+b_{j})(\rho+\rho^{\prime})}}{\sum_{i}e^{2b_{i}\rho}\sum_{i}e^{2b_{i}\rho^{\prime}}}}.$

Now, for $\rho^{\prime}=\rho+\varepsilon$, $|\varepsilon|<\epsilon$,

$\displaystyle\sin\theta_{\rho,\rho^{\prime}}=\sqrt{\frac{\sum_{i\neq
j}e^{2(b_{i}\rho+b_{j}\rho+b_{j}\varepsilon)}-e^{(b_{i}+b_{j})(2\rho+\varepsilon)}}{\sum_{i}e^{2b_{i}\rho}\sum_{i}e^{2b_{i}\rho^{\prime}}}}=\sqrt{\frac{\sum_{i\neq
j}e^{2\rho(b_{i}+b_{j})}(e^{2b_{j}\varepsilon}-e^{(b_{i}+b_{j})\varepsilon})}{\sum_{i}e^{2b_{i}\rho}\sum_{i}e^{2b_{i}\rho^{\prime}}}}.$

Using the Taylor’s series approximation for $e^{2b_{j}\varepsilon}$ and
$e^{(b_{i}+b_{j})\varepsilon}$, we note that the largest terms that survive
are quadratic in $\varepsilon$. $\sin\theta_{\rho,\rho^{\prime}}$, and
therefore also $\theta_{\rho,\rho^{\prime}}$, is $\tilde{O}(\epsilon)$.

Next it is easy to show that any point in $S_{\rho}$ is at most
$\tilde{O}(\theta_{\rho,\rho^{\prime}})$ from a point in $S_{\rho^{\prime}}$.
For $n=2$, $S_{\rho}$ and $S_{\rho^{\prime}}$ are along lines orthogonal to
$\rho$ and $\rho^{\prime}$ and are thus themselves at an angle
$\theta_{\rho,\rho^{\prime}}$. Since we further assume that the coefficients
are bounded by $R$, any point on $S_{\rho}$ is within
$O(R\theta_{\rho,\rho^{\prime}})=\tilde{O}(\theta_{\rho,\rho^{\prime}})$ of
the nearest point in $S_{\rho^{\prime}}$. For $n>2$, consider the 3-space
spanned by $\rho$, $\rho^{\prime}$ and an arbitrary $\varsigma\in S_{\rho}$.
$S_{\rho}$ and $S_{\rho^{\prime}}$ are along 2-planes in this space with
normal vectors $\rho,\rho^{\prime}$ respectively. Again it is straightforward
to see that the nearest point in the projection of $S_{\rho^{\prime}}$ to
$\varsigma$ is $\tilde{O}(\theta_{\rho,\rho^{\prime}})$.

The remaining proof is identical to that of Theorem 22 (see Theorem 18 of
[10]), and is omitted for brevity.

∎

We will also need the following lemma for the second step noted above, i.e.
obtain a result similar to Theorem 23 for exponential polynomials.

######  Lemma 26.

The equation $\sum_{i=1}^{n}a_{i}e^{b_{i}x}=0$ where
$a_{i},b_{i}\in\mathbb{R}$ has at most $n-1$ distinct solutions
$x\in\mathbb{R}$.

###### Proof.

We will use induction on $n$. It is easy to verify that there is no solution
for $n=1$. We assume the statement holds for all $1\leq n\leq N$. Consider the
equation $\phi_{N+1}(x)=\sum_{i=1}^{N+1}a_{i}e^{b_{i}x}=0$. WLOG $a_{1}\neq 0$
and we can write

$\phi_{N+1}(x)=\sum_{i=1}^{N+1}a_{i}e^{b_{i}x}=a_{1}e^{b_{1}x}\left(1+\sum_{i=2}^{N+1}\frac{a_{i}}{a_{1}}e^{(b_{i}-b_{1})x}\right)=a_{1}e^{b_{1}x}\left(1+g(x)\right).$

By our induction hypothesis, $g^{\prime}(0)=0$ has at most $N-1$ solutions,
and so $(1+g(x))^{\prime}$ has at most $N-1$ roots. By Rolle’s theorem,
$(1+g(x))$ has at most $N$ roots, and therefore $\phi_{N+1}(x)=0$ has at most
$N$ solutions. ∎

Lemma 26 implies that Theorem 23 may be applied. The number of discontinuities
may be exponentially high in this case. Indeed solving the quadratic objective
can result in an exponential equation of the form in Lemma 26 with
$O(|U|^{n})$ terms.

###  A.3 Learning several metrics simultaneously

We start by getting a couple useful definitions out of the way.

######  Definition 27 (Homogeneous algebraic hypersurface).

An algebraic hypersurface is an algebraic variety (a system of polynomial
equations) that may be defined by a single implicit equation of the form
$p(x_{1},\dots,x_{n})=0$, where $p$ is a multivariate polynomial. The degree
$d$ of the algebraic hypersurface is the total degree of the polynomial $p$.
We say that the algebraic hypersurface is homogeneous if $p$ is a homogeneous
polynomial, i.e. $p(\lambda x_{1},\dots,\lambda
x_{m})=\lambda^{d}p(x_{1},\dots,x_{n})$.

In the following we will refer to homogeneous algebraic hypersurfaces as
simply algebraic hypersurfaces. We will also need the standard definition of
set shattering, which we restate in our context as follows.

######  Definition 28 (Hitting and Shattering).

Let $\mathcal{C}$ denote a set of curves in $\mathbb{R}^{p}$. We say that a
subset of $\mathcal{C}$ is hit by a curve $s$ if the subset is exactly the set
of curves in $\mathcal{C}$ which intersect the curve $s$. A collection of
curves $\mathcal{S}$ shatters the set $\mathcal{C}$ if for each subset $C$ of
$\mathcal{C}$, there is some element $s$ of $\mathcal{S}$ such that $s$ hits
$C$.

To extend our learning results to learning graphs built from several metrics,
we will now state and prove a couple theorems involving algebraic
hypersurfaces. Our results generalize significantly the techniques from [10]
by bringing in novel connections with algebraic geometry.

See 6

###### Proof.

Let $\mathcal{C}$ denote a collection of $k$ algebraic hypersurfaces of degree
at most $d$ in $\mathbb{R}^{p}$. We say that a subset of $\mathcal{C}$ is hit
by a line segment if the subset is exactly the set of curves in $\mathcal{C}$
which intersect the segment, and hit by a line if some segment of the line
hits the subset. We seek to upper bound the number of subsets of $\mathcal{C}$
which may be hit by axis-aligned line segments. We will first consider
shattering by line segments in a fixed axial direction $x$. We can easily
extend this to axis-aligned segments by noting they may hit only $p$ times as
many subsets.

Let $L_{c}$ be a line in the $x$ direction. The subsets of $\mathcal{C}$ which
may be hit by (segments along) $L_{c}$ is determined by the pattern of
intersections of $L_{c}$ with hypersurfaces in $\mathcal{C}$. By Bezout’s
theorem, there are at most $kd+1$ distinct regions of $L_{c}$ due to the
intersections. Therefore at most $\binom{kd+1}{2}$ distinct subsets may be
hit.

Define the equivalence relation $L_{c_{1}}\sim L_{c_{2}}$ if the same
hypersurfaces in $\mathcal{C}$ intersect $L_{c_{1}}$ and $L_{c_{2}}$, and in
the same order (including with multiplicities). To determine these equivalence
classes, we will project the hypersurfaces in $\mathcal{C}$ on to a hyperplane
orthogonal to the $x$-direction. By the Tarski-Seidenberg-Łojasiewicz Theorem,
we get a semi-algebraic collection $\mathcal{C}_{x}$, i.e. a set of polynomial
equations and constraints in the projection space. Each cell of
$\mathcal{C}_{x}$ corresponds to an equivalence class. Using well-known upper
bounds for cylindrical algebraic decomposition (see for example [21]), we get
that the number of equivalence classes is at most
$O\left((2d)^{2^{p}-1}k^{2^{p}-1}2^{2^{p-1}}\right)$.

Putting it all together, the number of subsets hit by any axis aligned segment
is at most

$O\left(p\binom{kd+1}{2}(2d)^{2^{p}-1}k^{2^{p}-1}2^{2^{p-1}}\right).$

We are done as this is less than $2^{k}$ for fixed $d$ and $p$ and large
enough $k$, and therefore all subsets may not be hit.

∎

See 7

###### Proof.

The proof is similar to that of Theorem 23 (see [10]). The main difference is
that instead of relating the number of ways intervals can label vectors of
discontinuity points to the VC-dimension of intervals, we instead relate the
number of ways line segments can label vectors of $K$ algebraic hypersurfaces
of degree $d$ to the VC-dimension of line segments (when labeling algebraic
hypersurfaces), which from Theorem 6 is constant. To verify dispersion, we
need a uniform-convergence bound on the number of Lipschitz failures between
the worst pair of points $\alpha,\alpha^{\prime}$ at distance $\leq\epsilon$,
but the definition allows us to bound the worst rate of discontinuties along
any path between $\alpha,\alpha^{\prime}$ of our choice. We can bound the VC
dimension of axis aligned segments against bounded-degree algebraic
hypersurfaces, which will allow us to establish dispersion by considering
piecewise axis-aligned paths between points $\alpha$ and $\alpha^{\prime}$.

Let $\mathcal{C}$ denote the set of all algebraic hypersurfaces of degree $d$.
For simplicity, we assume that every function has its discontinuities
specified by a collection of exactly $K$ algebraic hypersurfaces. For each
function $l_{t}$, let $\gamma^{(t)}\in\mathcal{C}^{K}$ denote the ordered
tuple of algebraic hypersurfaces in $\mathcal{C}$ whose entries are the
discontinuity locations of $l_{t}$. That is, $l_{t}$ has discontinuities along
$(\gamma^{(t)}_{1},\dots,\gamma^{(t)}_{K})$, but is otherwise $L$-Lispchitz.

For any axis aligned path $s$, define the function
$f_{s}:\mathcal{C}^{K}\rightarrow\\{0,1\\}$ by

$\displaystyle f_{s}(\gamma)=\begin{cases*}1&if for some $i\in[K]$
$\gamma_{i}$ intersects $s$\\\ 0&otherwise,\end{cases*}$

where $\gamma=(\gamma_{1},\dots,\gamma_{K})\in\mathcal{C}^{K}$. The sum
$\sum_{t=1}^{T}f_{s}(\gamma^{(t)})$ counts the number of vectors
$(\gamma^{(t)}_{1},\dots,\gamma^{(t)}_{K})$ that intersect $s$ or,
equivalently, the number of functions $l_{1},\dots,l_{T}$ that are not
$L$-Lipschitz on $s$. We will apply VC-dimension uniform convergence arguments
to the class $\mathcal{F}=\\{f_{s}:\mathcal{C}^{K}\rightarrow\\{0,1\\}\mid
s\text{ is an axis-aligned path}\\}$. In particular, we will show that for an
independent set of vectors $(\gamma^{(t)}_{1},\dots,\gamma^{(t)}_{K})$, with
high probability we have that $\frac{1}{T}\sum_{t=1}^{T}f_{s}(\gamma^{(t)})$
is close to $\mathbb{E}[\frac{1}{T}\sum_{t=1}^{T}f_{s}(\gamma^{(t)})]$ for all
paths $s$. This uniform convergence argument will lead to the desired bounds.

Indeed, Theorem 6 implies that VC dimension of $\mathcal{F}$ is $O(\log K)$.
Now standard VC-dimension uniform convergence arguments for the class
$\mathcal{F}$ imply that with probability at least $1-\delta$, for all
$f_{s}\in\mathcal{F}$

$\displaystyle\left\lvert\frac{1}{T}\sum_{t=1}^{T}f_{s}(\gamma^{(t)})-\mathbb{E}\left[\frac{1}{T}\sum_{t=1}^{T}f_{s}(\gamma^{(t)})\right]\right\rvert\leq
O\left(\sqrt{\frac{\log(K/\delta)}{T}}\right)$ , or
$\displaystyle\left\lvert\sum_{t=1}^{T}f_{s}(\gamma^{(t)})-\mathbb{E}\left[\sum_{t=1}^{T}f_{s}(\gamma^{(t)})\right]\right\rvert\leq
O\left(\sqrt{T\log(K/\delta)}\right).$

Now since $D(T,s)=\sum_{t=1}^{T}f_{s}(\gamma^{(t)})$, we have for all $s$ and
$\delta$, with probability at least $1-\delta$, $\sup_{s\in
L}D(T,s)\leq\sup_{s\in L}\mathbb{E}[D(T,s)]+O(\sqrt{T\log(K/\delta)})$. Taking
expectation and setting $\delta=1/\sqrt{T}$ completes the proof as it allows
us to bound the expected discontinuities by $O(\sqrt{T})$ when the above high
probability event fails. ∎

Theorem 7 above generalizes the second step of the dispersion tool from single
parameter families to several hyperparameters, and uses Theorem 6 as a key
ingredient. To complete the first step of in the multi-parameter setting, we
can use a simple generalization of Theorem 22 by showing that few zeros are
likely to occur on a piecewise axis-aligned path on whose pieces the zero sets
of the multivariate polynomial is the zero set of a single-variable
polynomial. Putting together we get Theorem 12.

See 12

###### Proof.

Notice that $w(u,v)$ is a homogeneous polynomial in $\rho=(\rho_{i},i\in[p])$.
Further, the solutions of the quadratic objective subject to $f(u)=1/2$ for
some $u$ are also homogeneous polynomial equations, of degree $nd$. Now to
show dispersion, consider an axis-aligned path between any two parameter
vectors $\rho,\rho^{\prime}$ such that
$\left\lVert\rho-\rho^{\prime}\right\rVert<\epsilon$ (notice that the
definition of dispersion allows us to use any path between
$\rho,\rho^{\prime}$ for counting discontinuities). To compute the expected
number of non-Lipchitzness in along this path, notice that for any fixed
segment of this path, all but one variable are constant and the
discontinuities are the zeros of single variable polynomial with bounded-
density random coefficients, and that Theorem 22 applies. Summing along these
paths we get at most $\tilde{O}(p\epsilon)$ discontinuities in expectation for
any $\left\lVert\rho-\rho^{\prime}\right\rVert<\epsilon$. Theorem 7 now
completes the proof of dispersion in this case. ∎

###  A.4 Semi-bandit efficient algorithms

In this appendix we present details of the efficient algorithms for computing
the semi-bandit feedback sets in Algorithm 2. For unweighted graphs, we only
have a polynomial number $O(n^{2})$ of feedback sets and the feedback set for
a given $\rho_{t}$ is readily computed by looking up a sorted list of
distances $d(u,v)_{u,v\in L_{i}\cup U_{i}}$. For the weighted graph setting,
we need non-trivial algorithms as discussed in Section 4.2.3.

####  A.4.1 Min-cut objective

First some notation for this section. We will use $G=(V,E)$ to denote an
undirected graph with $V$ as the set of nodes and $E\subseteq V\times V$ the
weighted edges with capacity $d:E\rightarrow\mathbb{R}_{\geq 0}$. We are given
special nodes $s,t\in V$ called source and target vertices. Recall the
following definitions.

######  Definition 29.

(s,t)-flows An (s,t)-flow (or just flow if the source and target are clear
from context) is a function $f:V\times V\rightarrow\mathbb{R}_{\geq 0}$ that
satisfies the conservation constraint at every vertex v except possibly s and
t given by $\sum_{(u,v)\in E}f(u,v)=\sum_{(v,u)\in E}f(v,u)$. The value of
flow (also refered by just flow when clear from context) is the total flow out
of $s$, $\sum_{u\in V}f(s,u)-\sum_{u\in V}f(u,s)$.

######  Definition 30.

(s,t)-cut An (s,t)-cut (or just a cut if the source and target are clear from
context) is a partition of $V$ into $S,T$ such that $s\in S,t\in T$. We will
denote the set $\\{(u,v)\in E\mid u\in S,v\in T\\}$ of edges in the cut by
$\partial S$ or $\partial T$. The capacity of the cut is the total capacity of
edges in the cut.

For convenience we also define

######  Definition 31.

Path flow. An (s,t)-flow is a path flow along a path
$p=(s=v_{0},v_{1},\dots,v_{n}=t)$ if $f(u,w)>0$ iff $(u,w)=(v_{i},v_{i+1})$
for some $i\in[n-1]$.

######  Definition 32.

Residual capacity graph. Given a set of path flows $F$, the residual capacity
graph (or simply the residual graph) is the graph $G^{\prime}=(V,E)$ with
capacities given by $c^{\prime}(e)=c(e)-\sum_{f\in F}f(e)$.

We will list without proof some well-known facts about maximum flows and
minimum cuts in a graph which will be useful in our arguments.

######  Fact.

  * 1.

Let $f$ be any feasible $(s,t)$-flow, and let $(S,T)$ be any $(s,t)$-cut. The
value of $f$ is at most the capacity of $(S,T)$. Moreover, the value of $f$
equals the capacity of $(S,T)$ if and only if $f$ saturates every edge in the
cut.

  * 2.

Max-flow min-cut theorem. The value of maximum (value of) $(s,t)$-flow equals
the capacity of the minimum $(s,t)$-cut. It may be computed in $O(VE)$ time.

  * 3.

Flow Decomposition Theorem. Every feasible $(s,t)$-flow $f$ can be written as
a weighted sum of directed $(s,t)$-paths and directed cycles. Moreover, a
directed edge $(u,v)$ appears in at least one of these paths or cycles if and
only if $f(u,v)>0$, and the total number of paths and cycles is at most the
number of edges in the network. It may be computed in $O(VE)$ time.

We now have the machinery to prove the correctness and analyze the time
complexity of our Algorithm 3.

See 14

###### Proof.

First, we briefly recall the set up of the mincut objective. Let $L_{1}$ and
$L_{2}$ denote the labeled points $L$ of different classes. To obtain the
labels for $U$, we seek the smallest cut $(V_{1},V\setminus V_{1})$ of $G$
separating the nodes in $L_{1}$ and $L_{2}$. To frame as $s,t$-cut we can
augment the data graph with nodes $s,t$, and add infinite capacity edges to
nodes in $L_{1}$ and $L_{2}$ respectively. If $L_{i}\subseteq V_{1}$, label
exactly the nodes in $V_{1}$ with label $i$. The loss function, $l(\sigma)$
gives the fraction of labels this procedure gets right for the unlabeled set
$U$.

If the min-cut is the same for two values of $\sigma$, then so is prediction
on each point and thus the loss function $l(\sigma)$. So we seek the smallest
amount of change in $\sigma$ so that the mincut changes. Our semi-bandit
feedback set is given by the intervals for which the min-cut is fixed.
Consider a fixed value of $\sigma=\sigma_{0}$ and the corresponding graph
$G(\sigma_{0})$. We can compute the max-flow on $G(\sigma_{0})$, and
simultaneously obtain a min-cut $(V_{1},V\setminus V_{1})$ in time
$O(VE)=O(n^{3})$. All the edges in $\partial V_{1}$ are saturated by the flow.
Obtain the flow decomposition of the max-flow (again $O(VE)=O(n^{3})$). For
each $e_{i}\in\partial V_{1}$, let $f_{i}$ be a path flow through $e_{i}$ from
the flow decomposition (cycle flows cannot saturate, or even pass through,
$e_{i}$ since it is on the min-cut). Note that the $f_{i}$ are distinct due to
the max-flow min-cut theorem. Now as $\sigma$ is increased, we increment each
$f_{i}$ by the additional capacity in the corresponding edge $e_{i}$, until an
edge $e^{\prime}$ in $E\setminus\partial V_{1}$ saturates (at a faster rate
than the flow through it). This can be detected by expressing $f_{i}$ as a
function of $\sigma$ for each $f_{i}$ and computing the zero of an exponential
polynomial capturing the change in residual capacity of any edge
$e\notin\partial V_{1}$. Let $f_{j}$ be one of the path flows through
$e^{\prime}$. We reassign this flow to $e^{\prime}$ (it will now increase with
$e^{\prime}$ as its bottleneck) and find an alternate path avoiding this edge
through non-saturated edges and $e_{j}$ (if one exists) along which we send
the new $f_{j}$. We now increment all the path flows as before keeping their
bottleneck edges saturated. The procedure stops when we can no longer find an
alternate path for some $e_{j}$. But this means we must have a new cut with
the saturated edges, and therefore a new min-cut. This gives us a new critical
value of $\sigma$, and the desired upper end for the feedback interval.
Obtaining the lower end is possible by a symmetric procedure that decreases
the path flows while keeping edges saturated.

We remark that our procedure differs from the well-known algorithms for
obtaining min-cuts in a static graph. The greedy procedures for static graphs
need directed edges $(u,v)$ and $(v,u)$ in the residual graph, and find paths
through unsaturated edges through this graph to increase the flow, and cannot
work with monotonically increasing path flows. We however start with a max
flow and maintain the invariant that our flow equals some cut size throughout.

Finally note that each time we perform step 9 of the algorithm, a new
saturated edge stays saturated for all further $\sigma$ until the new cut is
found. So we can do this at most $O(n^{2})$ times. In each loop we need to
obtain the saturation condition for $O(n)$ edges corresponding to one new path
flow. ∎

We remind the reader that a remarkable property of finding the min-cuts
dynamically in our setting is an interesting “hybrid” combinatorial and
continuous set-up, which may be of independent interest. A similar dynamic,
but purely combinatorial, setting for recomputing flows efficiently online
over a discrete graph sequence has been studied in [1].

##  Appendix B Distributional setting

In this appendix we include details of proofs and algorithms from section 4.3.
Recall that we define the set of loss functions
$\mathcal{H}_{r}=\\{l_{A(G(r),L,U)}\mid 0\leq r<\infty\\}$, where $G(r)$ is
the family of threshold graphs specified by Definition 1a, and
$\mathcal{H}_{\sigma}=\\{l_{A(G(\sigma),L,U)}\mid 0\leq\sigma<\infty\\}$,
where $G(\sigma)$ is the family of exponential kernel graphs specified by
Definition 1c. We show lower bounds on the pseudodimension of these function
classes below.

See 16

We first prove the following useful statement which helps us construct general
examples with desirable properties. In particular, the following lemma
guarantees that given a sequence of values of $r$ of size $O(n)$, it is
possible to construct an instance $S$ of partially labeled points such that
the cost of the output of algorithm $A(G(r),L)$ on V as a function of $r$
oscillates above and below some threshold as $r$ moves along the sequence of
intervals $(r_{i},r_{i+1})$. Given this powerful guarantee, we can then pick
appropriate sequences of $r$ and generate a sample set of $\Omega(\log n)$
instances that correspond to cost functions that oscillate in a manner that
helps us pick $\Omega(n)$ values of $r$ that shatters the samples.

######  Lemma 33.

Given integer $n>5$ and a sequence of $n^{\prime}$ $r$’s such that
$1<r_{1}<r_{2}<\dots<r_{n^{\prime}}<2$ and $n^{\prime}\leq n-5$, there exists
a real valued witness $w>0$ and a labeling instance $S$ of partially labeled
$n$ points, such that for $0\leq i\leq n^{\prime}/2-1$, $l_{A(G(r),L)}<w$ for
$r\in(r_{2i},r_{2i+1})$, and $l_{A(G(r),L)}>w$ for $r\in(r_{2i+1},r_{2i+2})$
(where $r_{0}$ and $r_{n^{\prime}+1}$ correspond to immediate left and right
neighborhoods respectively of $r_{1}$ and $r_{n^{\prime}}$).

###### Proof.

We first present a sketch of the construction. We will use binary labels $a$
and $b$. We further have three points labeled $a$ (namely $a_{1},a_{2},a_{3}$)
and two points labeled $b$ (say $b_{1},b_{2}$). At some intial $r=r_{0}$, all
the like-labeled points are connected in $G(r_{0})$ and all the unlabeled
points (namely $u_{1},\dots,u_{n^{\prime}}$) are connected to $a_{1}$ as shown
in Figure 7(a). The algorithm $A(G(r),L)$ labels everything $a$ and gets
exactly half the labels right. As $r$ is increased to $r_{i}$, $u_{i}$ gets
connected to $b_{1}$ and $b_{2}$ (Figure 7(b)). If the sequence $u_{i}$ is
alternately labeled, the loss increases and decreases alternately as all the
predicted labels turn to $b$ as $r$ is increased to $r_{n^{\prime}}$. Further
increasing $r$ may connect all the unlabeled points with true label $a$ to
$a_{2}$ and $a_{3}$ (Figure 7(c)), although this is not crucial to our
argument. The rest of the proof gives concrete values of $r$ and verifies that
the construction is indeed feasible.

We will ensure all the pairwise distances are between 1 and 2, so that
triangle inequality is always satisfied. It may also be readily verified that
$O(\log n)$ dimensions suffice for our construction to exist. We start by
defining some useful constants. We pick $r_{-},r_{+},r_{\max}\in(1,2)$ such
that $r_{-}<r_{1}<\dots<r_{n^{\prime}}<r_{+}<r_{\max}$,

$\displaystyle r_{-}$ $\displaystyle=\frac{1+r_{1}}{2},$ $\displaystyle r_{+}$
$\displaystyle=1+\frac{r_{n^{\prime}}}{2},$ $\displaystyle r_{\max}$
$\displaystyle=1+\frac{r_{+}}{2}.$

We will now specify the distances of the labeled points. The points with the
same label are close together and away from the oppositely labeled points.

$\displaystyle d(a_{i},a_{j})$ $\displaystyle=r_{-},$ $\displaystyle 1\leq
i<j\leq 3,$ $\displaystyle d(b_{1},b_{2})$ $\displaystyle=r_{-},$
$\displaystyle d(a_{i},b_{j})$ $\displaystyle=r_{\max},$ $\displaystyle 1\leq
i\leq 3,1\leq j\leq 2.$

Further, the unlabeled points are located as follows

$\displaystyle d(a_{1},u_{k})$ $\displaystyle=r_{-},$ $\displaystyle 1\leq
k\leq n^{\prime},$ $\displaystyle d(b_{i},u_{k})$ $\displaystyle=r_{k},$
$\displaystyle 1\leq k\leq n^{\prime},1\leq i\leq 2,$ $\displaystyle
d(a_{i},u_{k})$ $\displaystyle=r_{+},$ $\displaystyle 1\leq k\leq
n^{\prime},2\leq i\leq 3,$ $\displaystyle d(u_{i},u_{j})$
$\displaystyle=r_{\max},$ $\displaystyle 1\leq i<j\leq n^{\prime}.$

That is, all unknown points are closest to $a_{1}$, followed by $b_{i}$’s,
remaining $a_{i}$’s and other $u_{i}$’s in order. Further let the true labels
of the unlabeled nodes be alternating with the index, i.e. $u_{k}$ is $a$ if
and only if $k$ is even.

We will now compute the loss for the soft labeling algorithm $A(G(r),L)$ of
[39] as $r$ varies from $r_{-}$ to $r_{+}$, starting with $r=r_{0}=r_{-}$. We
note that our construction also works for other algorithms as well, for
example the min-cut based approach of [16], but omit the details.

For the graph $G(r_{-})$, $A(G,L)$ labels each unknown node as $a$ since each
unknown point is a leaf node connected to $a_{1}$. Indeed if $f(a_{1})=1$, the
quadratic objective attains the minimum of 0 for exactly $f(u_{k})=1$ for each
$1\leq k\leq n^{\prime}$. This results in half the labels in the dataset being
incorrectly labeled since we stipulate that half the unknown labels are of
each category. This results in loss $l_{A(G(r_{-}),L)}=:l_{\text{high}}$ say.

---

$\displaystyle a_{1}$$\displaystyle a_{2}$$\displaystyle a_{3}$$\displaystyle
u_{n^{\prime}}$$\displaystyle u_{2}$$\displaystyle u_{1}$$\displaystyle
b_{1}$$\displaystyle b_{2}$ (a) $G(r_{-})$

$\displaystyle a_{1}$$\displaystyle a_{2}$$\displaystyle a_{3}$$\displaystyle
u_{n^{\prime}}$$\displaystyle u_{1}$$\displaystyle b_{1}$$\displaystyle
b_{2}$$\displaystyle u_{i}$ (b) $G(r_{i})$

$\displaystyle a_{1}$$\displaystyle a_{2}$$\displaystyle a_{3}$$\displaystyle
u_{n^{\prime}}$$\displaystyle u_{1}$$\displaystyle b_{1}$$\displaystyle b_{2}$
(c) $G(r_{+})$