Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis

Bo Jiang; Tianyi Lin; Shiqian Ma; Shuzhong Zhang

Source-linked AI summary

Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis

Bo Jiang, Tianyi Lin, Shiqian Ma, Shuzhong Zhang

arXiv:1605.02408v5May 9, 2016math.OCcs.LGstat.ML

TL;DR

The paper studies constrained nonconvex and nonsmooth optimization with multiple block variables. It develops stationarity definitions and first-order algorithms, establishing an O(ε^-q) complexity bound for generalized conditional gradient under Hölder gradient conditions.

Problem
The paper studies nonconvex and nonsmooth optimization problems with multiple block variables.
Method
The paper develops variational-inequality ε-stationarity definitions and applies generalized conditional gradient, ADMM variants, and proximal block coordinate descent using first-order information.
Results
The generalized conditional gradient method reaches an ε-stationary solution in O(ε^-q) iterations under Hölder continuity of the smooth gradient.
Takeaways & Limitations
The framework covers nonsmooth models and provides complexity analyses for first-order methods under assumptions differing from several recent approaches.
Takeaways & Limitations
The initial model restricts the last block by requiring r_N ≡ 0 and A_N to be the identity or full row rank.

Abstract

from arXiv · show

Nonconvex and nonsmooth optimization problems are frequently encountered in much of statistics, business, science and engineering, but they are not yet widely recognized as a technology in the sense of scalability. A reason for this relatively low degree of popularity is the lack of a well developed system of theory and algorithms to support the applications, as is the case for its convex counterpart. This paper aims to take one step in the direction of disciplined nonconvex and nonsmooth optimization. In particular, we consider in this paper some constrained nonconvex optimization models in block decision variables, with or without coupled affine constraints. In the case of without coupled constraints, we show a sublinear rate of convergence to an $ε$-stationary solution in the form of variational inequality for a generalized conditional gradient method, where the convergence rate is shown to be dependent on the Hölderian continuity of the gradient of the smooth part of the objective. For the model with coupled affine constraints, we introduce corresponding $ε$-stationarity conditions, and apply two proximal-type variants of the ADMM to solve such a model, assuming the proximal ADMM updates can be implemented for all the block variables except for the last block, for which either a gradient step or a majorization-minimization step is implemented. We show an iteration complexity bound of $O(1/ε^2)$ to reach an $ε$-stationary solution for both algorithms. Moreover, we show that the same iteration complexity of a proximal BCD method follows immediately. Numerical results are provided to illustrate the efficacy of the proposed algorithms for tensor robust PCA.

1 Introduction

The paper develops first-order methods and stationarity definitions for constrained nonconvex, nonsmooth optimization with block variables. It establishes iteration-complexity results for generalized conditional gradient, proximal ADMM variants, and proximal BCD methods under distinct model settings.

1 Introduction: The general model combines a differentiable possibly nonconvex term, blockwise nonsmooth terms, convex feasible sets, and affine coupling constraints.The baseline formulation restricts the last block, while later extensions relax restrictions on its regularizer and constraints.
1 Introduction: The framework targets applications including robust PCA and tensor models with low-rank, sparse, and noise components, including a low-CP-rank tensor formulation.The tensor formulation uses factor matrices and an estimated CP-rank, while robust PCA decomposes data into structured, sparse, and noise terms.
1 Introduction: Generalized conditional gradient reaches an ε-stationary solution in O(ε^-q) iterations, with q determined by the Hölder continuity of the smooth objective gradient.The result covers nonsmooth models beyond settings with Lipschitz-continuous gradients.
1 Introduction: The paper defines ε-stationary solutions through variational inequalities, allowing nonsmooth and nonconvex block regularizers in one model.For model (1.1), each r_i may be nonsmooth and nonconvex.
1 Introduction: Two proximal ADMM variants obtain ε-stationary solutions for the coupled-constraint model under block-update assumptions, including a gradient or majorization-minimization step for the last block.The variants are proximal ADMM-g and proximal ADMM-m.
1 Introduction: The same iteration-complexity framework yields a proximal cyclic BCD result without affine constraints, avoiding the KL-property parameter required by an earlier nonconvex BCD analysis.The paper derives this result as a by-product of the proximal ADMM analysis.

2 A generalized conditional gradient method

The generalized conditional gradient method extends conditional-gradient optimization to constrained nonsmooth nonconvex problems and provides ε-stationarity guarantees under Hölder-continuous gradients. Its line-search-based complexity is O(1/ε^2) generally and improves to O(1/ε) when the smooth objective is concave.

2.2 Generalized conditional gradient algorithm: The method assumes the Step 1 subproblems are relatively easy to solve, reflecting a standard conditional-gradient requirement.The feasible set is assumed convex and compact, and r is convex and nonsmooth.
2.1 An ǫ-stationary solution for problem (1.2): GCG targets an ε-stationary variational-inequality solution for a convex-set problem with convex nonsmooth regularizer r and differentiable possibly nonconvex f.The stationarity definition permits ε = 0 for exact stationarity and is weaker than the usual KKT condition.
2.2 Generalized conditional gradient algorithm: Each GCG iteration minimizes a linearized surrogate over S, performs an exact line search on a Hölder-based upper model, and updates by convex interpolation.The direction comes from the surrogate minimization, while the line search replaces the smooth term with a p-powered bound and upper-bounds the nonsmooth term.
2.3 An iteration complexity analysis: A small linearization improvement certifies ε-stationarity, while the generated objective sequence is monotonically nonincreasing.This certification connects surrogate progress directly to the variational-inequality stationarity criterion.
2.3 An iteration complexity analysis: O(1/ε) iterations suffice when the smooth function f is concave and GCG uses full steps.Under concavity, setting α_k = 1 yields the improved complexity.

