This work revisits a variant of the Polyak step-size based on Bregman projections due to Kiwiel (1997), and shows that mirror Polyak enjoys guarantees similar to its Euclidean counterpart, automatically adapting to relative notions of smoothness, Lipschitz continuity, or strong convexity.
Abstract
First-order methods typically require a specific step-size that depends on the regularity conditions of the objective function, such as the smoothness, Lipschitz continuity, or strong convexity constants. The Polyak step-size is a classical alternative for subgradient descent on convex functions that only uses knowledge of the optimal value of the objective function and automatically adapts to the above-mentioned regimes. However, many optimization problems are better described by non-Euclidean geometries and are more amenable to mirror descent. Extending this adaptivity to mirror descent is subtle. Some existing generalizations of the Polyak step-size rely on norms instead of purely on relative geometry, excluding many of the use cases of mirror descent. In this work, we revisit a variant of the Polyak step-size based on Bregman projections due to Kiwiel (1997), which we call mirror Polyak. This method is known to converge asymptotically, but its convergence rate is not known. We show that mirror Polyak enjoys guarantees similar to its Euclidean counterpart, automatically adapting to relative notions of smoothness, Lipschitz continuity, or strong convexity. We then leverage mirror Polyak to avoid having to know the optimal value in some structured optimization problems such as regularized linear and logistic regression. We propose a lifted formulation based on convex duality with optimal value exactly zero and a natural mirror map given by the problem's structure. Mirror Polyak applied to the lifted problem enjoys the same worst-case guarantees as the Polyak step-size in the original problem if we knew the optimal value.
In this paper, we study dual semismooth Newton (SSN) methods for degenerate polyhedral projection problems, where generalized Jacobians of the dual residual may remain singular even arbitrarily close to the solution set. Rather than regularizing these singular systems, we exploit the nonuniqueness of the dual representation. We introduce a primal--dual lifted projection-equivalent set that always possesses extreme points without additional structural assumptions on the polyhedron, and show that its extreme-point geometry identifies dual representatives at which nonsingular generalized Jacobians of the dual residual can be constructed. This geometry is further linked to a full-column-rank condition and a generalized weak strict Robinson constraint qualification, showing that the regularity required by the Newton step can be recovered rather than imposed \emph{a priori}. We also establish displacement bounds that connect representative selection throughout the algorithm with the local Newton mechanism. Building on this variational framework, we develop an inexact dual SSN method with local superlinear convergence and a globalized version combining monotone representative selection with a Wolfe line search. The resulting method is globally convergent and eventually recovers the fast local rate. Numerical experiments on regularized optimal transport, battery-scheduling feasibility restoration, and occupation-measure projection demonstrate its robustness in highly degenerate settings.
This work considers the design of first-order convex optimization algorithms and convergence proofs. In particular, we consider nonsmooth Lipschitz and smooth problems accessed through a subgradient or gradient oracle, respectively. For the general class of fixed-step first-order methods, prior work on Performance Estimation Problems (PEPs) has shown that structured, tight convergence proofs typically exist. Under mild conditions, we further show that any first-order method guaranteeing a bound on the primal objective gap $f(x_N)-f(x_\star)$ assuming only a bound on $\|x_0-x_\star\|$ actually has a stronger guarantee on an explicit, computable primal-dual gap at the same rate. These implicit optimal dual certificates, which take the form of affine lower bounds, also provide insight into the role of auxiliary sequences in momentum methods.
This work can specifically ensure, without any smoothness assumptions, convergence to Mordukhovich stationarity as long as the base directions asymptotically revert to the negative gradient for small stepsizes.
We study online optimization for a broad class of structured non-convex non-smooth problems where each loss is a composition of a difference-of-convex function with a smooth mapping, and the feasible region is defined by constraint functions of the same kind. We propose a time-smoothed proximal linear algorithm and a local-regret measure based on a proximal residual mapping. We show that this residual is a proper stationarity measure for the original problem: its fixed-point condition implies first-order stationarity. Our analysis relies on a tangent-cone characterization for a feasible region described by composite difference-of-convex constraints, which is of independent interest and allows each update to be computed via a convex optimization oracle, despite the non-convexity of the problem. We establish a local-regret bound and a bound on the total number of inner convex subproblems. We also derive an error bound connecting the proximal residual to the distance to stationarity, providing a quantitative certificate of approximate stationarity.
Jingwei Ji, Jong-Shi Pang, Renyuan Xu· 0 citations
We study Langevin-based methods for non-convex optimization under smoothness and dissipativity assumptions. Our focus is on obtaining non-asymptotic bounds for the expected excess risk rather than sampling guarantees for the full target distribution. The key ingredient of our analysis is a direct passage from relative entropy to objective-value error, based on a weighted Csisz\'ar--Kullback--Pinsker inequality and exponential-moment estimates. This avoids intermediate Wasserstein bounds and yields sharper dependence on the Log-Sobolev constant, a quantity that may scale exponentially with the inverse temperature and the dimension in non-convex problems. We first analyze the Unadjusted Langevin Algorithm with exact gradients and derive explicit bounds on $\mathbb{E}[F(x_k)]-\min F$ in terms of the inverse temperature, dimension, stepsize, smoothness and dissipativity parameters, and the Log-Sobolev constant. We then extend the result to an inexact-gradient version of ULA, allowing for biased and stochastic gradient surrogates whose mean-square error grows at most quadratically in the state. This framework covers stochastic gradients and zeroth-order estimators based only on function evaluations. In particular, we show that both Gaussian and spherical finite-difference estimators fit into the inexact-ULA theory and obtain explicit function-evaluation complexity bounds for zeroth-order Langevin optimization. To the best of our knowledge, these are the first non-asymptotic global non-convex optimization complexity bounds for zeroth-order ULA. We also provide numerical experiments illustrating the behavior of the proposed zeroth-order Langevin schemes.
E. Naldi, Marco Rando, Lorenzo Rosasco et al.· 0 citations
This paper proposes a general line-search Newton framework for unconstrained optimization that avoids repeated Hessian regularization by exploiting the Newton direction only when it is well-defined and suitable and provides the first Newton-type algorithm together with a comprehensive convergence analysis for this important class of nonconvex optimization problems.