# Huber Loss-Based Penalty Approach to Problems with Linear Constraints

arXiv: https://arxiv.org/abs/2311.00874 · HTML: https://mlsanity.com/paper/2311.00874/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Nov 2023.

## Built on by (most cited first, 2 of 2)

- [A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization](https://mlsanity.com/paper/2501.19214/) (2025)
- [Randomized Feasibility Methods for Constrained Optimization with Adaptive Step Sizes](https://mlsanity.com/paper/2601.20076/) (2026)

## Abstract (arXiv)

We consider a convex optimization problem with many linear inequality constraints. To deal with a large number of constraints, we provide a penalty reformulation of the problem, where the penalty is a variant of the one-sided Huber loss function with two penalty parameters. We study the infeasibility properties of the solutions of penalized problems for nonconvex and convex objective functions, as the penalty parameters vary with time. Then, we propose a random incremental penalty method for solving the original problem, and investigate its convergence properties for convex and strongly convex objective functions. We show that the iterates of the method converge to a solution of the original problem almost surely and in expectation for suitable choices of the penalty parameters and the stepsize. Also, we establish convergence rate of the method in terms of the expected function values by utilizing appropriately defined weighted averages of the iterates. We show O(ln1/2+ε k/√ k)-convergence rate when the objective function is convex and O(lnε k/k)-convergence rate when the objective function is strongly convex, with ε>0 being an arbitrarily small scalar.  To the best of our knowledge, these are the first results on the convergence rate for the penalty-based incremental subgradient method with time-varying penalty parameters.