Source-linked AI summary
Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
Yuyuan Ouyang, Yangyang Xu
TL;DR
Existing work largely establishes upper complexity bounds, leaving unclear whether first-order methods for these problems achieve optimal convergence orders. This paper derives lower complexity bounds for affinely constrained problems and bilinear saddle-point problems, including general first-order methods, and uses them to assess optimality.
Problem
Existing complexity analyses largely provide upper bounds, so it remains unclear whether first-order methods achieve optimal convergence orders.
Method
The paper derives lower complexity bounds first for affinely constrained smooth convex optimization and then extends the analysis to general bilinear saddle-point problems and general first-order methods.
Results
Theorems establish lower complexity bounds for affinely constrained problems and bilinear saddle-point problems under Lipschitz-gradient assumptions, including Euclidean-ball domains for the latter.
Takeaways & Limitations
The bounds fill the missing lower-bound analysis and can determine the optimality of existing first-order algorithms.
Takeaways & Limitations
The analysis uses a single oracle returning gradient and matrix-vector information simultaneously, and the instance sizes and feasible-set radii are allowed to be chosen in the constructions.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies information-based lower complexity bounds for first-order methods on affinely constrained convex optimization and general bilinear saddle-point problems. It shows that several known upper rates are unimprovable, including O(1/t) for convex constrained problems and matching tight bounds for general SPPs.
- 1.1 Main goal: Lower complexity bounds address whether first-order methods can be improved and guide the design of optimal algorithms.The paper constructs worst-case SPP instances whose required oracle complexity is bounded below by problem-dependent quantities.
- 1.2 Main results: O(1/t) generally cannot be accelerated to O(1/t^2) for affinely constrained convex problems, and O(1/t) is optimal.These problems are a special case of bilinear saddle-point problems, while projected gradient on suitable unconstrained problems can attain faster rates.
- 1.2 Main results: Theorem 2 extends the lower complexity bounds to general convex-concave bilinear saddle-point problems with Euclidean-ball domains.The construction covers both convex and strongly convex cases and allows arbitrary first-order rules based on oracle information.
- 1.2 Main results: The lower bounds are tight up to constant multiples or a logarithmic term when compared with several established upper complexity bounds.This comparison indicates the optimality of several existing first-order methods.
2 Lower complexity bounds under linear span assumption for affinely constrained problems
The section constructs hard affinely constrained convex quadratic instances and uses Krylov-subspace structure to lower-bound first-order convergence under the linear span assumption. It establishes bounds for convex and strongly convex cases, including dependence on constraint and smoothness parameters.
- Hard-instance construction: Hard convex quadratic instances force iterates of linear-span first-order methods into progressively expanding Krylov subspaces.The construction ensures x(t) ∈ K_{t−1} for t ≤ k, enabling lower bounds from restricted iterate structure.
- Convex lower bound: O(1/ε) iterations are necessary to obtain both ε-optimality and ε-feasibility for affinely constrained problems.The lower bound follows from |f(x(t))−f*| ≥ O(1/t) and ∥Ax(t)−b∥ ≥ O(1/t).
- Convex lower bound: O(L_A/ε) is a lower complexity bound when accounting for the constraint-matrix norm.The theorem’s hard instances have ∥A∥ = L_A, and the bound applies to algorithms satisfying the linear span assumption.
- Convex lower bound: O(L_f/ε) iterations are required to ensure objective error at most ε under the constructed convex instances.This dependence matches the order attained by optimal proximal gradient methods, subject to the paper’s restriction against projection onto Ax = b.
- Nonnegative constraint parameter: The positive-L_A construction excludes proximal gradient methods, motivating a second hard instance that allows L_A = 0.The later construction assumes only L_A = O(L_f), covers proximal gradient methods, and clarifies dependence on L_A and L_f.
- Strongly convex case: For strongly convex problems, the section develops a distance-based lower bound for methods whose iterates obey the linear span assumption.The hard instance is a quadratic program with a µ-strongly convex objective, ∥A∥ = L_A, and a unique primal-dual solution.
3 Lower complexity bounds of general first-order methods for affinely constrained problems
The paper extends lower-complexity results from linear-span methods to arbitrary first-order methods for affinely constrained problems. Rotational invariance and hard instances show that these bounds apply broadly under the stated smoothness, conditioning, and dimension assumptions.
- Key proposition: Rotational invariance constructs rotated instances preserving Lipschitz continuity, operator norms, and primal-dual solutions.Orthogonal matrices fix selected vectors while transferring the problem and its solutions to a rotated coordinate system.
- Lower bounds: For smooth convex instances, Theorem 6 establishes lower bounds for arbitrary first-order methods with Lf-Lipschitz gradients and operator norm LA.The theorem applies for positive Lf and LA and dimensions satisfying 8 < m ≤ n.
- Strong convexity: For strongly convex instances, Theorem 8 gives the corresponding lower complexity bound for every general first-order method.The hard instance has a µ-strongly convex objective, fixed operator norm LA, and a unique primal-dual solution.
- Key proposition: Any general first-order method admits a rotated hard instance whose iterates remain confined to prescribed Krylov subspaces.The construction applies to methods whose iterates are generated arbitrarily from first-order information, not only linear-span updates.
4 Lower complexity bounds on bilinear saddle-point problems
The paper transfers the affine-constraint lower-bound construction to bilinear saddle-point problems with compact Euclidean-ball domains. The resulting SPP lower bounds match known upper-bound orders, including the strongly convex setting.
- SPP construction: Affinely constrained optimization is a special case of bilinear SPPs, allowing earlier hard instances to inform the general saddle-point analysis.The reduction sets Y = R^m and g = 0, while compact-domain SPPs require a further construction.
- SPP construction: The hard SPPs use convex quadratic f, compact Euclidean balls X and Y, and matrix data controlled by Lf and LA.The quadratic objective has the form f(x) = 1/2 x^T Hx − h^T x with H positive semidefinite.
- General SPPs: Theorem 9 establishes a lower complexity bound for every first-order method on bilinear SPPs under Lf ≥ LA.The construction specifies Lipschitz gradient, operator norm, feasible-set radii, and primal-dual approximation guarantees.
- General SPPs: Theorem 9’s lower bound has the same form as the established upper bound, differing only in constants.The paper therefore concludes that the upper convergence order is not improvable under the considered setting.
- Strong convexity: Theorem 10 extends the SPP lower-complexity result to strongly convex f and instances with a unique optimal primal solution.The setting includes operator norm LA and Euclidean-ball domains with radii RX and RY.
5 On the tightness of the established lower complexity bounds
The established lower bounds are tight in order when compared with several first-order upper bounds. This comparison supports the optimality of multiple existing methods for the considered SPP classes.
- Tightness: The paper compares its lower bounds with the best known upper complexity bounds and finds matching convergence orders.The comparison is explicitly in terms of order, not necessarily identical constants.
- Strong convexity: In the strongly convex case, a known upper-bound iteration result has the same dominant term as the lower bound apart from a logarithmic factor.The comparison uses strong convexity to translate objective convergence into distance to the solution.
- Saddle-point methods: Nesterov’s smoothing scheme has an upper bound matching Theorem 9’s lower bound in order for bilinear SPPs with compact domains.The paper identifies the method as optimal for computing approximate solutions in this problem class.
- Saddle-point methods: The methods in [5, 6] also match the lower bound up to a constant multiple when applied to the associated primal problem.The paper consequently classifies them as optimal first-order methods for that formulation.
- Saddle-point methods: For f ≡ 0, existing saddle-point and variational-inequality methods yield rates indicating tightness of the corresponding lower bound.This comparison concerns the regime Lf ≤ LA.
6 Concluding remarks
The paper establishes lower complexity bounds for first-order methods on bilinear saddle-point problems and extends them from affinely constrained problems to general SPPs. It also identifies oracle and instance-design assumptions that delimit the results and motivate future work.
- Hard convex quadratic-programming instances establish lower bounds under a linear-span assumption for affinely constrained problems.
- A rotation-invariance technique extends the lower-bound results from affinely constrained problems to general saddle-point problems.
- The bounds are tight in comparison with established upper bounds and indicate the optimality of several existing first-order methods.
- The feasibility-residual lower bounds for affinely constrained problems do not depend on the objective because methods may omit objective-gradient information.
- The oracle model simultaneously returns gradient and matrix-vector multiplication information, leaving separate-oracle lower bounds for future work.
- The constructed instances determine the sizes of X and Y, so analogous bounds with fixed Lipschitz constants and diameters remain open.