PaperlayerView exact revision on arXiv

Source-linked AI summary

Parallel Selective Algorithms for Big Data Optimization

Francisco Facchinei, Gesualdo Scutari, Simone Sagratella

arXiv:1402.5521v5cs.DCcs.ITmath.NAmath.OC

TL;DR

Large-scale optimization with smooth possibly nonconvex objectives and block-separable nonsmooth regularizers needs methods that exploit parallelism without updating every variable. The paper proposes a deterministic decomposition framework spanning parallel, sequential, and selective updates, and reports consistent empirical outperformance on LASSO, logistic regression, and nonconvex problems.

  • Problem

    Large-scale problems of minimizing a smooth function plus a block-separable nonsmooth convex term are difficult for standard methods, motivating parallel and selective optimization methods.

  • Method

    The paper decomposes the problem into strongly convex subproblems based on convex approximations of F, allowing flexible parallel, sequential, selective, distributed, and inexact updates.

  • Results

    Numerical results on LASSO, logistic regression, and nonconvex problems consistently outperform state-of-the-art schemes.

  • Takeaways & Limitations

    The framework provides a single convergence-guaranteed structure encompassing full Jacobi, Gauss-Seidel-type, and intermediate update strategies.

  • Takeaways & Limitations

    The nonconvex evaluation is preliminary, with a more detailed analysis deferred to future work.

Abstract

from arXiv · show

We propose a decomposition framework for the parallel optimization of the sum of a differentiable (possibly nonconvex) function and a (block) separable nonsmooth, convex one. The latter term is usually employed to enforce structure in the solution, typically sparsity. Our framework is very flexible and includes both fully parallel Jacobi schemes and Gauss- Seidel (i.e., sequential) ones, as well as virtually all possibilities "in between" with only a subset of variables updated at each iteration. Our theoretical convergence results improve on existing ones, and numerical results on LASSO, logistic regression, and some nonconvex quadratic problems show that the new method consistently outperforms existing algorithms.

I. INTRODUCTION

The paper targets large-scale optimization problems combining a smooth function with a block-separable nonsmooth convex term, proposing a flexible parallel framework for nonconvex settings. Experiments on LASSO, logistic regression, and nonconvex problems report consistent outperformance of state-of-the-art schemes.

  • Motivation: Large-scale applications often use a nonsmooth term to promote sparse, parsimonious solutions, but their size makes standard optimization techniques difficult to apply.The motivating applications include compressed sensing, machine learning, genomics, and radio astronomy.
  • Motivation: Parallel methods are needed for big-data problems, while updating only selected blocks can reduce dimensionality-related computational burden.The paper notes that selective updates have also shown experimental benefits in restricted settings.
  • Contribution: The proposed framework decomposes nonconvex problems into simpler subproblems using convex approximations of F, solved in parallel or with only selected variables updated.The framework is deterministic and targets stationary solutions.
  • Contribution: Its update flexibility spans complete parallelism, sequential updates, and intermediate schemes, while supporting distributed implementations and inexact subproblem solutions.The framework also avoids requiring parameters such as the Lipschitz constant of ∇F.
  • Evaluation: Numerical results on LASSO, logistic regression, and nonconvex problems consistently outperform state-of-the-art schemes.The evaluation includes an extensive implementation on a parallel computer cluster.

II. PROBLEM DEFINITION

The paper studies minimizing a smooth, possibly nonconvex function plus a convex, possibly nondifferentiable block-separable term over a Cartesian-product feasible set. This formulation covers sparse and structured optimization problems including LASSO, logistic regression, support vector machines, and dictionary learning.

  • Problem formulation: The feasible set is a Cartesian product of lower-dimensional convex sets, with variables partitioned into corresponding blocks.The smooth term is F, while G is convex and block separable.
  • Problem formulation: The model allows F to be smooth and nonconvex, while G is convex, possibly nondifferentiable, and decomposes across variable blocks.Block separability supports the parallel treatment of nonsmooth terms.
  • Instances: LASSO is obtained with squared residual loss and an ℓ1 regularizer, promoting sparse solutions.The formulation also includes group-regularized variants such as sparse logistic regression.
  • Instances: Other instances include ℓ1-regularized support vector machines and dictionary learning with a non jointly convex objective.The dictionary-learning example combines Frobenius loss, matrix sparsity regularization, and constraints.
  • Assumptions: The analysis assumes closed convex block domains, differentiable F with Lipschitz-continuous gradient, continuous convex block terms, and coercivity.These assumptions are described as standard and applicable to many practical problems.

III. MAIN RESULTS

