Non-convex Optimization for Machine Learning

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.

The official publication is available from now publishers via http://dx.doi.org/10.1561/2200000058

References in corpus (22)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• The Loss Surfaces of Multilayer Networks
• Non-convex Optimization for Machine Learning
• Guaranteed Matrix Completion via Non-convex Factorization
• Convergence Analysis of Two-layer Neural Networks with ReLU Activation
• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• How to Escape Saddle Points Efficiently
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Recovery Guarantees for One-hidden-layer Neural Networks
• When Are Nonconvex Problems Not Scary?
• Exact Recovery of Sparsely-Used Dictionaries
• Robust Regression via Hard Thresholding
• New Algorithms for Learning Incoherent and Overcomplete Dictionaries
• Alternating Minimization for Mixed Linear Regression
• Universal Matrix Completion
• On Learning Discrete Graphical Models Using Greedy Methods
• Fast matrix completion without the condition number
• Orthogonal Matching Pursuit with Replacement
• Computational Limits for Matrix Completion
• Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
• Training Input-Output Recurrent Neural Networks through Spectral Methods
• Exact recoverability from dense corrupted observations via $L_1$ minimization

Cited by in corpus (46)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Non-convex Optimization for Machine Learning
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Sampling Can Be Faster Than Optimization
• Machine learning non-Markovian quantum dynamics
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Point-Cloud Deep Learning of Porous Media for Permeability Prediction
• Progress toward favorable landscapes in quantum combinatorial optimization
• Massive MIMO Hybrid Precoding for LEO Satellite Communications With Twin-Resolution Phase Shifters and Nonlinear Power Amplifiers
• SGD-Net: Efficient Model-Based Deep Learning with Theoretical Guarantees
• Bilevel methods for image reconstruction
• HePPCAT: Probabilistic PCA for Data with Heteroscedastic Noise
• Scalable Nonparametric Sampling from Multimodal Posteriors with the Posterior Bootstrap
• Stochastic noise can be helpful for variational quantum algorithms
• Quantum Dropout: On and Over the Hardness of Quantum Approximate Optimization Algorithm
• On Asymptotic Linear Convergence of Projected Gradient Descent for Constrained Least Squares
• Quantum Langevin Dynamics for Optimization
• Memorized Sparse Backpropagation
• Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
• Federated Optimization of Smooth Loss Functions
• Blind Super-resolution of Point Sources via Projected Gradient Descent
• Unveiling the Vulnerability of Private Fine-Tuning in Split-Based Frameworks for Large Language Models: A Bidirectionally Enhanced Attack
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• URLLC-Aware Proactive UAV Placement in Internet of Vehicles
• Efficient Learning of Decision-Making Models: A Penalty Block Coordinate Descent Algorithm for Data-Driven Inverse Optimization
• The exact worst-case convergence rate of the gradient method with fixed step lengths for L-smooth functions
• Measuring the local non-convexity of real algebraic curves
• Uniform Convergence of Gradients for Non-Convex Learning and Optimization
• A Projected Gradient Method for Opinion Optimization with Limited Changes of Susceptibility to Persuasion
• Rotation-Invariant Rapid TRISO-Fueled Pebble Identification Based on Feature Matching and Point Cloud Registration
• Data-informed Deep Optimization
• High-Dimensional Robust Mean Estimation via Gradient Descent
• Minimizing the negativity of quantum circuits in overcomplete quasiprobability representations
• On the Sample Complexity and Optimization Landscape for Quadratic Feasibility Problems
• Data-driven Computing in Elasticity via Chebyshev Approximation
• The Minimizer of the Sum of Two Strongly Convex Functions
• GPU Accelerated Batch Multi-Convex Trajectory Optimization for a Rectangular Holonomic Mobile Robot
• Analysis of the rSVDdpd Algorithm: A Robust Singular Value Decomposition Method using Density Power Divergence
• Automated Resonance Identification in Nuclear Data Evaluation
• rSVDdpd: A Robust Scalable Video Surveillance Background Modelling Algorithm
• Low Rank Regularization: A Review
• ${\ell }_p$-Norm Multiple Kernel One-Class Fisher Null-Space
• Certified Multi-Fidelity Zeroth-Order Optimization
• Transforming physics-informed machine learning to convex optimization
• Weighted Fisher Discriminant Analysis in the Input and Feature Spaces
• Det-CGD: Compressed Gradient Descent with Matrix Stepsizes for Non-Convex Optimization