PaperlayerView exact revision on arXiv

Source-linked AI summary

A globally convergent algorithm for nonconvex optimization based on block coordinate update

Yangyang Xu, Wotao Yin

arXiv:1410.1386v2math.OC

TL;DR

Nonconvex nonsmooth optimization often lacks proofs that the entire iterate sequence converges to a critical point. The paper proposes block prox-linear updates and establishes whole-sequence convergence under the KL property, with applications including globally convergent regression and matrix-factorization methods.

  • Problem

    Existing analyses often prove only objective or subsequence convergence, leaving whole-iterate convergence for nonconvex nonsmooth algorithms rarely established.

  • Method

    The block prox-linear method updates one variable block at a time by minimizing a prox-linear surrogate, with deterministic or randomly shuffled block order.

  • Results

    Under the KL property, the entire iterate sequence converges to a critical point with an estimated asymptotic rate, including applications to regression and nonnegative matrix factorization.

  • Takeaways & Limitations

    The method provides global convergence guarantees for several nonconvex optimization applications when block-separable nonsmooth terms and the stated regularity conditions hold.

  • Takeaways & Limitations

    The convergence theory requires assumptions such as the KL property and Lipschitz continuity on a bounded set, while the RRI application can violate conditions when factors vanish or blow up.

Abstract

from arXiv · show

Nonconvex optimization problems arise in many areas of computational science and engineering and are (approximately) solved by a variety of algorithms. Existing algorithms usually only have local convergence or subsequence convergence of their iterates. We propose an algorithm for a generic nonconvex optimization formulation, establish the convergence of its whole iterate sequence to a critical point along with a rate of convergence, and numerically demonstrate its efficiency. Specially, we consider the problem of minimizing a nonconvex objective function. Its variables can be treated as one block or be partitioned into multiple disjoint blocks. It is assumed that each non-differentiable component of the objective function or each constraint applies to one block of variables. The differentiable components of the objective function, however, can apply to one or multiple blocks of variables together. Our algorithm updates one block of variables at time by minimizing a certain prox-linear surrogate. The order of update can be either deterministic or randomly shuffled in each round. We obtain the convergence of the whole iterate sequence under fairly loose conditions including, in particular, the Kurdyka-Łojasiewicz (KL) condition, which is satisfied by a broad class of nonconvex/nonsmooth applications. We apply our convergence result to the coordinate descent method for non-convex regularized linear regression and also a modified rank-one residue iteration method for nonnegative matrix factorization. We show that both the methods have global convergence. Numerically, we test our algorithm on nonnegative matrix and tensor factorization problems, with random shuffling enable to avoid local solutions.

1. Introduction.

The paper targets broad nonconvex, possibly nonsmooth block-structured optimization problems, where whole-sequence convergence is rarely established. It proposes a block prox-linear method that updates one block at a time and supports deterministic or randomized block orders.

  • Problem formulation: The framework minimizes a nonconvex objective with differentiable coupling f and proximable, possibly nonsmooth block terms r_i over closed nonempty sets X_i.Convexity is not assumed for f, r_i, or X_i; constraints can be represented through indicator functions.
  • Applications: The formulation covers nonconvex sparse regression, dictionary learning, rank minimization, matrix and tensor factorization, and higher-order principal component analysis.Examples include ℓp-quasi-norm regularization and nonnegativity, sparsity, or orthogonality constraints.
  • Motivation: Existing analyses often prove only objective or subsequence convergence, while whole-sequence convergence to a critical point is rarely established for nonsmooth nonconvex problems.The lack of convexity prevents standard convex inequalities and Fejér-monotonicity arguments.
  • Block prox-linear method: The proposed block prox-linear method selects one block and updates it by minimizing a prox-linear surrogate with a quadratic proximal term and the corresponding nonsmooth regularizer.At each iteration, only the selected block is updated.
  • Update strategies: The update block may be chosen deterministically or randomly, and the method can randomly shuffle all blocks at the beginning of each cycle.The paper reports that random shuffling leads to better numerical performance.

Special cases.

