In order to cluster the textual data with high dimension in modern data analysis, the spherical
k
-means clustering is presented. It aims to partition the given points with unit length into
k
sets so ...as to minimize the within-cluster sum of cosine dissimilarity. In this paper, we mainly study seeding algorithms for spherical
k
-means clustering, for its special case (with separable sets), as well as for its generalized problem (
α
-spherical
k
-means clustering). About the spherical
k
-means clustering with separable sets, an approximate algorithm with a constant factor is presented. Moreover, it can be generalized to the
α
-spherical separable
k
-means clustering. By slickly constructing a useful function, we also show that the famous seeding algorithms such as
k
-means++ and
k
-means|| for
k
-means problem can be applied directly to solve the
α
-spherical
k
-means clustering. Except for theoretical analysis, the numerical experiment is also included.
The problem of maximizing a normalized monotone non-submodular set function subject to a cardinality constraint arises in the context of extracting information from massive streaming data. In this ...paper, we present four streaming algorithms for this problem by utilizing the concept of diminishing-return ratio. We analyze these algorithms to obtain the corresponding approximation ratios, which generalize the previous results for the submodular case. The numerical experiments show that our algorithms have better solution quality and competitive running time when compared to an existing algorithm.
Stochastic optimization has experienced significant growth in recent decades, with the increasing prevalence of variance reduction techniques in stochastic optimization algorithms to enhance ...computational efficiency. In this paper, we introduce two projection-free stochastic approximation algorithms for maximizing diminishing return (DR) submodular functions over convex constraints, building upon the Stochastic Path Integrated Differential EstimatoR (SPIDER) and its variants. Firstly, we present a SPIDER Continuous Greedy (SPIDER-CG) algorithm for the monotone case that guarantees a
(
1
-
e
-
1
)
OPT
-
ε
approximation after
O
(
ε
-
1
)
iterations and
O
(
ε
-
2
)
stochastic gradient computations under the mean-squared smoothness assumption. For the non-monotone case, we develop a SPIDER Frank–Wolfe (SPIDER-FW) algorithm that guarantees a
1
4
(
1
-
min
x
∈
C
‖
x
‖
∞
)
OPT
-
ε
approximation with
O
(
ε
-
1
)
iterations and
O
(
ε
-
2
)
stochastic gradient estimates. To address the practical challenge associated with a large number of samples per iteration, we introduce a modified gradient estimator based on SPIDER, leading to a Hybrid SPIDER-FW (Hybrid SPIDER-CG) algorithm, which achieves the same approximation guarantee as SPIDER-FW (SPIDER-CG) algorithm with only
O
(
1
)
samples per iteration. Numerical experiments on both simulated and real data demonstrate the efficiency of the proposed methods.
Spherical
k
-means clustering as a known NP-hard variant of the
k
-means problem has broad applications in data mining. In contrast to
k
-means, it aims to partition a collection of given data ...distributed on a spherical surface into
k
sets so as to minimize the within-cluster sum of cosine dissimilarity. In the paper, we introduce spherical
k
-means clustering with penalties and give a
2
max
{
2
,
M
}
(
1
+
M
)
(
ln
k
+
2
)
-approximation algorithm. Moreover, we prove that when against spherical
k
-means clustering with penalties but on separable instances, our algorithm is with an approximation ratio
2
max
{
3
,
M
+
1
}
with high probability, where
M
is the ratio of the maximal and the minimal penalty cost of the given data set.
We analyze the convergence of the price of anarchy (PoA) of Nash equilibria in atomic congestion games with growing total demand
T
. When the cost functions are polynomials of the same degree, we ...obtain explicit rates for a rapid convergence of the PoAs of pure and mixed Nash equilibria to 1 in terms of 1/
T
and
d
max
/
T
, where
d
max
is the
maximum
demand controlled by an individual. Similar convergence results carry over to the random inefficiency of the random flow induced by an arbitrary mixed Nash equilibrium. For arbitrary polynomial cost functions, we derive a related convergence rate for the PoA of pure Nash equilibria (if they exist) when the demands fulfill certain regularity conditions and
d
max
is bounded as
T
→
∞
.
In this general case, also the PoA of mixed Nash equilibria converges to 1 as
T
→
∞
when
d
max
is bounded. Our results constitute the first convergence analysis for the PoA in atomic congestion games and show that selfish behavior is well justified when the total demand is large.
The online optimization model was first introduced in the research of machine learning problems (Zinkevich, Proceedings of ICML, 928–936, 2003). It is a powerful framework that combines the ...principles of optimization with the challenges of online decision-making. The present research mainly consider the case that the reveal objective functions are convex or submodular. In this paper, we focus on the online maximization problem under a special objective function
Φ
(
x
)
:
0
,
1
n
→
R
+
which satisfies the inequality
1
2
⟨
u
T
∇
2
Φ
(
x
)
,
u
⟩
≤
σ
·
‖
u
‖
1
‖
x
‖
1
⟨
u
,
∇
Φ
(
x
)
⟩
for any
x
,
u
∈
0
,
1
n
,
x
≠
0
. This objective function is named as one sided
σ
-smooth (OSS) function. We achieve two conclusions here. Firstly, under the assumption that the gradient function of OSS function is L-smooth, we propose an
(
1
-
exp
(
(
θ
-
1
)
(
θ
/
(
1
+
θ
)
)
2
σ
)
)
- approximation algorithm with
O
(
T
)
regret upper bound, where
T
is the number of rounds in the online algorithm and
θ
,
σ
∈
R
+
are parameters. Secondly, if the gradient function of OSS function has no L-smoothness, we provide an
1
+
(
(
θ
+
1
)
/
θ
)
4
σ
-
1
-approximation projected gradient algorithm, and prove that the regret upper bound of the algorithm is
O
(
T
)
. We think that this research can provide different ideas for online non-convex and non-submodular learning.
Relevance and diversity are two desirable properties in data retrieval applications, an important field in data science and machine learning. In this paper, we consider three maximization problems to ...balance these two factors. The objective function in each problem is the sum of a monotone submodular function
f
and a supermodular function
g
, where
f
and
g
capture the relevance and diversity of any feasible solution, respectively. In the first problem, we consider a special supermodular diversity function
g
of a sum-sum format satisfying the relaxed triangle inequality, for which we propose a greedy-type approximation algorithm with an
1
-
1
/
e
,
1
/
(
2
α
)
-bifactor approximation ratio, improving the previous
1
/
(
2
α
)
,
1
/
(
2
α
)
-bifactor approximation ratio. In the second problem, we consider an arbitrary supermodular diversity function
g
, for which we propose a distorted greedy method to give a
min
1
-
k
f
e
-
1
,
1
-
k
g
e
-
(
1
-
k
g
)
-approximation algorithm, improving the previous
k
f
-
1
1
-
e
-
k
f
(
1
-
k
g
)
-approximation ratio, where
k
f
and
k
g
are the curvatures of the submodular function
f
and the supermodular funciton
g
, respectively. In the third problem, we generalize the uniform matroid constraint to the
p
matroid constraints, for which we present a local search algorithm to improve the previous
1
-
k
g
(
1
-
k
g
)
k
f
+
p
-approximation ratio to
min
p
+
1
-
k
f
p
(
p
+
1
)
,
1
-
k
g
p
+
k
g
(
1
-
k
g
)
2
p
+
(
1
-
k
g
)
2
.
The exploration of submodular optimization problems on the integer lattice offers a more precise approach to handling the dynamic interactions among repetitive elements in practical applications. In ...today’s data-driven world, the importance of efficient and reliable privacy-preserving algorithms has become paramount for safeguarding sensitive information. In this paper, we delve into the DR-submodular and lattice submodular maximization problems subject to cardinality constraints on the integer lattice, respectively. For DR-submodular functions, we devise a differential privacy algorithm that attains a
(
1
-
1
/
e
-
ρ
)
-approximation guarantee with additive error
O
(
r
σ
ln
|
N
|
/
ϵ
)
for any
ρ
>
0
, where
N
is the number of groundset,
ϵ
is the privacy budget,
r
is the cardinality constraint, and
σ
is the sensitivity of a function. Our algorithm preserves
O
(
ϵ
r
2
)
-differential privacy. Meanwhile, for lattice submodular functions, we present a differential privacy algorithm that achieves a
(
1
-
1
/
e
-
O
(
ρ
)
)
-approximation guarantee with additive error
O
(
r
σ
ln
|
N
|
/
ϵ
)
. We evaluate their effectiveness using instances of the combinatorial public projects problem and the budget allocation problem within the bipartite influence model.
Many combinatorial optimization problems can be reduced to submodular optimization problems. However, many cases in practical applications do not fully comply with the diminishing returns ...characteristic. This paper studies the problem of maximizing weakly-monotone non-submodular non-negative set functions without constraints, and extends the normal submodular ratio to weakly-monotone submodular ratio
γ
^
. In this paper, two algorithms are given for the above problems. The first one is a deterministic greedy approximation algorithm, which realizes the approximation ratio of
γ
^
γ
^
+
2
. When
γ
^
=
1
, the approximate ratio is 1/3, which matches the ratio of the best deterministic algorithm known for the maximization of submodular function without constraints. The second algorithm is a random greedy algorithm, which improves the approximation ratio to
γ
^
γ
^
+
1
. When
γ
^
=
1
, the approximation ratio is 1/2, the same as the best algorithm for the maximization of unconstrained submodular set functions.
In this paper, we consider the uniform capacitated
k
-means problem (UC-
k
-means), an extension of the classical
k
-means problem (
k
-means) in machine learning. In the UC-
k
-means, we are given a ...set
D
of
n
points in
d
-dimensional space and an integer
k
. Every point in the
d
-dimensional space has an uniform capacity which is an upper bound on the number of points in
D
that can be connected to this point. Every two-point pair in the space has an associated connecting cost, which is equal to the square of the distance between these two points. We want to find at most
k
points in the space as centers and connect every point in
D
to some center without violating the capacity constraint, such that the total connecting costs is minimized. Based on the technique of local search, we present a bi-criteria approximation algorithm, which has a constant approximation guarantee and violates the cardinality constraint within a constant factor, for the UC-
k
-means.
