PaperlayerView exact revision on arXiv

Source-linked AI summary

Parallel Algorithms for Constrained Tensor Factorization via the Alternating Direction Method of Multipliers

Athanasios P. Liavas, Nicholas D. Sidiropoulos

arXiv:1409.2383v2math.NAcs.DCcs.ITcs.NAmath.IT

TL;DR

Tensor factorization methods have largely been developed for centralized, single-machine computation, despite big-data applications requiring parallel architectures and practically important constraints such as nonnegativity. This paper develops an ADMoM-based constrained factorization framework; experiments suggest it can achieve close to state-of-the-art accuracy in many cases.

  • Problem

    Most tensor factorization algorithms were designed for centralized, single-machine computation, while big-data tensors may require parallel architectures and constraints such as nonnegativity require constrained updates.

    Source: §I · p. 2

  • Method

    The paper develops an ADMoM-based constrained tensor factorization framework, using nonnegative CP decomposition as its working example.

    Source: §I · p. 3

  • Results

    Experiments suggest ADMoM NTF can efficiently achieve close to state-of-the-art factorization accuracy in many cases.

    Source: E. Discussion · p. 24

  • Takeaways & Limitations

    Its suitability for high-performance parallel implementation may make the framework a valuable tool in the NTF toolbox.

    Source: E. Discussion · p. 24

    The authors identify improvement of ADMoM NTF's behavior in high-rank cases as a remaining problem.

    Source: §VII · p. 25

Abstract

from arXiv · show

Tensor factorization has proven useful in a wide range of applications, from sensor array processing to communications, speech and audio signal processing, and machine learning. With few recent exceptions, all tensor factorization algorithms were originally developed for centralized, in-memory computation on a single machine; and the few that break away from this mold do not easily incorporate practically important constraints, such as nonnegativity. A new constrained tensor factorization framework is proposed in this paper, building upon the Alternating Direction method of Multipliers (ADMoM). It is shown that this simplifies computations, bypassing the need to solve constrained optimization problems in each iteration; and it naturally leads to distributed algorithms suitable for parallel implementation on regular high-performance computing (e.g., mesh) architectures. This opens the door for many emerging big data-enabled applications. The methodology is exemplified using nonnegativity as a baseline constraint, but the proposed framework can more-or-less readily incorporate many other types of constraints. Numerical experiments are very encouraging, indicating that the ADMoM-based nonnegative tensor factorization (NTF) has high potential as an alternative to state-of-the-art approaches.

I. INTRODUCTION · A. Notation · II. NON-NEGATIVE TENSOR FACTORIZATION

The paper develops ADMoM-based constrained tensor factorization, focusing on non-negative CP decomposition, to avoid constrained subproblems within iterations and enable distributed computation. It defines the NTF fitting problem and notation, and reports encouraging experiments for the approach.

I. INTRODUCTION

  • Most earlier tensor factorization algorithms assumed centralized, single-machine in-memory computation, which is inadequate when large tensors require cloud or parallel computing.Source: §I · p. 2
  • Prior distributed CP approaches based on ALS did not address regular mesh architectures or constraints on latent factors.Source: §I · p. 3
  • The framework focuses on non-negative CP decomposition but can extend to other factor constraints, Tucker3, and tensor completion.Source: §I · p. 3
  • The proposed ADMoM iterations avoid solving constrained optimization problems, reducing per-iteration complexity relative to constrained least-squares methods such as NALS.Source: §I · p. 3
  • ADMoM also naturally yields distributed algorithms suited to regular high-performance-computing architectures, including mesh architectures.Source: §I · p. 3
  • ADMoM-based NTF experiments are encouraging, suggesting the approach has significant potential as an alternative to state-of-the-art methods.Source: §I · p. 3

A. Notation

  • The notation section defines conventions for vectors, matrices, and tensors and specifies the norms, projections, products, and pseudoinverse used in the paper.Source: A. Notation · p. 4

II. NON-NEGATIVE TENSOR FACTORIZATION

  • The NTF section formulates estimation of nonnegative factor matrices for a noisy tensor using a factorization-quality objective, with Gaussian i.i.d. noise motivating a common choice.Source: §II · p. 4

III. ADMOM

Section III introduces ADMoM for a split optimization problem, defines its augmented Lagrangian with penalty parameter ρ, and describes an iterative method whose state includes z_k and y_k. Under certain conditions including convexity, ADMoM converges in a certain sense; for nonconvex tensor factorization, the goal is a good local minimum.

