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

2016/10/18 by Haihao Lu, Lu, Haihao, Robert M. Freund +3 · 25 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

paper · pdf · doi:10.48550/arxiv.1610.05708

openalex publication_date 2016/10/18 · 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\nconvex optimization assumes that the gradient of the objective function is\nuniformly smooth with some Lipschitz constant L. However, in many settings\nthe differentiable convex function f(\⋅) is not uniformly smooth -- for\nexample in D-optimal design where f(x):=-\ln \det(HXH^T), or even the\nunivariate setting with f(x) := -\ln(x) + x². Herein we develop a notion of\n"relative smoothness" and relative strong convexity that is determined relative\nto a user-specified "reference function" h(\⋅) (that should be\ncomputationally tractable for algorithms), and we show that many differentiable\nconvex functions are relatively smooth with respect to a correspondingly\nfairly-simple reference function h(\⋅). We extend two standard algorithms\n-- the primal gradient scheme and the dual averaging scheme -- to our new\nsetting, with associated computational guarantees. We apply our new approach to\ndevelop a new first-order method for the D-optimal design problem, with\nassociated computational complexity analysis. Some of our results have a\ncertain overlap with the recent work citebbt.\n

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 without 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
• Provable Maximum Entropy Manifold Exploration via Diffusion Models
• Gradient-Normalized Smoothness for Optimization with Approximate Hessians

Related

• Inexact Relative Smoothness and Strong Convexity for Optimization and 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\n First-order Methods
• On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems
• Convex and Non-convex Optimization Under Generalized Smoothness