PGD algorithm converges to local minima in nonconvex matrix completion.
problem Matrix completion with low-rank promotion using nonconvex penalties.
method Proximal gradient descent algorithm for nonconvex penalties.
result PGD algorithm converges to restricted strictly local minimizers with eventually linear rate.
Stochastic Gradient Descent prefers minimizers with flat basins in nonconvex problems.
problem Understanding why SGD prefers minimizers with flat basins in nonconvex problems.
method Detailed analysis of a generic stochastic quadratic problem, deriving a deterministic mechanism.
result Derives a deterministic mechanism explaining why SGD prefers flat minimizers.
As surrogate functions of L0-norm, many nonconvex penalty functions have been proposed to enhance the sparse vector recovery. It is easy to extend these nonconvex penalty functions on singular values of a matrix to enhance low-rank matrix recovery. However, different from convex optimization, solving the nonconvex l…
New nonconvex methods improve SysID efficiency and accuracy.
problem Efficiently identify low-order linear systems from limited data.
method Proposes two nonconvex reformulations of Hankel-rank minimization for SysID.
result Nonconvex methods achieve lower statistical error rates and sample complexities.
Paper proposes a nonconvex approach for sparse reduced rank regression.
problem Sparse reduced rank regression model estimation problem.
method Formulated as a nonconvex optimization problem with alternating minimization method.
result Nonconvex function leads to better estimation accuracy and efficiency.
New algorithm finds global minima in smooth nonconvex problems.
problem Smooth nonconvex optimization problems with specific properties.
method Second-order trust-region algorithm converging efficiently to global minimizer.
result Proves convergence to a global minimizer without special initializations.
New algorithm for privacy-preserving nonconvex optimization.
problem Privacy-preserving nonconvex empirical risk minimization.
method Differentially private stochastic gradient descent algorithm.
result Achieves strong privacy guarantees efficiently with improved utility.
Introduces PPMM algorithm for nonconvex robust regression problems.
problem Nonconvex tuning-free robust regression problems.
method PPMM algorithm with inner subproblems solved by SSN-PPA.
result Converges to d-stationary point with KL property.
Analyzes alternating minimization for nonconvex sets in high-dimensional statistics.
problem Optimizing loss functions over nonconvex sets in high-dimensional statistics.
method Local concavity coefficients for nonconvex sets, alternating minimization, inexact algorithms.
result Reveals distinctions between alternating and non-alternating methods, provides convergence conditions.
New method helps nonconvex optimization algorithms avoid local minima.
problem Nonconvex optimization problems often get stuck in local minima.
method Run-and-Inspect Method: Adds inspection phase to existing algorithms.
result Approximate R-local minimizers are globally optimal under certain conditions.
Develops efficient method for nonconvex problems using Regula Falsi.
problem Nonconvex inverse problems with likelihood constraints.
method Regula Falsi root-finding techniques applied to level-set formulations.
result Proves extension of level-set methods to nonconvex problems.
Efficient algorithm solves sparse nonconvex regression problems.
problem Sparse nonconvex square-root-loss regression problems.
method Proximal majorization-minimization (PMM) algorithm with sparse semismooth Newton method.
result Converges to a d-stationary point with Kurdyka-Łojasiewicz property.
Parallel algorithm finds sparse solutions for nonconvex problems.
problem Nonconvex sparsity-regularized rank minimization.
method Parallel best-response algorithm with exact line search.
result Guaranteed convergence to a stationary point.
Paper analyzes SARAH for nonconvex optimization with mini-batches.
problem Solving nonconvex optimization problems with mini-batches.
method Stochastic Recursive Gradient Algorithm (SARAH) for nonconvex losses.
result Sublinear and linear convergence rates for different types of nonconvex functions.
Katyusha X adds momentum to SVRG for faster non-convex optimization.
problem Minimizing sum-of-nonconvex functions in machine learning.
method Adding momentum to SVRG method.
result Provable accelerated stochastic algorithm for sum-of-nonconvex functions.
Survey of tractable nonconvex problems using symmetry.
problem Nonlinear models with symmetries create complex, nonconvex objective landscapes.
method Analysis of geometric structure and symmetry roles.
result Efficient methods can find global minimizers due to symmetry.
New algorithm for nonconvex optimization on constrained Riemannian manifolds converges quickly.
problem Optimization on constrained Riemannian manifolds.
method Block majorization-minimization (BMM) for smooth nonconvex objectives with Riemannian constraints.
result Converges to stationary points within O(ε−2) iterations. New method improves signal reconstruction with nonconvex penalties and parameter control.
problem Reconstructing sparse signals with nonconvex penalties and nonconvexity control.
method Introduces nonconvex penalties (SCAD, MCP) with nonconvexity parameters and controls them to guide AMP trajectory.
result Achieves perfect reconstruction for relatively dense signals with small nonconvexity parameters.
SGD achieves a O(ε−4) bound for minimizing gradient norm of smooth functions.
problem Finding stationary points with SGD for gradient norm minimization.
method Stochastic Gradient Descent (SGD) for smooth, possibly nonconvex functions.
result The O(ε−4) bound for gradient norm minimization cannot be improved upon. Paper offers efficient methods for nonconvex functions.
problem Minimizing smooth quasar-convex functions.
method Near-optimal accelerated gradient descent method.
result Near-optimal number of function and gradient evaluations.
New algorithm finds approximate minimizers for noisy convex functions.
problem Minimizing convex functions with noisy approximations that are nonconvex.
method Combining simulated annealing with stochastic gradient Langevin dynamics.
result Polynomial time algorithm for finding approximate minimizers.
Paper proposes a new method for SP with covariates using PADR and ERM.
problem Stochastic programming with covariate information.
method Empirical risk minimization (ERM) with nonconvex piecewise affine decision rules (PADR).
result The method provides theoretical consistency and computational tractability for nonconvex SP problems.
A new method for robust PCA using nonconvex rank approximation.
problem Recovering a matrix of minimal rank in data mining and machine learning.
method Proposes a nonconvex rank approximation to the nuclear norm, solving the associated nonconvex minimization problem with an efficient algorithm.
result Our method outperforms current state-of-the-art algorithms in both accuracy and efficiency.
Paper develops algorithms for nonsmooth, nonconvex statistical learning problems.
problem Nonsmooth and nonconvex objectives in statistical learning.
method Bregman-surrogate algorithm framework, including local linear approximation, mirror descent, iterative thresholding, DC programming.
result Global convergence rates for nonconvex and nonsmooth objectives in high dimensions.
Paper analyzes nonconvex bandit problems with improved adaptive methods.
problem Continuous armed bandit problems for nonconvex cost functions.
method Simple and adaptive bin splitting methods.
result Adaptive method achieves locally minimax optimal expected cumulative regret.
New method reduces complexity for nonconvex optimization problems.
problem Minimizing composite functions with random or finite sum inner mappings.
method Stochastic composite gradient method with incremental variance reduction.
result Achieves complexity similar to best first-order methods for expected-value and finite-sum nonconvex functions.
Symmetric critical points lead to symmetry breaking in neural networks.
problem Understanding symmetry in critical points of invariant functions.
method Analyzing the symmetry of critical points and their neighbors in invariant nonconvex functions.
result Symmetric critical points in invariant nonconvex functions are generically followed by symmetry breaking adjacent points.
SGD approximates diffusion processes in nonconvex optimization.
problem Nonconvex optimization problems in machine learning.
method Diffusion approximation of SGD using master equation.
result SGD dynamics can escape local minima and saddle points.
Proposes BMME for optimizing nonsmooth nonconvex problems with block structure.
problem Optimizing nonsmooth nonconvex problems with block structure.
method Block Alternating Bregman Majorization Minimization with Extrapolation (BMME).
result Subsequential convergence to a first-order stationary point under mild assumptions, global convergence under stronger conditions.
New method solves subspace optimization problems efficiently.
problem Finding a k-dimensional subspace in high dimensions.
method Local linear convergence of gradient methods under strict complementarity.
result Gradient method converges linearly in high dimensions.
BMM algorithm improves convergence for nonconvex optimization problems.
problem Constrained nonsmooth nonconvex optimization problems.
method Block majorization-minimization with diminishing radius.
result Improved convergence rate for nonconvex optimization problems.
Optimizes nonconvex optimization by converting it to static regret minimization.
problem Nonconvex optimization challenges in machine learning.
method Black-box online-to-nonconvex conversion with static regret minimization oracles.
result Achieves optimal convergence rates for nonconvex optimization.
Gradient descent with preconditioning finds global optima in overparameterized nonconvex factorization.
problem Finding global optima in nonconvex Burer-Monteiro factorization.
method Preconditioned gradient descent for overparameterized nonconvex function minimization.
result Gradient descent with preconditioning achieves linear convergence in the overparameterized case.
Improved guarantees for nonconvex matrix factorization with rank overparameterization.
problem Minimizing nonconvex objective over low-rank matrices.
method Overparameterized Burer--Monteiro approach, leveraging smoothness and strong convexity.
result Local optimization globally converges to global optimum under certain rank conditions.
CD methods tackle nonconvex optimization with three terms, achieving critical points.
problem Minimizing nonconvex functions with specific structure.
method Developed randomized CD, randomly permuted CD, and accelerated CD methods.
result CD methods converge to critical points with sublinear complexity.
The paper explores nonconvex penalties using Bernstein functions for sparse estimation.
problem Sparse estimation in high-dimensional problems.
method Nonconvex penalties based on Bernstein functions, with coordinate descent and proximal alternating linearized minimization methods.
result The Bernstein penalty leads to effective sparse estimation and classification.
The paper shows linear convergence of a proximal gradient algorithm with extrapolation for nonconvex problems.
problem Minimizing the sum of a differentiable and a convex function under error bound condition.
method Proximal gradient algorithm with extrapolation, under error bound condition.
result The sequence generated converges R-linearly to a stationary point of the problem.
New method improves image and signal processing with nonconvex rank surrogates and dual momentum.
problem Optimizing nonconvex rank minimization problems in image processing.
method Proposes a novel nonconvex rank surrogate, uses ADMM with dual momentum trick.
result Effective in image and signal processing applications, outperforming state-of-the-art methods.
Unified analysis of Langevin dynamics for nonconvex optimization with improved convergence rates.
problem Global convergence of Langevin dynamics based algorithms for nonconvex optimization.
method Unified framework analyzing numerical approximations to Langevin dynamics.
result Improved convergence rates for gradient Langevin dynamics and stochastic gradient Langevin dynamics.
Study optimization landscapes for overcomplete representations, showing benign geometric structures.
problem Optimizing overcomplete representations in high-dimensional data analysis.
method Formulate as ℓ4-norm optimization problems with spherical constraint, analyze geometric properties. result Nonconvex objectives have benign geometric structures, ensuring local search algorithms find target solutions.
Paper analyzes ADMM convergence for nonconvex Gaussian phase retrieval.
problem Nonconvex optimization in Gaussian phase retrieval.
method Block coordinate descent as ADMM with dual variable fixed.
result Block coordinate descent converges linearly to global minimizer.
TiAda adapts adaptive gradient methods for nonconvex minimax optimization.
problem Nonconvex minimax optimization challenges in achieving convergence.
method TiAda is a time-scale adaptive GDA algorithm for nonconvex minimax optimization.
result TiAda achieves near-optimal complexities in deterministic and stochastic settings.
CD converges linearly for MCP/SCAD penalized least squares.
problem Recovering sparse signals from data.
method Coordinate descent for MCP/SCAD penalized least squares.
result CD converges linearly to solutions of MCP/SCAD penalized least squares.
Riemannian gradient descent helps escape saddle points on curved spaces.
problem Minimizing nonconvex functions on curved spaces (Riemannian manifolds).
method Perturbed Riemannian gradient descent algorithm.
result Converges to second-order stationary points, matching unconstrained smooth minimization rates.
New ancient and eternal solutions found for mean curvature flow from minimal surfaces.
problem Finding new examples of mean curvature flow solutions.
method Constructing embedded ancient and eternal solutions related to unstable minimal hypersurfaces.
result Found nonconvex, non-soliton solutions to mean curvature flow.
New ADMM algorithm tackles nonconvex constraints from GANs for faster learning.
problem Learning with nonconvex constraints from neural network outputs.
method Linearized ADMM algorithm for convex objective with nonconvex constraint.
result Efficient algorithm with provable convergence rates for specific neural network architectures.
The paper improves SGD's generalization error bounds for nonconvex optimization.
problem Improving generalization error bounds for SGD in nonconvex optimization.
method Characterizing the on-average stability of SGD iterates and using it to derive probabilistic generalization error bounds.
result Improved generalization error bounds for SGD in both nonconvex and gradient dominant loss functions.
This work uses Lasry-Lions envelopes to solve nonconvex optimization problems.
problem Nonconvex and nonsmooth terms in optimization problems.
method Develops a homotopy approach using Lasry-Lions envelopes to approximate and solve the original problem.
result The method can solve composite minimization problems and is more effective than classical alternatives in certain domains.