Relatively-Smooth Convex Optimization by First-Order Methods, and Applications

2016/10/18 by Haihao Lu, Lu, Haihao, Robert M. Freund +3 · 1 voice · 39 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #math.OC

paper · pdf · doi:10.48550/arxiv.1610.05708

openalex publication_date 2016/10/18 · arxiv published 2016/10/18 · arxiv created 2017/10/10 · arxiv updated 2017/10/11 · openalex created_date 2021/02/01 · openalex updated_date 2026/07/28

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 L. However, in many settings the differentiable convex function f(⋅) is not uniformly smooth -- for example in D-optimal design where f(x):=-ln det(HXH^T), or even the univariate setting with f(x) := -ln(x) + x². Herein we develop a notion of "relative smoothness" and relative strong convexity that is determined relative to a user-specified "reference function" h(⋅) (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 h(⋅). 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 D-optimal design problem, with associated computational complexity analysis. Some of our results have a certain overlap with the recent work \citebbt.

Citations

• Smooth minimization of non-smooth functions

Cited by

• Optimal Convex Optimization with Inexact Second-Order Oracles
• Flow Density Control: Generative Optimization Beyond Entropy-Regularized Fine-Tuning
• The Hidden Cost of Approximation in Online Mirror Descent
• Optimization landscape of ℓ₀-Bregman relaxations
• First-order majorization-minimization meets high-order majorant: Boosted inexact high-order forward-backward method
• Optimization of Bregman Variational Learning Dynamics
• Natural Gradient VI: Guarantees for Non-Conjugate Models
• Nonlinearly Preconditioned Gradient Methods: Momentum and Stochastic Analysis
• Approximate Bregman proximal gradient algorithm with variable metric Armijo--Wolfe line search
• Entropy-Smooth Convex Optimization Cannot Be Accelerated
• Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning
• Simple linesearch-free first-order methods for nonconvex optimization
• Bregman Douglas-Rachford Splitting Method
• Linearly involved Generalized Moreau Enhanced Model with Non-quadratic Smooth Convex Data Fidelity Functions
• An Optimization Perspective on the Monotonicity of the Multiplicative Algorithm for Optimal Experimental Design
• On Relatively Smooth Optimization over Riemannian Manifolds
• Inverse harmonic clustering for multi-pitch estimation: an optimal transport approach
• Linesearch-free adaptive Bregman proximal gradient for convex minimization under local relative smoothness
• On exploration of an interior mirror descent flow for stochastic nonconvex constrained problem
• Enhancing Stability of Physics-Informed Neural Network Training Through Saddle-Point Reformulation
• Convergence of drift-diffusion PDEs arising as Wasserstein gradient flows of convex functions
• Deep Equilibrium models for Poisson Imaging Inverse problems via Mirror Descent
• A Fully Adaptive Frank-Wolfe Algorithm for Relatively Smooth Problems and Its Application to Centralized Distributed Optimization
• Bregman level proximal subdifferentials and new characterizations of Bregman proximal operators
• Provable Maximum Entropy Manifold Exploration via Diffusion Models
• Gradient-Normalized Smoothness for Optimization with Approximate Hessians
• Glocal Smoothness: Line search and adaptive step sizes can help in theory too!
• A Triple-Bregman Balanced Primal-Dual Algorithm for Saddle Point Problems
• Bregman proximal gradient method for linear optimization under entropic constraints
• Multilevel Bregman Proximal Gradient Descent
• On the natural domain of Bregman operators
• Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias
• Non-KKT Accumulation in Entropic Mirror Descent
• Proximal gradient-type method with generalized distance and convergence analysis without global descent lemma
• The Symmetry Coefficient of Positively Homogeneous Functions
• Stochastic Saddle Avoidance Beyond Unit Excitation and Smoothness: A Pathwise Lyapunov-Perron Framework
• On the Iterate Convergence of Bregman Projected Gradient Method
• Curvature Residual Geometry in Bregman Regression
• Variational Online Mirror Descent for Robust Learning in Schrödinger Bridge

Discussions

• There are those two well-known paper: pubsonline.informs.org/doi/abs/10.1... arxiv.org/abs/1610.05708 [bsky, 2 points, 1 comments]

Related

• Inexact Relative Smoothness and Strong Convexity for Optimization and\n Variational Inequalities by Inexact Model
• New insights in smoothness and strong convexity with improved convergence of gradient descent
• Smooth Strongly Convex Interpolation and Exact Worst-case Performance of First-order Methods
• On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems
• Convex and Non-convex Optimization Under Generalized Smoothness