Coresets For Monotonic Functions
with Applications to Deep Learning
Elad Tolochinsky, Dan Feldman

arXiv:1802.07382v1 [cs.LG] 21 Feb 2018

February 22, 2018
Abstract
Coreset (or core-set) in this paper is a small weighted subset Q of the input set
P P with respect to
a given monotonic function f : R → R that provably approximates its fitting loss p∈P f (p · x) to any
given x ∈ Rd . Using Q we can obtain approximation to x∗ that minimizes this loss, by running existing
optimization algorithms on Q. We provide: (i) a lower bound that proves that there are sets with no
coresets smaller than n = |P | , (ii) a proof that a small coreset of size near-logarithmic in n exists for
any input P , under natural assumption that holds e.g. for logistic regression and the sigmoid activation
function. (iii) a generic algorithm that computes Q in O(nd + n log n) expected time, (iv) novel technique
for improving existing deep networks using such coresets, (v) extensive experimental results with open
code.

1

Motivation

Traditional algorithms in computer science and machine learning are usually tailored to handle only off-line
finite data set that is stored in memory. However, many modern systems do not use this computation model.
For example, GPS data from millions of smartphones, high definition images, YouTube videos, Twitter’s
text twitts, or audio signals from music or speech recognition arrive in a streaming fashion. The era of
Internet of Things (IoT) provides us with wearable devices and mini-computers that collect data sets that
are being gathered by ubiquitous information-sensing mobile devices, aerial sensory technologies (remote
sensing), genome sequencing, cameras, microphones, radio-frequency identification chips, finance (such as
stocks) logs, internet search, and wireless sensor networks [17, 23, 11].
Limited memory. In such systems the input is an infinite stream that may be grown in practive to peta
bytes of data-sets, and cannot be stored in memory. The data may arrive in real-time, and not just being
read from a hard drive, so only one-pass over data and small memory is allowed.
Parallel computations. Even if we have streaming algorithms to maintain and learn Big data in memory
from million of users, it is not reasonable to apply them on our laptop, and a large set of computation machines
is used instead. However, using, for example, GPUs that run thousands of threads in parallel require us to
design parallel version of our algorithms, which may be very hard to design and debug.
Distributed computations.
If the data-set is distributed among many machines, e.g. network or
“cloud”, there is an additional problem of non-shared memory, which may be replaced by expensive and
slow communication between the machines.
Limited computation power.
Modern computation devices such as GPUs pose additional challenges
since in order to run efficiently in parallel, unlike CPUs, only limited set of simple commands and algorithms
may be used. However, unlike modern GPU cards that are plugged into expensive and strong servers on
1

the cloud, IoT devices are usually small and low cost. This results in a very weak computation power that
is similar to computers in the previous century, as well as energy (battery) consuming issues that avoid us
from running CPU extensive algorithms.
Weak or no theoretical guarantees.
Due to the modern computation models above, learning even
trivial properties of the data can become a non trivial task, as stated in [11]. These problems are felt
especially within the scope of machine learning applications, where the common optimization functions and
and model may be NP-hard to compute, already in the off-line settings. The result is neglecting, in some
sense, decades of theoretical computer science research, and replacing it by fast heuristics and ad-hoc rules
that have no theoretical guarantees but may be easy to implement, with reasonable results. Sometimes
the papers include proofs of weak guarantees such as fast running time (with no approximation guarantee),
convergence to a local minima (but not global, and in unbounded amount of time), or somewhat unnatural
assumptions regarding the input or the behaviour of the algorithms.
Deep learning suggests to minimize a function that can be defined in what is known as a neural network.
While it is considered a serious breakthrough in AI, and the state-of-the-art in many practical applications,
it has very little theoretical guarantees regarding the relation between the output parameters (network) and
the optimal network. This is not surprising as, it is known that even computing the optimal parameters of a
single layer with a single neuron that uses the sigmoid activation function is NP-hard, including reasonable
approximations [24]. Modern deep networks may consists of hundreds of layers, each with dozens of neurons
with many different functions.

2

Coresets

Coresets suggest a natural solution or at least a very generic approach to attack the above challenges without
re-inventing computer science, have some promising theoretical guarantees, and still use the success of existing
heuristics. The idea is that instead of suggesting a new algorithm to solve the problem at hand from scratch,
we summarize the data and reduced it in some sense, so that we can compute the optimal solution on the
coreset using existing algorithms, while still getting provable approximation. The main challenge is to prove
that there is a good trade-off between the coreset size and the guaranteed approximation. The exact coreset
definition and its guarantees is inconsistent, as well as the name of the new set. Hence, it makes more sense
to estimate the quality of a coreset by its properties, such as the following two properties.
Composable coresets refer to the output of coreset constructions that can be computed independently
on different machines for different data-sets P1 and P2 to obtain the coresets C1 and C2 , then be merged
to their union C1 ∪ C2 , and re-compressed to a coreset C3 of C1 ∪ C2 . If the “coreset for coresets” C3 is a
coreset for the union of the original sets P1 ∪ P2 , then the coreset construction outputs composable coresets.
Unlike othe type of coresets, composable coreset allow us to handle Big data as follows.
Streaming, and distributed updates of the data using small memory and update time per point can
be obtained from any (off-line) composable coreset scheme that outputs a coreset of a small size. We can
also compute such coresets on distributed data (e.g. in cloud or smartphones), or dynamic data (with point
deletion support in near-logarithmic time, but linear memory, e.g hard drive). This is now a common technique, known as merge-and-reduce tree and is explained in details in many papers; see e.g. [11] and references
therein. Such coresets can be computed also on data that is distributed and streamed simultaneously as was
proved in [14].
Based on this classic reduction, for the rest of the paper we focus only on off-line (but composable)
coreset construction.

2

Weighted subset that is also a coreset, means that the coreset is essentially a small subset of the input
points. Each point in the coreset is also associated with a positive (real) weight. Intuitively, the weight of
a coreset point tells us how many points it represents in the original data. Indeed, the sum of weights in
the coreset is usually approximately the size n of the input set. Weighted coresets has many advantages
over other type of coresets, such as e.g. linear combinations of points, sometimes called sketches. For
example, (i) Generalizing existing algorithms to handle weighted input points of the coreset is usually easy
or exist (as the public code we used in this paper), (ii) If the input is sparse, then the coreset is also sparse,
(iii) interpretation of the coreset is easier, (iv) numerical errors are usually small compared to, e.g., linear
combinations of points when positive and negative coefficient cancel themselves in theory but not in practice.
Coresets as a bridge between theory and heuristics. In theory we should run the optimal algorithm
on the coreset to get an approximation for the optimal solution of the real data. In practice, as stated in the
previous section, for many of the problems in machine learning (such as deep learning) we do not have such
provable optimal solution or even non-trivial approximations. Instead we run our favorite existing heuristic
on the coreset. Since the coreset is small, we can run these heurisitcs many times on the coreset instead of
one time on the full original data. Due do this reason, and also since coreset removes noise and smooth the
optimization function in some sense, we usually get better result (i.e., negative ε) in practice by running the
heuristic many times (e.g. from different initial seeds) on the coreset. Indeed, this is the case in this paper
when we run our coreset on heuristics for optimizing the sigmoid function over the input.

3

Our contribution

We assume that we are given a set P of n points in Rd , and a non-decreasing monotonic functions f : R → R.
Such a function represents a loss of fitting kernel function (model, classifiers). For example, f (y) = 1+e1−y .
for the case of sigmoid function, and f (y) = ln (1 + ey ) for the case of logistic regression, which are both used
as activation functions in the last layer of neural networks for obtaining the final classification
P(probability
between 0 and 1) for each label class. The total loss or sum of errors for every x ∈ Rd is then p∈P f (p · x),
where p may be multiplied by its label y ∈ {0, 1} for supervised data.
For a given error parameter ε ∈ (0, 1), we wish to compute an ε-coreset Q ⊆ P , with a weight function
u : Q → [0, ∞) that provably approximates the fitting cost of P for every x ∈ Rd , up to a multiplicative
factor of 1 ± ε, i.e.,
X
X
X
(1 − ε)
f (p · x) ≤
w(p)f (p · x) ≤ (1 + ε)
f (p · x).
p∈P

p∈Q

p∈P