The main framework builds strongly convex block subproblems from convex first-order approximations of F, allowing deterministic selective updates, parallelism, and inexact solutions. Under stated assumptions and parameter conditions, its iterates converge to stationary solutions.

  • Framework construction: The method replaces F with convex block approximations that preserve its block gradient, retains the nonsmooth term, and adds a proximal quadratic term.Uniform strong convexity makes the resulting block subproblems well behaved.
  • Selective updates: The framework can update all blocks simultaneously, one block sequentially, or any selected subset containing a sufficiently nonoptimal block.Selection can use optimality measures or cheaper error bounds.
  • Algorithm: FLEXA permits inexact block solves and uses a relaxed update combining the current iterate with computed block solutions.The algorithm selects blocks through E_i(x^k), solves their subproblems to accuracy ε_i^k, and applies step size γ^k.
  • Convergence: Under assumptions A1–A6 and the theorem’s step-size and error conditions, the algorithm either finitely reaches a stationary solution or has stationary limit points.If inexact solutions persist infinitely often, the theorem additionally assumes that G is globally Lipschitz on X.
  • Variants and implementation: The framework includes full Jacobi, Gauss-Southwell, and related schemes, while distributed implementations require only limited information exchange when many variables are updated in parallel.For inexact updates, Lipschitz continuity of G is automatic when G is a norm or X is bounded.

A. Gauss-Jacobi algorithms

The Gauss-Jacobi extensions distribute variable blocks across processors, update variables sequentially within each processor, and can selectively update subsets of those variables. Their convergence theory covers hybrid parallel-sequential schemes and stationary limit points under additional assumptions.

  • A. Gauss-Jacobi algorithms: The framework also supports hybrid Jacobi–Gauss-Seidel schemes that update groups of variables simultaneously while computing entries within each group sequentially.The paper identifies these schemes as suited to multi-core and multi-processor architectures.
  • A. Gauss-Jacobi algorithms: Gauss-Jacobi assigns blocks to processors, computes within-processor updates sequentially, and uses newly computed values in subsequent calculations.This avoids wasting resources by recomputing each block against only the previous global iterate.
  • A. Gauss-Jacobi algorithms: Gauss-Jacobi with selection chooses subsets within processor partitions while preserving parallel execution across processors.The selected union must include at least one block whose error measure is sufficiently large.
  • Convergence: Under the theorem’s conditions plus boundedness of ∇F on X, both Gauss-Jacobi variants either terminate at a stationary solution or have stationary limit points.The same conclusion is stated for the selected and nonselected variants.
  • Empirical behavior: The experiments report that the selected Gauss-Jacobi algorithm performs well for highly nonlinear objective functions.The paper directs the detailed empirical evidence to its numerical-results section.

IV. EXAMPLES AND SPECIAL CASES

The framework generates diverse parallel, sequential, and partially updating algorithms by varying approximants, error bounds, stepsizes, and block partitions. Examples include Jacobi, coordinate-descent, logistic-regression, and dictionary-learning schemes, with convergence supported under broad conditions.

  • Framework flexibility: The general algorithms encompass many schemes through choices of approximants, error bounds, stepsizes, and block partitions.These choices control iteration complexity, communication overhead, and convergence speed while preserving common convergence conditions.
  • Step-size choices: The framework supports step-size rules including diminishing stepsizes, line searches, and suitably small constant stepsizes.Line searches may reduce iterations but require shared memory and coordination; constant stepsizes can lead to extremely slow convergence.
  • Selective updates: Partial variable updates require an error bound function, whereas updating all blocks avoids computing that bound.The all-block choice is always feasible within the framework.
  • Approximants: The approximant can range from linearizing F to using convex, second-order, or structure-preserving approximations.These choices include parallel nonlinear Jacobi methods, Newton-like reduced updates, and approximations that retain convex parts while linearizing nonconvex ones.
  • Special cases: Without convexity, the framework still supports convergence of Jacobi-type methods to stationary points.For convex smooth unconstrained problems, it avoids the strong contraction conditions required by classical parallel methods.
  • Applications: LASSO admits parallel coordinate updates with closed-form soft-thresholding, while logistic regression admits fully distributed parallel updates using second-order approximations.The examples instantiate the framework for structured nonsmooth objectives and blockwise convex smooth terms.

V. RELATED WORKS

