PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-convex Optimization for Machine Learning

Prateek Jain, Purushottam Kar

arXiv:1712.07897v1stat.MLcs.LGmath.OC

TL;DR

Machine-learning models often require non-convex objectives or structural constraints, but the resulting problems can be difficult to solve. This monograph develops and analyzes direct non-convex optimization methods, including projected gradient descent and alternating minimization, and presents convergence guarantees and applications while noting limits on coverage and scope.

  • Problem

    Non-convex objectives and constraints better capture many learning problems but can be NP-hard to solve, while convergence and recovery properties of practical heuristics remain insufficiently understood.

  • Method

    The monograph develops analytical tools for direct non-convex methods, including projected gradient descent, alternating minimization, low-rank projection, and related algorithms.

  • Results

    The monograph presents convergence guarantees for generalized projected gradient descent and alternating minimization under stated regularity and structural assumptions.

  • Takeaways & Limitations

    Structured non-convex problems can admit scalable direct solvers when their additional task structure is carefully analyzed and exploited.

  • Takeaways & Limitations

    The discussion focuses on tensor decomposition itself rather than detailing reductions from machine-learning applications to tensor decomposition.

Abstract

from arXiv · show

A vast majority of machine learning algorithms train their models and perform inference by solving optimization problems. In order to capture the learning and prediction problems accurately, structural constraints such as sparsity or low rank are frequently imposed or else the objective itself is designed to be a non-convex function. This is especially true of algorithms that operate in high-dimensional spaces or that train non-linear models such as tensor models and deep networks. The freedom to express the learning problem as a non-convex optimization problem gives immense modeling power to the algorithm designer, but often such problems are NP-hard to solve. A popular workaround to this has been to relax non-convex problems to convex ones and use traditional methods to solve the (convex) relaxed optimization problems. However this approach may be lossy and nevertheless presents significant challenges for large scale optimization. On the other hand, direct approaches to non-convex optimization have met with resounding success in several domains and remain the methods of choice for the practitioner, as they frequently outperform relaxation-based techniques - popular heuristics include projected gradient descent and alternating minimization. However, these are often poorly understood in terms of their convergence and other properties. This monograph presents a selection of recent advances that bridge a long-standing gap in our understanding of these heuristics. The monograph will lead the reader through several widely used non-convex optimization techniques, as well as applications thereof. The goal of this monograph is to both, introduce the rich literature in this area, as well as equip the reader with the tools and techniques needed to analyze these simple procedures for non-convex problems.

Part I: Introduction and Basic Tools

Part I introduces non-convex optimization through applications and supplies foundational convex-optimization tools for readers who need them.

  • Part I: Introduction and Basic Tools: Section 1 motivates non-convex optimization by discussing applications and clarifying the monograph’s scope.
  • Part I: Introduction and Basic Tools: Section 2 provides notation and basic convex-optimization concepts that can be skipped or consulted as needed by experienced readers.
  • Part I: Introduction and Basic Tools: Figure 1 recommends reading Sections 5 after 4, while allowing readers to proceed from Section 3 directly to Section 7.

Part II: Non-convex Optimization Primitives

Part II develops non-convex optimization primitives and applies them to sparse recovery, low-rank recovery, robust regression, phase retrieval, and related learning problems.

  • Part II: Non-convex Optimization Primitives: The monograph presents projected gradient descent, alternating minimization, EM, and stochastic non-convex optimization as central algorithmic primitives.
  • Applications: Part III applies these techniques to sparse recovery, low-rank matrix recovery, robust regression, and phase retrieval.
  • Sparse Recovery: Sparse recovery examines conditions enabling polynomial-time recovery and provably optimal solutions via non-convex projected gradient descent.
  • Low-rank Matrix Recovery: Low-rank matrix recovery generalizes sparse linear regression and emphasizes low-rank matrix completion using projected gradient descent and alternating minimization.
  • Robust Regression: Robust regression studies algorithms resistant to adversarial data corruption and their applications to robust face reconstruction.
  • Scope and Organization: The monograph balances state-of-the-art coverage with accessibility, while acknowledging that rapid developments make comprehensive summarization difficult.

Introduction

