Nonsmooth Optimization

Preconditioned subgradient method for composite optimization: overparameterization and fast convergence

Categories Nonlinear Optimization, Nonsmooth Optimization, Optimization in Data Science Tags , , , ,

Composite optimization problems involve minimizing the composition of a smooth map with a convex function. Such objectives arise in numerous data science and signal processing applications, including phase retrieval, blind deconvolution, and collaborative filtering. The subgradient method achieves local linear convergence when the composite loss is well-conditioned. However, if the smooth map is, in a … Read more

Accelerated proximal gradient algorithm for weakly convex function

Categories Nonlinear Optimization, Nonsmooth Optimization, Unconstrained Optimization Tags , , , ,

In this work, we investigate the accelerated proximal gradient algorithm (APGα) for weakly convex composite optimization problems. Building upon the framework of B¨ohm and Wright, and additionally assuming that f is convex and coercive while g is bounded below, we establish an objective residual convergence rate of O(1⁄j²) for α≥3. Moreover, when α›3, this rate … Read more

A Simple Adaptive Proximal Gradient Method for Nonconvex Optimization

Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

Consider composite nonconvex optimization problems where the objective function consists of a smooth nonconvex term (with Lipschitz-continuous gradient) and a convex (possibly nonsmooth) term. Existing parameter-free methods for such problems often rely on complex multi-loop structures, require line searches, or depend on restrictive assumptions (e.g., bounded iterates). To address these limitations, we introduce a novel … Read more

On the Convergence and Properties of a Proximal-Gradient Method on Hadamard Manifolds

Categories Constrained Nonlinear Optimization, Global Optimization Theory, Nonsmooth Optimization Tags , , ,

In this paper, we address composite optimization problems on Hadamard manifolds, where the objective function is given by the sum of a smooth term (not necessarily convex) and a convex term (not necessarily differentiable). To solve this problem, we develop a proximal gradient method defined directly on the manifold, employing a strategy that enforces monotonicity … Read more

Optimal diagonal preconditioning beyond worst-case conditioning: theory and practice of omega scaling

Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization, Optimization in Data Science Tags , , , ,

Preconditioning is essential in many areas of mathematics, and in particular is a fundamental tool for accelerating iterative methods for solving linear systems. In this work, we study optimal diagonal preconditioning under two distinct notions of conditioning: the classical worst-case \(\kappa\)-condition number and the averaging-based \(\omega\)-condition number. We observe that \(\omega\)-optimal preconditioning generally outperforms \(\kappa\)-optimal … Read more

Approximating inequality systems within probability functions: studying implications for problems and consistency of first-order information

Categories Nonsmooth Optimization, Stochastic Programming Tags , , , ,

In this work, we are concerned with the study of optimization problems featuring so-called probability or chance constraints. Probability constraints measure the level of satisfaction of an underlying random inequality system and ensure that this level is high enough. Such an underlying inequality system could be expressed by an abstractly known or perhaps costly to … Read more

On the convergence rate of the Douglas-Rachford splitting algorithm

Categories Complementarity and Variational Inequalities, Convex Optimization, Nonsmooth Optimization Tags , ,

This work is concerned with the convergence rate analysis of the Dou- glas–Rachford splitting (DRS) method for finding a zero of the sum of two maximally monotone operators. We obtain an exact rate of convergence for the DRS algorithm and demonstrate its sharpness in the setting of convex feasibility problems. Further- more, we investigate the … Read more

Alternating Iteratively Reweighted \(\ell_1\) and Subspace Newton Algorithms for Nonconvex Sparse Optimization

Categories Nonlinear Optimization, Nonsmooth Optimization Tags , ,

This paper presents a novel hybrid algorithm for minimizing the sum of a continuously differentiable loss function and a nonsmooth, possibly nonconvex, sparsity‑promoting regularizer. The proposed method adaptively switches between solving a reweighted \(\ell_1\)-regularized subproblem and performing an inexact subspace Newton step. The reweighted \(\ell_1\)-subproblem admits an efficient closed-form solution via the soft-thresholding operator, thereby … Read more

Online Convex Optimization with Heavy Tails: Old Algorithms, New Regrets, and Applications

Categories Convex Optimization, Nonsmooth Optimization Tags , ,

In Online Convex Optimization (OCO), when the stochastic gradient has a finite variance, many algorithms provably work and guarantee a sublinear regret. However, limited results are known if the gradient estimate has a heavy tail, i.e., the stochastic gradient only admits a finite \(\mathsf{p}\)-th central moment for some \(\mathsf{p}\in\left(1,2\right]\). Motivated by it, this work examines … Read more