Source-linked AI summary
Relatively-Smooth Convex Optimization by First-Order Methods, and Applications
Haihao Lu, Robert M. Freund, Yurii Nesterov
TL;DR
Uniform smoothness can fail or yield impractically large constants for differentiable convex objectives. The paper introduces relative smoothness and relative strong convexity with respect to tractable reference functions, extends primal-gradient and dual-averaging schemes, and applies them to D-optimal design. It provides general convergence and computational guarantees, including linear convergence under both relative conditions, while noting weaker guarantees than Frank–Wolfe for D-optimal design.
Problem
Standard first-order methods require uniformly Lipschitz gradients, but many differentiable convex objectives are not uniformly smooth or have impractically large smoothness constants.
Method
The paper defines relative smoothness and relative strong convexity using a computationally tractable reference function h, then extends primal-gradient and dual-averaging schemes.
Results
The resulting theory provides computational guarantees for both schemes, including linear convergence when f is relatively smooth and relatively strongly convex, and supports a D-optimal design method.
Takeaways & Limitations
Many differentiable convex problems without uniform Lipschitz-continuous gradients can still be addressed using simple reference functions and relative curvature conditions.
Takeaways & Limitations
For D-optimal design, the primal-gradient and dual-averaging schemes have inferior computational guarantees to the specialized Frank–Wolfe method, although they provide a general applicable theory.
Abstract
from arXiv · showhide
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(\cdot)$ 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^2$. Herein we develop a notion of "relative smoothness" and relative strong convexity that is determined relative to a user-specified "reference function" $h(\cdot)$ (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(\cdot)$. 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 \cite{bbt}.
1 Introduction, Definition of “Relative-Smoothness,” and Basic Properties
Standard first-order guarantees rely on uniform gradient smoothness, which can be unsuitable for convex functions whose curvature varies widely. The paper replaces this requirement with relative smoothness and relative strong convexity defined through a reference function, and extends primal-gradient and dual-averaging methods.
- Relative smoothness: The Bregman distance D_h(y,x)=h(y)−h(x)−⟨∇h(x),y−x⟩ provides the reference-function geometry used in these definitions.The paper introduces h as a reference function and defines relative properties using its associated Bregman distance.
- Motivation: Uniform Lipschitz-gradient assumptions can be impractical for functions whose second-order behavior varies dramatically, including −ln(x)+x^2, where L_f≈exp20 on a level set.The paper gives D-optimal design, |x|^3, and x^4 as additional examples lacking uniform smoothness.
- Relative smoothness: Relative smoothness and relative strong convexity define f relative to a user-specified differentiable convex reference function h, without requiring a particular norm.The reference function need not itself be strictly or strongly convex.
- Algorithms: The paper extends primal gradient and dual averaging schemes, deriving computational guarantees and linear convergence when relative smoothness and relative strong convexity both hold.The analysis includes a primal-gradient theorem and a dual-averaging theorem under their respective relative conditions.
- Basic properties: Relative smoothness and strong convexity are preserved under suitable nonnegative sums and linear transformations, supporting construction of tractable reference functions.The stated propositions combine component functions with weighted reference functions.
- Basic properties: Equivalent characterizations relate relative smoothness and relative strong convexity to convexity of function differences and, under twice differentiability, to Hessian conditions.The proposition also gives equivalent gradient-inner-product conditions.
2 Examples of Relatively Smooth Optimization Problems
The paper constructs simple reference functions that make broad classes of non-uniformly smooth convex problems relatively smooth and keep the resulting subproblems tractable. Applications include polynomial-growth objectives, D-optimal design, and generalized volumetric barriers.
- Reference functions can be constructed so that relative smoothness is easily determined and the associated subproblem is efficiently solvable.
- 2.1 Optimization over R^n with ∥∇2f(x)∥ growing as a polynomial in ∥x∥2: For polynomially growing Hessians, Proposition 2.1 bounds the relative-smoothness constant using an r-degree polynomial majorant and a reference function based on ∥x∥2.
- 2.1 Optimization over R^n with ∥∇2f(x)∥ growing as a polynomial in ∥x∥2: Virtually every twice-differentiable convex function on R^n is relatively smooth with respect to some simple polynomial function of ∥x∥2.
- 2.1 Optimization over R^n with ∥∇2f(x)∥ growing as a polynomial in ∥x∥2: The polynomial-growth examples admit efficiently solvable subproblems, including scalar root-finding and one-dimensional convex optimization after projection constraints are incorporated.
- 2.2 D-Optimal Design Problem: For D-optimal design on the simplex, the logarithmic barrier is 1-smooth relative to the objective, and the subproblem reduces to finding a unique scalar root efficiently.
- 2.3 Generalized Volumetric Function Optimization: The generalized volumetric function f_p is p(p + 1)-smooth relative to the logarithmic reference function on the simplex.
- A simple reference function also provides relative smoothness when gradients grow near the open boundary, despite the absence of uniform Lipschitz continuity on Q.
3 Computational Analysis for the Primal Gradient Scheme and the Dual Averaging Scheme
The paper extends primal gradient and dual averaging schemes to relative smoothness, deriving sublinear and linear convergence guarantees under relative smoothness and strong convexity.
- Primal Gradient Scheme: Theorem 3.1 establishes monotonic decrease and convergence bounds for the Primal Gradient Scheme when f is relatively smooth and relatively strongly convex.The result applies for L > 0 and μ ≥ 0.
- Primal Gradient Scheme: μ > 0 yields linear convergence for the Primal Gradient Scheme, while μ = 0 yields an O(1/k) sublinear rate.The linear and sublinear cases follow from the two inequalities in the theorem’s bound.
- Primal Gradient Scheme: The Primal Gradient Scheme avoids the symmetry measure α used in related analyses and uses a 1/L update instead of the smaller (1 + α)/2L step-size.The paper contrasts this with the NoLips analysis, whose guarantee depends on α.
- Primal Gradient Scheme: The analysis uses the Three-Point Property, relative smoothness, and relative strong convexity to derive the descent inequality and monotonicity.Substituting x = x_i−1 shows f(x_i) ≤ f(x_i−1).
- Dual Averaging Scheme: Dual Averaging requires the strong-convexity coefficient μ for implementation, although μ can conservatively be set to zero when unavailable.Its update also requires solving a subproblem of the same form as the primal scheme’s subproblem.
- Dual Averaging Scheme: Theorem 3.2 gives Dual Averaging convergence guarantees when f is relatively smooth and relatively strongly convex with L > μ.Its first inequality likewise gives linear convergence when μ > 0.
4 D-Optimal Design Revisited: Computational Guarantees using the Primal Gradient or Dual Averaging Scheme
The paper applies its general primal-gradient and dual-averaging guarantees to D-optimal design, obtaining computational bounds under relative smoothness. These methods offer general-theory guarantees, although their bounds are inferior to the specialized Frank-Wolfe analysis.
- D-Optimal Design Setup: D-optimal design uses f(x) = −ln det(HXH^T) on Q = ∆n, with f 1-smooth relative to a logarithmic barrier.The subproblem required by the schemes is efficiently solvable.
- Dual Averaging Guarantee: The Dual Averaging Scheme obtains the identical bound, with the final quantity being mini=1,...,k f(xi) − f∗ rather than the last iterate's gap.The proof follows the same logic because the relevant Bregman and reference-function differences coincide here.
- Comparison with Frank-Wolfe: The Primal Gradient and Dual Averaging bounds can be inferior to Frank-Wolfe's specialized D-optimal-design guarantee, but they arise from a general theory applicable to the problem.The comparison emphasizes a trade-off between generality and specialized computational performance.
A.1 Solving the subproblem (9) when h(x) is a convex function of ∥x∥2
The subproblem can be reduced to one-dimensional concave maximization when Euclidean projection onto Q and the univariate conjugate of the reference function are tractable.
- Scalar Reduction: When h(x) is a convex function of ∥x∥2^2, introduce y = ∥x∥2^2 and define the corresponding scalar domain D.The construction treats the reference term through a univariate convex function g.
- Conjugate Reformulation: Convex conjugacy represents g(y) as the supremum over t of ty − g∗(t), enabling reformulation of the subproblem.The reformulation depends on exchanging minimization and supremum under a strong-duality-like condition.
- Computational Condition: The resulting subproblem is one-dimensional concave maximization if Euclidean projection onto Q is easy and g∗ can be conveniently formed and evaluated.Thus computational tractability depends on both the projection oracle and the univariate conjugate.
A.2 Extension to Composite Optimization
The paper extends relative-smoothness analysis and the Primal Gradient Scheme to composite objectives by incorporating a nonsmooth term through subgradients and modified Bregman distances.
- Composite Formulation: For composite optimization, define f̄(x) = f(x) + P(x) and h̄(x) = Lh(x) + P(x), which may be nondifferentiable because of P.Relative smoothness is defined using the equivalent subgradient condition.
- Algorithmic Update: Using the same subgradient gP(x) in f̄ and h̄ cancels it from the Primal Gradient update, so it need not be computed explicitly.The resulting update coincides with NoLips and PGA-B up to the step-size.
- Surrogate Subproblem: The composite surrogate is si(x) = f(xi) + ⟨∇f(xi), x − xi⟩ + LDh(x, xi) + P(x), and xi+1 minimizes this surrogate over Q.This surrogate underlies the generalized computational guarantee.
- Proof Extension: Subgradients at successive iterates are specified from the surrogate's optimality conditions and used to define the composite subgradients and Bregman distance.The proof then uses a specialized Three Point Property for composite optimization.
- Guarantee: The proof of the Primal Gradient computational guarantee extends by replacing the smooth quantities with their composite counterparts and using relation (45).This directly transfers Theorem 3.1 to the composite setting.
A.3 Criteria for choosing the reference function h(·)
Choosing a reference function balances a tighter convergence bound against the computational difficulty of solving the associated subproblem.
- Bound Quality: For a twice-differentiable objective with µ = 0, reducing the Hessian of Lh − f can reduce the convergence bound.Because the optimum is generally unknown, the criterion is to make this Hessian small throughout int Q.
- Trade-off: Choosing Lh = f makes the gap Hessian zero, but solving the subproblem becomes as hard as solving the original optimization problem.This is the tight-bound extreme of the reference-function trade-off.
- Trade-off: The quadratic reference function used in standard gradient descent makes the subproblem easy but can leave the gap Hessian huge, producing a poorer convergence bound.This is the tractable but potentially loose-bound extreme.
- Preconditioning: Preconditioning uses h(x) = 1/2⟨x, Bx⟩ with a computationally friendly positive-definite matrix B, typically diagonal.The design criteria are easy equations with B and closeness of B to the Hessian of f.