| 1. |
- Dresdner, Gideon, et al.
(författare)
-
Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization
- 2022
-
Ingår i: Proceedings of The 25th International Conference on Artificial Intelligence and Statistics. - : PMLR.
-
Konferensbidrag (refereegranskat)abstract
- We propose a stochastic conditional gradient method (CGM) for minimizing convex finite-sum objectives formed as a sum of smooth and non-smooth terms. Existing CGM variants for this template either suffer from slow convergence rates, or require carefully increasing the batch size over the course of the algorithm's execution, which leads to computing full gradients. In contrast, the proposed method, equipped with a stochastic average gradient (SAG) estimator, requires only one sample per iteration. Nevertheless, it guarantees fast convergence rates on par with more sophisticated variance reduction techniques. In applications we put special emphasis on problems with a large number of separable constraints. Such problems are prevalent among semidefinite programming (SDP) formulations arising in machine learning and theoretical computer science. We provide numerical experiments on matrix completion, unsupervised clustering, and sparsest-cut SDPs.
|
|
| 2. |
- Locatello, Francesco, et al.
(författare)
-
Stochastic Frank-Wolfe for Composite Convex Minimization
- 2019
-
Ingår i: Advances in Neural Information Processing Systems 32 (NeurIPS 2019).
-
Konferensbidrag (refereegranskat)abstract
- A broad class of convex optimization problems can be formulated as a semidefinite program (SDP), minimization of a convex function over the positive-semidefinite cone subject to some affine constraints. The majority of classical SDP solvers are designed for the deterministic setting where problem data is readily available. In this setting, generalized conditional gradient methods (aka Frank-Wolfe-type methods) provide scalable solutions by leveraging the so-called linear minimization oracle instead of the projection onto the semidefinite cone. Most problems in machine learning and modern engineering applications, however, contain some degree of stochasticity. In this work, we propose the first conditional-gradient-type method for solving stochastic optimization problems under affine constraints. Our method guarantees O(k-1/3) convergence rate in expectation on the objective residual and O(k-5/12) on the feasibility gap.
|
|