Machine-learning problems often require high-dimensional structural constraints or non-convex objectives, which improve modeling fidelity but can be computationally intractable. This monograph introduces tools for analyzing non-convex methods that can exploit favorable structure to achieve scalable, sometimes optimal solutions.

  • Motivation: High-dimensional learning applications require structural constraints to regularize models and prevent ill-posed inference problems.Examples include document classification, recommendation, signal processing, and bio-informatics.
  • Motivation: Non-convex objectives or constraints improve modeling flexibility but can make optimization NP-hard, including for approximate solutions.Deep networks, tensor decompositions, sparsity, and low-rank structure are representative cases.
  • Examples of Non-Convex Optimization Problems: Sparse recovery discards irrelevant covariates and can work with n ≥s log p observations rather than n ≥p, despite its non-convex constraint and NP-hardness.The objective may remain convex while the sparsity constraint is non-convex.
  • Examples of Non-Convex Optimization Problems: Low-rank matrix formulations use non-convex rank constraints, while factorization A = UV⊤ provides an alternate representation with latent user and item vectors.These vectors can support interpretation of user behavior and item popularity, as well as content-based recommendation.
  • Non-Convex Optimization Approach: Under suitable problem structure, direct non-convex methods can avoid general intractability, attain provably optimal solutions, and often scale better than convex relaxations.The monograph presents algorithmic and analytic tools for designing and analyzing these methods, while restricting breadth and depth across topics.

Mathematical Tools

This section develops convex-analysis concepts and projection tools that support the analysis of optimization algorithms, then derives convergence guarantees for projected gradient descent in convex settings.

  • Convex Analysis: Convex sets contain every line segment between two members, whereas a single excluded convex combination makes a set non-convex.Convex sets therefore cannot have inward bulges.
  • Convex Analysis: Convex functions lie above their tangent planes, while strong convexity and strong smoothness impose quadratic lower and upper growth bounds.The parameters α and β determine the respective growth limits.
  • Convex Projections: Projection onto a closed set selects a closest point; convex projections additionally satisfy first-order geometric properties useful for algorithm analysis.Projection Property-O holds for arbitrary sets, while Properties-I and II can fail for non-convex sets.
  • Projected Gradient Descent: Projected gradient descent combines gradient updates with projection onto the constraint set and admits closed-form projections for common balls and soft thresholding for the unit L1 ball.For the unit L2 ball, projection is normalization; for the unit L1 ball, it is soft thresholding.
  • Convergence with Bounded Gradient Convex Functions: For convex objectives with bounded gradients, PGD's average iterate approaches the optimum, and diminishing progress indicates convergence to a global optimum.The average-iterate result supports selecting an averaged iterate, with Jensen's inequality requiring convexity.
  • Strongly Convex and Smooth Objectives: For objectives satisfying strong convexity and strong smoothness, the final PGD iterate converges and achieves an accelerated convergence rate compared with general convex functions.This permits using the final iterate rather than an averaged or best iterate.

Non-Convex Projected Gradient Descent

Non-convex projected gradient descent becomes analyzable when non-convex constraints admit efficient projections and objectives satisfy suitable restricted properties on the constraint set. Under these conditions, generalized PGD can converge efficiently despite the general hardness of non-convex optimization.

  • Motivation: Non-convex problems can be NP-hard, and standard convex optimization techniques do not generally extend to them.This motivates exploiting additional structure rather than expecting universal algorithms.
  • Generalized Projected Gradient Descent: For structured objectives and constraint sets, gPGD converges to the global optimum in polynomial time with a linear convergence rate.The convergence theorem assumes α-RSC and β-RSS over the constraint set, with β/α < 2 and step length η = 1/β.
  • Scope: The section prioritizes generality and accessible analysis, while more refined, problem-specific results are deferred to later application sections.The authors explicitly identify fineness of results as the cost of this broad exposition.
  • Projection onto Non-Convex Sets: Projected gradient descent on non-convex sets requires solving a projection problem that may itself be NP-hard.For well-structured sets, however, projections can still be computed efficiently.
  • Projection onto Non-Convex Sets: Projection onto s-sparse vectors is obtained by retaining the s coordinates of largest magnitude and setting the rest to zero.The projection follows by sorting coordinates by magnitude and preserving the top s entries.
  • Projection onto Non-Convex Sets: Low-rank projection is computed by singular value decomposition, retaining the top r singular values and corresponding singular vectors.The Eckart-Young-Mirsky theorem establishes this projection for the Frobenius norm and, more generally, unitarily invariant norms.
  • Generalized Projected Gradient Descent: Efficient projection does not guarantee the favorable projection properties used in convex PGD convergence proofs.The non-convex projections discussed in the section fail those properties, requiring more careful analysis.
  • Restricted Convexity: Restricted convexity requires objective properties only on the constraint set, allowing non-convex functions to satisfy restricted strong convexity and smoothness there.Such RSC/RSS properties occur in practical non-convex optimization settings.

Alternating Minimization