III. ADMOM

  • ADMoM is presented as a technique for solving an optimization problem involving variables x and z, with linear constraint data A, B, and c and objective functions f and g [26].The passage specifies x ∈ R^n1, z ∈ R^n2, A ∈ R^m×n1, B ∈ R^m×n2, c ∈ R^m, f : R^n1 → R, and g : R^n2 → R.Source: §III · p. 5
  • The augmented Lagrangian for the optimization problem includes a penalty parameter ρ > 0.The supplied passage does not specify the full expression.Source: §III · p. 5
  • At iteration k + 1, ADMoM proceeds from the algorithm state comprising z_k and y_k.The passage introduces the iteration but does not include its update equations.Source: §III · p. 5
  • Under certain conditions, including convexity of f and g, ADMoM converges in a certain sense; for nonconvex tensor factorization, the goal is a good local minimum, given its NP-hardness [15].The passage frames a good local minimum as a realistic goal irrespective of the approach or algorithm used.Source: §III · p. 5

A. ADMoM for set-constrained optimization · IV. ADMOM FOR NTF

The paper reformulates closed-convex-set constraints so ADMoM uses projection updates, then applies this splitting approach to NTF to avoid constrained subproblems during each iteration.

A. ADMoM for set-constrained optimization

  • Introducing auxiliary variables makes the set-constrained problem equivalent to an objective with an indicator function for the closed convex set.The set is X, and the auxiliary variable z belongs to R^n.Source: A. ADMoM for set-constrained… · p. 6
  • The resulting ADMoM iteration uses Euclidean projection onto X [26].The stated iteration assumes the current z and y values have been computed.Source: A. ADMoM for set-constrained… · p. 6

IV. ADMOM FOR NTF

  • To put the NTF problem (1) into ADMoM form, the equivalent optimization problem introduces auxiliary variables ˜A ∈ RI×F, ˜B ∈ RJ×F, and ˜C ∈ RK×F, with A=˜A, B=˜B, and C=˜C.Source: §IV · p. 6
  • Because the first ADMoM minimization is non-convex, the paper proposes an alternating optimization scheme for its updates.The scheme uses equivalent expressions for fX.Source: §IV · p. 7
  • The NTF ADMoM iteration avoids solving constrained optimization problems, which is favorable when problem sizes are very large.The updates may run for a predetermined number of iterations or until convergence.Source: §IV · p. 7
  • The original iterates A, B, and C need not be nonnegative, whereas their auxiliary copies are nonnegative by construction.Upon convergence, the original factors become nonnegative or their negative elements become very small.Source: §IV · p. 7

A. Computational complexity per iteration · B. Convergence

The paper gives rough per-iteration complexity estimates for ADMoM’s matrix updates and shows that, under Proposition 1’s condition, accumulation points are KKT points; convergence implies a KKT limit.

A. Computational complexity per iteration

B. Convergence

  • Under Proposition 1’s condition, every accumulation point of the ADMoM sequence is a KKT point of the NTF problem, as are accumulation points of (A_k, B_k, C_k).Source: B. Convergence · p. 9
  • Whenever the sequence Z_k converges, its limit is a KKT point; practical convergence is discussed with the numerical experiments.Source: B. Convergence · p. 9

C. Stopping criteria … A. Matrix unfoldings in terms of partitioned matrix factors

The paper specifies practical ADMoM stopping and penalty-adaptation rules, extends the framework to structural constraints, and derives partitioned unfoldings to support distributed NTF when tensor dimensions are large.

C. Stopping criteria

  • For the other residuals, analogous conditions apply: a reasonable relative tolerance is ǫrel ⪅ 10^-3, while ǫabs depends on the scale of latent-factor values.The stopping criteria involve quantities on the scale of the latent factors, which in most cases is small compared with the tensor. Computing them during every ADMoM iteration is not computationally demanding.Source: C. Stopping criteria · p. 10

D. Varying penalty parameters

  • Penalty parameters ρA, ρB, and ρC can be adapted using their corresponding primal and dual residuals: larger penalties reduce primal residuals, while smaller penalties tend to reduce dual residuals.The adaptation uses parameters µ, τ_incr, and τ_decr, each greater than 1.Source: D. Varying penalty parameters · p. 10

E. ADMoM for tensor factorization with structural constraints

  • Structural constraints can be incorporated by projecting onto the relevant feasible set; for nonnegative factors with at most cA nonzeros, sorting computes the required projection, while more complex constraints remain future work.The framework also covers box or other set constraints when projection onto the constraint set is easy.Source: E. ADMoM for tensor factorization with… · p. 10