The paper’s convergence analysis relies on the KL property and essentially cyclic block updates, covering several nonconvex special cases while excluding RBCD. The KL assumption applies broadly because many nonsmooth and nonconvex functions satisfy it.

  • Update conditions: Under essentially cyclic updates, each block is selected at least once within every T ≥ s consecutive iterations, while update order is otherwise arbitrary.The convergence results cover the listed special cases except randomized block coordinate descent, whose analysis requires different strategies.
  • Convergence assumptions: Whole-sequence convergence of Algorithm 1 requires the objective function F to satisfy the Kurdyka-Lojasiewicz property.This property is used as a key assumption for convergence to a critical point.
  • KL examples: The KL property includes ℓp-(quasi)norms for p ∈ [0, +∞], piecewise polynomial functions, several indicator functions, the matrix rank function, and other examples.Examples include indicators of polyhedral sets, orthogonal matrix sets, and the positive semidefinite cone.
  • Relation to prior results: Earlier prox-linear results with extrapolation assume a convex nonsmooth component, so they do not apply when both smooth and nonsmooth terms are nonconvex.The paper positions its convergence guarantee as addressing fully nonconvex problems.

2. Convergence analysis.

Under mild smoothness, block-update, and monotonicity conditions, the analysis establishes criticality of every limit point and, with the KL property, convergence of the entire iterate sequence. It also provides convergence-rate bounds and shows that objective monotonicity can be enforced by backtracking.

  • Descent and subsequence convergence: Under Assumptions 1–3, every finite limit point of the iterates is a critical point of the optimization problem.The result applies to iterates generated with the prescribed α_k and ω_k choices.
  • Descent and subsequence convergence: The analysis first proves objective decrease and square-summability of successive iterate differences, supporting convergence arguments for Algorithm 1.These results are established through Lemma 2.1 and Proposition 2.2.
  • Monotonicity condition: A nonincreasing objective can be maintained by selecting a positive extrapolation weight through backtracking under a mild assumption.The analysis states that a range of nontrivial ω_k > 0 exists and that all numerical examples satisfy the relevant proposition’s assumptions.
  • Whole sequence convergence: With the KL property, Condition 2.1, and a finite limit point, the whole iterate sequence converges to that limit point.The stated conditions are presented as broadly applicable, with Lipschitz continuity required only on a bounded set.
  • Convergence rate: The KL exponent yields linear-type convergence for θ ∈ [0, 1/2] and a sublinear bound of order k^−(1−θ)/(2θ−1) for θ ∈ (1/2, 1).The corresponding iterate-distance bounds are ∥x_k − x̄∥ ≤ Cα^k and ∥x_k − x̄∥ ≤ Ck^−(1−θ)/(2θ−1), respectively.

3. Applications and numerical results.

The applications establish convergence for nonconvex regularized linear regression and nonnegative matrix factorization, including whole-sequence convergence under KL-based conditions. Numerical experiments show that random shuffling can improve performance and success rates, while extrapolation accelerates convergence.

  • Nonconvex regularized linear regression: For MCP- and SCAD-regularized linear regression, the proposed updates converge to a coordinate-wise minimizer when a finite limit point exists.The result assumes standardized data and penalty parameters γ > 1 for MCP or γ > 2 for SCAD.
  • Nonnegative matrix factorization: For nonnegative matrix factorization, the modified RRI method produces a bounded sequence whose whole iterate sequence converges to a critical point.The modification normalizes columns of X and uses a Lipschitz constant for the block gradient; the updates retain closed-form solutions.
  • Nonnegative matrix factorization: Random shuffling significantly improved modified RRI performance on the Swimmer dataset, although it performed almost the same as cyclic updates on randomly generated data.Both update orders produced the same final objective values on random data and the Swimmer dataset.
  • Numerical convergence: The extrapolation technique significantly accelerates convergence, while removing extrapolation reduces the block-prox method to block coordinate gradient descent.The comparison is presented through Figure 3.4.
  • Tensor factorization: Among 50 independent runs, the randomly shuffled method succeeded 21 times, compared with 11 successes for the cyclic method.Success required the relative Frobenius reconstruction error to fall below 10^-3.

4. Conclusions. · Appendix A. Proofs of key lemmas.