Alternating minimization decomposes multivariable optimization into successive marginal problems, making it useful when joint convexity is absent but coordinate-wise structure remains tractable. Under bounded sublevel sets and suitable marginal curvature and bistability conditions, generalized alternating minimization admits rapid convergence guarantees.

  • Overview: Alternating minimization is a general primitive underlying methods such as Lloyd’s k-means algorithm and the EM algorithm.It is applied to optimization problems involving two or more groups of variables.
  • Marginal Convexity: Many applications lack joint convexity even when optimization over individual variables remains tractable.Matrix completion is cited as an example whose objective is marginally convex in both variables but not jointly convex.
  • Marginal Convexity: Marginal convexity requires convexity in one variable for every fixed value of the other variable, and the analogous condition for the second variable.Joint convexity implies marginal convexity, but the converse does not hold.
  • Generalized Alternating Minimization: Generalized alternating minimization iteratively optimizes separate variable blocks and returns a point with near-optimal objective value.Its practical success comes from replacing one large problem with several intermediate marginal problems that are often easy or closed-form to solve.
  • Convex Convergence Guarantee: With joint convexity, marginal smoothness, a bounded initial sublevel set, and suitable initialization, gAM has a convergence guarantee.The bounded sublevel set keeps the iterates from diverging because objective values are monotone.
  • Bistability: Bistability links local coordinate-wise optimization behavior to global optimality under marginal convexity.For marginally convex objectives, a point is bistable exactly when its gradient is zero.
  • Non-Convex Convergence Guarantee: For possibly non-convex objectives satisfying MSC, MSS, and robust bistability within the initial sublevel set, gAM can converge rapidly.These structural properties need only hold within that sublevel set, not globally.
  • Non-Convex Convergence Guarantee: The convergence factor worsens as the condition number κ and robustness constant C increase, with η0 approaching 1 and slowing the procedure.Small κ and C correspond to faster convergence in the stated rate.

The EM Algorithm

The EM algorithm estimates parameters in latent-variable models by optimizing a tractable Q-function that improves likelihood, with guarantees ranging from monotonicity to local linear convergence under suitable conditions.

  • EM underlies learning algorithms for Gaussian mixture models, hidden Markov models, and mixed regression, while relating closely to k-means clustering.
  • The likelihood-based framework seeks a parameter that best explains observed samples from a known parametric family, but direct likelihood optimization can be expensive.
  • The Q-function serves as an efficiently optimizable lower-bounding proxy whose maximization improves the data likelihood and can avoid inaccessible marginal likelihood calculations.
  • EM reduces latent-variable computation from |Z|^n marginal-likelihood terms to n·|Z| terms, supporting scalability through soft assignments.
  • EM never decreases population or sample likelihood under the stated update schemes, although monotonicity alone does not guarantee recovery of the true parameter.
  • With suitable local strong concavity and smoothness, initialization within a neighborhood of θ∗ yields contractive updates and linear convergence when β < α.

Stochastic Optimization Techniques

Non-convex objectives make global optimization generally NP-hard, but structural properties such as strict saddles can let simple gradient-based methods reach local optima. The section develops noisy and projected noisy gradient descent guarantees and applies them to tensor decomposition.

  • Motivation: Global optimization of non-convex objectives is NP-hard in general, motivating guarantees for finding local minima instead.Saddle points can stall gradient descent without meaningfully optimizing the objective.
  • Strict-saddle structure: Strict-saddle structure supplies steep descent directions that enable simple optimization methods to escape saddle points and achieve local optimality.The section presents this as the mechanism behind provable guarantees.
  • Noisy gradient descent: For f(x, y) = x2 −y2, noisy gradient descent escapes the origin with high probability and drives the objective toward −∞ when η < 1.The iterates satisfy x_t → 0 while |y_t| → ∞.
  • Projected noisy gradient descent: PNGD extends the local-convergence guarantee to constrained problems whose constraint set is a smooth manifold.The stated iteration dependence is similar to NGD.
  • Tensor decomposition: Orthogonal tensor decomposition satisfies the required SCSa structure, and its only local minima are ±u_i, enabling component recovery through PNGD and deflation.After recovering one component, the procedure subtracts its rank-one tensor contribution and repeats.

Sparse Recovery

