PaperlayerView exact revision on arXiv

Source-linked AI summary

Linearized Alternating Direction Method with Parallel Splitting and Adaptive Penalty for Separable Convex Programs in Machine Learning

Zhouchen Lin, Risheng Liu, Huan Li

arXiv:1310.5035v2math.NAcs.LGmath.OCstat.ML

TL;DR

Large-scale machine-learning problems often involve multi-block linearly constrained separable convex programs, while standard ADM and LADM are primarily developed for two-block settings. The paper proposes LADMPSAP, combining linearization, parallel splitting, and adaptive penalties, and reports stronger convergence results, practical computational advantages, and favorable numerical performance.

  • Problem

    Existing ADM and LADM theories mainly cover two-block problems, while naive multi-block extensions may diverge and large-scale convex programs challenge interior-point scalability.

  • Method

    LADMPSAP combines linearized subproblems, parallel splitting, and adaptive penalty updates to solve multi-block separable convex programs.

  • Results

    The method provides convergence results allowing unbounded penalty parameters under bounded-subgradient conditions, including sufficient and necessary conditions for global convergence.

  • Takeaways & Limitations

    Closed-form subproblems, preservation of sparsity and low-rankness, and parallelism make LADMPSAP suitable for sparse-representation, low-rank-recovery, and distributed-computing applications.

  • Takeaways & Limitations

    Naive multi-block ADM/LADM generalizations may diverge, and prior approaches can destroy iterate structure or require fixed penalty parameters.

Abstract

from arXiv · show

Many problems in machine learning and other fields can be (re)for-mulated as linearly constrained separable convex programs. In most of the cases, there are multiple blocks of variables. However, the traditional alternating direction method (ADM) and its linearized version (LADM, obtained by linearizing the quadratic penalty term) are for the two-block case and cannot be naively generalized to solve the multi-block case. So there is great demand on extending the ADM based methods for the multi-block case. In this paper, we propose LADM with parallel splitting and adaptive penalty (LADMPSAP) to solve multi-block separable convex programs efficiently. When all the component objective functions have bounded subgradients, we obtain convergence results that are stronger than those of ADM and LADM, e.g., allowing the penalty parameter to be unbounded and proving the sufficient and necessary conditions} for global convergence. We further propose a simple optimality measure and reveal the convergence rate of LADMPSAP in an ergodic sense. For programs with extra convex set constraints, with refined parameter estimation we devise a practical version of LADMPSAP for faster convergence. Finally, we generalize LADMPSAP to handle programs with more difficult objective functions by linearizing part of the objective function as well. LADMPSAP is particularly suitable for sparse representation and low-rank recovery problems because its subproblems have closed form solutions and the sparsity and low-rankness of the iterates can be preserved during the iteration. It is also highly parallelizable and hence fits for parallel or distributed computing. Numerical experiments testify to the advantages of LADMPSAP in speed and numerical accuracy.

1 Introduction

Large-scale machine-learning problems often take the form of linearly constrained separable convex programs, but existing methods face scalability and multi-block convergence challenges. LADMPSAP combines linearization, parallel splitting, and adaptive penalties to address these challenges while preserving useful structure in applications.

  • Problem setting: Many machine-learning problems can be formulated as linearly constrained separable convex programs with multiple variable blocks.Blocks may be vectors or matrices, and extra convex-set constraints can be incorporated through auxiliary variables.
  • Applications: The method is intended for diverse machine-learning models, including latent low-rank representation, nonnegative matrix completion, and overlapped group sparse logistic regression.These models use separable objectives, auxiliary variables, and convex constraints to fit the general program form.
  • Scalability challenge: Interior-point methods can require O(q6) work per iteration for q × q nuclear-norm problems, making them unsuitable for large-scale computing.Such problems include matrix completion, robust principal component analysis, and low-rank representation.
  • Scalability challenge: ADM and LADM theories mostly address two-block problems, while naive multi-block extensions may diverge.Multi-block formulations arise in applications such as robust principal component analysis with dense noise.
  • Limitations of prior methods: Existing alternatives can destroy sparsity or low-rankness, require difficult subproblem solves, or depend on a fixed penalty parameter.These limitations complicate tuning and can reduce suitability for sparse-representation and low-rank-recovery problems.
  • Proposed approach: LADMPSAP combines linearized subproblems, parallel splitting, and adaptive penalties for multi-block separable convex programs.Its design targets cheap subproblems, preservation of sparsity and low-rankness, and parallel or distributed computation.

