Non-convex optimization for machine learning

DOI10.1561/2200000058zbMATH Open1388.68251arXiv1712.07897OpenAlexW2772283936MaRDI QIDQ4643371FDOQ4643371

Authors: Prateek Jain, Purushottam Kar 

Publication date: 24 May 2018

Published in: Foundations and Trends® in Machine Learning (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1712.07897

Recommendations

• Non-convex projected gradient descent for generalized low-rank tensor regression
• Optimization Landscape of Neural Networks
• Modern nonconvex nondifferentiable optimization
• On the optimization landscape of tensor decompositions
• On Nonconvex Optimization for Machine Learning

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Approximation methods and heuristics in mathematical programming (90C59) Nonconvex programming, global optimization (90C26)

Cited In (54)

• Exterior-point optimization for sparse and low-rank optimization
• Robust singular value decomposition with application to video surveillance background modelling
• Certified multifidelity zeroth-order optimization
• State space emulation and annealed sequential Monte Carlo for high dimensional optimization
• Measuring the local non-convexity of real algebraic curves
• Title not available (Why is that?)
• Nonlinear optimization and support vector machines
• Nonlinear optimization and support vector machines
• Provably training overparameterized neural network classifiers with non-convex constraints
• On fluorophore imaging by nonlinear diffusion model with dynamical iterative scheme
• A deep energy method for finite deformation hyperelasticity
• Title not available (Why is that?)
• Optimization in machine learning: a distribution-space approach
• High-dimensional low-rank tensor autoregressive time series modeling
• An integrated design method for active fault diagnosis and control
• A unified Douglas-Rachford algorithm for generalized DC programming
• Finding the global optimum of a class of quartic minimization problem
• Machine learning algorithms of relaxation subgradient method with space extension
• A combined dictionary learning and TV model for image restoration with convergence analysis
• First-order methods for convex optimization
• Proximal ADMM for nonconvex and nonsmooth optimization
• Nested alternating minimization with FISTA for non-convex and non-smooth optimization problems
• Extrapolated plug-and-play three-operator splitting methods for nonconvex optimization with applications to image restoration
• Bilevel Methods for Image Reconstruction
• Exact Recovery of Multichannel Sparse Blind Deconvolution via Gradient Descent
• Sharp global convergence guarantees for iterative nonconvex optimization with random data
• A quasi-Newton approach to nonsmooth convex optimization problems in machine learning
• Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems
• Sublinear optimization for machine learning
• Orientation estimation of cryo-EM images using projected gradient descent method
• Learning Enabled Constrained Black-Box Optimization
• A Finite Time Analysis of Temporal Difference Learning with Linear Function Approximation
• CoolPINNs: a physics-informed neural network modeling of active cooling in vascular systems
• Stable and robust LQR design via scenario approach
• Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals
• Nonsmooth rank-one matrix factorization landscape
• The exact worst-case convergence rate of the gradient method with fixed step lengths for \(L\)-smooth functions
• A backward SDE method for uncertainty quantification in deep learning
• Assessing Monotonicity: An Approach Based on Transformed Order Statistics
• Zeroth-order nonconvex stochastic optimization: handling constraints, high dimensionality, and saddle points
• Recent Theoretical Advances in Non-Convex Optimization
• A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Points
• Optimal control under nonconvexity: A generalized Hamiltonian approach
• Graphmax for text generation
• A Nonlinear Matrix Decomposition for Mining the Zeros of Sparse Data
• Parametric deep energy approach for elasticity accounting for strain gradient effects
• On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint
• An inertial proximal alternating direction method of multipliers for nonconvex optimization
• Joint learning of linear time-invariant dynamical systems
• Low-rank, Orthogonally Decomposable Tensor Regression With Application to Visual Stimulus Decoding of fMRI Data
• A unified analysis of stochastic gradient‐free Frank–Wolfe methods
• Tail probability estimates of continuous-time simulated annealing processes
• Systems of Bounded Rational Agents with Information-Theoretic Constraints
• A Bayesian perspective of statistical machine learning for big data

This page was built for publication: Non-convex optimization for machine learning

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