The framework extends prior parallel and sequential SCA approaches to broader nonconvex, nonsmooth, distributed, and partially updating settings. It also permits varied approximations and inexact subproblem solutions without relying on line searches.

  • Prior work: Prior parallel SCA methods largely use proximal-gradient schemes and first-order approximations, limiting exploitation of additional structure in F.The paper contrasts these methods with approaches that use richer approximations to improve practical convergence speed.
  • Scope: The framework handles nonconvex nonsmooth problems, varied approximations of F, and inexact subproblem solutions.These capabilities broaden the method beyond deterministic gradient-like schemes and exact block updates.
  • Comparison: Compared with earlier partial-update schemes, the framework avoids restrictions tied to convexity, maximum simultaneous updates, exact subproblem solutions, or line searches.The cited comparison identifies these restrictions in prior algorithms.
  • Parallelism: The framework is fully parallel and distributed, does not rely on line searches, and supports general partial variable updates.The degree of parallelism can be chosen by the user.

VI. NUMERICAL RESULTS

The numerical study evaluates parallelism and selective variable updates on LASSO, logistic regression, and nonconvex problems. Experiments compare the proposed framework with state-of-the-art methods on a parallel computing architecture.

  • Experimental goals: The experiments test parallelism and selective greedy updates as two key features of the proposed framework.The study examines whether updating only some variables influences performance.
  • Benchmarks: The benchmark problems include LASSO, logistic regression, and nonconvex instances.LASSO and logistic regression are presented as widely studied convex cases of the target problem class.
  • Computing setup: The algorithms were implemented in C++ with Intel MKL and tested on the SUNY Buffalo General Compute Cluster.The cluster configuration included 372 processor nodes and experiments used up to 40 parallel units.

A. LASSO problem

The LASSO experiments instantiate FLEXA with fully parallel or selective updates and compare it with established distributed and sequential methods across sparsity levels and core counts. FLEXA σ = 0.5 consistently performs best, while selective updates become increasingly beneficial as solutions become less sparse.

  • Algorithm and implementation: FLEXA σ = 0.5 updates only a subset of variables, whereas FLEXA σ = 0 updates all variables at every iteration; both are convergent.The selective set always includes the variable with the largest error bound.
  • Algorithms compared: The LASSO comparisons include FISTA, SpaRSA, GRock, and Greedy-1BCD alongside FLEXA.The study evaluates competitive distributed and sequential algorithms for LASSO.
  • Experimental setup: 10,000-variable LASSO groups span solution sparsities of 1%, 10%, 20%, 30%, and 40%, with experiments averaged over ten random realizations using 40 cores.CPU time includes communication and pre-iteration computations.
  • Results: FLEXA σ = 0.5 consistently outperforms the implemented algorithms, and its advantage over FLEXA σ = 0 increases as solution sparsity decreases.FISTA reaches low accuracy relatively quickly for less sparse solutions but struggles at high accuracy; SpaRSA is less effective on very large problems.
  • Parallel performance: When increasing from 8 to 20 cores, FLEXA's running time approximately halves on LASSO problems.The paper reports similar behavior for smaller problems and other core counts, while noting that speed-up depends on implementation factors.
  • Selective updates: Selective updates can accelerate convergence because variables identified as zero remain zero in subsequent iterations, reducing unnecessary calculations.The best σ may depend on the problem, but the paper gives this identification behavior as theoretical motivation for selective updates.

B. Logistic regression problems

The logistic-regression experiments evaluate FLEXA variants and competing methods on three datasets using relative error, CPU time, and FLOPS. High nonlinearities favor Gauss-Seidel-type updates, while selective updates remain useful as parallelism increases.

  • Experimental setup: The implementation uses the optimality measure ∥Z(x)∥∞ because the optimal objective value is unknown.Z(x)=0 is equivalent to the standard necessary optimality condition.
  • Experimental setup: The tests use three LIBSVM logistic-regression datasets, with data distributed across parallel processors.The datasets are evaluated with 8, 16, 20, and 40 cores.
  • Results: GJ-FLEXA with one core clearly outperforms the other methods on the logistic-regression tests.The one-core configuration is nonparallel and has Gauss-Seidel-type behavior.
  • Results: Gauss-Seidel-type methods perform better than pure Jacobi methods because the logistic-regression objective is highly nonlinear.Figure 3 reports relative error versus time and FLOPS for gisette, real-sim, and rcv.
  • Results: Selective variable updates improve logistic-regression performance, whereas the tested parallelism does not appear beneficial in this setting.This comparison includes the dedicated coordinate-descent method.

C. Nonconvex quadratic problems