The appendix establishes key lemmas under the parameter choice α_k = 1/(γL_k) for all k and uses Lipschitz continuity of the relevant partial gradient. The supplied passages provide no substantive conclusion-section content.

  • Appendix A. Proofs of key lemmas.: Appendix A assumes α_k = 1/(γL_k) for every k.This parameter choice is stated as holding for all k.
  • Appendix A. Proofs of key lemmas.: Appendix A also states a condition involving ˜ω_j for every j.The supplied passage is truncated and does not specify the full condition.
  • Appendix A. Proofs of key lemmas.: The proof considers the case b_k = i.This case distinction appears directly in the supplied proof passage.
  • Appendix A. Proofs of key lemmas.: The argument invokes Lipschitz continuity of ∇_{x_i}f at x^{k−1}.The passage introduces this continuity property as the basis for the proof step, although the statement is truncated.

A.1. Proof of Lemma 2.1.

The proof of Lemma 2.1 combines inequalities based on Cauchy–Schwarz, Lipschitz continuity, Young’s inequality, and the block-update parameter choice. It then substitutes the resulting bound and invokes (1.8) to complete the proof.

  • The argument combines inequalities involving Cauchy–Schwarz, Lipschitz continuity of the gradient, and Young’s inequality.
  • Choosing αk = 1/(γLk) yields the final equality used in the proof.
  • Substitution of the resulting expression and recalling (1.8) completes the proof.

A.2. Proof of the claim in Remark 2.2.

The proof establishes the claim in Remark 2.2 by summing (2.4) over k from 1 to K, which yields the desired result.

  • The argument concludes the proof of the claim in Remark 2.2.
  • The proof sums (2.4) over k from 1 to K.
  • This summation gives the desired result.

A.3. Proof of Proposition 2.2.

The proof concludes by taking K →∞ in an inequality, using Assumption 3 and the lower boundedness of F from Assumption 1. It also invokes a condition ensuring prox_{α_k r_i} is single valued near x^{k−1}.

  • A.3. Proof of Proposition 2.2.: An earlier inequality uses the fact d_i^0 ≥ ℓ for all i and j.
  • A.3. Proof of Proposition 2.2.: The proof lets K →∞ and uses Assumption 3 to conclude that d_i^K →∞ for all i.This conclusion follows from the preceding inequality together with the lower boundedness of F in Assumption 1.
  • A.3. Proof of Proposition 2.2.: The proof cites Corollary 5.20 and Example 5.23 of for single-valuedness of prox_{α_k r_i} near x^{k−1}.

A.4. Proof of Proposition 2.4.

The proof analyzes the extrapolated point and uses block-update optimality, limit arguments, and lower semicontinuity to establish a nonincreasing objective for sufficiently small extrapolation weights.

  • Extrapolated point: The proof explicitly defines the extrapolated point using weight ω.The notation identifies the extrapolated point as ˆx_i^k(ω).
  • Optimality argument: Block-update optimality provides the inequality used to compare objective values.The argument begins from the optimality of x_i^k.
  • Limit argument: Taking the limit superior of the resulting inequality advances the limiting argument.The proof applies a limit-superior operation to both sides.
  • Lower semicontinuity: Lower semicontinuity of r_i is invoked to control the limiting regularization term.The proof uses that r_i is lower semicontinuous when taking a lim inf.
  • Conclusion: There exists ω̄_k > 0 such that F(x^{k−1}) − F(x^k(ω)) ≥ 0 for every ω ∈ [0, ω̄_k].This establishes the claimed objective nonincrease for sufficiently small weights and completes the proof.

A.5. Proof of Lemma 2.5.

The proof of Lemma 2.5 derives successive inequalities, combines them to obtain a cumulative bound, and then establishes the stated conclusions by summation and explicit constant choices.

  • Equation (2.11) is rewritten as the starting point for the proof’s inequality chain.
  • Cauchy–Schwarz and the bound n_i,m+1 − n_i,m ≤ N are used to control the relevant terms.
  • Combining (A.5), (A.9), and (A.10), then summing over m from M1 through M2 ≤ M, yields an arranged cumulative inequality.
  • The proof selects constants satisfying C2 = 1/(2C1), C3 = C1/2, and C4 = β√2, completing the proof of (2.12).
  • Letting M1 = 1 and M2 → ∞ in the summed relation gives (2.13) when the series sum of B_m is finite.

