REVIEW 5 cited by
Algorithms for stochastic optimization with functional or expectation constraints
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
This paper considers the problem of minimizing an expectation function over a closed convex set, coupled with a {\color{black} functional or expectation} constraint on either decision variables or problem parameters. We first present a new stochastic approximation (SA) type algorithm, namely the cooperative SA (CSA), to handle problems with the constraint on devision variables. We show that this algorithm exhibits the optimal ${\cal O}(1/\epsilon^2)$ rate of convergence, in terms of both optimality gap and constraint violation, when the objective and constraint functions are generally convex, where $\epsilon$ denotes the optimality gap and infeasibility. Moreover, we show that this rate of convergence can be improved to ${\cal O}(1/\epsilon)$ if the objective and constraint functions are strongly convex. We then present a variant of CSA, namely the cooperative stochastic parameter approximation (CSPA) algorithm, to deal with the situation when the constraint is defined over problem parameters and show that it exhibits similar optimal rate of convergence to CSA. It is worth noting that CSA and CSPA are primal methods which do not require the iterations on the dual space and/or the estimation on the size of the dual variables. To the best of our knowledge, this is the first time that such optimal SA methods for solving functional or expectation constrained stochastic optimization are presented in the literature.
Forward citations
Cited by 5 Pith papers
-
Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization
An inexact proximal-point penalty algorithm finds ε-stationary points of non-convex constrained problems in O~(ε^{-5/2}) steps with convex constraints and O~(ε^{-3}) to O~(ε^{-4}) steps with non-convex constraints.
-
Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimization
ConEx, a single-loop primal-dual method with constraint extrapolation, achieves best-known convergence rates for convex functional constrained problems, and a proximal point method achieves O(1/ε) complexity to approx...
-
First-Order Softmax Weighted Switching Gradient Method for Distributed Stochastic Minimax Optimization with Stochastic Constraints
A single-loop softmax-weighted switching-gradient method solves constrained federated minimax problems at Õ(ε^{-4}) oracle complexity with high-probability guarantees and partial-participation analysis.
-
A Data Efficient and Feasible Level Set Method for Stochastic Convex Optimization with Expectation Constraints
A stochastic feasible level-set method maintains a high-probability feasible solution path for convex optimization with expectation constraints, with iteration complexity comparable to stochastic subgradient methods.
-
Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints
A proximally constrained subgradient method finds a nearly stationary point for weakly convex objectives with weakly convex constraints in O(1/epsilon^4) deterministic and O~(1/epsilon^6) stochastic iterations.
Discussion (0). Continue with ORCID to comment.