Videos

Accelerated First-Order Optimization under Nonlinear Constraints

Presenter
July 25, 2023
Abstract
My talk will explore analogies between first-order algorithms for constrained optimization and non-smooth dynamical systems for designing a new class of accelerated first-order algorithms for constrained optimization. Unlike Frank-Wolfe or projected gradients, these algorithms avoid optimization over the entire feasible set at each iteration. I will highlight various convergence results in convex and nonconvex settings and derive rates for the convex setting. An important property of these algorithms is that constraints are expressed in terms of velocities instead of positions, which naturally leads to sparse, local and convex approximations of the feasible set (even if the feasible set is nonconvex). Thus, the complexity tends to grow mildly in the number of decision variables and in the number of constraints, which makes the algorithms suitable for machine learning applications. To that extent, I will discuss numerical results from applying our algorithms to compressed sensing and sparse regression problems, highlighting the fact that nonconvex lp constraints (p