A.6. Proof of Proposition 2.6. · A.7. Proof of Lemma 2.8.

The proofs establish Proposition 2.6 by controlling delayed block updates through Lipschitz continuity and related inequalities. Lemma 2.8 derives separate descent-rate bounds for γ ≥ 1 and γ < 1, while the appendix gives closed-form update solutions by cases.

  • A.6. Proof of Proposition 2.6.: A.6. The proof places extrapolated block points in B4ρ(¯x) and applies Lipschitz continuity of ∇_xif(x) together with inequalities (1.10), (A.16)–(A.19).The final estimate also uses triangle inequalities and the bound ˜L_i ≤ L.
  • A.6. Proof of Proposition 2.6.: A.6. Proposition 2.6 uses update delays bounded between k−T and k, with pairwise indices κ_i,j between k−2T and k.These bounds follow from Assumption 3 and account for blocks updated at earlier iterations.
  • A.6. Proof of Proposition 2.6.: A.6. For γ ≥ 1, monotonicity gives (A_k−1−A_k)^γ ≤ A_k−1−A_k, reducing (2.23) to A_k ≤ (α + β)(A_k−1−A_k).The proof states that item 1 then follows immediately.
  • A.7. Proof of Lemma 2.8.: A.7. For γ < 1, the proof reverses the power inequality and obtains A_k ≤ (α + β)(A_k−1−A_k)^γ.It then introduces h(x) = x^−1/γ and uses its nonincreasing monotonicity.
  • A.7. Proof of Lemma 2.8.: A.7. A positive constant μ is defined as the unique solution satisfying 0 < μ < 1, after which the proof establishes the claimed inequality from (A.20) and (A.21).The supplied passage indicates the claim is immediate under a stated condition, without displaying that condition.
  • A.7. Proof of Lemma 2.8.: A.7. Appendix B derives closed-form solutions for both updates in (3.9), rewriting (3.9a) and solving the resulting problem (B.1).The transformation uses c = a − b and separates the solution into three cases.
  • A.7. Proof of Lemma 2.8.: A.7. When c < 0, (B.1) is solved by assigning x_i0 = 1 to an index attaining c_max and setting all other components to zero.If multiple components attain c_max, any one may be selected.
  • A.7. Proof of Lemma 2.8.: A.7. When c ≤ 0 with zero and negative components, the negative components vanish and the zero-component subvector can be any nonnegative unit vector; the positive-component case has a unique solution.The positive-case proof uses equality conditions involving collinearity with c_I+ and the remaining components.

Appendix C. Proofs of convergence of some examples. · C.1. Proof of Theorem 3.3.

The proof of Theorem 3.3 reduces, via Theorem 2.7, to establishing boundedness of {Yk}. Objective decrease and nonnegativity yield bounded residual-related quantities and entrywise bounds that complete the argument.

  • Appendix C. Proofs of convergence of some examples.: Theorem 3.3 follows from Theorem 2.7 once boundedness of {Yk} is verified.The proof explicitly identifies this boundedness as the remaining requirement.
  • Appendix C. Proofs of convergence of some examples.: Defining Ek = Xk(Yk)⊤−M, every iteration decreases the objective, so {Ek} is bounded.This boundedness is the starting point for controlling the iterates.
  • C.1. Proof of Theorem 3.3.: Because {Ek} and M are bounded, {Ek + M} is bounded.The proof uses the residual definition to transfer boundedness to the product-related sequence.
  • C.1. Proof of Theorem 3.3.: The proof establishes that the summed entries i,j (Ek + M)ij remain finite.This finite-sum property is stated as an intermediate bound.
  • C.1. Proof of Theorem 3.3.: The columns of Ek + M satisfy an entrywise bound derived from their (i, j)-th entries.The passage introduces the relevant column structure and entries of Yk.
  • C.1. Proof of Theorem 3.3.: Nonnegativity of Xk and Yk, together with the stated bound on entries of xk, yields ij ≤a√m for all i, j, and k.The proof concludes with this uniform entrywise inequality.
Loading 1410.1386v2…