Our results are as follows. (i) A lower bound that proves that there are no such small coresets in general.
More precisely, there are input sets with no coresets of size smaller than n, for every given ε ∈ (0, 1) and
integer n ≥ 1.
(ii) To overcome this lower bound, we add natural assumptions regarding f , mainly a regularization term
to the loss function, which is often added anyway to avoid overfitting. In fact, without this term the function
is minimizes where x approaches infinity. However, after adding the regularization term, the sigmoid function
2
above becomes g(p, x) = f (p, x)+kxk2 /k, where k > 0 defines the trade-off between minimizing the function
and the complexity (length, in this case) of the set of parameters.
While minimizing such functions may still be NP-hard (such as in the sigmoid case), we prove that a
coreset Q of size that is near-logarithmic in n exists for any input set P .
(iii) A generic algorithm that computes the coreset Q above in O(nd + n log n) expected time. Unlike most
existing algorithms and results, the algorithm bounds sensitivity for general sets of monotonoic functions,
and not a specific function. We can then obtain approximation to the desired model of P by running existing
algorithms on Q, that can be computed for streaming and distributed Big data.
(iv) Novel technique for applying our coresets to deep learning in order to get better classifiers than the
state of the art.

3

(v) An open-code implementation of our algorithm [1], and extensive experimental results on both synthetic and real-world public datasets.

4

Related Work

In [15] Har-Peled shows how to construct a coreset of one dimensional points sets (d = 1) for sums of single
variable real valued functions. In the scope of machine learning most of the research involves clustering
techniques [12, 13, 10] and regressions [2, 6, 30]. Several coresets were constructed for supervised learning
problems including coresets for Gaussian mixture models [8], and SVM [25, 16].
The work by [18] introduces lower bounds on the total sensitivity of the logistic regression problem that
is used in this paper. It also introduces an upper bound for the total sensitivity and coreset size based on
k-clustering coresets. However the bounds hold only for input set P from very specific distributions (roughly,
when P is well separated into k clusters).
The main tool of this work uses the unified framework presented in [9], which was recently improved
in [3]. We also use the reduction from L∞ coresets that approximates maxp∈P f (p · x) to our L1 coreset
(sum of loss) which was introduced in [27].

5

Overview

Our algorithm is based on previous results that are summarized in Section 6. Mainly, the fact that in order
to compute a coreset (which is a weighted subset) for a loss function it suffices to bound the sensitivity
(importance) of each point and the VC-dimension of the related function, as defined in the section. The
size of the coreset depends on the sum of sensitivities over all the points, the VC-dimension, and the desired
approximation error ε. A bound on the VC-dimension for the family of monotonic function is known to be
O(d) [18], so the majority of the paper is devoted to bound the sensitivity of each point.
In Section 7 we show example input sets that have no coreset that is smaller than the input size, for
monotonic functions. This motivates the necessity of the assumptions in Section 8 regarding the properties
of the function. Mainly, that it includes a regularization term that depends on kxk. This term is usually
added anyway, both in theory and practice, to reduce the P
complexity of the model and avoid overfitting,
where k > 0 determines the tradeoff between minimizing p∈P f (p, x) and using very large x. In fact,
without this term k, the trivial minimizer is usually x = ∞. In Section 8 we also introduce our main generic
algorithm for coreset construction for such families of monotonic functions. After stating the general result,
we demonstrate it for a coreset for the sigmoid activation function.
In Section 11 we show experimental results on synthetic and real data sets. In particular, we show a
technique to improve the fitting cost of existing neural network by computing coreset for the input to its
last layer, and update its weights.

6

Preliminaries

We first describe the framework of [9] for computing coresets for certain optimization problems. The framework is based on a non-uniform sampling technique. We sample points with different probabilities in such a
way that points that have a high influence on the optimization problem are sampled with higher probability,
to make sure that the sample contains the important points. At the same time, in order to keep the sample
unbiased, the sample points are weighted reciprocal to their sampling probability. To quantify the influence
of single point on the optimization problem, Feldman and Langberg uses a term that was named sensitivity
in [21].
Definition 1 (Query space). Let P be a finite set called points, and w : P 0 →(0, ∞) for some P 0 ⊇ P be
called a weight function. Then (P, w) is called a weighted set. A special case is (P, 1) where w(p) = 1 for

4

every p ∈ P . Let X be a set called queries, and c : P × X → [0, ∞) be a given cost or loss function. The
total cost of P with respect to a query x ∈ X is
X
C (P, w, x) =
w (p) c (p, x) .
p∈P

The tuple (P, w, X, c) is called a query space.
Definition 2 (Sensitivity). [9, 21] The sensitivity of a point p ∈ P in a query space (P, w, X, c) is
s(p) = sP,w,X,c (p) = sup
x∈X

w (p) c (p, x)
,
C (P, w, x)

where the supermum is over
P every x ∈ X such that C (P, w, x) > 0. The total sensitivity of the query space
is t(P ) = t(P, w, X, c) = p∈P s(p).
The main contribution of Feldman and Langberg is to establish a connection to the theory of range spaces
and VC-dimension. The dimension of a query space is a measure to its combinatorial complexity.
Definition 3 (VC-dimension). [9, 26] For a query space (P, w, X, c) we define
range (x, r) = {p ∈ P | w (p) c (p.x) ≤ r} ,
for every x ∈ X and r ≥ 0 . The dimension of (P, w, X, c) is the size |G| of the largest subset G ⊆ P such
that have
|{G ∩ range (x, r) |x ∈ X, r ≥ 0}| = 2|G| .
Feldman and Langberg show how to compute a weighted subset (Q, u) that will approximate the total
cost C (P, w, x) for every query, up to a multiplicative factor of 1 ± ε without further assumptions. Such a
set is sometimes called a coreset as follows,
Definition 4 (ε-coreset). Let (P, w, X, c) be a query space, and ε ∈ (0, 1) be an error parameter. An
ε-coreset of (P, w, X, c) is a weighted set (Q, u) such that
∀x ∈ X : |C (P, w, x) − C (Q, u, x)| ≤ εC (P, w, x) .
In [9] it was proved how small total sensitivity implies small coreset, and the size was reduced lately
in [3].
Theorem 5 (coreset construction). [3, 9] Let (P, w, X, c) be a query space of dimension d and total sensitivity
t. Let ε, δ ∈ (0, 1). Let Q be a random sample of

 
1
10t
,
|Q| ≥ 2 d log t + log
ε
δ
i.i.d points from P , such that for every p ∈ P and q ∈ Q we have p = q with probability 1t · sP,w,X,c (p).
tw(p)
Let u (p) = sP,w,X,c
(p)|Q| for every p ∈ Q. Then, with probability at least 1 − δ, (Q, u) is an ε-coreset of
(P, w, X, c).

7

Lower Bounds

In this section we show that without adding additional assumption on the function, no coreset exist for
monotonic function f that satisfies
f (−x)
lim
= 0.
(1)
x→∞ f (x)
5

That is, for every n ≥ 1, we can find a set P of size n such that any corest of P is of size n. The reason
we chose to focus on this property is because most of the common functions used for learning satisfy this
property.
To see this we will use the notion of total sensitivity defined above. Theorem 5 states that a small upper
bound on the sensitivity is a sufficient condition for the existence of a coreset. We will show that this is also
a necessary condition in the sense that if the sensitivity of every point is too large, no non-trivial coreset can
exist.
Lemma 6 (Lower bound via Total sensitivity). Let (P, w, X, c) be a query space, and ε ∈ (0, 1). If every
p ∈ P has sensitivity sP,w,X,c (p) = 1, then for every ε-coreset (Q, u) we have Q = P .
Proof. Let (Q, u) be a weighted set, where Q ⊂ P . It suffices to prove that (Q, u) is not an ε-coreset for P .
Denote
umax ∈ arg max u (p) , and wmin ∈ arg min w (p) .
p∈Q

p∈P

Let p ∈ P \ Q. By the assumption sP,w,X,c (p) ≥ 1, there is xp ∈ X such that
umax
wmin (1 − ε)
w (p) c (p, xp )
=1>
−
.
C (P, w, xp )
umax
umax
Multiplication by C(P, w, xp ) yields
w (p) c (p, xp ) >
umax − wmin (1 − ε)
· C (P, w, xp ) .
umax

(2)

We have that
C (Q, u, xp ) =

X

