  Parameter-free optimization algorithms refer to algorithms whose convergence
rate is optimal with respect to the initial point without any learning rate to
tune. They are proposed and well-studied in the online convex optimization
literature. However, all the existing parameter-free algorithms can only be
used for convex minimization problems. It remains unclear how to design a
parameter-free algorithm for convex-concave min-max problems. In fact, the best
known convergence rates of the algorithms for solving these problems depend on
the size of the domain, rather than on the distance between initial point and
the optimal solution. In this paper, we provide the first parameter-free
algorithm for several classes of convex-concave problems and establish
corresponding state-of-the-art convergence rates, including
strictly-convex-strictly-concave min-max problems and min-max problems with
non-Euclidean geometry. As a by-product, we utilize the parameter-free
algorithm as a subroutine to design a new algorithm, which obtains fast rates
for min-max problems with a growth condition. Extensive experiments are
conducted to verify our theoretical findings and demonstrate the effectiveness
of the proposed algorithm.
