Dual subgradient algorithms for large-scale nonsmooth learning problems
From MaRDI portal
Abstract: "Classical" First Order (FO) algorithms of convex optimization, such as Mirror Descent algorithm or Nesterov's optimal algorithm of smooth convex optimization, are well known to have optimal (theoretical) complexity estimates which do not depend on the problem dimension. However, to attain the optimality, the domain of the problem should admit a "good proximal setup". The latter essentially means that 1) the problem domain should satisfy certain geometric conditions of "favorable geometry", and 2) the practical use of these methods is conditioned by our ability to compute at a moderate cost {em proximal transformation} at each iteration. More often than not these two conditions are satisfied in optimization problems arising in computational learning, what explains why proximal type FO methods recently became methods of choice when solving various learning problems. Yet, they meet their limits in several important problems such as multi-task learning with large number of tasks, where the problem domain does not exhibit favorable geometry, and learning and matrix completion problems with nuclear norm constraint, when the numerical cost of computing proximal transformation becomes prohibitive in large-scale problems. We propose a novel approach to solving nonsmooth optimization problems arising in learning applications where Fenchel-type representation of the objective function is available. The approach is based on applying FO algorithms to the dual problem and using the {em accuracy certificates} supplied by the method to recover the primal solution. While suboptimal in terms of accuracy guaranties, the proposed approach does not rely upon "good proximal setup" for the primal problem but requires the problem domain to admit a Linear Optimization oracle -- the ability to efficiently maximize a linear form on the domain of the primal problem.
Recommendations
Cites work
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 3493797 (Why is no real title available?)
- scientific article; zbMATH DE number 3244852 (Why is no real title available?)
- scientific article; zbMATH DE number 3296905 (Why is no real title available?)
- scientific article; zbMATH DE number 3345848 (Why is no real title available?)
- scientific article; zbMATH DE number 3192366 (Why is no real title available?)
- 10.1162/15324430260185628
- Accuracy certificates for computational problems with convex structure
- Conditional gradient algorithms with open loop step size rules
- Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
- Dual extrapolation and its applications to solving variational inequalities and related problems
- Dualization of signal recovery problems
- High-dimensional covariance matrix estimation in approximate factor models
- Introductory lectures on convex optimization. A basic course.
- New variants of bundle methods
- Non-Euclidean restricted memory level method for large-scale convex optimization
- On first-order algorithms for \(\ell_{1}/\)nuclear norm minimization
- Primal-dual subgradient methods for convex problems
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- Proximité et dualité dans un espace hilbertien
- Smooth minimization of non-smooth functions
Cited in
(15)- The cyclic block conditional gradient method for convex optimization problems
- Data-driven nonsmooth optimization
- Decomposition techniques for bilinear saddle point problems and variational inequalities with affine monotone operators
- Hessian barrier algorithms for linearly constrained optimization problems
- Conditional gradient sliding for convex optimization
- Unifying mirror descent and dual averaging
- Semi-inner-products for convex functionals and their use in image decomposition
- Conditional gradient algorithms for norm-regularized smooth convex optimization
- First-order methods for convex optimization
- New results on subgradient methods for strongly convex optimization problems with a unified analysis
- All-in-one robust estimator of the Gaussian mean
- Solving variational inequalities with monotone operators on domains given by linear minimization oracles
- Level-set methods for convex optimization
- Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs
- Duality between subgradient and conditional gradient methods
This page was built for publication: Dual subgradient algorithms for large-scale nonsmooth learning problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q484132)