u (q) c (q, xp )

q∈Q

X u (q)
umax X
w (q) c (p, xp ) ≤
w (q) c (q, xp )
w (q)
wmin
q∈Q
q∈Q
umax X
≤
w (p) c (p0 , xp )
wmin 0
=

(3)

p ∈P \{p}

umax
(C (P, w, xp ) − w (p) c (p, xp ))
wmin


umax
umax − wmin (1 − ε)
<
C (P, w, xp ) 1 −
wmin
umax
=

(4)

= (1 − ε) C (P, w, xp ) ,
where (3) is by the assumption p ∈ P \ Q, and (4) is by (2). Hence Q cannot be used to approximate
C(P, w, xp ) and thus is not an ε-coreset for P .
To complete the proof of our lower bound we now only need to show that there is a set of points for
which the sensitivity of every point is 1. Together with the lemma above, this will complete the proof. The
idea behind finding a set for which every point has sensitivity 1 is to find a set of points in which every point
is linearly separable from the rest of the set. Such a set was shown to exist in [18].
Lemma 7. [18] There is a finite set of points P ⊆ Rd such that for every p ∈ P and R > 0 there is yp ∈ Rd
of length kyp k ≤ R such that yp · p = −R, and for every q ∈ P \ {p} we have yp · q ≥ R.
We now prove that the sensitivity of every point in the set above is 1. We generalize a result from [18]
by letting the cost be any function upholding the conditions of Theorem 8 and the data to be weighted.
6

Theorem 8. Let f : R → (0, ∞) be a non-decreasing monotonic function that satisfies (1). and let c (x, p) =
d
f (x · p) for every x, p ∈ Rd . Let ε ∈ (0, 1), n ≥ 1 be an integer, and w
 : R → (0, ∞). There is a set
d
d
P ⊂ R of |P | = n points such that if (Q, u) is an ε-coreset of P, w, R , c then Q = P .
Proof. Let P ⊆ Rd be the set that is defined in Lemma 7, and let p ∈ P , and R > 0. By Lemma 7, there is
yp ∈ Rd such that yp · p = −R, and for every q ∈ P \ {p} we have −yp · q ≤ −R. By this pair of properties,
f (−yp · p) = f (R) and f (−yp · q) ≤ f (−R) ,
where in the last inequality we use the assumption that f is non-decreasing. By letting xp = −yp , we have
w(q)f (−yp · q)
w(q)f (−R)
w(q)f (xp · q)
=
≤
.
w(p)f (xp · p)
w(p)f (−yp · p)
w(p)f (R)
Therefore, by letting wmax ∈ arg maxp∈P w (p),
w (p) f (xp u · p)
q∈P w (q) f (xp · q)

sP,w,Rd ,c (p) ≥ P
=

w (p) f (xp · p)
P
w (p) f (p · xp ) + q∈P \{p} w (q) f (xp · q)
1

=
1+
≥

P

w(q)f (xp ·q)
q∈P \{p} w(p)f (xp ·p)

1
max f (−R)
1 + (n − 1) ww(p)f
(R)

1

≥
1+

w(q)f (−R)
q∈P \{p} w(p)f (R)

P

.

By replacing x with R in (1), we have
lim

R→∞

wmax f (−R)
wmax
f (−R)
=
lim
= 0.
w (p) f (R)
w(p) R→∞ f (R)

Thus we obtain
sP,w,Rd ,c (p) = sup
R>0

1
max f (−R)
1 + (n − 1) ww(p)f
(R)

= 1.

Theorem 8 then follows from the last equality and Lemma 6.

8

Coresets For Monotonic Bounded Functions

Lemma 9. Let P ⊂ Rd be a finite set, M > 0, f : R → (0, M ] be a non-decreasing function. Let
g : [0, ∞) → [0, ∞) and k > 0. For every x ∈ Rd and p0 ∈ P define ck (p0 , x) = f (p0 · x) + g(kxk)
. Let
k
p ∈ P and bp > 0 such that for every z > 0


g (z)
g (z)
f (kpk z) +
≤ bp f (− kpk z) +
.
(5)
k
k
Then for every x ∈ Rd
max
ck (p0 , x) ≤
0

p ∈P

M
(bp + 1) ck (p, x) .
f (0)

Proof. Let x ∈ Rd and q ∈ P such that x · q > 0. We have, by the monotonic properties of f ,
f (0) ≤ f (x · q) .
7

(6)

Algorithm 1 Monotonic-Coreset(P, ε, δ, k)
Input: A set P of n points in Rd ,
an error parameter ε ∈ (0, 1),
probability of failure δ ∈ (0, 1), and
a real valued regularization term k > 0.
Output: An ε-coreset (Q, u) for (P, 1, Rd , csigmoid,k ).
1: Sort the points in P = {p1 , · · · , pn } by their length, i.e., kp1 k ≤ · · · ≤ kpn k.
2: for every j ∈ {1, · · · , n} do
√
132 k pj + 2
3:
Set s(pj ) ←
j
4: end for
Pn
5: Set t ←
s(pi )
i=1

1
10t
d ln t + ln
6: Set m ← 2
ε
δ
7: Pick a sample Q ⊆ P of |Q| ≥ min {m, n} i.i.d. points such that for every q ∈ Q and p ∈ P we have
p = q with probability s(p)/t.
8: for every pi ∈ Q do
1
9:
Set u (pi ) ←
|Q| Prob (pi )
10: end for
11: return (Q, u)

Hence,
max
f (x · p0 ) ≤ M =
0

p ∈P

M
M
f (0) ≤
f (x · q) ,
f (0)
f (0)

where the first inequality is since f is bounded by M , and the last inequality is by (6). By adding
both sides of (7) and since 1 ≤ fM
(0) we obtain,
max
ck (p0 , x) = max
f (x · p0 ) +
0
0
p ∈P

p ∈P

(7)
g(kxk)
k

to

g (kxk)
k

g (kxk)
M
f (x · q) +
f (0)
k


M
g (kxk)
≤
f (x · q) +
.
f (0)
k
≤

The rest of the proof follows by case analysis on the sign of x · p, i.e. (i) x · p ≥ 0 and (ii) x · p < 0.
Case (i): x · p ≥ 0. Substituting q = p in (8) yields


g (kxk)
M
0
max
ck (p , x) ≤
f (x · p) +
p0 ∈P
f (0)
k
M
M
ck (p, x) ≤
(bp + 1)ck (p, x),
=
f (0)
f (0)

(8)

(9)

where the last inequality follows by the assumption bp > 0. Case (ii): x · p < 0. In this case x · (−p) > 0.

8

Substituting q = −p in (8) yields


M
g (kxk)
max
ck (p , x) ≤
f (x · (−p)) +
p0 ∈P
f (0)
k


M
g (kxk)
≤
f (kxk kpk) +
f (0)
k


M
g (kxk)
≤
bp f (− kxk kpk) +
f (0)
k


M
g (kxk)
≤
bp f (x · p) +
,
f (0)
k
M
M
bp ck (p, x) ≤
(bp + 1)ck (p, x),
=
f (0)
f (0)
0

(10)
(11)
(12)
(13)
(14)

where (11) and (13) are by the Cauchy-Schwartz inequality and the monotonicity of f , and (12) follows by
substituting z = kxk in (5).
Theorem 10. Let ε, δ ∈ (0, 1), p ∈ P and bp > 0 such that for every z > 0


g (z)
g (z)
≤ bp f (− kpk z) +
.
f (kpk z) +
k
k

(15)

Then, there is a weighted set (Q, u) such that with probability at least 1 − δ, (Q, u) is an ε-coreset for
(P, 1, Rd , ck ). Moreover, by letting bmax ∈ arg maxp∈P bp and t = (1 + fM
(0) bmax ) ln n,

|Q| ∈ O

t
ε2



1
d log t + log
δ



Proof. Let p ∈ P , by Lemma 9 we obtain
max
ck (p0 , x) ≤
0

p ∈P

M
(bp + 1) ck (p, x) ≤
f (0)
M
(bmax + 1) ck (p, x).
f (0)

Where (16) is by Lemma 9 and (17) holds since for every p ∈ P , bp ≤ bmax . Thus, {p} is an

(16)
(17)
h

M
f (0)


i
(bmax + 1) − 1 -

L∞ coreset. Using the reduction in [27] we have that


