Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Lower complexity bounds of first-order methods for convex-concave
  bilinear saddle-point problems   On solving a convex-concave bilinear saddle-point problem (SPP), there have
been many works studying the complexity results of first-order methods. These
results are all about upper complexity bounds, which can determine at most how
many efforts would guarantee a solution of desired accuracy. In this paper, we
pursue the opposite direction by deriving lower complexity bounds of
first-order methods on large-scale SPPs. Our results apply to the methods whose
iterates are in the linear span of past first-order information, as well as
more general methods that produce their iterates in an arbitrary manner based
on first-order information. We first work on the affinely constrained smooth
convex optimization that is a special case of SPP. Different from gradient
method on unconstrained problems, we show that first-order methods on affinely
constrained problems generally cannot be accelerated from the known convergence
rate $O(1/t)$ to $O(1/t^2)$, and in addition, $O(1/t)$ is optimal for convex
problems. Moreover, we prove that for strongly convex problems, $O(1/t^2)$ is
the best possible convergence rate, while it is known that gradient methods can
have linear convergence on unconstrained problems. Then we extend these results
to general SPPs. It turns out that our lower complexity bounds match with
several established upper complexity bounds in the literature, and thus they
are tight and indicate the optimality of several existing first-order methods.

11
The categories of this paper are: hep-lat
31
The categories of this paper are: ao-sci
1
The categories of this paper are: cs
36
The categories of this paper are: cmp-lg
33
The categories of this paper are: plasm-ph
21
The categories of this paper are: adap-org
25
The categories of this paper are: patt-sol
34
The categories of this paper are: chem-ph
15
The categories of this paper are: nucl-ex
8
The categories of this paper are: hep-ex
0
The categories of this paper are: hep-ph
6
The categories of this paper are: astro-ph
37
The categories of this paper are: supr-con
7
The categories of this paper are: hep-th
20
The categories of this paper are: acc-phys
9
The categories of this paper are: nlin