Sensitivity analysis for mirror-stratifiable convex functions
From MaRDI portal
Publication:4554065
DOI10.1137/17M113825XzbMATH Open1461.65148arXiv1707.03194OpenAlexW2963484923WikidataQ129063043 ScholiaQ129063043MaRDI QIDQ4554065FDOQ4554065
Authors: Jalal Fadili, Jérôme Malick, Gabriel Peyré 
Publication date: 7 November 2018
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Abstract: This paper provides a set of sensitivity analysis and activity identification results for a class of convex functions with a strong geometric structure, that we coined "mirror-stratifiable". These functions are such that there is a bijection between a primal and a dual stratification of the space into partitioning sets, called strata. This pairing is crucial to track the strata that are identifiable by solutions of parametrized optimization problems or by iterates of optimization algorithms. This class of functions encompasses all regularizers routinely used in signal and image processing, machine learning, and statistics. We show that this "mirror-stratifiable" structure enjoys a nice sensitivity theory, allowing us to study stability of solutions of optimization problems to small perturbations, as well as activity identification of first-order proximal splitting-type algorithms. Existing results in the literature typically assume that, under a non-degeneracy condition, the active set associated to a minimizer is stable to small perturbations and is identified in finite time by optimization schemes. In contrast, our results do not require any non-degeneracy assumption: in consequence, the optimal active set is not necessarily stable anymore, but we are able to track precisely the set of identifiable strata.We show that these results have crucial implications when solving challenging ill-posed inverse problems via regularization, a typical scenario where the non-degeneracy condition is not fulfilled. Our theoretical results, illustrated by numerical simulations, allow to characterize the instability behaviour of the regularized solutions, by locating the set of all low-dimensional strata that can be potentially identified by these solutions.
Full work available at URL: https://arxiv.org/abs/1707.03194
Recommendations
sensitivityconvex analysisinverse problemsactive setsapplications in imaging and machine learningfirst-order splitting algorithms
Numerical mathematical programming methods (65K05) Convex programming (90C25) Sensitivity, stability, parametric optimization (90C31)
Cites Work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- Title not available (Why is that?)
- Statistics for high-dimensional data. Methods, theory and applications.
- Title not available (Why is that?)
- A wavelet tour of signal processing. The sparse way.
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- Atomic Decomposition by Basis Pursuit
- Variational Analysis
- Model Selection and Estimation in Regression with Grouped Variables
- Convex analysis and monotone operator theory in Hilbert spaces
- Title not available (Why is that?)
- Exact matrix completion via convex optimization
- Decoding by Linear Programming
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- Convex Analysis
- Proximal splitting methods in signal processing
- Solving monotone inclusions via compositions of nonexpansive averaged operators
- Necessary and sufficient conditions for linear convergence of \(\ell^1\)-regularization
- Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
- On Sparse Representations in Arbitrary Redundant Bases
- Title not available (Why is that?)
- Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs
- Variational methods in imaging
- Convexifying the set of matrices of bounded rank: applications to the quasiconvexification and convexification of the rank function
- Consistency of trace norm minimization
- The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
- Orthogonal invariance and identifiability
- Gradient-based algorithms with applications to signal-recovery problems
- Towards a Mathematical Theory of Super‐resolution
- Exact support recovery for sparse spikes deconvolution
- Newton methods for nonsmooth convex minimization: connections among \(\mathcal U\)-Lagrangian, Riemannian Newton and SQP methods
- Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit
- Title not available (Why is that?)
- The 𝒰-Lagrangian of a convex function
- Active Sets, Nonsmoothness, and Sensitivity
- On the convergence of the iterates of the ``fast iterative shrinkage/thresholding algorithm
- Title not available (Why is that?)
- Linear convergence of iterative soft-thresholding
- Perturbations, approximations and sensitivity analysis of optimal control systems
- Partial Smoothness, Tilt Stability, and Generalized Hessians
- Sharp support recovery from noisy random measurements by \(\ell_1\)-minimization
- Optimality, identifiability, and sensitivity
- Generic minimizing behavior in semialgebraic optimization
- Low complexity regularization of linear inverse problems
- Activity identification and local linear convergence of forward-backward-type methods
- Model Consistency of Partly Smooth Regularizers
- Local Linear Convergence of ISTA and FISTA on the LASSO Problem
- Model selection with low complexity priors
- Identifying active manifolds in regularization problems
- Local convergence properties of Douglas-Rachford and alternating direction method of multipliers
- Confexifying the counting function on \(\mathbb R^{p}\) for convexifying the rank function on \(M_{m,n}(\mathbb R)\)
Cited In (10)
- Differentiating Nonsmooth Solutions to Parametric Monotone Inclusion Problems
- Nonsmoothness in machine learning: specific structure, proximal identification, and applications
- On the interplay between acceleration and identification for the proximal gradient algorithm
- Local linear convergence of proximal coordinate descent algorithm
- Proximal gradient methods with adaptive subspace sampling
- Convergence of the forward-backward algorithm: beyond the worst-case with the help of geometry
- Exact recovery of the support of piecewise constant images via total variation regularization
- On the strong convergence of forward-backward splitting in reconstructing jointly sparse signals
- Active-set Newton methods and partial smoothness
- Thresholding gradient methods in Hilbert spaces: support identification and linear convergence
Uses Software
This page was built for publication: Sensitivity analysis for mirror-stratifiable convex functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4554065)