2 Review of LADMAP for the Two-Block Case

The paper reviews two-block LADMAP and develops LADMPSAP to address the convergence difficulties of naively extending LADMAP to multiple blocks. It establishes global convergence conditions and an ergodic convergence-rate result for the proposed method.

  • LADMAP review: Two-block LADMAP updates the variable blocks alternately because each latest block iterate is immediately used in the next update.This alternating dependency distinguishes the two-block procedure from the proposed parallel-splitting method.
  • Multi-block difficulty: Naively extending LADMAP or ADM to multiple blocks can diverge, so two-block convergence proofs do not directly apply.The difficulty is tied to incompatible Fejér-monotonicity inequalities; prior work introduced Gaussian back substitution for correction.
  • LADMPSAP method: LADMPSAP updates all xi in parallel and adapts the penalty parameter βk, while modifying the multiplier construction and requiring larger ηi values.The method inherits the penalty-update procedures from LADMAP but replaces the block-dependent multiplier quantity with an i-independent one.
  • Global convergence: When βk is non-decreasing and upper bounded and ηi > n∥Ai∥2, LADMPSAP converges to a KKT point of problem (1).For bounded subgradients, the paper removes the upper-bound requirement on βk and proves sufficient and necessary global-convergence conditions.
  • Convergence rate: The proposed optimality measure is the magnitude of a nonnegative quantity that equals zero exactly at an optimal solution.This measure handles constrained problems and avoids comparing iterates with all feasible primal-dual points.
  • Convergence rate: The paper proves an ergodic convergence-rate result for averaged iterates that applies with bounded or unbounded penalty sequences.The result provides an O(1/K) rate for the optimality measure in the relevant case and is consistent with the requirement that βk approach infinity.

4 Practical LADMPSAP for Convex Programs with Convex Set Constraints

The paper extends LADMPSAP to separable convex programs with convex set constraints by introducing auxiliary variables and using easily computable projections. Refined parameter estimates yield convergence to a KKT point while retaining a practical parallel algorithm.

  • Model reformulation: The practical extension assumes projections onto the closed convex sets X_i are easily computable, as for nonnegative or positive semi-definite cones.This assumption covers many convex sets used in machine learning.
  • Model reformulation: Auxiliary variables convert each constraint x_i ∈ X_i into an equality with a separate constrained variable, enabling LADMPSAP to handle convex set constraints.The reformulation uses x_i = x_{n+i} and x_{n+i} ∈ X_i, with characteristic functions representing the sets.
  • Algorithm: The algorithm computes an auxiliary multiplier, updates all x_i variables in parallel, then updates the multiplier and adaptive penalty parameter.The practical implementation uses the refined 2n-block formulation and corresponding parameter replacements.
  • Convergence: The refined choices η_i > n∥A_i∥^2 + 2 and η_{n+i} > 2 guarantee convergence to a KKT point when β_k is non-decreasing and upper bounded.These estimates are tighter than the pessimistic values obtained by directly applying the earlier theorem.
  • Convergence: When all original subgradients are bounded, the upper bound β_max can be removed, and the ergodic convergence-rate result also carries over.The rate is inherited from the original LADMPSAP through refined parameter estimation.

5 Proximal LADMPSAP for Even More General Convex Programs

The paper generalizes LADMPSAP to objectives whose proximal operations are difficult by splitting each objective into smooth and proximable components, linearizing the smooth part, and adding proximal terms. The resulting proximal LADMPSAP converges to KKT points and has an ergodic convergence-rate guarantee.

  • Objective extension: Proximal LADMPSAP addresses objectives with difficult proximal operations by decomposing each f_i into a smooth component g_i and an easily proximable component h_i.The smooth component has Lipschitz-continuous gradient, while h_i may be nondifferentiable.
  • Objective extension: The method linearizes the smooth component and adds a proximal term, producing easily solvable subproblems with τ_i^(k) = T_i + β_kη_i.The parameters satisfy T_i ≥ L_i and η_i > n∥A_i∥^2.
  • Algorithm: The algorithm updates the auxiliary multiplier, solves all x_i subproblems in parallel, and then updates λ and β using the adaptive-penalty rules.This procedure is summarized as Algorithm 3, proximal LADMPSAP.
  • Convergence: Under a non-decreasing, upper-bounded penalty sequence and positive proximal parameters, proximal LADMPSAP converges to a KKT point.The convergence statement applies to the generalized separable convex model.
  • Convergence: The method also has an ergodic convergence-rate theorem, and an analogous result applies when extra convex set constraints are introduced.The constrained extension uses auxiliary variables as in the earlier practical formulation.

