Relatively smooth convex optimization by first-order methods, and applications
From MaRDI portal
Abstract: The usual approach to developing and analyzing first-order methods for smooth convex optimization assumes that the gradient of the objective function is uniformly smooth with some Lipschitz constant . However, in many settings the differentiable convex function is not uniformly smooth -- for example in -optimal design where , or even the univariate setting with . Herein we develop a notion of "relative smoothness" and relative strong convexity that is determined relative to a user-specified "reference function" (that should be computationally tractable for algorithms), and we show that many differentiable convex functions are relatively smooth with respect to a correspondingly fairly-simple reference function . We extend two standard algorithms -- the primal gradient scheme and the dual averaging scheme -- to our new setting, with associated computational guarantees. We apply our new approach to develop a new first-order method for the -optimal design problem, with associated computational complexity analysis. Some of our results have a certain overlap with the recent work cite{bbt}.
Recommendations
- Optimized first-order methods for smooth convex minimization
- An optimal gradient method for smooth strongly convex minimization
- Optimizing the efficiency of first-order methods for decreasing the gradient of smooth convex functions
- Fastest rates for stochastic mirror descent methods
- Nearly optimal first-order methods for convex optimization under gradient norm measure: an adaptive regularization approach
Cites work
- A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
- Computation of Minimum-Volume Covering Ellipsoids
- Gradient methods for minimizing composite functions
- scientific article; zbMATH DE number 4015993 (Why is no real title available?)
- scientific article; zbMATH DE number 1807400 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 3562783 (Why is no real title available?)
- scientific article; zbMATH DE number 3052220 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- Large step volumetric potential reduction algorithms for linear programming
- Linear convergence of a modified Frank–Wolfe algorithm for computing minimum-volume enclosing ellipsoids
- Minimum-volume ellipsoids. Theory and algorithms
- On the complexity of approximating the maximal inscribed ellipsoid for a polytope
- On the Minimum Volume Covering Ellipsoid of Ellipsoids
- On the Second-Order Feasibility Cone: Primal-Dual Representation and Efficient Projection
- Optimal and Efficient Designs of Experiments
- Primal-dual subgradient methods for convex problems
- Rounding of Polytopes in the Real Number Model of Computation
- Smooth minimization of non-smooth functions
- The Equivalence of Two Extremum Problems
- The volumetric barrier for semidefinite programming.
Cited in
(only showing first 100 items - show all)- New computational guarantees for solving convex optimization problems with first order methods, via a function growth condition measure
- Point process estimation with Mirror Prox algorithms
- New characterizations of Hoffman constants for systems of linear constraints
- Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute gradient for structured convex optimization
- Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems
- Algorithms for nonnegative matrix factorization with the Kullback-Leibler divergence
- Quartic first-order methods for low-rank minimization
- The condition number of a function relative to a set
- Accelerated Bregman proximal gradient methods for relatively smooth convex optimization
- A Laplacian approach to _1-norm minimization
- Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
- Fastest rates for stochastic mirror descent methods
- A block inertial Bregman proximal algorithm for nonsmooth nonconvex problems with application to symmetric nonnegative matrix tri-factorization
- An inexact proximal augmented Lagrangian framework with arbitrary linearly convergent inner solver for composite convex optimization
- Cyclic coordinate descent in the Hölder smooth setting
- A dual Bregman proximal gradient method for relatively-strongly convex optimization
- Several accelerated subspace minimization conjugate gradient methods based on regularization model and convergence rate analysis for nonconvex problems
- Optimal complexity and certification of Bregman first-order methods
- Global convergence of model function based Bregman proximal minimization algorithms
- Extragradient and extrapolation methods with generalized Bregman distances for saddle point problems
- Proximal gradient algorithms under local Lipschitz gradient continuity. A convergence and robustness analysis of PANOC
- Screening for a reweighted penalized conditional gradient method
- Golden ratio algorithms for variational inequalities
- Implementable tensor methods in unconstrained convex optimization
- Bregman proximal mappings and Bregman-Moreau envelopes under relative prox-regularity
- Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity
- Convergence of the exponentiated gradient method with Armijo line search
- Finitely determined functions
- Superfast second-order methods for unconstrained convex optimization
- Numerical methods for some classes of variational inequalities with relatively strongly monotone operators
- Affine-invariant contracting-point methods for convex optimization
- Perturbed Fenchel duality and first-order methods
- Inexact accelerated high-order proximal-point methods
- A simple nearly optimal restart scheme for speeding up first-order methods
- Bregman three-operator splitting methods
- On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization
- Smoothing and first order methods: a unified framework
- First-order and second-order optimality conditions for nonsmooth constrained problems via convolution smoothing
- Analogues of switching subgradient schemes for relatively Lipschitz-continuous convex programming problems
- Proximal-like incremental aggregated gradient method with linear convergence under Bregman distance growth conditions
- Inexact high-order proximal-point methods with auxiliary search procedure
- An optimal high-order tensor method for convex optimization
- Block Bregman majorization minimization with extrapolation
- Tensor methods for finding approximate stationary points of convex functions
- Inexact basic tensor methods for some classes of convex optimization problems
- Gradient methods with memory
- Exact gradient methods with memory
- Revisiting linearized Bregman iterations under Lipschitz-like convexity condition
- Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation
- Continuous-time convergence rates in potential and monotone games
- On the linear convergence of a Bregman proximal point algorithm
- Bregman proximal point algorithm revisited: a new inexact version and its inertial variant
- Understanding non-negative matrix factorization in the framework of Bregman divergence
- Contracting proximal methods for smooth convex optimization
- Nonlinear forward-backward splitting with projection correction
- Sharpness, restart, and acceleration
- A Bregman forward-backward linesearch algorithm for nonconvex composite optimization: superlinear convergence to nonisolated local minima
- Dual space preconditioning for gradient descent
- On inexact solution of auxiliary problems in tensor methods for convex optimization
- Inexact model: a framework for optimization and variational inequalities
- Bregman Finito/MISO for nonconvex regularized finite sum minimization without Lipschitz gradient continuity
- Accelerated Bregman Primal-Dual Methods Applied to Optimal Transport and Wasserstein Barycenter Problems
- Analysis of the Frank-Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier
- Accelerated First-Order Methods for Convex Optimization with Locally Lipschitz Continuous Gradient
- Factor-\(\sqrt{2}\) acceleration of accelerated gradient methods
- Affine Invariant Convergence Rates of the Conditional Gradient Method
- Dualities for Non-Euclidean Smoothness and Strong Convexity under the Light of Generalized Conjugacy
- A stochastic variance reduction algorithm with Bregman distances for structured composite problems
- Stochastic composition optimization of functions without Lipschitz continuous gradient
- Hyperfast second-order local solvers for efficient statistically preconditioned distributed optimization
- No-regret algorithms in on-line learning, games and convex optimization
- No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization
- Super-Universal Regularized Newton Method
- Convergence rate analysis of the multiplicative gradient method for PET-type problems
- An alternating structure-adapted Bregman proximal gradient descent algorithm for constrained nonconvex nonsmooth optimization problems and its inertial variant
- Provable Phase Retrieval with Mirror Descent
- Some adaptive first-order methods for variational inequalities with relatively strongly monotone operators and generalized smoothness
- First-order methods for convex optimization
- Adaptive Third-Order Methods for Composite Convex Optimization
- Data-Driven Mirror Descent with Input-Convex Neural Networks
- Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
- Random Coordinate Descent Methods for Nonseparable Composite Optimization
- Convergence Analysis for Bregman Iterations in Minimizing a Class of Landau Free Energy Functionals
- SPIRAL: a superlinearly convergent incremental proximal algorithm for nonconvex finite sum minimization
- Coordinate descent methods beyond smoothness and separability
- The rate of convergence of Bregman proximal methods: local geometry versus regularity versus sharpness
- A Bregman proximal subgradient algorithm for nonconvex and nonsmooth fractional optimization problems
- Gradient descent in the absence of global Lipschitz continuity of the gradients
- An interior proximal gradient method for nonconvex optimization
- Inexact tensor methods and their application to stochastic convex optimization
- Stochastic mirror descent for convex optimization with consensus constraints
- The geometry of monotone operator splitting methods
- The exact worst-case convergence rate of the alternating direction method of multipliers
- Complementary composite minimization, small gradients in general norms, and applications
- High-order methods beyond the classical complexity bounds: inexact high-order proximal-point methods
- A mirror inertial forward-reflected-backward splitting: convergence analysis beyond convexity and Lipschitz smoothness
- Convergence rate bounds for the mirror descent method: IQCs, Popov criterion and Bregman divergence
- Approximate Bregman proximal gradient algorithm for relatively smooth nonconvex optimization
- Stochastic dual coordinate descent with adaptive heavy ball momentum for linearly constrained convex optimization
- Multiblock ADMM for nonsmooth nonconvex optimization with nonlinear coupling constraints
This page was built for publication: Relatively smooth convex optimization by first-order methods, and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4603043)
