Analysis of generalized Bregman surrogate algorithms for nonsmooth nonconvex statistical learning

DOI10.1214/21-AOS2090zbMATH Open1486.62212arXiv2112.09191OpenAlexW4200303272MaRDI QIDQ2073715FDOQ2073715

Authors: Yiyuan She, Zhifeng Wang, Jiuwu Jin 

Publication date: 7 February 2022

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: Modern statistical applications often involve minimizing an objective function that may be nonsmooth and/or nonconvex. This paper focuses on a broad Bregman-surrogate algorithm framework including the local linear approximation, mirror descent, iterative thresholding, DC programming and many others as particular instances. The recharacterization via generalized Bregman functions enables us to construct suitable error measures and establish global convergence rates for nonconvex and nonsmooth objectives in possibly high dimensions. For sparse learning problems with a composite objective, under some regularity conditions, the obtained estimators as the surrogate's fixed points, though not necessarily local minimizers, enjoy provable statistical guarantees, and the sequence of iterates can be shown to approach the statistical truth within the desired accuracy geometrically fast. The paper also studies how to design adaptive momentum based accelerations without assuming convexity or smoothness by carefully controlling stepsize and relaxation parameters.

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

Recommendations

• A Bregman stochastic method for nonconvex nonsmooth problem beyond global Lipschitz gradient continuity
• Non-smooth non-convex Bregman minimization: unification and new algorithms
• Optimal computational and statistical rates of convergence for sparse nonconvex learning problems
• Global convergence of ADMM in nonconvex nonsmooth optimization
• An outer-inner linearization method for non-convex and nondifferentiable composite regularization problems

zbMATH Keywords

nonconvex optimizationBregman divergencenonsmooth optimizationMM algorithmsmomentum-based accelerationstatistical algorithmic analysis

Mathematics Subject Classification ID

Nonparametric regression and quantile regression (62G08) Linear regression; mixed models (62J05) Learning and adaptive systems in artificial intelligence (68T05) Ridge regression; shrinkage estimators (Lasso) (62J07) Nonconvex programming, global optimization (90C26)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Nearly unbiased variable selection under minimax concave penalty
• Adaptive subgradient methods for online learning and stochastic optimization
• Weak convergence and empirical processes. With applications to statistics
• Graphical models, exponential families, and variational inference
• Ideal spatial adaptation by wavelet shrinkage
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• Title not available (Why is that?)
• One-step sparse estimates in nonconcave penalized likelihood models
• On the conditions used to prove oracle results for the Lasso
• Simultaneous analysis of Lasso and Dantzig selector
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• Analysis of multi-stage convex relaxation for sparse regularization
• Robust Statistics
• Introductory lectures on convex optimization. A basic course.
• Sparsity oracle inequalities for the Lasso
• Variable selection using MM algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Clustering with Bregman divergences.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Decoding by Linear Programming
• Title not available (Why is that?)
• A Statistical View of Some Chemometrics Regression Tools
• Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
• Convex Analysis
• Optimal computational and statistical rates of convergence for sparse nonconvex learning problems
• Learning the parts of objects by non-negative matrix factorization
• Oracle inequalities and optimal inference under group sparsity
• Iterative hard thresholding for compressed sensing
• An iterative algorithm for fitting nonconvex penalized generalized linear models with grouped predictors
• Thresholding-based iterative selection procedures for model selection and shrinkage
• Accelerated gradient methods for nonconvex nonlinear and stochastic programming
• Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
• Recovering Sparse Signals With a Certain Family of Nonconvex Penalties and DC Programming
• The DC (Difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems
• Strong oracle optimality of folded concave penalized estimation
• Regularized \(M\)-estimators with nonconvexity: statistical and algorithmic theory for local optima
• MM algorithms for geometric and signomial programming
• Penalized Bregman divergence for large-dimensional regression and classification
• Group Iterative Spectrum Thresholding for Super-Resolution Sparse Spectral Selection
• Title not available (Why is that?)
• Cluster analysis: unsupervised learning via supervised learning with a non-convex penalty
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• Learning Topology and Dynamics of Large Recurrent Neural Networks
• On the finite-sample analysis of \(\Theta\)-estimators

Cited In (2)

• Gaining Outlier Resistance With Progressive Quantiles: Fast Algorithms and Theoretical Studies
• A framework of regularized low-rank matrix models for regression and classification

Uses Software

• AdaGrad

This page was built for publication: Analysis of generalized Bregman surrogate algorithms for nonsmooth nonconvex statistical learning

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