M
d
t(P, 1, R , ck ) ∈ O t = (1 +
bmax ) ln n .
f (0)
By 5 we obtain the required result.

9

Example: Coreset For the Sigmoid Activation Function

We present an application to the framework described above for sums of sigmoid functions.
Lemma 11. Let f (z) =
and for every z ≥ 0,

1
1+e−z

for every z ∈ R and let c > 0. There is k0 > 0 such that for every k ≥ k0
z2
k
2
+ zk

f (cz) +
f (−cz)
Proof. See Lemma 20 in the appendix.

9

√
≤ 66c k.

Lemma 12. Let P = {p1 , . . . , pn } ⊂ Rd be a set of points, sorted by their length. I.e. kpi k ≤ pj
every 1 ≤ i ≤ j ≤ n. Let k > 0 and csigmoid,k (p, x) =

1
1+e−p·x

kxk2
k

for

d

for every x ∈ R and p ∈ P . Then


√
kpj k k+1
the sensitivity of every pj ∈ P is bounded by s(p) = sP,1,Rd ,csigmoid,k (p) ∈ O
, and the total
j
+

sensitivity is


t=

X
p∈P


n
√ X
pj
.
s(p) ∈ O log n + k
j
j=1

Proof. Define f (z) = 1+e1−z and g(z) = z 2 for every z ∈ R. Let x ∈ Rd , pj ∈ P and i ∈ [1, j] be an integer.
We substitute c = kpi k in Lemma 19 to obtain that for every z > 0
z2
k
2
+ zk

f (kpi k z) +
f (− kpi k z)
Denote bpi = 66 kpi k

√

≤ 66 kpi k

√
k.
2

k and multiply the above term by f (− kpi k z) + zk to get


z2
z2
f (kpi k z) +
≤ bpi f (− kpi k z) +
.
k
k
= z 2 , M = 1, f (0) = 21 yields

max
csigmoid,k (p0 , x) ≤ 2 bpi + 1 csigmoid,k (pi , x) .
0

Substituting in Lemma 9 p = pi , f (z) =

1
1+e−z , g (z)

(18)

p ∈P

Thus

csigmoid,k pj , x ≤ max
csigmoid,k (p0 , x)
p0 ∈P

≤2 bpi + 1 csigmoid,k (pi , x) ,

(19)
(20)


where (26) is since pj ∈ P and (27) is by (18). Dividing both sides by 2 bpi + 1 yields

csigmoid,k pj , x

csigmoid,k (pi , x) ≥
.
(21)
2 bpi + 1

We now proceed to bound the sensitivity of pj . Since the set of points p1 , . . . , pj is a subset of P , and

since the cost function csigmoid,k pj , x is positive we have that
X

csigmoid,k (p0 , x) ≥

p0 ∈P

j
X

csigmoid,k (pi , x) .

(22)

i=1

By summing (28) over i ≤ j, we obtain
j
X

csigmoid,k (pi , x) ≥ csigmoid,k (pj , x)

i=1

j
X
i=1

≥ csigmoid,k (pj , x)
where the last inequality holds since bpi = 66 kpi k
X

√

1
2(bpi + 1)
j

2(bpj + 1)

(23)

,

k ≤ bpj for every i ≤ j. Combining (29) and (30) yields

csigmoid,k (p0 , x) ≥

0

p ∈P

10

jcsigmoid,k (pj , x)
2(bpj + 1)

(24)

Therefore, the sensitivity is bounded by
csigmoid,k (pj , x)
0
x∈Rd
p0 ∈P csigmoid,k (p , x)
√
2(bpj + 1)
2(66 kpj k k + 1)
≤
≤
.
j
j

sP,1,Rd ,csigmoid,k (pj ) = sup P

Summing this sensitivity bounds the total sensitivity by


√
n
n
X
√ X
2(66 kpj k k + 1)
kp
k
j
.
∈ O log n + k
j
j
j=1
j=1

Theorem 13. Let P be a set of n points in the unit ball of Rd , ε, δ ∈ (0, 1), and k > 0. For every p, x ∈ Rd ,
let
2
1
kxk
csigmoid,k (p, x) =
+
.
1 + e−p·x
k
Let (Q, u) be the output of a call to Monotonic-Coreset(P, ε, δ, k); see Algorithm 1.
Then, with probability at least 1 − δ, (Q, u) is an ε-coreset for (P, 1, Rd , csigmoid,k ), i.e., for every x ∈ Rd
X

csigmoid,k (p, x) −

p∈P

≤ε

X

u(p)csigmoid,k (p, x)

p∈Q

X

csigmoid,k (p, x) .

p∈P

Moreover, for t = (1 +

√

k) log n,

|Q| ∈ O

t
ε2



1
d log t + log
δ



and (Q, u) can be computed in O(dn + n log n) time.
Proof. By [18], the dimension of (P, w, Rd , c) is at most d + 1, where (P, w) is a weighted set, P ⊆ Rd ,
and c(p, x) = f (p · x) for some monotonic and invertible function f . By Lemma 12, the total sensitivity of
(P, 1, Rd , csigmoid,k ) is bounded by




n
n
X
√ X
√
kpj k 
1
t ∈ O log n + k
= O log n + k
j
j
j=1
j=1


√
= O (1 + k) log n ,
where the last equality holds since the input points are in the unit ball.
Plugging these upper bounds on the dimension and total sensitivity of the query space in Theorem 5,
yields that a call to Algorithm 1, which samples points from P based on their sensitivity bound, returns the
desired coreset (Q, u). The running time is dominated by sorting the length of the points in O(n log n) time
after computing them in O(nd) time.

11

10

Example: Coreset for Logistic Regression

We show that our framework can be used for construction a coreset for logistic regression.
Lemma 14. Let f = log(1 + ex ) for every x ∈ R and let c > 0. Then, there is k0 > 0 such that for every
k ≥ k0 and for every 0 ≤ x ≤ R

2
log 2ecR √
f (cx) + xk
kc.
2 ≤ 3
log(2)
f (−cx) + xk
Proof. See Lemma 22 in the appendix.
Lemma 15. Let P = {p1 , . . . , pn } ⊂ Rd be a set of points, sorted by their length. I.e. kpi k ≤ pj

for

kxk2
k

x

every 1 ≤ i ≤ j ≤ n. Let R, k > 0 and clogistic,k (p, x) = log(1 + e ) +
for every x ∈ B(0, R) and
p ∈ P . Denote by B(0, R) the ball of radius R 
centered at theorigin. Then the sensitivity of every pj ∈ P
√
R2 kpj k k+R
, and the total sensitivity is
is bounded by s(p) = sP,1,B(0,R),clogistic,k (p) ∈ O
j


t=

X
p∈P


n
X
√
kp
k
j 
s(p) ∈ O R log n + R2 k
.
j
j=1

Proof. Define f (z) = log(1 + ez ) and g(z) = z 2 for every z ∈ R. Let x ∈ Rd , pj ∈ P and i ∈ [1, j] be an
integer. We substitute c = kpi k in Lemma 22 to obtain that for every z > 0
x2
k
2
+ xk

f (kpi k x) +
f (− kpi k x)


Denote bpi = 3

log 2ekpi kR
log(2)



√

≤3


log 2ekpi kR √
k kpi k .
log(2)

k kpi k and multiply the above term by f (− kpi k z) +
z2
≤ bpi
f (kpi k z) +
k



z2
f (− kpi k z) +
k

z2
k

to get


.

Substituting in Lemma 9 p = pi , f (z) = log(1 + ez ), g(z) = z 2 , M = log(1 + eR ), f (0) = log(2) yields
max clogistic,k (p0 , x) ≤

p0 ∈P

log(1 + eR )(bpi + 1)clogistic,k (pi , x)
.
log(2)

(25)

clogistic,k (pj , x) ≤ max
clogistic,k (p0 , x) ≤
0

(26)

log(1 + eR )(bpi + 1)clogistic,k (pi , x)
,
log(2)

(27)

Thus
p ∈P

where (26) is since pj ∈ P and (27) is by (25). Dividing both sides by
clogistic,k (pi , x) ≥

log(1+eR )
log(2) (bpi

clogistic,k (pj , x)
.
log(1+eR )
log(2) (bpi + 1)

12

+ 1) yields
(28)


