38 research outputs found
On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games
No full textCharacterizing the performance of no-regret dynamics in multi-player games is a foundational problem at the interface of online learning and game theory. Recent results have revealed that when all players adopt specific learning algorithms, it is possible to improve exponentially over what is predicted by the overly pessimistic no-regret framework in the traditional adversarial regime, thereby leading to faster convergence to the set of coarse correlated equilibria (CCE) - a standard game-theoretic equilibrium concept. Yet, despite considerable recent progress, the fundamental complexity barriers for learning in normal- and extensive-form games are poorly understood. In this paper, we make a step towards closing this gap by first showing that - barring major complexity breakthroughs - any polynomial-time learning algorithms in extensive-form games need at least 2^{log^{1/2 - o(1)} ||} iterations for the average regret to reach below even an absolute constant, where || is the number of nodes in the game. This establishes a superpolynomial separation between no-regret learning in normal- and extensive-form games, as in the former class a logarithmic number of iterations suffices to achieve constant average regret. Furthermore, our results imply that algorithms such as multiplicative weights update, as well as its optimistic counterpart, require at least 2^{(log log m)^{1/2 - o(1)}} iterations to attain an O(1)-CCE in m-action normal-form games under any parameterization. These are the first non-trivial - and dimension-dependent - lower bounds in that setting for the most well-studied algorithms in the literature. From a technical standpoint, we follow a beautiful connection recently made by Foster, Golowich, and Kakade (ICML '23) between sparse CCE and Nash equilibria in the context of Markov games. Consequently, our lower bounds rule out polynomial-time algorithms well beyond the traditional online learning framework, capturing techniques commonly used for accelerating centralized equilibrium computation
On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem
No full textWe study the search problem class PPA_q defined as a modulo-q analog of the well-known polynomial parity argument class PPA introduced by Papadimitriou (JCSS 1994). Our first result shows that this class can be characterized in terms of PPA_p for prime p.
Our main result is to establish that an explicit version of a search problem associated to the Chevalley - Warning theorem is complete for PPA_p for prime p. This problem is natural in that it does not explicitly involve circuits as part of the input. It is the first such complete problem for PPA_p when p ≥ 3.
Finally we discuss connections between Chevalley-Warning theorem and the well-studied short integer solution problem and survey the structural properties of PPA_q
The computational complexity of finding stationary points in non-convex optimization
No full textFinding approximate stationary points, i.e., points where the gradient is approximately zero, of non-convex but smooth objective functions f over unrestricted d-dimensional domains is one of the most fundamental problems in classical non-convex optimization. Nevertheless, the computational and query complexity of this problem are still not well understood when the dimension d of the problem is independent of the approximation error. In this paper, we show the following computational and query complexity results:
The problem of finding approximate stationary points over unrestricted domains is PLScomplete.
For d = 2, we provide a zero-order algorithm for finding ε-approximate stationary points that requires at most O(1/ε) value queries to the objective function.
We show that any algorithm needs at least Ω(1/ε) queries to the objective function and/or its gradient to find ε-approximate stationary points when d = 2. Combined with the above, this characterizes the query complexity of this problem to be Θ(1/ε).
For d = 2, we provide a zero-order algorithm for finding ε-KKT points in constrained optimization problems that requires at most O(1/ √ ε) value queries to the objective function. This closes the gap between the works of Bubeck and Mikulincer [2020] and Vavasis [1993] and characterizes the query complexity of this problem to be Θ(1/ √ ε).
Combining our results with the recent result of Fearnley et al. [2022], we show that finding approximate KKT points in constrained optimization is reducible to finding approximate stationary points in unconstrained optimization but the converse is impossible
The Computational Complexity of Finding Stationary Points in Non-Convex Optimization
No full textFinding approximate stationary points, i.e., points where the gradient is approximately zero, of non-convex but smooth objective functions over unrestricted -dimensional domains is one of the most fundamental problems in classical non-convex optimization. Nevertheless, the computational and query complexity of this problem are still not well understood when the dimension of the problem is independent of the approximation error. In this paper, we show the following computational and query complexity results:
1. The problem of finding approximate stationary points over unrestricted domains is PLS-complete.
2. For , we provide a zero-order algorithm for finding -approximate stationary points that requires at most value queries to the objective function.
3. We show that any algorithm needs at least queries to the objective function and/or its gradient to find -approximate stationary points when . Combined with the above, this characterizes the query complexity of this problem to be .
4. For , we provide a zero-order algorithm for finding -KKT points in constrained optimization problems that requires at most value queries to the objective function. This closes the gap between the works of Bubeck and Mikulincer [2020] and Vavasis [1993] and characterizes the query complexity of this problem to be .
5. Combining our results with the recent result of Fearnley et al. [2022], we show that finding approximate KKT points in constrained optimization is reducible to finding approximate stationary points in unconstrained optimization but the converse is impossible.Journal versio
Efficient Statistics, in High Dimensions, from Truncated Samples
No full textWe provide an efficient algorithm for the classical problem, going back to Galton, Pearson,and Fisher, of estimating, with arbitrary accuracy the parameters of a multivariate normal distribution from truncated samples. Truncated samples from ad-variate normal N(μ,Σ) means a samples is only revealed if it falls in some subset S⊆Rd; otherwise the samples are hidden and their count in proportion to the revealed samples is also hidden. We show that the meanμand covariance matrixΣcan be estimated with arbitrary accuracy in polynomial-time, as long as we have oracle access to S, and S has non-trivial measure under the unknown d-variate normal distribution. Additionally we show that without oracle access to S, any non-trivial estimation is impossible
A converse to Banach's fixed point theorem and its CLS-completeness
No full textBanach's fixed point theorem for contraction maps has been widely used to analyze the convergence of iterative methods in non-convex problems. It is a common experience, however, that iterative maps fail to be globally contracting under the natural metric in their domain, making the applicability of Banach's theorem limited. We explore how generally we can apply Banach's fixed point theorem to establish the convergence of iterative methods when pairing it with carefully designed metrics.
Our first result is a strong converse of Banach's theorem, showing that it is a universal analysis tool for establishing global convergence of iterative methods to unique fixed points, and for bounding their convergence rate. In other words, we show that, whenever an iterative map globally converges to a unique fixed point, there exists a metric under which the iterative map is contracting and which can be used to bound the number of iterations until convergence. We illustrate our approach in the widely used power method, providing a new way of bounding its convergence rate through contraction arguments.
We next consider the computational complexity of Banach's fixed point theorem. Making the proof of our converse theorem constructive, we show that computing a fixed point whose existence is guaranteed by Banach's fixed point theorem is CLS-complete. We thus provide the first natural complete problem for the class CLS, which was defined in [Daskalakis, Papadimitriou 2011] to capture the complexity of problems such as P-matrix LCP, computing KKT-points, and finding mixed Nash equilibria in congestion and network coordination games
On the Complexity of Deterministic Nonsmooth and Nonconvex Optimization
No full textIn this paper, we present several new results on minimizing a nonsmooth and
nonconvex function under a Lipschitz condition. Recent work shows that while
the classical notion of Clarke stationarity is computationally intractable up
to some sufficiently small constant tolerance, the randomized first-order
algorithms find a -Goldstein stationary point with the
complexity bound of , which is independent
of dimension ~\citep{Zhang-2020-Complexity, Davis-2022-Gradient,
Tian-2022-Finite}. However, the deterministic algorithms have not been fully
explored, leaving open several problems in nonsmooth nonconvex optimization.
Our first contribution is to demonstrate that the randomization is
\textit{necessary} to obtain a dimension-independent guarantee, by proving a
lower bound of for any deterministic algorithm that has access to
both and oracles. Furthermore, we show that the
oracle is \textit{essential} to obtain a finite-time convergence guarantee, by
showing that any deterministic algorithm with only the oracle is not
able to find an approximate Goldstein stationary point within a finite number
of iterations up to sufficiently small constant parameter and tolerance.
Finally, we propose a deterministic smoothing approach under the
\textit{arithmetic circuit} model where the resulting smoothness parameter is
exponential in a certain parameter (e.g., the number of nodes in the
representation of the function), and design a new deterministic first-order
algorithm that achieves a dimension-independent complexity bound of
.Comment: 28 Pages; Fix an error and add relevant reference
