# Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal Oracle

arXiv: https://arxiv.org/abs/2210.13968 · HTML: https://mlsanity.com/paper/2210.13968/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 52 references that are in the map.
- First posted on arXiv 25 Oct 2022.

## Builds on (most cited first, 14 of 14)

- [Beyond a Gaussian Denoiser: Residual Learning of Deep CNN for Image Denoising](https://mlsanity.com/paper/1608.03981/) (2016)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls](https://mlsanity.com/paper/1708.02105/) (2017)
- [Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functions](https://mlsanity.com/paper/1504.05002/) (2015)
- [The proximal augmented Lagrangian method for nonsmooth composite optimization](https://mlsanity.com/paper/1610.04514/) (2016)
- [A Conditional Gradient-Based Augmented Lagrangian Framework](https://mlsanity.com/paper/1901.04013/) (2019)
- [Faster Projection-free Convex Optimization over the Spectrahedron](https://mlsanity.com/paper/1605.06203/) (2016)
- [On the non-ergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming](https://mlsanity.com/paper/1603.05738/) (2016)
- [Frank-Wolfe Splitting via Augmented Lagrangian Method](https://mlsanity.com/paper/1804.03176/) (2018)
- [Improved Complexities of Conditional Gradient-Type Methods with Applications to Robust Matrix Recovery Problems](https://mlsanity.com/paper/1802.05581/) (2018)
- [Generalized Conditional Gradient with Augmented Lagrangian for Composite Minimization](https://mlsanity.com/paper/1901.01287/) (2019)
- [Fast Stochastic Algorithms for Low-rank and Nonsmooth Matrix Problems](https://mlsanity.com/paper/1809.10477/) (2018)
- [On the simplicity and conditioning of low rank semidefinite programs](https://mlsanity.com/paper/2002.10673/) (2020)
- [Logarithmic Regret for Online Gradient Descent Beyond Strong Convexity](https://mlsanity.com/paper/1802.04623/) (2018)

## Built on by (most cited first, 3 of 3)

- [First-Order Sparse Convex Optimization: Better Rates with Sparse Updates](https://mlsanity.com/paper/2506.19075/) (2025)
- [Low-Rank Extragradient Methods for Scalable Semidefinite Optimization](https://mlsanity.com/paper/2402.09081/) (2024)
- [Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization](https://mlsanity.com/paper/2609.24423/) (2026)

## Abstract (arXiv)

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 textitprojection-free augmented Lagrangian-based method, in which primal updates are carried out using a textitweak proximal oracle (WPO). In an earlier work, WPO was shown to be more powerful than the standard textitlinear 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/√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 that of our method can outperform state-of-the-art LMO-based Lagrangian-based methods.