V. DISTRIBUTED ADMOM FOR LARGE NTF

  • The distributed NTF development assumes all tensor dimensions are large, although the framework also handles cases where only one or two dimensions are large.Source: §V · p. 11

A. Matrix unfoldings in terms of partitioned matrix factors

B. Distributed ADMoM for large NTF

Distributed ADMoM reformulates large NTF with auxiliary factor copies and equality constraints, enabling independent parallel block updates while avoiding constrained optimization subproblems. With matching initialization, it follows the same evolution as centralized ADMoM.

B. Distributed ADMoM for large NTF

  • The large-NTF formulation introduces partitioned auxiliary factor copies constrained to equal their corresponding factor blocks.Source: B. Distributed ADMoM for large NTF · p. 12
  • During each ADMoM iteration, the method avoids constrained optimization subproblems and computes independent A, B, and C block updates in parallel.The A-block updates are independent; the algorithm then computes the B- and C-block updates in parallel.Source: B. Distributed ADMoM for large NTF · p. 13
  • With identical initialization, distributed and centralized ADMoM evolve identically, so studying either form suffices to characterize both.The distributed form uncovers inherent parallelism in the A, B, and C block updates.Source: B. Distributed ADMoM for large NTF · p. 14

C. A parallel implementation of ADMoM for large NTF

The section outlines a mesh-based distributed ADMoM implementation for large NTF, including its data layout and communication pattern. It also describes communication limits, support for other constraints, and architecture-specific work deferred to future implementations.

C. A parallel implementation of ADMoM for large NTF

VI. NUMERICAL EXPERIMENTS · A. Comparison of ADMoM with NALS and NLS

Across the tested scenarios, there is no clear overall winner among ADMoM, NALS, and NLS, but ADMoM is much faster when one tensor dimension is very large and rank is relatively small. ADMoM’s runtime is less predictable at high ranks, partly because convergence depends on initialization.

A. Comparison of ADMoM with NALS and NLS

  • The study compared nonnegative ADMoM NTF with NALS via parafac and NLS via sdf nls across 12 scenarios varying tensor dimensions, rank, and additive noise.Each scenario used 50 realizations; the algorithms were initialized randomly.Source: A. Comparison of ADMoM with NALS and NLS · p. 16
  • Stopping parameters were chosen so that converged algorithms achieved practically the same relative factorization error, and all three algorithms converged in every realization.For the large-dimension experiment, stopping conditions were relaxed for all algorithms.Source: A. Comparison of ADMoM with NALS and NLS · pp. 16, 17, 19
  • For I = 104, J = K = 50, F = 10, and σ2_N = 10−2, ADMoM was much faster than NALS and NLS and slightly more accurate in relative factorization error.The comparison used relaxed stopping conditions; analogous observations were reported for larger I.Source: Table II · p. 19, A. Comparison of ADMoM with NALS and NLS · pp. 19–20, Figure 4 · p. 20
  • Across scenarios, there was no clear winner: NLS performed very well at high ranks, while ADMoM was more competitive at small ranks, especially when one dimension was much larger than the others.All algorithms converged in every realization.Source: A. Comparison of ADMoM with NALS and NLS · pp. 17, 19
  • At high ranks, NALS and NLS behaved more predictably than ADMoM, whose cputime had large variance associated with initialization-sensitive convergence.ADMoM ran for up to 400 iterations before restarting from a new random initial point if it had not converged.Source: A. Comparison of ADMoM with NALS and NLS · pp. 17, 19
  • For I = 3000, J = K = 50, and σ2_N = 10−2, runtimes were stable at F = 3, but ADMoM’s runtime variance increased at F = 30.At F = 30, ADMoM converged faster than NALS and NLS from good initial points but needed one or more restarts from bad points.Source: Figure 2 · p. 18, Figure 3 · p. 18, A. Comparison of ADMoM with NALS and NLS · p. 19

B. A closer look at ADMoM

For I = 3000, J = K = 50, F = 30, and σ2 N = 10−2, ADMoM often required restarts to converge; its final path to convergence was stable around 320 iterations, estimating its fastest possible convergence.