Sparse recovery applies non-convex optimization to high-dimensional problems where the desired model is sparse. The section develops recovery guarantees for IHT under suitable design properties and reviews extensions and comparisons with convex methods.

  • Motivation: Sparse recovery targets practical problems where high-dimensional models contain relatively few active components.Applications include sparse regression and gene expression analysis.
  • Projected Gradient Descent: IHT is simple and fast, but its recovery guarantees depend on special structure in the design matrix.The sparse optimization problem is generally NP-hard, while structured design matrices can permit efficient recovery.
  • Extensions: The section’s tailored IHT analysis achieves weaker design requirements than a direct generic projected-gradient analysis.It requires only η = 1 rather than a prescribed η = 1/(1 + δs), and also discusses noisy extensions and alternative Lq formulations.
  • Design Properties: Restricted isometry provides a sufficient design condition under which IHT guarantees universal sparse recovery.The section also places RSC-RSS, REP, and NSP in a hierarchy of design properties.
  • RIP Constructions: n ≥ Ω(...) measurements suffice for certain random matrix distributions to satisfy RIP with high probability.The cited result applies for fixed sparsity order k < p/2 and failure probability exponentially small in n.
  • IHT Guarantees: Theorem 7.2 guarantees IHT recovery when δ3s < 1/2, using step length η = 1 and projection sparsity k = s.The guarantee applies to any s-sparse vector in the noiseless model y = Xw∗.

Low-rank Matrix Recovery

Low-rank matrix recovery generalizes sparse recovery to matrices and arises in system identification and recommendation systems. The section motivates affine rank minimization through low-order modeling and sparse observations.

  • Overview: Low-rank matrix recovery is introduced as a matrix analogue of sparse recovery requiring specialized algorithmic and analytic tools.The discussion proceeds from general recovery to low-rank matrix completion.
  • Collaborative Filtering: Recommendation systems observe only a small fraction of user-item preference scores and seek to recover the remaining entries.The observed count satisfies k ≪ m · n, so the recovery problem is not initially well posed or uniquely solvable.
  • Collaborative Filtering: Assuming a low-rank preference matrix represents user-item scores through inner products of r-dimensional user and item vectors.This assumption converts the completion task into an optimization problem over observed entries.
  • LTI Systems: Linear time-invariant system identification fits a low-order model by recovering a vector whose Hankel matrix has low rank.Gaussian impulses and observed outputs produce the measurements used for fitting.
  • Computational Challenge: The rank-minimization formulation is non-convex and NP-hard, motivating the specialized methods developed in the remainder of the section.The same computational difficulty appears in matrix completion.
  • Affine Rank Minimization: Affine rank minimization unifies the LTI and collaborative-filtering examples by recovering a low-rank matrix from affine measurements.Collaborative filtering corresponds to affine transformations that select individual matrix entries.

F , (LRMC)

The low-rank matrix completion section develops matrix design conditions and the Singular Value Projection method. Matrix RIP supports affine recovery guarantees, while incoherence is needed to make completion identifiable.

  • Matrix Design Properties: Matrix RIP generalizes restricted isometry by requiring affine measurements to preserve the geometry of all low-rank matrices up to a specified rank.It rules out substantial distortion of low-rank matrices.
  • Matrix Design Properties: Random measurement models satisfy matrix RIP with k = O(nr) affine measurements in settings where the measurement map is controllable.This result covers examples such as image compression and LTI systems.
  • Matrix Completion: Matrix completion requires a distinct incoherence property because low rank alone does not ensure unique recovery from randomly observed entries.A low-rank matrix concentrated on a few locations may never be sampled.
  • Matrix Completion: Incoherence excludes low-rank matrices that are also sparse, making a small random set of observations sufficient for unique completion.The property bounds row norms of the left and right singular matrices.
  • Singular Value Projection: SVP applies projected gradient descent by projecting iterates onto the low-rank set through a truncated singular value decomposition.The method is designed for general affine rank minimization problems.
  • SVP Guarantees: Under matrix RIP, SVP offers linear convergence to the optimum for low-rank matrix recovery.The noiseless proof parallels IHT conceptually but analyzes sparsity in the singular-value domain.
  • SVP Guarantees: If δ2r < 1/3, SVP contracts the objective error by the factor 2δ2r/(1 − δ2r) under the theorem’s step-length and target-rank settings.The theorem uses η = 1/(1 + δ2r) and target rank q = r.

F . (LRMC*)