6 Numerical Results

Experiments evaluate LADMPSAP and its practical and proximal variants across latent LRR, nonnegative matrix completion, image inpainting, and overlapping group sparse logistic regression. The reported results show faster and more numerically accurate performance than several competing methods, with adaptive penalty improving speed.

  • Latent Low-Rank Representation: LADMPSAP is compared with APG, naive ADM, naive LADM, LADMGB, and LADMPS on latent LRR experiments.The comparisons use computing time, iterations, relative errors, and clustering accuracy averaged over 10 runs.
  • Latent Low-Rank Representation: LADMPSAP is faster and more numerically accurate than LADMGB, while adaptive penalty makes it faster than LADMPS.The final penalty values were 21.1567, 42.2655, and 81.4227 for the three data settings.
  • Latent Low-Rank Representation: On Hopkins155, LADMPSAP is faster than the other compared methods, including LADMPS, across 156 motion sequences.The evaluation reports average computing time, iterations, and classification errors.
  • Nonnegative Matrix Completion: For synthetic nonnegative matrix completion, LADMPSAP has much better numerical performance than LADM.The comparison uses relative nonnegative feasibility, with FA defined from the computed solution and ground truth.
  • Group Sparse Logistic Regression with Overlap: In overlapping group sparse logistic regression, proximal LADMPSAP is faster and more numerically accurate because competing methods have time-consuming subproblem computations.All compared algorithms recover the ground-truth support, while proximal LADMPSAP uses fewer costly inner computations.
  • Group Sparse Logistic Regression with Overlap: In pathway analysis, proximal LADMPSAP is more than ten times faster than the active set method and remains competitive in prediction error and pathway-level sparseness.It uses a training set more than ten times larger than the active set method in the reported comparison.

7 Conclusions

The paper proposes LADMPSAP for linearly constrained multi-block separable convex programs in machine learning. It uses parallel splitting and adaptive penalty with cheap proximal or projection steps, while the authors note remaining numerical algebraic computations as a scalability boundary.

  • Conclusions: LADMPSAP is proposed to efficiently solve linearly constrained multi-block separable convex programs common in machine learning.The method combines linearization, parallel splitting, and adaptive penalty.
  • Conclusions: Proximal operations and projections are easily solvable in the targeted problems, making each iteration cheap and preserving sparse or low-rank iterates.The method is also highly parallel and suited to parallel or distributed computing.
  • Conclusions: Numerical experiments report advantages of LADMPSAP over other possible first-order methods.The conclusion summarizes the experimental evidence across the paper’s machine-learning applications.
  • Conclusions: Large-scale applications still require numerical algebraic computations within component proximal operations, motivating integration with distributed techniques for scalability.The authors specifically mention distributed incomplete Cholesky factorization and caching factorization techniques.

A Proof of Theorem 1

Under the stated assumptions, the generated sequence is Fejér monotone and converges globally to a KKT point of problem (1). The proof establishes feasibility, optimality, and convergence of the whole sequence.

  • Fejér monotonicity: Proposition 2 establishes a Fejér-monotone sequence, a cornerstone for convergence analysis of Lagrange-multiplier algorithms.For more than two blocks, the proof cannot reproduce the inequality structure used in earlier two-block analysis.
  • Boundedness and accumulation: The algorithm-generated sequence is bounded and has accumulation points under the assumptions of Proposition 3.The proof then analyzes an arbitrary accumulation point.
  • KKT characterization: Each accumulation point, together with its multiplier, is a KKT point of problem (1).The proof identifies the limiting primal-dual point through the KKT conditions.
  • Optimality: Every accumulation point satisfies the feasibility condition and is an optimal solution to problem (1).The argument uses the feasibility and optimality conditions associated with a KKT point.
  • Global convergence: The whole sequence converges to a KKT point of problem (1), rather than merely possessing convergent subsequences.Because the limiting point can be any accumulation point, the proof concludes convergence of the complete sequence.

