Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization

Abstract

We consider the problem of optimizing the sum of a smooth convex function and a non-smooth convex function using proximal-gradient methods, where an error is present in the calculation of the gradient of the smooth term or in the proximity operator with respect to the non-smooth term. We show that both the basic proximal-gradient method and the accelerated proximal-gradient method achieve the same convergence rate as in the error-free case, provided that the errors decrease at appropriate rates.Using these rates, we perform as well as or better than a carefully chosen fixed error level on a set of structured sparsity problems.

Neural Information Processing Systems (2011)

References in corpus (1)

• Fast Overlapping Group Lasso

Cited by in corpus (76)

• Convex Optimization for Big Data
• The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $1/k^2$
• Embedded Online Optimization for Model Predictive Control at Megahertz Rates
• An Online Plug-and-Play Algorithm for Regularized Image Reconstruction
• A Universal Catalyst for First-Order Optimization
• Distributed Compressed Sensing For Static and Time-Varying Networks
• Stop Wasting My Gradients: Practical SVRG
• From Averaging to Acceleration, There is Only a Step-size
• Lower Bounds and Optimal Algorithms for Personalized Federated Learning
• Composite Self-Concordant Minimization
• Efficient Sparse Group Feature Selection via Nonconvex Optimization
• Supervised Feature Selection in Graphs with Path Coding Penalties and Network Flows
• Zeroth-Order Regularized Optimization (ZORO): Approximately Sparse Gradients and Adaptive Sampling
• Projected Nesterov's Proximal-Gradient Algorithm for Sparse Signal Reconstruction with a Convex Constraint
• Smoothed Variable Sample-size Accelerated Proximal Methods for Nonsmooth Stochastic Convex Programs
• Distributed Gradient Methods with Variable Number of Working Nodes
• Contracting Proximal Methods for Smooth Convex Optimization
• Hybrid Differentially Private Federated Learning on Vertically Partitioned Data
• Distributed and Inexact Proximal Gradient Method for Online Convex Optimization
• Predictive Online Convex Optimization
• Automatic alignment for three-dimensional tomographic reconstruction
• Neumann Networks for Inverse Problems in Imaging
• A new convergence analysis and perturbation resilience of some accelerated proximal forward-backward algorithms with errors
• Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry
• A Generic Acceleration Framework for Stochastic Composite Optimization
• On the Convergence of SGD with Biased Gradients
• Stochastic Nonconvex Optimization with Large Minibatches
• Decentralized Accelerated Gradient Methods With Increasing Penalty Parameters
• Searching to Exploit Memorization Effect in Learning from Corrupted Labels
• A Primal-Dual Smoothing Framework for Max-Structured Non-Convex Optimization
• Information-theoretic analysis for transfer learning
• Analysis of Biased Stochastic Gradient Descent Using Sequential Semidefinite Programs
• Tracking Performance of Online Stochastic Learners
• Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method
• Inexact Tensor Methods with Dynamic Accuracies
• Tail bounds for stochastic approximation
• (Bandit) Convex Optimization with Biased Noisy Gradient Oracles
• Parameter Estimation with the Ordered ${\ell }_2$ Regularization via an Alternating Direction Method of Multipliers
• Distributed Inexact Successive Convex Approximation ADMM: Analysis-Part I
• Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip
• Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Streaming Data
• Convergence Rates of Biased Stochastic Optimization for Learning Sparse Ising Models
• On the Convergence of Learning-based Iterative Methods for Nonconvex Inverse Problems
• A convex approach to the Gilbert-Steiner problem
• Semi-proximal Mirror-Prox for Nonsmooth Composite Minimization
• Accelerated differential inclusion for convex optimization
• Asynchronous Schemes for Stochastic and Misspecified Potential Games and Nonconvex Optimization
• OneAdapt: Fast Configuration Adaptation for Video Analytics Applications via Backpropagation
• Learning Deep Neural Networks under Agnostic Corrupted Supervision
• Factorization Machines with Regularization for Sparse Feature Interactions
• Iterative regularization for convex regularizers
• On the computation of equilibria in monotone and potential stochastic hierarchical games
• Resource-aware Exact Decentralized Optimization Using Event-triggered Broadcasting
• Locally Accelerated Conditional Gradients
• Applying FISTA to optimization problems (with or) without minimizers
• On starting and stopping criteria for nested primal-dual iterations
• Exact worst-case convergence rates of the proximal gradient method for composite convex minimization
• A Survey on Large-scale Machine Learning
• Dual Smoothing and Level Set Techniques for Variational Matrix Decomposition
• Bregman Proximal Gradient Algorithm with Extrapolation for a class of Nonconvex Nonsmooth Minimization Problems
• Augmented Lagrangian Optimization under Fixed-Point Arithmetic
• A Distributed Quasi-Newton Algorithm for Primal and Dual Regularized Empirical Risk Minimization
• New Computational and Statistical Aspects of Regularized Regression with Application to Rare Feature Selection and Aggregation
• Distributed proximal gradient algorithm for non-smooth non-convex optimization over time-varying networks
• Online Stochastic Gradient Methods Under Sub-Weibull Noise and the Polyak-Łojasiewicz Condition
• Sparse hierarchical interaction learning with epigraphical projection
• Small errors in random zeroth-order optimization are imaginary
• Learning to solve TV regularized problems with unrolled algorithms
• Curvature-Exploiting Acceleration of Elastic Net Computations
• Conditions for Convergence in Regularized Machine Learning Objectives
• Accelerated Randomized Mirror Descent Algorithms For Composite Non-strongly Convex Optimization
• Variance-Reduced Splitting Schemes for Monotone Stochastic Generalized Equations
• Optimization for Supervised Machine Learning: Randomized Algorithms for Data and Parameters
• Learning Graph Neural Networks with Approximate Gradient Descent
• ${\ell }_2$-norm Flow Diffusion in Near-Linear Time
• A New Class of Composite Objective Multi-step Estimating-sequence Techniques (COMET)