The AM-MC method solves low-rank matrix completion by alternating least-squares updates over factor matrices. Its analysis combines incoherent initialization, fresh sampling, and preservation of incoherence to establish linear convergence under sufficient sampling.

  • AM-MC Method: AM-MC factorizes the matrix so that fixing either factor reduces the update to an efficient least-squares problem.This alternating-minimization approach is widely used in collaborative filtering.
  • Assumptions: The analysis assumes rank-one incoherent matrices observed through independent Bernoulli sampling.The sampling probability is p, and incoherence bounds the magnitudes of the singular-vector entries.
  • Analysis Setup: Fresh sample sets let the analysis treat the current iterate as fixed when applying concentration bounds at each alternation step.Available samples can be randomly partitioned into groups for successive iterations.
  • Convergence: Sufficient sampling preserves 2µ-incoherence across iterates and makes successive factor estimates increasingly close to the optimum.The convergence proof relies on initialization, preservation of incoherence, and decreasing angular distance.
  • Limitation: SVP convergence is difficult to establish for matrix completion because entry-sampling affine maps do not readily satisfy matrix RIP.This limits direct transfer of the affine-recovery analysis to LRMC.

Robust Linear Regression

Robust linear regression estimates a linear model despite adversarially corrupted responses, without manually identifying corrupted observations. The monograph analyzes alternating-minimization and gradient-based methods that recover the model under sparse-corruption conditions and can scale efficiently.

  • Problem setting: Robust linear regression fits a model when responses contain adversarial outliers or malicious corruptions.The setting includes applications in signal processing, finance, machine learning, and data analytics.
  • Applications: Face recognition can be formulated as reconstructing a new image from database images, but occlusions corrupt features and can cause false alarms.The corruption locations need not be identified manually.
  • Algorithms: AM-RR applies generalized alternating minimization to robust regression and provides scalable solutions without requiring precise initialization.Its convergence guarantee assumes structural conditions involving αn−k and βk.
  • Guarantees: For Gaussian design matrices, AM-RR tolerates up to n/70 adversarial corruptions, including corruptions arbitrary in location and magnitude.This guarantee does not require specific initialization.
  • Algorithms: Gradient-based updates preserve linear convergence while making both model and active-set updates near-linear time instead of super-quadratic per alternation.The gradient version is often an order of magnitude faster in practice than fully corrective AM-RR.

ORIGINAL DISTORTED OLS AM-RR

Robust regression methods are compared through theoretical limits, computational trade-offs, and empirical face-reconstruction performance. AM-RR improves scalability over relaxation-based and exponential-time alternatives, while accepting a lower stated breakdown point than least median of squares.

  • Empirical comparison: AM-RR achieves far superior face reconstruction to ordinary least squares and correctly identifies occlusion locations.The comparison uses two face images with different applied occlusions.
  • Theoretical limits: Recovery is impossible when a fully adaptive adversary corrupts at least half the responses.The adversary can make two different models indistinguishable.
  • Theoretical guarantees: The SSC property rules out two distinct model vectors agreeing on every subset of at most k data points.This supports identifiability under sparse corruption.
  • Related methods: Least median of squares can achieve a breakdown point as high as n/2 − p but has exponential time complexity.Its computational cost is contrasted with the near-linear gradient version of AM-RR.
  • Related methods: AM-RR’s gradient version runs in near-linear time, whereas least median of squares requires time exponential in p.The comparison highlights a robustness–runtime trade-off.

Phase Retrieval

Phase retrieval seeks to recover a signal from magnitudes of linear measurements whose phases are unavailable. The section exploits random measurement structure to analyze alternating-minimization and gradient-descent methods, with guarantees strongest for Gaussian measurements.

  • Problem formulation: Phase retrieval recovers a complex signal from magnitudes of complex linear measurements when measurement phases are not observed.Over the reals, the task becomes solving quadratic equations.
  • Applications: Applications include X-ray crystallography, transmission electron microscopy, and coherent diffraction imaging, where measurement processes lose or encode signal phase indirectly.These techniques use diffraction or electron measurements to infer internal structure.
  • Problem formulation: Randomly sampled measurement vectors make efficient recovery possible despite the general intractability of quadratic systems.The resulting algorithms can require only a small number of measurements.
  • Scope: The analysis focuses on Gaussian measurements because recovery guarantees for random Fourier measurements remain unavailable, despite their relevance to crystallography.Coded diffraction measurements are treated as a more practical but more complicated exception.
  • Initialization: Spectral initialization places the starting estimate within a small constant distance of the optimal signal.This initialization supports the subsequent convergence analysis.
  • Convergence guarantees: For Gaussian measurements, GSAM reaches an ϵ-optimal estimate in roughly log(1/ϵ) iterations, while Wirtinger Flow uses cheaper gradient steps with linear convergence.Coded diffraction patterns receive a similar guarantee with a slightly inferior rate, requiring a multiplicative factor of p more steps than Gaussian WF.
Loading 1712.07897v1…