We now proceed to bound the sensitivity of pj . Since the set of points p1 , . . . , pj is a subset of P , and
since the cost function clogistic,k (pj , x) is positive we have that
X

clogistic,k (p0 , x) ≥

j
X

clogistic,k (pi , x).

(29)

log(2)
≥
log(1 + eR )(bpi + 1)

(30)

0

i=1

p ∈P

By summing (28) over i ≤ j, we obtain
j
X

clogistic,k pi , x) ≥

i=1

clogistic,k (pj , x)

j
X
i=1

j log(2)
,
log(1 + eR )(bpj + 1)
√
R
)
= 3 log(1+e
log(2) kpi k k ≤ bpj for every i ≤ j. Combining (29) and (30)

clogistic,k (pj , x)

where the last inequality holds since bpi
yields
X
j log(2)clogistic,k (pj , x)
clogistic,k (p0 , x) ≥
log(1 + eR )(bpj + 1)
0

(31)

p ∈P

Therefore, the sensitivity is bounded by
sP,1,B(0,R),clogistic,k (pj ) =
sup
x∈B(0,R)

clogistic,k (pj , x)
≤
0
p0 ∈P clogistic,k (p , x)

P

log(1 + eR )(bpj + 1)

≤
j log(2)


√
R
)
log(1 + eR ) 3 log(1+e
kpj k k + 1
log(2)
j log(2)

√
R2 kpj k k+R
.
j


Thus, sP,1,B(0,R),clogistic,k (pj ) ∈ O

n
X
R 2 pj

√
j

j=1

k+R

.

Summing this sensitivity bounds the total sensitivity by



n
X
√
kp
k
j 
∈ O R log n + R2 k
.
j
j=1

Theorem 16. Let P be a set of n points in the unit ball of Rd , ε, δ ∈ (0, 1), and R, k > 0. For every
p ∈ Rd ,x ∈ B(0, R) let
2
kxk
clogistic,k (p, x) = log (1 + ep·x ) +
.
k
Let (Q, u) be the output of a call to Monotonic-Coreset(P, ε, δ, k).
Then, with probability at least 1 − δ, (Q, u) is an ε-coreset for (P, 1, Rd , clogistic,k ), i.e., for every x ∈ Rd
X

clogistic,k (p, x) −

p∈P

≤ε

X
p∈Q

X

clogistic,k (p, x) .

p∈P

13

u(p)clogistic,k (p, x)

√
Moreover, for t = R log n(1 + R k),

|Q| ∈ O

t
ε2



1
d log t + log
δ



and (Q, u) can be computed in O(dn + n log n) time.
Proof. By [18], the dimension of (P, w, Rd , c) is at most d + 1, where (P, w) is a weighted set, P ⊆ Rd ,
and c(p, x) = f (p · x) for some monotonic and invertible function f . By Lemma 15, the total sensitivity of
(P, 1, Rd , clogistic,k ) is bounded by


n
X
√
kpj k 
=
t ∈ O R log n + R2 k
j
j=1


n

X
√
√ 
1
= O R log n(1 + R k) ,
O R log n + R2 k
j
j=1
where the last equality holds since the input points are in the unit ball.
Plugging these upper bounds on the dimension and total sensitivity of the query space in Theorem 5,
yields that a call to Monotonic-Coreset, which samples points from P based on their sensitivity bound,
returns the desired coreset (Q, u). The running time is dominated by sorting the length of the points in
O(n log n) time after computing them in O(nd) time. Sampling m = |Q| points from n points according to
such a given distribution takes O(1) time after pre-processing of O(n) time.

11

Experimental Results

We implemented Algorithm 1 and run it on both synthetic and real-world datasets as explained below. To
be consistent with the theoretical results, we apply the algorithm specifically on the sigmoid function, and
as common in related coresets papers, we also focus on the traditional off-line construction. This is since
the approximation error of the streaming, distributed and dynamic versions of such coreset constructions
is based on running the off-line versions independently on multiple subsets of the data, merge the resulting
coreset and reduce them again recursively. We leave these extensions to the full version of the paper.
Open code.
For the benefit of the community, and for reproducing our experimental results, our code is
open under the GPL license and all the experiments are reproducible.

11.1

Minimizing Sum of Sigmoids

We used 2 datasets from the UCI repository Lichman (2013) and a synthetic data for our experiments.
Synthetic dataset. This data contains a set of n = 20, 010 points in R2 . 20, 000 of the points were generated by sampling a two dimensional normal distribution with mean µ1 = (10, 000, 10, 000) and covariance
0
matrix Σ1 = ( 0.0025
0
0.0025 ) and 10 points were generated by sampling a two dimensional normal distribution
0
with mean µ2 = (−9998, −9998) and covariance matrix Σ2 = ( 0.0025
0
0.0025 )
Bank marketing dataset [22] 1 consists n = 20, 000 records. Each record is a d = 10 dimensional vector
with numerical values. The data was generated for direct marketing campaigns of a Portuguese banking
institution. Each record represents a marketing call to a client, that aims to convince him/her to buy a
product (bank term deposit). A binary label (yes or no) was added to each record. We used the numerical
1 https://archive.ics.uci.edu/ml/datasets/bank+marketing

14

0.0010

0.0006 +8.349e 1

+8.348e 1

Coreset
Uniform Sampling
Full Data

0.0005

Success Rate

0.0008
0.0006
0.0004

0.0004
0.0003
0.0002

0.0002

0.0001
Coreset

10000

Uniform Sampling

20000

file

(a) Error box-plots for 35, 000 points sampled from the Cifar10
dataset using uniform sampling and our coreset sampling scheme.

30000

Subset Size

40000

50000

(b) The success rate for classifying the Cifar10 dataset.

Figure 1: Using Coresets to boost Cifar10 classification
values of the records to predict if a subscription was made.This dataset was also used for experimentation
in [29, 4]. The challenge is to compute a classification model for this supervised data, that gets a record
that represents a potential client as an input, and returns the binary label as an output, or more generally,
an estimated probability of the event that the client would buy the product. Such a model may also tell
the company the connection between the features of the client and the outcome of the call, as well as the
importance of each feature in the decision.
Wine Quality dataset [5] 2 This dataset contains records of physicochemical and sensory data about
the red and white variants of the Portuguese “Vinho Verde” win. Each record in the dataset is a d = 12
dimensional numerical feature vector. Each record in the dataset is labeled ’white’ or ’red’. The total number
of samples is n = 6497. This dataset was also used for experimentation in [28, 7, 19]. The data is the results
of a chemical analysis of wines grown in the same region in Italy but derived from different cultivars. The
analysis determined the quantities of 13 constituents found in each of the types of wines. The goal is to
train a classification model for this labeled data, which gets the chemical data of a wine sample as an input
ad returns the binary label as an output.
11.1.1

Experimental Setup

For a given size m we computed a coreset of size m using Algorithm 1. We used the datasets above to
produce coresets of size 0.1n ≤ m ≤ 0.9n, where n is the size of the full data, then we normalized the data
and found the optimal solution to the problem with values of k = 100, 500, 1000 using the BFGS algorithm.
We repeated the experiment with a uniform sample of size m. For each optimal solution that we have
found, we computed the sum of sigmoids and denoted these ”approximated solutions” by C1 and C2 for our
algorithm and uniform sampling respectively. The ”ground truth” C k was computed using BFGS on the
entire dataset. The empirical error is then defined to be Et = CCkt − 1 for t = 1, 2. For every size m we
computed E1 and E2 100 times and calculated the mean of the results.

11.2

Convolutional Neural Networks

While we do not have coreset for the set of complete neural networks, we suggest a novel technique to use
coresets for improving existing state-of-the art networks. In this network, the layers except from the last
one get the original input and produce a set P of the input with different features that correspond to the
neurons in this layer. By computing coreset Q for P and the sigmoid function, we can train each neuron
much faster by running existing heuristic for sigmoid optimization on Q. The result is a suggestion for a
2 https://archive.ics.uci.edu/ml/datasets/wine+quality

15

0.0000040

Coreset
Uniform Sampling

0.0000035

Coreset
Uniform Sampling

0.0007
0.0006

0.0004

0.0000030

0.0005

0.0000020

0.0003

Error

Error

0.0000025
Error

Coreset
Uniform Sampling

0.0005

0.0003

0.0002

0.0000015
0.0000010

0.0002

0.0001

0.0000005
0.0000000 1000 2000 3000 4000 5000 6000 7000 8000 9000
Subset Size

(a) Synthetic dataset, k = 100

0.00001000

0.0004

0.0001
2000

3000

4000

5000

Subset Size

6000

7000

(b) Bank Marketing dataset, k = 500

0.0000

500

1000

1500

Subset Size

2000

(c) Wine dataset, k = 1000

Figure 2: Comparison between uniform sampling and our coreset.
0.00035

0.0004

0.00030
0.0003

0.00025
0.00020

0.0002

0.00015
0.00010

0.0001

0.00005
0.0000

Coreset

0.00000

Uniform Sampling

(a) Bank Marketing dataset, k = 500

Coreset

Uniform Sampling

(b) Wine dataset, k = 1000

Figure 3: Error box-plots for 25, 000 points sampled from the real datasets using uniform sampling and our
coreset sampling scheme.
new weights for the last layer of the network. For our experiments we used the Cifar10 dataset[20], which
consists of 60, 000 32 × 32 color images in 10 classes with 6000 images per class. We used 50, 000 points
as training data and 10, 000 points for testing data. For m = 5, 000, 15, 000, 25, 000, 35, 000, we sampled m
points from P using our implementation of Algorithm 1, and trained the a new softmax output layer using
the sampled subset. We then used the testing data to test the performance of the network. We compared
our algorithm to uniform sampling and to the success rate of the original set. We repeated every experiment
10 times and calculated the average of the results.

11.3

Results

Figure 2 depicts results for the sigmoid experiment It can be seen that our sampling algorithm outperforms
uniform sampling. Important to note, that our algorithm starts with small error value compared to others
and improves error value gradually with sample size, while two others starts with greater error values and
succeeds to converge to smaller values only for large sample subsets
Figure 3 shows the box-plot of error distribution for the 100 experiments performed with 25, 000 points
subsets of the Wine and Bank marketing datasets. It can be seen that the variance of our algorithm is
considerably smaller then the variance of the uniform sampling scheme.
The results of the Cifar10 classification are depicted in Figure 1(b). It can be seen that out coreset
outperform the results obtained by uniform sampling and the results obtained by training the network on
the original dataset. These results suggest that much can be gained from using coresets for training of NN.
Figure 1(a) shows the box-plot of error distribution for the 10 experiments performed with 35, 000 points
subsets of the Cifar10 dataset.

16

References
[1] Coreset for monotonic functions with applications to deep learning full version, 2018.
[2] Christos Boutsidis, Petros Drineas, and Malik Magdon-Ismail. Near-optimal coresets for least-squares
regression. IEEE transactions on information theory, 59(10):6880–6892, 2013.
[3] Vladimir Braverman, Dan Feldman, and Harry Lang. New frameworks for offline and streaming coreset
constructions. arXiv preprint arXiv:1612.00889, 2016.
[4] Flavio Chierichetti, Ravi Kumar, Silvio Lattanzi, and Sergei Vassilvitskii. Fair clustering through
fairlets. In Advances in Neural Information Processing Systems, pages 5036–5044, 2017.
[5] Paulo Cortez, António Cerdeira, Fernando Almeida, Telmo Matos, and José Reis. Modeling wine
preferences by data mining from physicochemical properties. Decision Support Systems, 47(4):547–553,
2009.
[6] Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W Mahoney. Sampling
algorithms and coresets for \ell p regression. SIAM Journal on Computing, 38(5):2060–2078, 2009.
[7] Gal Elidan. Copula bayesian networks. In Advances in neural information processing systems, pages
559–567, 2010.
[8] Dan Feldman, Matthew Faulkner, and Andreas Krause. Scalable training of mixture models via coresets.
In Advances in neural information processing systems, pages 2142–2150, 2011.
[9] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In
Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 569–578. ACM,
2011.
[10] Dan Feldman, Morteza Monemizadeh, and Christian Sohler. A ptas for k-means clustering based on
weak coresets. In Proceedings of the twenty-third annual symposium on Computational geometry, pages
11–18. ACM, 2007.
[11] Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constantsize coresets for k-means, pca and projective clustering. In Proceedings of the Twenty-Fourth Annual
ACM-SIAM Symposium on Discrete Algorithms, pages 1434–1453. SIAM, 2013.
[12] Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constantsize coresets for k-means, pca and projective clustering. In Proceedings of the Twenty-Fourth Annual
ACM-SIAM Symposium on Discrete Algorithms, pages 1434–1453. Society for Industrial and Applied
Mathematics, 2013.
[13] Dan Feldman and Leonard J Schulman. Data reduction for weighted and outlier-resistant clustering.
In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1343–
1354. Society for Industrial and Applied Mathematics, 2012.
[14] Dan Feldman and Tamir Tassa. More constraints, smaller coresets: constrained matrix approximation
of sparse big data. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining (KDD’15), pages 249–258. ACM, 2015.
[15] Sariel Har-Peled. Coresets for discrete integration and clustering. In International Conference on
Foundations of Software Technology and Theoretical Computer Science, pages 33–44. Springer, 2006.
[16] Sariel Har-Peled, Dan Roth, and Dav Zimak. Maximum margin coresets for active and noise tolerant
learning. In IJCAI, pages 836–841, 2007.
[17] J. Hellerstein. Parallel programming in the age of big data. Gigaom Blog. 9th November, 2008.
17

[18] Jonathan Huggins, Trevor Campbell, and Tamara Broderick. Coresets for scalable bayesian logistic
regression. In Advances In Neural Information Processing Systems, pages 4080–4088, 2016.
[19] Hiroshi Kajino, Yuta Tsuboi, and Hisashi Kashima. A convex formulation for learning from crowds.
Transactions of the Japanese Society for Artificial Intelligence, 27(3):133–142, 2012.
[20] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.
[21] M. Langberg and L. J. Schulman. Universal ε approximators for integrals. To appear in proceedings of
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010.
[22] Sérgio Moro, Paulo Cortez, and Paulo Rita. A data-driven approach to predict the success of bank
telemarketing. Decision Support Systems, 62:22–31, 2014.
[23] T. Segaran and J. Hammerbacher. Beautiful Data: The Stories Behind Elegant Data Solutions. O’Reilly
Media, 2009.
[24] Jiřı́ Šı́ma. Training a single sigmoidal neuron is hard. Training, 14(11), 2006.
[25] Ivor W Tsang, James T Kwok, and Pak-Ming Cheung. Core vector machines: Fast svm training on
very large data sets. Journal of Machine Learning Research, 6(Apr):363–392, 2005.
[26] V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to
their probabilities. Theory Prob. Appl., 16:264–280, 1971.
[27] Kasturi Varadarajan and Xin Xiao. A near-linear algorithm for projective clustering integer points.
In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1329–
1342. SIAM, 2012.
[28] Shusen Wang and Zhihua Zhang. Improving cur matrix decomposition and the nyström approximation
via adaptive sampling. The Journal of Machine Learning Research, 14(1):2729–2769, 2013.
[29] Peifeng Yin, Ping Luo, and Taiga Nakamura. Small batch or large batch: Gaussian walk with rebound
can teach. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery
and Data Mining, pages 1275–1284. ACM, 2017.
[30] Yan Zheng and Jeff M Phillips. Coresets for kernel regression. arXiv preprint arXiv:1702.03644, 2017.

18

12

Appendix

Lemma 17. Let f : R → (0, ∞) be a monotonic increasing function such that f (0) > 0. Let c, k > 0. There
is exactly one number xkc > 0 that simultaneously satisfies the following claims.

 √
(i) f −c kxkc = x2kc .
 √ 
(ii) For every x > 0, if f −c kx > x2 then x < xkc .
 √ 
(iii) For every x > 0, if f −c kx < x2 then x > xkc .
(iv) There is k0 > 0 such that for every k ≥ k0
√
1
≤ c k.
xkc
Proof. Let g(x) = x2 . Define

√
hkc (x) = f (−c kx) − g(x).

(32)

hkc (0) = f (0)

(33)

(i): It holds that
and


f (0) + 1 < 0,
(34)
 √ 
p

where (34) holds since f −c kx ≤ f (0) for every x > 0, and g
f (0) + 1 = f (0)+1. From (33) and (34)
h
p

i
we have that 0 ∈ hkc
f (0) + 1 , hkc (0) . Using the Intermediate Value Theorem (Theorem 23) we have
 p

that there is x1 ∈ 0, f (0) + 1 such that
hkc

p

hkc (x1 ) = 0.

(35)

We prove that x1 is unique. By contradiction. Assume that there is x2 6= x1 such that
hkc (x1 ) = hkc (x2 ) = 0.

(36)

Wlog assume that x1 < x2 . By The Mean Value Theorem (Theorem 24), there is r ∈ (x1 , x2 ) such that
hkc (x2 ) − hkc (x1 )
x2 − x1
= 0,

h0kc (r) =

(37)
(38)

where (38) is by (36). The derivative of hkc is
  √ 
0
h0kc (x) = f −c kx − g(x)
 √ 
√
= − c kf 0 −c kx − g 0 (x) < 0,

(39)
(40)

where (39) is by (32) and (40) is since f is monotonic increasing and thus f 0 (x) > 0 for every x ∈ R and
x, k, c > 0. (40) is a contradiction to (38). Thus the Assumption (36) is false and x1 is unique.
By (32) and (35)
 √

f −c kx1 = g(x1 ).
(41)

19

By letting xkc = x1 and recalling that g(x) = x2 we obtain
 √

f −c kxkc = x2kc .
 √ 
(ii): Let x > 0 such that f −c kx > x2 . Plugging this and the definition g(x) = x2 in (32) yields
hkc (x) > 0.

(42)

We already proved that h0kc (x) < 0 always. By the Inverse of Strictly Monotone Function Theorem (The−1
orem 25) we have that the inverse h−1
kc of hkc is a strictly monotone decreasing function. Applying hkc on
both sides of (42) gives
x < xkc .
 √ 
(iii): Let x > 0 such that f −c kx < x2 . By this and by the definition of g and (32) we have
hkc (x) < 0.

(43)

We already proved that h0kc (x) < 0 always. By the Inverse of Strictly Monotone Function Theorem (Theo−1
rem 25) we have that hkc has a strictly monotone decreasing inverse function h−1
kc . Applying hkc on both
sides of (43) gives
x > xkc .
(iv): We need to prove that there is k0 such that for every k > k0 we have
1
xkc ≥ √
c k

(44)

1
xkc < √ .
c k

(45)

By contradiction, assume that

It holds that

 √

f −c kxkc > f (−1).
√
where (46) holds since f is increasing and by (45) −c kxkc > −1. Since limk→∞
such that for every k > k0
f (−1) >

(46)
1
c2 k

= 0, there is k0 > 0

1
c2 k

(47)

> x2kc ,
where (47) is by (45). Plugging (47) in (46) yields
 √

f −c kxkc > x2kc .

(48)

In contradictions to (i). Thus
1
xkc ≥ √
k c

(49)

Lemma 18. Let f be as in Lemma 17 and let x1,1 > 0 which is obtained by applying Lemma 17(i) with f
and k = c = 1. Then, For every x ≥ 0
(
)
2
f (x) + x2
≤ max 2, 2
.
f (−x) + x2
x1,1
20

Proof. Let x ≥ 0. Substituting k = c = 1 in Lemma 17(i) yields that f (−x1,1 ) = x21,1 . We show that
o
n
f (x)+x2
2
via the following case analysis. (i) f (x) ≥ x2 , (ii) f (x) ≥ x2 , (iii) f (x) < x2 and
≤
max
2,
2
2
f (−x)+x
x
1,1

f (−x) ≥ x2 , and (iv) f (x) < x2 and f (−x) < x2 .
Case (i): f (x) ≥ x2 and f (−x) ≥ x2 . Since f (−x) ≥ x2 , by substituting k = c = 1 in Lemma 17(ii),
we have that x ≤ x1,1 . Hence
f (−x) + x2 ≥f (−x)

(50)

≥f (−x1,1 )

(51)

=x21 ,

(52)

where (50) is since x2 > 0, (51) is since f is increasing and x ≤ x1,1 , and (52) is by definition of x1,1 . By
adding f (x) to both sides of the assumption f (x) ≥ x2 of Case (i) we obtain
2f (x) ≥ f (x) + x2 .

(53)

(
)
f (x) + x2
2f (x)
2
2
≤ 2
≤ 2 ≤ max 2, 2
.
f (−x) + x2
x1,1
x1,1
x1,1

(54)

By (53) and (52) we obtain

Case (ii): f (x) ≥ x2 and f (−x) < x2 . Since f (−x) < x2 , substituting k = c = 1 in Lemma 17(iii),
there is x1,1 such that
f (−x) + x2 ≥x2
>x21,1 ,

(55)
(56)

where (55) is since f is a positive function and (56) is since x > x1,1 . By adding f (x) to both sides of the
assumption f (x) ≥ x2 of Case (ii) we have that
f (x) + x2 ≤ 2f (x) .

(57)

(
)
2f (x)
2
2
f (x) + x2
≤ 2
≤ 2 ≤ max 2, 2
.
f (−x) + x2
x1,1
x1,1
x1,1

(58)

By (57)) and (56) we obtain