B Proof of Theorem 2

Theorem 2 extends convergence analysis to non-decreasing, unbounded penalty parameters under bounded-subgradient assumptions. The proof shows that primal iterates still converge to an optimal solution.

  • Assumptions: If βk is non-decreasing and unbounded, ηi > n∥Ai∥2, and ∂fi(x) is bounded, Proposition 3 remains valid.These conditions are stated as sufficient assumptions for retaining the proposition’s conclusions.
  • Multiplier control: The scaled multiplier sequence βk^-1λk remains bounded, supporting the limiting argument for unbounded penalties.This boundedness follows from Proposition 3-2).
  • Unbounded penalty: Theorem 2 specifically addresses the case where the penalty sequence is unbounded; bounded penalties were already covered by Theorem 1.The proof therefore focuses on the unbounded case.
  • Accumulation: The primal sequence is bounded and therefore has at least one accumulation point.This provides the limiting point used in the remainder of the proof.
  • Optimality: Every accumulation point is feasible and converges to an optimal solution of problem (1).The proof combines feasibility from Proposition 3-1) with optimality derived from Proposition 3-2).

C Proof of Theorem 3

Theorem 3 constructs nonzero linear mappings that expose a failure mode of convergence to a chosen optimum under a rank-deficiency condition. The proof uses a Cauchy-sequence argument for an auxiliary sequence.

  • Construction: The proof constructs linear mappings Bi whose matrix representations satisfy a nontrivial algebraic relation.The mappings are required not all to be zero.
  • Rank condition: Because the relevant solution is not full column rank, the associated system has nonzero solutions for the Bi matrices.This rank condition enables the construction used in the theorem.
  • Limit argument: Under the stated boundedness condition, the auxiliary sequence {vk} is Cauchy and therefore converges to a limit v∞.The proof explicitly defines the limit after establishing the Cauchy property.
  • Initialization dependence: A badly initialized sequence can fail to converge to the selected optimal solution.The construction relies on φ not being a zero mapping under the conditions imposed on Bi.

D Proofs of Proposition 1 and Theorem 4

The proofs establish an optimality characterization for Proposition 1 and derive Theorem 4 through inequalities based on the algorithm’s penalty lower bound and convexity.

  • Proposition 1: If ˜x is optimal, it satisfies condition (24).The proof checks this implication directly from optimality.
  • Proposition 1: Conversely, satisfaction of condition (24), together with feasibility, implies that ˜x is an optimal solution to problem (1).The proof reduces the objective comparison to f(˜x) = f(x∗).
  • Theorem 4: Convexity of f and the squared Frobenius norm supplies the final inequality used in the proof of Theorem 4.This step follows the preceding inequality combination.
  • Theorem 4: Theorem 4’s proof uses βk ≥ β0, guaranteed by the parameter conditions, before summing inequalities through iteration K.The summed inequalities are then normalized by division.

E Proof of Theorem 5

The proof establishes boundedness and convergence properties for the iterates, then identifies the limiting point as feasible and satisfying the KKT conditions.

  • The argument proceeds by proving a proposition and applying the same technique to establish Theorem 5.
  • The generated sequence is shown to be bounded and therefore to have an accumulation point.
  • A convergent subsequence of the iterates approaches a limiting primal-dual point.
  • The proof uses inequalities involving the iterates, penalty parameters, and dual variables to derive the convergence claims.
  • The limiting primal variables form a feasible solution, and the limiting primal-dual tuple is a KKT point.

G Proof of Theorem 7

The proof aggregates the iteration inequalities over a finite range and uses the penalty-parameter monotonicity to obtain the stated bound.

  • The proof divides an inequality by βk and uses the non-decrement of βk and non-increment of βk^-1.
  • These aggregation steps yield the convergence estimate stated in the theorem.
  • It then sums the resulting inequalities from k = 0 through K and divides both sides by the associated normalization term.
Loading 1310.5035v2…