Analyzing and Improving Greedy 2-Coordinate Updates for Equality-Constrained Optimization via Steepest Descent in the 1-Norm

We consider minimizing a smooth function subject to a summation constraint over its variables. By exploiting a connection between the greedy 2-coordinate update for this problem and equality-constrained steepest descent in the 1-norm, we give a convergence rate for greedy selection under a proximal...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-07
Main Authors: Ramesh, Amrutha Varshini, Mishkin, Aaron, Schmidt, Mark, Zhou, Yihan, Jonathan Wilder Lavington, She, Jennifer
Format: Article
Language:English
Subjects:
Constraints
Iterative methods
Optimization
Support vector machines
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider minimizing a smooth function subject to a summation constraint over its variables. By exploiting a connection between the greedy 2-coordinate update for this problem and equality-constrained steepest descent in the 1-norm, we give a convergence rate for greedy selection under a proximal Polyak-Lojasiewicz assumption that is faster than random selection and independent of the problem dimension \(n\). We then consider minimizing with both a summation constraint and bound constraints, as arises in the support vector machine dual problem. Existing greedy rules for this setting either guarantee trivial progress only or require \(O(n^2)\) time to compute. We show that bound- and summation-constrained steepest descent in the L1-norm guarantees more progress per iteration than previous rules and can be computed in only \(O(n \log n)\) time.
ISSN:2331-8422