Case (iii): f (x) < x2 and f (−x) ≥ x2 . By adding x2 to both sides of the assumption f (x) < x2 of Case
(iii) we have that
f (x) + x2 ≤ 2x2 .
(59)
Furthermore, since f (−x) > 0 we have that
f (−x) + x2 ≥ x2 .

(60)

(
)
f (x) + x2
2x2
2
≤ 2 ≤ 2 ≤ max 2, 2
.
f (−x) + x2
x
x1,1

(61)

Combining (59) and (60) we obtain

Case (iv): f (x) < x2 and f (−x) < x2 . By adding x2 to both sides of the assumption f (x) < x2 of
Case (iv) we have that
f (x) + x2 ≤ 2x2 .
(62)
21

Furthermore, since f (−x) > 0 we have that
f (−x) + x2 ≥ x2 .

(63)

(
)
2x2
2
f (x) + x2
≤ 2 ≤ 2 ≤ max 2, 2
.
f (−x) + x2
x
x1,1

(64)

Combining (62) and (63) we obtain

Combining the results of the case analysis: (54), (58), (61),and (64) we have that
(
)
2
f (x) + x2
≤ max 2, 2
.
f (−x) + x2
x1,1

(65)

Lemma 19. Let f be as in Lemma 17, x1,1 as in Lemma 18 and c > 0. Assume that there is D > 1 such
 < D for every y ≥ 0. Then, there is k0 > 0 such that for every k ≥ k0 and for every x ≥ 0,
