PPubMed31 May 2024

Primal Subgradient Methods with Predefined Step Sizes

Yurii Nesterov

Abstract

In this paper, we suggest a new framework for analyzing primal subgradient methods for nonsmooth convex optimization problems. We show that the classical step-size rules, based on normalization of subgradient, or on knowledge of the optimal value of the objective function, need corrections when they are applied to optimization problems with constraints. Their proper modifications allow a significant acceleration of these schemes when the objective function has favorable properties (smoothness, strong convexity). We show how the new methods can be used for solving optimization problems with functional constraints with a possibility to approximate the optimal Lagrange multipliers. One of our primal-dual methods works also for unbounded feasible set.

§ The Valyu brief

The paper, in five minutes

Read from the full text via Valyu Contents

A new framework corrects classical step-size rules for constrained nonsmooth convex optimization, accelerating primal subgradient methods and enabling Lagrange multiplier approximation.

What’s new

i.Introduces a new analytical framework for primal subgradient methods applied to nonsmooth convex problems with constraints
ii.Provides corrected step-size rules that significantly accelerate convergence when the objective has smoothness or strong convexity
iii.Shows how the methods solve functional‑constraint problems and can approximate optimal Lagrange multipliers
iv.Presents a primal‑dual method that remains valid for unbounded feasible sets

How they did it

The authors define the algorithms using a predefined strongly convex prox‑function and derive step‑size parameters by solving explicit equations for the dual step‑size λ_k. Convergence is proved through a series of lemmas and theorems that bound Bregman distances and directional proximity measures, yielding explicit complexity formulas. Numerical complexity bounds are obtained by fixing the total number of iterations N and choosing step sizes h_k = R_0/√(N+1).

What they found

With step size h = R_0/√(N+1) the minimal directional proximity satisfies δ*_N ≤ R_0/√(N+1)
Theorem 1 gives F_k ≤ F_* + (L_ν r_0^{1+ν}/(1+ν))·(1/k)^{(1+ν)/2} for Hölder‑continuous gradients
Theorem 5 guarantees f_i(x_k) ≤ M_i·h_{kN} for each constraint i
Theorem 8 shows the primal‑dual gap f_0^{*N}−φ^* ≤ M_0·h_{kN}

Caveats

✕The convexity of the Bregman distance in its first argument (required for Lemma 6) is not common and holds only for specific prox‑functions
✕Existence of an optimal dual solution is not guaranteed; when it fails the dual approximation quality can degrade
✕Evaluating the dual function φ(λ) may be as costly as solving the original problem, limiting practical use
✕The analysis assumes knowledge of constants such as R_0, L_ν, M_i and a bound D on the Bregman distance, which may be unavailable in some applications

§ The Valyu brief

Reading the full paper and taking notes. This takes a few seconds…

§ Ask this paper

Ask a question about this paper

Valyu reads the full text and answers from what the paper actually says.

§ Related work in other archives

Primal Subgradient Methods with Predefined Step Sizes

The paper, in five minutes

Ask a question about this paper

Similar papers in all four archives

Similar papers in all four archives

The paper, in five minutes