Approximation accuracy, gradient methods, and error bound for structured convex optimization
From MaRDI portal
Publication:607498
The paper deals with the problem of accuracy estimation if optimization problems arising in practical applications are approximated by convex relaxations. Such relaxations are often highly structured and large scale. The author tries to answer the following two questions: (1) How accurate are approximations obtained via the convex relaxations; (2) How fast can the convex relaxations be solved? Examples from the area of compressed sensing and sensor network localization are considered. As an appropriate method for solving the structured and large scale relaxations the first-order gradient methods are proposed. An error bound on the distance to the solution set of the convex relaxation is derived for a class of regularized problems, and linear convergence of the gradient methods is investigated.
Recommendations
- A unified approach to error bounds for structured convex optimization problems
- Explicit and efficient error estimation for convex minimization problems
- The extragradient method for convex optimization in the presence of computational errors
- An approximation method with nonsummable errors for convex minimization problems
- Gradient methods with regularization for constrained optimization problems and their complexity estimates
- Approximating parameterized convex optimization problems
- Approximating parameterized convex optimization problems
- Computable error bounds and estimates for the conjugate gradient method
- Error Bound and Reduced-Gradient Projection Algorithms for Convex Minimization over a Polyhedral Set
- On numerical estimates of errors in solving convex optimization problems
Cites work
- (Robust) edge-based semidefinite programming relaxation of sensor network localization
- 10.1162/15324430152748218
- A Convergent Incremental Gradient Method with a Constant Step Size
- A coordinate gradient descent method for linearly constrained smooth optimization and support vector machines training
- A coordinate gradient descent method for nonsmooth separable minimization
- A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization
- A Distributed SDP Approach for Large-Scale Noisy Anchor-Free Graph Realization with Applications to Molecular Conformation
- A fast hybrid algorithm for large-scale \(l_{1}\)-regularized logistic regression
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A generalized proximal point algorithm for certain non-convex minimization problems
- A Linearly Convergent Dual-Based Gradient Projection Algorithm for Quadratically Constrained Convex Minimization
- A Maxmin Location Problem
- A New Alternating Minimization Algorithm for Total Variation Image Reconstruction
- A new approach to collaborative filtering: operator estimation with spectral regularization
- A simple proof of the restricted isometry property for random matrices
- A Singular Value Thresholding Algorithm for Matrix Completion
- Adapting to Unknown Smoothness via Wavelet Shrinkage
- Algorithmic Aspects of Wireless Sensor Networks
- An Efficient TVL1 Algorithm for Deblurring Multichannel Images Corrupted by Impulsive Noise
- An Incremental Gradient(-Projection) Method with Momentum Term and Adaptive Stepsize Rule
- An Iterative Regularization Method for Total Variation-Based Image Restoration
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
- Atomic Decomposition by Basis Pursuit
- Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization
- Bregman Iterative Algorithms for \ell₁-Minimization with Applications to Compressed Sensing
- Bregman Monotone Optimization Algorithms
- Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
- Convergence of a block coordinate descent method for nondifferentiable minimization
- Convergence of Approximate and Incremental Subgradient Methods for Convex Optimization
- Convergence of Proximal-Like Algorithms
- Convex Analysis
- Convex multi-task feature learning
- Convex optimization methods for dimension reduction and coefficient estimation in multivariate linear regression
- Decoding by Linear Programming
- Distributed asynchronous incremental subgradient methods
- Dual coordinate ascent methods for non-strictly convex minimization
- Duality-based algorithms for total-variation-regularized image restoration
- Error bounds and convergence analysis of feasible descent methods: A general approach
- Excessive Gap Technique in Nonsmooth Convex Minimization
- Exploiting Sparsity in SDP Relaxation for Sensor Network Localization
- Finite-Dimensional Variational Inequalities and Complementarity Problems
- First-Order Methods for Sparse Covariance Selection
- Fixed point and Bregman iterative methods for matrix rank minimization
- For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution
- Further Relaxations of the Semidefinite Programming Approach to Sensor Network Localization
- Further Results on Stable Recovery of Sparse Overcomplete Representations in the Presence of Noise
- Graph rigidity via Euclidean distance matrices
- Grassmannian frames with applications to coding and communication
- Greed is Good: Algorithmic Results for Sparse Approximation
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Heuristic and Special Case Algorithms for Dispersion Problems
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 4164577 (Why is no real title available?)
- scientific article; zbMATH DE number 4079168 (Why is no real title available?)
- scientific article; zbMATH DE number 3722433 (Why is no real title available?)
- scientific article; zbMATH DE number 3465097 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1131479 (Why is no real title available?)
- scientific article; zbMATH DE number 2079345 (Why is no real title available?)
- scientific article; zbMATH DE number 1382772 (Why is no real title available?)
- scientific article; zbMATH DE number 778130 (Why is no real title available?)
- scientific article; zbMATH DE number 913711 (Why is no real title available?)
- scientific article; zbMATH DE number 3296905 (Why is no real title available?)
- scientific article; zbMATH DE number 3381785 (Why is no real title available?)
- scientific article; zbMATH DE number 964349 (Why is no real title available?)
- Ideal spatial adaptation by wavelet shrinkage
- Identification of Matrices Having a Sparse Representation
- Incremental gradient algorithms with stepsizes bounded away from zero
- Interior Gradient and Proximal Methods for Convex and Conic Optimization
- Interior projection-like methods for monotone variational inequalities
- Interior-point method for nuclear norm approximation with application to system identification
- Introductory lectures on convex optimization. A basic course.
- Just relax: convex programming methods for identifying sparse signals in noise
- Matching pursuits with time-frequency dictionaries
- Mathematical Programming in Neural Networks
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- Model Selection and Estimation in Regression with Grouped Variables
- Model selection and estimation in the Gaussian graphical model
- Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data
- Multi-class discriminant kernel learning via convex programming
- NESTA: A fast and accurate first-order method for sparse recovery
- Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming
- Numerical Optimization
- On linear-time algorithms for the continuous quadratic Knapsack problem
- On Sparse Representations in Arbitrary Redundant Bases
- On the Convergence Rate of Dual Ascent Methods for Linearly Constrained Convex Minimization
- On the Linear Convergence of Descent Methods for Convex Essentially Smooth Minimization
- On the Statistical Analysis of Smoothing by Maximizing Dirty Markov Random Field Posterior Distributions
- Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization
- Parallel Gradient Distribution in Unconstrained Optimization
- Parallel Variable Distribution
- Parallel variable distribution for constrained optimization
- Parallel Variable Transformation in Unconstrained Optimization
- Pathwise coordinate optimization
- Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
- Primal-dual subgradient methods for convex problems
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Proximal Minimization Methods with Generalized Bregman Functions
- Recovery of Exact Sparse Representations in the Presence of Bounded Noise
- Robust Stochastic Approximation Approach to Stochastic Programming
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Second-order Cone Programming Methods for Total Variation-Based Image Restoration
- Second‐Order Cone Programming Relaxation of Sensor Network Localization
- Sensor network localization, Euclidean distance matrix completions, and graph realization
- Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
- Smooth minimization of non-smooth functions
- Smoothing technique and its applications in semidefinite optimization
- Sparse inverse covariance estimation with the graphical lasso
- Sparse Reconstruction by Separable Approximation
- Sparse representations in unions of bases
- Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit
- Sparsity-preserving SOR algorithms for separable quadratic and linear programming
- SpaseLoc: An Adaptive Subproblem Algorithm for Scalable Wireless Sensor Network Localization
- Stable recovery of sparse overcomplete representations in the presence of noise
- Stable signal recovery from incomplete and inaccurate measurements
- Sum of squares method for sensor network localization
- The Group Lasso for Logistic Regression
- The restricted isometry property and its implications for compressed sensing
- Theory of semidefinite programming for sensor network localization
- Uncertainty principles and ideal atomic decomposition
Cited in
(only showing first 100 items - show all)- A simplified view of first order methods for optimization
- On globally Q-linear convergence of a splitting method for group Lasso
- A unified approach to error bounds for structured convex optimization problems
- A modified proximal gradient method for a family of nonsmooth convex optimization problems
- On the computational efficiency of subgradient methods: a case study with Lagrangian bounds
- A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tseng error bound property
- Level-set methods for convex optimization
- Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
- An alternating direction method for finding Dantzig selectors
- An alternating direction method of multipliers with the BFGS update for structured convex quadratic optimization
- On the convergence of the iterates of proximal gradient algorithm with extrapolation for convex nonsmooth minimization problems
- Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems
- A sequential partial linearization algorithm for the symmetric eigenvalue complementarity problem
- A dual reformulation and solution framework for regularized convex clustering problems
- Bounds for the tracking error of first-order online optimization methods
- An accelerated smoothing gradient method for nonconvex nonsmooth minimization in image processing
- Variational analysis perspective on linear convergence of some first order methods for nonsmooth convex optimization problems
- Some modified fast iterative shrinkage thresholding algorithms with a new adaptive non-monotone stepsize strategy for nonsmooth and convex minimization problems
- A control-theoretic perspective on optimal high-order optimization
- An inexact accelerated stochastic ADMM for separable convex optimization
- Linear convergence of prox-SVRG method for separable non-smooth convex optimization problems under bounded metric subregularity
- Perturbation techniques for convergence analysis of proximal gradient method and other first-order algorithms via variational analysis
- Augmented Lagrangian methods for convex matrix optimization problems
- A note on approximate accelerated forward-backward methods with absolute and relative errors, and possibly strongly convex objectives
- On convex envelopes and regularization of non-convex functionals without moving global minima
- Error bounds for non-polyhedral convex optimization and applications to linear convergence of FDM and PGM
- Faster subgradient methods for functions with Hölderian growth
- The modified second APG method for DC optimization problems
- A telescopic Bregmanian proximal gradient method without the global Lipschitz continuity assumption
- Generalized affine scaling algorithms for linear programming problems
- Further properties of the forward-backward envelope with applications to difference-of-convex programming
- When only global optimization matters
- Convex optimization approach to signals with fast varying instantaneous frequency
- A unified penalized method for sparse additive quantile models: an RKHS approach
- Computing proximal points of convex functions with inexact subgradients
- Proximal gradient methods for multiobjective optimization and their applications
- Iteratively reweighted \(\ell _1\) algorithms with extrapolation
- A simple convergence analysis of Bregman proximal gradient algorithm
- Augmented Lagrangian method with alternating constraints for nonlinear optimization problems
- A very simple SQCQP method for a class of smooth convex constrained minimization problems with nice convergence results
- On proximal gradient method for the convex problems regularized with the group reproducing kernel norm
- An inexact dual fast gradient-projection method for separable convex optimization with linear coupled constraints
- A globally convergent proximal Newton-type method in nonsmooth convex optimization
- Iteration complexity analysis of dual first-order methods for conic convex programming
- Linear convergence of descent methods for the unconstrained minimization of restricted strongly convex functions
- A family of subgradient-based methods for convex optimization problems in a unifying framework
- Linear convergence of proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth minimization problems
- Gradient-based algorithms with applications to signal-recovery problems
- Optimized first-order methods for smooth convex minimization
- New results on subgradient methods for strongly convex optimization problems with a unified analysis
- A block successive upper-bound minimization method of multipliers for linearly constrained convex optimization
- Iterative Proportional Scaling Revisited: A Modern Optimization Perspective
- Block coordinate proximal gradient methods with variable Bregman functions for nonsmooth separable optimization
- Robust least square semidefinite programming with applications
- Proximal methods for the latent group lasso penalty
- On the linear convergence of a proximal gradient method for a class of nonsmooth convex minimization problems
- Quadratic growth conditions for convex matrix optimization problems associated with spectral functions
- Generalized conditional gradient for sparse estimation
- Accelerated residual methods for the iterative solution of systems of equations
- Error Bound and Reduced-Gradient Projection Algorithms for Convex Minimization over a Polyhedral Set
- Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization
- On the linear convergence of the approximate proximal splitting method for non-smooth convex optimization
- Discerning the linear convergence of ADMM for structured convex optimization through the lens of variational analysis
- Proximal-like incremental aggregated gradient method with linear convergence under Bregman distance growth conditions
- A proximal gradient splitting method for solving convex vector optimization problems
- An Accelerated Level-Set Method for Inverse Scattering Problems
- On numerical estimates of errors in solving convex optimization problems
- A First-Order Optimization Algorithm for Statistical Learning with Hierarchical Sparsity Structure
- Bregman proximal point algorithm revisited: a new inexact version and its inertial variant
- Two-stage approach to multivariate linear regression with sparsely mismatched data
- On the linear convergence of the alternating direction method of multipliers
- Error bounds, quadratic growth, and linear convergence of proximal methods
- Adaptive FISTA for Nonconvex Optimization
- Iteration complexity analysis of block coordinate descent methods
- A new convergence analysis and perturbation resilience of some accelerated proximal forward-backward algorithms with errors
- Iteration complexity of a block coordinate gradient descent method for convex optimization
- On degenerate doubly nonnegative projection problems
- An extrapolated iteratively reweighted \(\ell_1\) method with complexity analysis
- Smooth over-parameterized solvers for non-smooth structured optimization
- Convergence rates of gradient methods for convex optimization in the space of measures
- A singular value shrinkage thresholding algorithm for folded concave penalized low-rank matrix optimization problems
- Convergence of an asynchronous block-coordinate forward-backward algorithm for convex composite optimization
- Quadratic error bound of the smoothed gap and the restarted averaged primal-dual hybrid gradient
- Proximal gradient method with extrapolation and line search for a class of non-convex and non-smooth problems
- An inertial projection and contraction algorithm for pseudomonotone variational inequalities without Lipschitz continuity
- Two classes of spectral three-term derivative-free method for solving nonlinear equations with application
- Customized Douglas-Rachford splitting methods for structured inverse variational inequality problems
- A proximal sub-gradient method for group Lasso-type problems
- A fully relaxed Tseng's splitting method
- A unified and efficient proximal gradient descent algorithm for penalized convoluted support vector machines
- SOR- and Jacobi-type iterative methods for solving _1 - _2 problems by way of Fenchel duality
- A unified proximal gradient method for nonconvex composite optimization with extrapolation
- Global convergence of block Bregman proximal iteratively reweighted algorithm with extrapolation
- The modified second APG method for a class of nonconvex nonsmooth problems
- On the analysis of semismooth Newton-type methods for composite optimization
- On the convergence analysis of a proximal gradient method for multiobjective optimization
- Proximal gradient method for convex multiobjective optimization problems without Lipschitz continuous gradients
- Parallel block coordinate descent methods with identification strategies
- Inertial Bregman proximal iteratively reweighted algorithms for a class of nonconvex nonsmooth regularized problems
- Feature-aware regularization for sparse online learning
This page was built for publication: Approximation accuracy, gradient methods, and error bound for structured convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q607498)
