First-order methods for stochastic and finite-sum convex optimization with deterministic constraints
Organizations: Department of Industrial and Systems Engineering, University of Minnesota, USA
Abstract
In this paper, we study a class of stochastic and finite-sum convex optimization problems with deterministic constraints. Existing methods typically aim to find an - solution, in which both the expected constraint violation and the expected optimality gap are within a prescribed tolerance . However, in many practical applications, constraints must be nearly satisfied with certainty, rendering such solutions potentially unsuitable due to the risk of substantial violations. To address this issue, we propose stochastic first-order methods for finding an - (-SFSO) solution, where the constraint violation is deterministically bounded by and the expected optimality gap is at most . Our methods apply an accelerated stochastic gradient (ASG) scheme or a modified variance-reduced ASG scheme to a sequence of quadratic penalty subproblems with appropriately chosen penalty parameters. We establish first-order oracle complexity bounds for the proposed methods in computing an -SFSO solution. Preliminary numerical results are presented to illustrate the performance of the proposed methods.
Figures & tables
| Sample space | Method | Penalty scheme | -EFSO complexity | -SFSO complexity |
|---|---|---|---|---|
| Infinite | Alg. 1 | constant ( ) | ||
| Infinite | Alg. 1 | dynamic ( ) | ||
| Finite | Alg. 2 | constant ( ) | ||
| Finite | Alg. 2 | constant ( ) | ||
| Finite | Alg. 2 | dynamic, eq. ( 32 ) | ||
| Finite | Alg. 2 | dynamic, eq. ( 38 ) |
Stochastic Optimization
Stochastic optimization studies how to find good decisions or model parameters when objectives, data, or feedback are random or noisy.
See all 226 papers