Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal
Oracle
- URL: http://arxiv.org/abs/2210.13968v1
- Date: Tue, 25 Oct 2022 12:51:43 GMT
- Title: Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal
Oracle
- Authors: Dan Garber, Tsur Livney, Shoham Sabac
- Abstract summary: This paper considers a convex composite optimization problem with affine constraints.
Motivated by high-dimensional applications in which exact projection/proximal computations are not tractable, we propose a textitprojection-free augmented Lagrangian-based method.
- Score: 16.290192687098383
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers a convex composite optimization problem with affine
constraints, which includes problems that take the form of minimizing a smooth
convex objective function over the intersection of (simple) convex sets, or
regularized with multiple (simple) functions. Motivated by high-dimensional
applications in which exact projection/proximal computations are not tractable,
we propose a \textit{projection-free} augmented Lagrangian-based method, in
which primal updates are carried out using a \textit{weak proximal oracle}
(WPO). In an earlier work, WPO was shown to be more powerful than the standard
\textit{linear minimization oracle} (LMO) that underlies conditional
gradient-based methods (aka Frank-Wolfe methods). Moreover, WPO is
computationally tractable for many high-dimensional problems of interest,
including those motivated by recovery of low-rank matrices and tensors, and
optimization over polytopes which admit efficient LMOs. The main result of this
paper shows that under a certain curvature assumption (which is weaker than
strong convexity), our WPO-based algorithm achieves an ergodic rate of
convergence of $O(1/T)$ for both the objective residual and feasibility gap.
This result, to the best of our knowledge, improves upon the $O(1/\sqrt{T})$
rate for existing LMO-based projection-free methods for this class of problems.
Empirical experiments on a low-rank and sparse covariance matrix estimation
task and the Max Cut semidefinite relaxation demonstrate the superiority of our
method over state-of-the-art LMO-based Lagrangian-based methods.
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) - Developing Lagrangian-based Methods for Nonsmooth Nonconvex Optimization [2.7998963147546148]
We develop a framework for developing Lagrangian-based methods.
We show that our framework can be extended to solve constrained problems with expectation constraints.
arXiv Detail & Related papers (2024-04-15T03:50:47Z) - Low-Rank Extragradient Methods for Scalable Semidefinite Optimization [0.0]
We focus on high-dimensional and plausible settings in which the problem admits a low-rank solution.
We provide several theoretical results proving that, under these circumstances, the well-known Extragradient method converges to a solution of the constrained optimization problem.
arXiv Detail & Related papers (2024-02-14T10:48:00Z) - Constrained Bi-Level Optimization: Proximal Lagrangian Value function
Approach and Hessian-free Algorithm [8.479947546216131]
We develop a Hessian-free gradient-based algorithm-termed proximal Lagrangian Value function-based Hessian-free Bi-level Algorithm (LV-HBA)
LV-HBA is especially well-suited for machine learning applications.
arXiv Detail & Related papers (2024-01-29T13:50:56Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
Many real-world problems have complicated non functional constraints and use a large number of data points.
Our proposed method outperforms an existing method with the previously best-known result.
arXiv Detail & Related papers (2022-12-19T14:48:54Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
We propose a conditional gradient method (CGM) for minimizing convex finite-sum objectives formed as a sum of smooth and non-smooth terms.
The proposed method, equipped with an average gradient (SAG) estimator, requires only one sample per iteration. Nevertheless, it guarantees fast convergence rates on par with more sophisticated variance reduction techniques.
arXiv Detail & Related papers (2022-02-26T19:10:48Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints.
A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual.
This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
arXiv Detail & Related papers (2021-10-20T02:57:21Z) - A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained
Optimization [25.73397307080647]
We present a new model of a general convex or non objective machine machine objectives.
We propose an algorithm that solves a constraint with gradually relaxed point levels of each subproblem.
We demonstrate the effectiveness of our new numerical scale problems.
arXiv Detail & Related papers (2020-10-23T05:24:05Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
We propose two novel conditional gradient-based methods for solving structured convex optimization problems.
The most important feature of our framework is that only a subset of the constraints is processed at each iteration.
Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
arXiv Detail & Related papers (2020-07-07T21:26:35Z) - IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex.
Our approach consists of approximately solving a sequence of sub-problems induced by the accelerated augmented Lagrangian method.
When coupled with accelerated gradient descent, our framework yields a novel primal algorithm whose convergence rate is optimal and matched by recently derived lower bounds.
arXiv Detail & Related papers (2020-06-11T18:49:06Z)
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.