On the Fenchel Duality between Strong Convexity and Lipschitz Continuous Gradient

Abstract

We provide a simple proof for the Fenchel duality between strong convexity and Lipschitz continuous gradient. To this end, we first establish equivalent conditions of convexity for a general function that may not be differentiable. By utilizing these equivalent conditions, we can directly obtain equivalent conditions for strong convexity and Lipschitz continuous gradient. Based on these results, we can easily prove Fenchel duality. Beside this main result, we also identify several conditions that are implied by strong convexity or Lipschitz continuous gradient, but are not necessarily equivalent to them. This means that these conditions are more general than strong convexity or Lipschitz continuous gradient themselves.

Cited by in corpus (15)

• Smoothness and Stability in GANs
• Fast and Three-rious: Speeding Up Weak Supervision with Triplet Methods
• Path Length Bounds for Gradient Descent and Flow
• Ivy: Instrumental Variable Synthesis for Causal Inference
• Robust time-of-arrival localization via ADMM
• Linearly-Convergent FISTA Variant for Composite Optimization with Duality
• High-Resolution Modeling of the Fastest First-Order Optimization Method for Strongly Convex Functions
• Mechanism Design for Demand Management in Energy Communities
• Distributed Optimal Generation and Load-Side Control for Frequency Regulation in Power Systems
• Small errors in random zeroth-order optimization are imaginary
• Beyond Bandit Feedback in Online Multiclass Classification
• The Gradient Convergence Bound of Federated Multi-Agent Reinforcement Learning with Efficient Communication
• Concavifiability and convergence: necessary and sufficient conditions for gradient descent analysis
• Linear convergence of the Douglas-Rachford algorithm via a generic error bound condition
• Stochastic Iterative Hard Thresholding for Low-Tucker-Rank Tensor Recovery