3 Variants of ADMM for solving nonconvex problems with affine constraints

This section develops two proximal ADMM variants for constrained nonconvex problems with affine coupling and analyzes their convergence to ε-stationary solutions. The algorithms use proximal block updates and either gradient-based or majorization-based treatment of the final block.

3.3 Proximal gradient-based ADMM (proximal ADMM-g): The analysis assumes Lipschitz continuity of the smooth gradient, lower-bounded objective and regularizer terms, and suitable solvability of the proximal subproblems.For proximal ADMM-g, the final block is handled by a gradient step, while the other block subproblems may be nonconvex but are assumed solvable to global optimality.
3.2 An ε-stationary solution for problem (1.1): The section introduces ε-stationarity conditions for affine-constrained nonconvex problems under two settings involving either Lipschitz regularizers on compact domains or lower-semicontinuous regularizers on unconstrained domains.The conditions are formulated through variational inequalities and generalized subgradients.
3.3 Proximal gradient-based ADMM (proximal ADMM-g): Proximal ADMM-g applies proximal augmented-Lagrangian minimization to the first blocks, a gradient step to the final block, and then updates the Lagrange multiplier.The method is presented for the sharing-problem case with A_N = I.
3.3 Proximal gradient-based ADMM (proximal ADMM-g): Proximal ADMM-g returns an ε-stationary solution under both settings, with iteration complexity bounds established through the algorithm’s descent and stationarity estimates.The cited conclusions cover Definitions 3.5 and 3.6 under Settings 1 and 2.
3.4 Proximal majorization ADMM (proximal ADMM-m): The proximal ADMM-m analysis likewise proves that the algorithm returns an ε-stationary solution under the corresponding settings.The proof uses monotonicity and boundedness properties of the associated potential function.

4 Extensions

The extensions relax restrictions on the last block variable, establish proximal ADMM-m complexity under stated assumptions, and derive a proximal BCD complexity result through an equivalent ADMM formulation.

4.1 Relaxing the assumption on the last block variable x_N: The extension removes the restrictions r_N ≡ 0 and A_N = I or full row rank from the last block variable.The generalized formulation permits a nonsmooth r_N and a constrained x_N.
4.1 Relaxing the assumption on the last block variable x_N: Under Assumption 4.1 and bounded level sets, proximal ADMM-m reaches an ε-stationary solution in O(1/ε^4) iterations.The result assumes a Lipschitz-continuous gradient and a full-row-rank constraint matrix.
4.1 Relaxing the assumption on the last block variable x_N: Without Assumption 4.1, the available proximal ADMM-m complexity bound worsens to O(1/ε^6).The alternative parameter choices are K = 1/ε^6, μ(ε) = 1/ε^2, and β(ε) = 3/ε^2.
4.2 Proximal BCD (Block Coordinate Descent): Proximal BCD is obtained by introducing an auxiliary variable and applying proximal ADMM-g to an equivalent problem.The auxiliary block is fixed to b, making the ADMM formulation reduce exactly to the proximal BCD algorithm.
4.2 Proximal BCD (Block Coordinate Descent): The proximal BCD iterate is shown to be an ε-stationary solution for the corresponding nonconvex, nonsmooth problem.The method updates blocks cyclically with positive-definite proximal matrices.

5 Numerical Experiments

The experiments evaluate BCD, proximal BCD, and two proximal ADMM variants on nonconvex nonsmooth tensor robust PCA across several rank initializations. The reported comparisons favor the three proximal or ADMM methods over BCD, while proximal BCD can use fewer iterations with a larger factorization basis.

Model and algorithms: The robust tensor PCA model combines a CP low-rank tensor, sparse ℓ1 corruption, and quadratic noise fitting.The experiment uses the equivalent formulation with variables A, B, C, Z, and E.
Experimental setup: The experiments compare BCD, proximal BCD, proximal ADMM-g, and proximal ADMM-m for tensor robust PCA.Twenty random instances are averaged for each fixed tensor dimension and CP-rank setting.
Experimental setup: All four algorithms use a maximum of 2000 iterations and stop when θ_k falls below 10^-6.The ADMM parameter choices are listed in Table 2.
Results: BCD mostly converges to a local solution, whereas the other three methods are much better at finding the global optimum across Tables 3–5.The comparison uses averaged relative error, iteration count, and the number of solutions meeting the relative-error threshold.
Results: With a larger tensor-factorization basis, the results improve over the smaller-basis settings, and proximal BCD usually requires fewer iterations than either ADMM variant.This comparison corresponds to the setting reported in Table 5.