B. A closer look at ADMoM

  • ADMoM often needed restarts in the scenario I = 3000, J = K = 50, F = 30, and σ2 N = 10−2.The paper compares total iterations, iters, with mod(iters, nmax), the iterations required if ADMoM always starts from good initial points.Source: B. A closer look at ADMoM · pp. 20–21
  • The total iteration count, iters, is compatible with ADMoM’s cputime in this scenario.The cputime is plotted in Figure 3, and the iteration counts in Figure 5.Source: B. A closer look at ADMoM · p. 20, Figure 5 · p. 21
  • About 320 iterations on ADMoM’s final path to convergence provide an estimate of its fastest possible convergence in this scenario.The number of iterations on this final path, mod(iters, nmax), is described as quite stable around its mean.Source: Figure 5 · p. 21, B. A closer look at ADMoM · p. 21

C. ADMoM NTF with under- and over-estimated rank … VII. CONCLUSION

Overestimated rank can ultimately achieve error trajectories as good as exact rank, though its restart and convergence behavior varies. Box-linear constraints, parallel implementation, and broader applicability are demonstrated or proposed, while evaluation and high-rank performance remain open concerns.

C. ADMoM NTF with under- and over-estimated rank

  • With noisy data, overestimated-rank ADMoM ultimately matches exact-rank error but needs more restarts (1.92 vs. 1.08), while underestimated rank converges to higher error.The mean restart count for underestimated rank was 1.22.Source: Figure 6 · p. 22, C. ADMoM NTF with under- and… · pp. 22–23
  • For noiseless data, exact and overestimated rank have no error floor, though overestimation slows at high precision; mean restarts were 1.14, 1.06, and 1.54 for exact, over-, and underestimation.Similar behavior was observed with more drastic rank under- and over-estimation.Source: Figure 7 · p. 22, C. ADMoM NTF with under- and… · p. 23

D. ADMoM for NTF with box-linear constraints

E. Discussion

  • The authors report that ADMoM NTF can efficiently achieve close to state-of-the-art accuracy and is suitable for high-performance parallel implementation.They describe it, as far as they know, as the first NTF algorithm with this parallel property.Source: E. Discussion · p. 24
  • The paper presents basic performance metrics, but fuller evaluation is needed; real-world data experiments and constraints beyond nonnegativity are ongoing.Source: E. Discussion · p. 24
  • High-rank cases are a weak point because ADMoM has high CPU-time variance; improving this behavior, potentially by combining NLS and ADMoM, needs further research.Source: E. Discussion · p. 24
  • When centralized and distributed ADMoM start from the same point, they evolve identically, so the distributed algorithm inherits centralized ADMoM’s convergence properties.Source: E. Discussion · p. 24

VII. CONCLUSION

  • The conclusion presents ADMoM as a constrained tensor-factorization framework, exemplified with third-order nonnegative factorization and generalizable to higher-order tensors, other constraints, tensor factorizations, and completion.Experiments suggest ADMoM-based NTF may be an alternative to state-of-the-art methods and, in some cases, may become state-of-the-art; high-rank behavior remains to be improved.Source: §VII · pp. 24–25

APPENDIX A EXTENSION TO HIGHER ORDER TENSORS · APPENDIX B ON THE EQUIVALENCE OF THE CENTRALIZED AND THE DISTRIBUTED ADMOM NTF

The appendices show how the ADMoM NTF framework extends to higher-order tensors and establish that its distributed updates expose parallelism already present in the centralized algorithm.

APPENDIX A EXTENSION TO HIGHER ORDER TENSORS

  • The extension focuses on fourth-order tensors, with the general higher-order case described as obvious.Source: Appendix A · p. 25
  • Partitioning A, B, C, and D as in subsection V-A makes W(1) consist of NA × ND blocks.The passage states that each (i, j)-th block has a specified form, but that form is not included in the supplied text.Source: Appendix A · p. 25
  • Analogous partitionings apply to the other unfoldings, making centralized and distributed ADMoM NTF development straightforward.Source: Appendix A · p. 25

APPENDIX B ON THE EQUIVALENCE OF THE CENTRALIZED AND THE DISTRIBUTED ADMOM NTF

  • The equivalence proof compares the centralized A_k update with updates of its distributed blocks A_k^{nA}, for nA = 1, . . . , NA.Source: Appendix B · p. 25
  • Rewriting the centralized A_k update in partitioned form yields each distributed block update, with the matrix inverse shared across blocks and computed once.The derivation uses partitionings of C_k ⊙ B_k.Source: Appendix B · pp. 25–26
  • The blockwise update equivalence extends analogously to B_k and C_k, while equivalence of the remaining variable updates is trivial.Source: Appendix B · p. 26
  • The distributed ADMoM uncovers the inherent parallelism of the centralized ADMoM through the partitionings introduced earlier.Source: Appendix B · p. 26

Related papers

Loading 1409.2383v2…