that f(cy)
y
f

√

k

x2
k
2
+ xk

(

f (cx) +
f (−cx)

≤ 3D max 2,

2

)

x21,1

√
c k.

Proof. Let x ≥ 0 and k, c > 0. We have that
f (cx) +

where (66) holds since

f(cy)

f

y
√
k

x2
≤Df
k

x2
k
) 


2
x
x2
≤D max 2, 2
f −√
,
+
x1,1
k
k


x
√
k
(



(66)

+

< D for every y ≥ 0 and (67) holds since

x2
k

(67)
2

≤ D xk , and since, by Lemma 18,

for every positive z we have that
(
)
2
f (z) + z 2
≤ max 2, 2
.
f (−z) + z 2
x1,1
Dividing (67) by f (−cx) +

x2
k

yields
x2
k
2
+ xk

f (cx) +
f (−cx)
We now proceed to bound Rck =

)   x  x2 
f − √k + k
2

.
≤ D max 2, 2
2
x1,1
f (−cx) + xk
(



2
f − √x + xk
k

2

f (−cx)+ xk

. By denoting z =

Rck =

√x
k

f (−z) + z 2
 √ 
.
f −c kz + z 2

(68)

we have that
(69)

 √ 
We now compute an upper bound for Rck using the following case analysis: (i) f (−z) ≥ z 2 and f −c kz ≥
 √ 
 √ 
z 2 , (ii) f (−z) < z 2 and f −c kz < z 2 , (iii), and (iv) f (−z) < z 2 and f −c kz ≥ z 2 . Let zck > 0 be
 √

2
such that f −c kzck = zck
as given by Lemma 17(i). There are four cases
22

 √ 
 √ 
Case (i): f (−z) ≥ z 2 and f −c kz ≥ z 2 . Since f −c kz ≥ z 2 , by Lemma 17(iii) we have that
z ≤ zck . Thus
 √ 
 √

f −c kz ≥f −c kzck
(70)
2
=zck
,

(71)

where (70) holds since f is monotonic and z ≤ zck , and (71) is from the definition of zck . Furthermore, by
adding f (−z) to both sides of the assumption f (−z) ≥ z 2 , we have that
f (−z) + z 2 ≤ 2f (−z) .

(72)

Substituting (72) and (71) in (69) yields
Rck =

2f (−z)
f (−z) + z 2
1
 √ 
≤
≤ 2 ,
2
zck
zck
f −c kz + z 2

(73)

where the last inequality, is sincef (−z) ≤1/2 for every z ≥ 0.
√
Case (ii): f (−z) < z 2 and f −c kz < z 2 . By adding z 2 to both sides of the assumption f (−z) < z 2 ,
we have that
f (−z) + z 2 ≤ 2z 2 .
(74)
 √ 
Furthermore, since f −c kz > 0 we have that
 √ 
f −c kz + z 2 ≥ z 2 .

(75)

f (−z) + z 2
2z 2
 √ 
≤ 2 = 2.
z
f −c kz + z 2

(76)

Combining (74) and (75) yields
Rck =

 √ 
 √ 
Case (iii): f (−z) ≥ z 2 and f −c kz < z 2 . Since f −c kz < z 2 , by Lemma 17 we have that
z > zck . Thus
 √ 
2
f −c kz + z 2 ≥ z 2 ≥ zck
.
(77)
By adding f (−z) to both sides of the assumption f (−z) ≥ z 2 , we have that
2f (−z) ≥ f (−z) + z 2 .

(78)

Substituting (77) and (78) in (69) yields
Rck =

2f (−z)
f (−z) + z 2
1
 √ 
≤
≤ 2 .
2
z
z
2
ck
ck
f −c kz + z

(79)

 √ 
Case (iv): f (−z) < z 2 and f −c kz ≥ z 2 . By adding z 2 to both sides of the assumption f (−z) < z 2 ,
we have that
f (−z) + z 2 ≤ 2z 2 .
(80)
 √ 
Since f −c kz > 0 we have that
 √ 
f −c kz + z 2 > z 2 .
(81)
23

Plugging (80) and (81) in (69) yields
Rck =

f (−z) + z 2
2z 2
 √ 
≤ 2 = 2.
z
f −c kz + z 2

(82)

Combining the results of the case analysis: (73), (76), 79,and (82) we have that
Rck ≤ 2 +

1
2 .
zck

(83)

By Lemma 17(iv) we have that there is k0 > 0 such that for every k ≥ k0 ,

Substituting (84) in (83) yields

√
1
≤ c k.
2
zck

(84)

√
Rck ≤ 2 + c k,

(85)

by (68) we have
x2
k
2
+ xk

f (cx) +
f (−cx)

(
≤ D max 2,

)

2
x21,1

Rck .

Substituting (85) in the last term gives
x2
k
2
+ xk

f (cx) +
f (−cx)
It holds that for every k ≥

Lemma 20. Let f =
and for every x ≥ 0

1
c2

1
1+e−x

(
≤ D max 2,

2

)



x21,1

√ 
2+c k .

√
we have 2 ≤ 2c k plugging this in the above term yields
(
)
2
√
f (cx) + xk
2
≤ 3D max 2, 2
c k.
x2
x1,1
f (−cx) + k

for every x ∈ R and let c > 0. Then, there is k0 > 0 such that for every k ≥ k0
x2
k
2
+ xk

f (cx) +
f (−cx)

√
≤ 66c k

Proof. It holds that f (0) > 0. Applying Lemma 17 with k = c = 1 yields x1,1 such that f (−x1,1 ) = x21,1 .
We now bound x1,1 . Calculation shows that
 p
 p
2
f − ln (1.2) >
ln (1.2) .
Plugging x =

p
ln (1.2), k = 1, c = 1 in Lemma 17(ii) yields
p
x1 ≥ ln (1.2).

(86)

By applying Lemma 18 with f we have
(
)
f (x) + x2
2
≤ max 2, 2
≤ 11,
f (−x) + x2
x1,1
24

(87)

where the last inequality is by (94).
For every c, k > 0 it holds that
f (cx)
  ≤ 2,
(88)
f √xk
 
where (92) holds since for every y > 0 f (y) ≤ 1 and f √xk ≥ 12 . Applying Lemma 19 with f, D = 2 yields
x2
k
2
+ xk

f (cx) +
f (−cx)

√
≤ 66 kc.

(89)


2
Lemma 21. Let f = 1+e1−x
for every x ∈ R and let c > 0. Then, there is k0 > 0 such that for every
k ≥ k0 and for every x ≥ 0
2
√
f (cx) + xk
≤ 168c k
x2
f (−cx) + k
Proof. It holds that f (0) > 0. Applying Lemma 17 with k = c = 1 yields x1,1 such that f (−x1,1 ) = x21,1 .
We now bound x1,1 . Calculation shows that
 p
 p
2
f − ln (1.15) >
ln (1.15) .
Plugging x =

p
ln (1.15), k = 1, c = 1 in Lemma 17(ii) yields
p
x1 ≥ ln (1.15).

(90)

By applying Lemma 18 with f we have
(
)
f (x) + x2
2
≤ max 2, 2
≤ 14,
f (−x) + x2
x1,1

(91)

where the last inequality is by (94).
For every c, k > 0 it holds that
f (cx)
  ≤ 4,
(92)
f √xk
 
where (92) holds since for every y > 0 f (y) ≤ 1 and f √xk ≥ 14 . Applying Lemma 19 with f, D = 4 yields
x2
k
2
+ xk

f (cx) +
f (−cx)

√
≤ 168 kc.

(93)

Lemma 22. Let f = log(1 + ex ) for every x ∈ R and let c > 0. Then, there is k0 > 0 such that for every
k ≥ k0 and for every 0 ≤ x ≤ R

2
log 2ecR √
f (cx) + xk
kc.
2 ≤ 3
log(2)
f (−cx) + xk

25

Proof. Let 0 ≤ x ≤ R. Applying Lemma 17 with k = c = 1 yields x1,1 such that f (−x1,1 ) = x21,1 . We now
bound x1,1 . Calculation shows that
 p
2
 p
ln (1.2) .
f − ln (1.2) >
p
Plugging x = ln (1.2), k = 1, c = 1 in Lemma 17(ii) yields
p
x1 ≥ ln (1.2).
(94)
By applying Lemma 18 with f we have
(
)
2
f (x) + x2
≤ max 2, 2
≤ 11,
f (−x) + x2
x1,1

(95)

where the last inequality is by (94).
For every c, k > 0, since x ≤ R and f is increasing we have that
f (cx) ≤ f (cR) ,

(96)

furthermore, since x ≥ 0 and f is increasing we have that


x
f √
≥ log (2) .
k
We have that
f (cR)
f (cx)
 ≤
x
log (2)
f √

(97)

(98)

k

log 1 + ecR
log (2)

log 2ecR
≤
,
log (2)



=

(99)
(100)

where (98) is by (96) and (97), (99) is by the definition of f and (100) holds since Rc > 0. Applying
log(2ecR )
Lemma 19 with f, D = log(2) yields

2
log 2ecR √
f (cx) + xk
kc.
(101)
2 ≤ 3
log (2)
f (−cx) + xk
Theorem 23 (Intermediate Value Theorem). Let a, b ∈ R such that a < b and let f : [a, b] → R be a
continuous function. Then for every u such that
min {f (a) , f (b)} ≤ u ≤ max {f (a) , f (b)} ,
there is c ∈ (a, b) such that f (c) = u.
Theorem 24 (Mean Value Theorem). Let a, b ∈ R such that a < b and f : [a, b] → R a continuous function
on the closed interval [a, b] and differentiable on the open interval (a, b) . Then there is c ∈ (a, b) such that
f (b) − f (a)
.
b−a
Theorem 25 (Inverse of Strictly Monotone Function Theorem). Let I ⊆ R. Let f : I → R be strictly
monotonic function. Let the image of f be J. Then f has an inverse function f −1 and
f 0 (c) =

• If f is strictly increasing then so is f −1 .
• If f is strictly decreasing then so is f −1 .

26

