Proximal distance algorithms: theory and practice

MaRDI QIDQ5381120zbMATH OpenFDO

Authors Kevin L. Keys, Hua Zhou, Kenneth Lange

Publication date 7 June 2019

Full work available at URL https://arxiv.org/abs/1604.05694, http://jmlr.csail.mit.edu/papers/v20/17-687.html

zbMATH Keywords

EM algorithmprojectionconstrained optimizationmajorizationproximal operator

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Numerical mathematical programming methods (65K05) Nonlinear programming (90C30)

Abstract: Proximal distance algorithms combine the classical penalty method of constrained minimization with distance majorization. If $$ is the loss function, and $C$ is the constraint set in a constrained minimization problem, then the proximal distance principle mandates minimizing the penalized loss $$ and following the solution $$ to its limit as $ho$ tends to $infty$. At each iteration the squared Euclidean distance $$ is majorized by the spherical quadratic $$, where $$ denotes the projection of the current iterate $$ onto $C$. The minimum of the surrogate function $$ is given by the proximal map $$. The next iterate $$ automatically decreases the original penalized loss for fixed $ho$. Since many explicit projections and proximal maps are known, it is straightforward to derive and implement novel optimization algorithms in this setting. These algorithms can take hundreds if not thousands of iterations to converge, but the stereotyped nature of each iteration makes proximal distance algorithms competitive with traditional algorithms. For convex problems, we prove global convergence. Our numerical examples include a) linear programming, b) nonnegative quadratic programming, c) projection to the closest kinship matrix, d) projection onto a second-order cone constraint, e) calculation of Horn's copositive matrix index, f) linear complementarity programming, and g) sparse principal components analysis. The proximal distance algorithm in each case is competitive or superior in speed to traditional methods.

Recommendations

• The proximal distance algorithm
• Distance majorization and its applications
• Proximal algorithms in statistics and machine learning
• Common fixed points of an infinite family of nonexpansive mappings in uniformly convex metric spaces
• Rescaling and stepsize selection in proximal methods using separable generalized distances

Cites work

• scientific article; zbMATH DE number 3973706 (Why is no real title available?)
• scientific article; zbMATH DE number 192986 (Why is no real title available?)
• scientific article; zbMATH DE number 1201576 (Why is no real title available?)
• scientific article; zbMATH DE number 734901 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 3201668 (Why is no real title available?)
• scientific article; zbMATH DE number 3192366 (Why is no real title available?)
• scientific article; zbMATH DE number 3061616 (Why is no real title available?)
• scientific article; zbMATH DE number 3108780 (Why is no real title available?)
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• A Numerically Stable Solver for Positive Semidefinite Quadratic Programs Based on Nonnegative Least Squares
• A Singular Value Thresholding Algorithm for Matrix Completion
• A differential equation for modeling Nesterov's accelerated gradient method: theory and insights
• A variational approach to copositive matrices
• Accelerated gradient methods for nonconvex nonlinear and stochastic programming
• An Iteration Formula for Fredholm Integral Equations of the First Kind
• An algorithmic approach to nonlinear analysis and optimization
• Applications of second-order cone programming
• Closest point search in lattices
• Composite difference-MAX programs for modern statistical estimation problems
• Computing in operations research using Julia
• Computing the nearest correlation matrix--a problem from finance
• Conic optimization via operator splitting and homogeneous self-dual embedding
• Constructing copositive matrices from interior matrices
• Convergence analysis of difference-of-convex algorithm with subanalytic data
• Convex analysis and monotone operator theory in Hilbert spaces
• Convex analysis and nonlinear optimization. Theory and examples.
• Convex functions and their applications. A contemporary approach
• Discussion
• Distance majorization and its applications
• Generalized power method for sparse principal component analysis
• JuMP: a modeling language for mathematical optimization
• LSMR: An Iterative Algorithm for Sparse Least-Squares Problems
• LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
• Line Search Filter Methods for Nonlinear Programming: Motivation and Global Convergence
• Linear and nonlinear programming.
• MM optimization algorithms
• Majorization as a tool for optimizing a class of matrix functions
• Matrix completion via an alternating direction method
• Mean Value Methods in Iteration
• Minimization of a class of matrix trace functions by means of refined majorization
• On Fréchet subdifferentials
• On consistency and sparsity for principal components analysis in high dimensions
• On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
• Optimal detection of sparse principal components in high dimension
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Proximal splitting methods in signal processing
• SPADES and mixture models
• Second-order cone programming
• Semianalytic and subanalytic sets
• Sparse inverse covariance estimation with the graphical lasso
• Sparse principal component analysis via regularized low rank matrix approximation
• Spectral regularization algorithms for learning large incomplete matrices
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• The convergence rate of the penalty function method
• The proximal distance algorithm
• The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
• Variational methods for the solution of problems of equilibrium and vibrations

Cited in

(21)

• Sparse vertex discriminant analysis: variable selection for biomedical classification applications
• Proximal MCMC for Bayesian Inference of Constrained and Regularized Estimation
• The proximal distance algorithm
• Algorithms for computing the optimal transitive approximation of a proximity relation
• Calculation of the Prokhorov distance by optimal quantization and maximum flow
• The Emperor Has No Caps! A Comparison of DCJ and Algebraic Distances
• Dimension Reduction for Integrative Survival Analysis
• Understanding non-negative matrix factorization in the framework of Bregman divergence
• Perspective functions: proximal calculus and applications in high-dimensional statistics
• Algorithms for Sparse Support Vector Machines
• Random minibatch subgradient algorithms for convex problems with functional constraints
• Discussion: ``A brief survey of modern optimization for statisticians
• Online Kernel-Based Mode Learning
• A Sharper Computational Tool for Regression
• A Legacy of EM Algorithms
• Finding best approximation pairs for two intersections of closed convex sets
• The stochastic proximal distance algorithm
• A proximal algorithm with quasi distance. Application to habit's formation
• A penalized method of alternating projections for weighted low-rank Hankel matrix optimization
• Distance majorization and its applications
• High-performance statistical computing in the computing environments of the 2020s

Describes a project that uses

Uses Software

• CRAIG
• GitHub
• proxdist
• PMA
• JuMP
• UNLocBoX
• Ipopt
• LSQR

This page was built for publication: Proximal distance algorithms: theory and practice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5381120)