The paper presents preliminary nonconvex quadratic experiments comparing FLEXA with FISTA and SpaRSA under two sparsity levels. The results suggest good nonconvex behavior, but the analysis remains limited in scope.

  • Scope: A more detailed analysis of FLEXA in the nonconvex case is deferred to future work.The paper presents only preliminary results on nonconvex quadratic problems because of space limitations.
  • Comparison: FLEXA is compared with FISTA and SpaRSA, and all three algorithms converge to the same stationary point in the tests.Only SpaRSA has convergence guarantees for nonconvex problems among the compared methods.
  • Evaluation measures: The figures track relative error and merit value against elapsed time for the two sparsity settings.Figure 4 uses 1% sparsity, while Figure 5 uses 10% sparsity.
  • Results: The preliminary tests indicate that FLEXA performs well on nonconvex problems.This conclusion is limited to the reported preliminary quadratic experiments.

VII. CONCLUSIONS

The paper concludes that its flexible framework unifies many update schemes while allowing user control over parallelism and variable selection. Preliminary experiments are promising, but broader testing and parameter tuning remain open.

  • Framework: The framework minimizes a possibly nonconvex differentiable function plus a possibly nonsmooth, block-separable convex function.This formulation covers the paper’s target problem class.
  • Framework: Users can control the degree of parallelism and the number of variables updated at each iteration.All resulting algorithms converge under the same conditions.
  • Framework: Many well-known sequential and simultaneous solution methods are special cases of the framework.The framework supports multiple practical realizations for different problem classes.
  • Evidence: Preliminary tests show that the proposed schemes can outperform state-of-the-art algorithms.Experiments on larger and more varied problem classes are identified as future work.
  • Open issues: The initial choice and subsequent tuning of the τ_i parameters remain key issues for further study.The conclusion states that these parameters partly determine algorithm behavior.

A. Intermediate results

The intermediate analysis establishes properties of the blockwise approximation mapping used by the framework. Under the stated assumptions, it is Lipschitz, its fixed points coincide with stationary solutions, and selected updates yield useful bounds.

  • Approximation properties: The approximation function H(·;y) is uniformly strongly convex in x, with constant c_τ>0.This provides uniqueness for the block subproblem solutions.
  • Approximation properties: The mapping b_x(y) is Lipschitz continuous under the framework’s assumptions.The proof combines strong convexity, optimality inequalities, and Lipschitz continuity of the gradient approximation.
  • Stationarity: The fixed points of b_x(·) coincide with the stationary solutions of the original problem.A fixed point satisfies the stationarity condition through block separability and convexity of G.
  • Update analysis: The block-update optimality conditions provide the inequalities used to establish descent and convergence bounds.These conditions are applied to selected variable sets S and current iterates.
  • Convergence analysis: The convergence argument uses a sequence inequality of the form X_{k+1}≤X_k−Y_k+Z_k with summable errors Z_k.The associated lemma yields convergence when the sequence does not diverge to −∞.
  • Convergence analysis: Algorithm 1’s selected update includes an index whose error measure is at least a fraction ρ of the maximum error measure.This greedy-selection property supports the iteration bound in Lemma 10.

B. Proof of Theorem 1

The proof establishes convergence by bounding accumulated errors, showing that the objective sequence converges, and proving that every limit point is stationary. It also verifies that the Gauss-Jacobi scheme satisfies the inexact Jacobi framework's convergence conditions.

  • Descent and error control: The descent analysis bounds the error terms T^k and establishes a summability condition needed for convergence.Assumption (iv) is used to bound T^k, after which γ^k → 0 yields a positive descent constant for sufficiently large k.
  • Descent and error control: Coercivity prevents the objective sequence from diverging to −∞, so the descent argument implies convergence to a finite value.The proof first obtains an alternative between divergence to −∞ and convergence, then excludes divergence using the lower bound on V.
  • Stationarity of limit points: A contradiction argument shows that the residual bx(x^k) − x^k converges to zero.If the residual stayed bounded away from zero along an infinite subsequence, the descent inequalities would contradict convergence of V(x^k).
  • Stationarity of limit points: Every limit point is stationary because residual convergence and continuity give bx(x̄) = x̄, after which Proposition 8(b) applies.Boundedness of {x^k}, obtained from coercivity and convergence of V(x^k), guarantees at least one limit point.
  • Application to Algorithm 2: If block updates are eventually exact, global Lipschitz continuity of G is unnecessary because the associated error terms vanish.Under eventual exact computation, the term involving L_G disappears and all T^k are zero.
  • Application to Algorithm 2: Algorithm 2 is proved to be an inexact Jacobi instance by verifying its block-update errors satisfy the convergence conditions of Theorem 1.The proof bounds the update residuals using the algorithm's error rule, Proposition 8, and bounded gradients.
Loading 1402.5521v5…