Efficient Projection-Free Algorithms for Saddle Point Problems
- URL: http://arxiv.org/abs/2010.11737v1
- Date: Wed, 21 Oct 2020 15:05:53 GMT
- Title: Efficient Projection-Free Algorithms for Saddle Point Problems
- Authors: Cheng Chen, Luo Luo, Weinan Zhang, Yong Yu
- Abstract summary: We study projection-free algorithms for convex-strongly-concave saddle point problems with complicated constraints.
Our method combines Conditional Gradient Sliding with Mirror-Prox and shows that it only requires $tildeO (1/sqrtepsilon)$ evaluations and $tildeO (1/epsilon2)$ linear optimizations in the batch setting.
- Score: 39.88460595129901
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Frank-Wolfe algorithm is a classic method for constrained optimization
problems. It has recently been popular in many machine learning applications
because its projection-free property leads to more efficient iterations. In
this paper, we study projection-free algorithms for convex-strongly-concave
saddle point problems with complicated constraints. Our method combines
Conditional Gradient Sliding with Mirror-Prox and shows that it only requires
$\tilde{O}(1/\sqrt{\epsilon})$ gradient evaluations and
$\tilde{O}(1/\epsilon^2)$ linear optimizations in the batch setting. We also
extend our method to the stochastic setting and propose first stochastic
projection-free algorithms for saddle point problems. Experimental results
demonstrate the effectiveness of our algorithms and verify our theoretical
guarantees.
Related papers
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries.
We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
arXiv Detail & Related papers (2024-06-28T02:56:22Z) - Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
This paper presents a subgradient-based algorithm for constrained nonsmooth convex computation.
Our proposed algorithm can handle nonsmooth problems with general convex functional inequality constraints.
Similar performance is observed when deterministic subgradients are replaced with subgradients.
arXiv Detail & Related papers (2023-11-18T23:06:33Z) - Projection-Free Online Convex Optimization via Efficient Newton
Iterations [10.492474737007722]
This paper presents new projection-free algorithms for Online Convex Optimization (OCO) over a convex domain $mathcalK subset mathbbRd$.
arXiv Detail & Related papers (2023-06-19T18:48:53Z) - Projection-free Adaptive Regret with Membership Oracles [31.422532403048738]
Most iterative algorithms require the computation of projections onto convex sets, which can be computationally expensive.
Recent work by GK22 gave sublinear adaptive regret guarantees with projection free algorithms based on the Frank Wolfe approach.
We give projection-free algorithms that are based on a different technique, inspired by Mhammedi22, that replaces projections by set-membership computations.
arXiv Detail & Related papers (2022-11-22T23:53:06Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary.
Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
arXiv Detail & Related papers (2021-06-02T22:03:36Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
We propose a new algorithm -- the Momentum- Single-timescale Approximation (MSTSA) -- for tackling problems.
MSTSA allows us to control the error in iterations due to inaccurate solution to the lower level subproblem.
arXiv Detail & Related papers (2021-02-15T07:10:33Z) - Towards an efficient approach for the nonconvex $\ell_p$ ball
projection: algorithm and analysis [3.4693390973571594]
This paper primarily focuses on computing the Euclidean projection of a vector onto the $ell_p$ ball in which $pin(0,1)$.
We develop a novel numerical approach for computing the stationary point through solving a sequence of projections onto the reweighted $ell_1$-balls.
The proposed algorithm is shown to converge uniquely under mild conditions and has a worst-case $O(1/sqrtk)$ convergence rate.
arXiv Detail & Related papers (2021-01-05T04:51:12Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
Bilevel optimization is a class of problems which exhibit a two-level structure.
We propose a two-timescale approximation (TTSA) algorithm for tackling such a bilevel problem.
We show that a two-timescale natural actor-critic policy optimization algorithm can be viewed as a special case of our TTSA framework.
arXiv Detail & Related papers (2020-07-10T05:20:02Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
We study the problem of zero-order optimization of a strongly convex function.
We consider a randomized approximation of the projected gradient descent algorithm.
Our results imply that the zero-order algorithm is nearly optimal in terms of sample complexity and the problem parameters.
arXiv Detail & Related papers (2020-06-14T10:42:23Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.