On solving large-scale polynomial convex problems by randomized first-order algorithms
From MaRDI portal
Abstract: One of the most attractive recent approaches to processing well-structured large-scale convex optimization problems is based on smooth convex-concave saddle point reformu-lation of the problem of interest and solving the resulting problem by a fast First Order saddle point method utilizing smoothness of the saddle point cost function. In this paper, we demonstrate that when the saddle point cost function is polynomial, the precise gra-dients of the cost function required by deterministic First Order saddle point algorithms and becoming prohibitively computationally expensive in the extremely large-scale case, can be replaced with incomparably cheaper computationally unbiased random estimates of the gradients. We show that for large-scale problems with favourable geometry, this randomization accelerates, progressively as the sizes of the problem grow, the solution process. This extends significantly previous results on acceleration by randomization, which, to the best of our knowledge, dealt solely with bilinear saddle point problems. We illustrate our theoretical findings by instructive and encouraging numerical experiments.
Recommendations
- A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems
- A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio
- Randomized first order algorithms with applications to \(\ell _{1}\)-minimization
- First-order methods in large-scale semidefinite optimization.
- Large-scale convex optimization via saddle point computation
Cites work
- A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems
- A sublinear-time randomized approximation algorithm for matrix games
- Efficiency of coordinate descent methods on huge-scale optimization problems
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 5485455 (Why is no real title available?)
- On first-order algorithms for \(\ell_{1}/\)nuclear norm minimization
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Randomized first order algorithms with applications to \(\ell _{1}\)-minimization
- Robust Stochastic Approximation Approach to Stochastic Programming
- Smooth minimization of non-smooth functions
- Solving variational inequalities with stochastic mirror-prox algorithm
Cited in
(7)- Randomized first order algorithms with applications to \(\ell _{1}\)-minimization
- First-order methods in large-scale semidefinite optimization.
- Online first-order framework for robust convex optimization
- Memory-efficient structured convex optimization via extreme point sampling
- An accelerated first-order method for solving SOS relaxations of unconstrained polynomial optimization problems
- Unifying framework for accelerated randomized methods in convex optimization
- Aggregating regular norms
This page was built for publication: On solving large-scale polynomial convex problems by randomized first-order algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5252231)
