More Like this

1. Randomized sketch descent methods for non-separable linearly constrained optimization

   https://doi.org/10.1093/imanum/draa018  

   Necoara, Ion; Takáč, Martin (May 2020, IMA Journal of Numerical Analysis)

   null (Ed.)

   Abstract In this paper we consider large-scale smooth optimization problems with multiple linear coupled constraints. Due to the non-separability of the constraints, arbitrary random sketching would not be guaranteed to work. Thus, we first investigate necessary and sufficient conditions for the sketch sampling to have well-defined algorithms. Based on these sampling conditions we develop new sketch descent methods for solving general smooth linearly constrained problems, in particular, random sketch descent (RSD) and accelerated random sketch descent (A-RSD) methods. To our knowledge, this is the first convergence analysis of RSD algorithms for optimization problems with multiple non-separable linear constraints. For the general case, when the objective function is smooth and non-convex, we prove for the non-accelerated variant sublinear rate in expectation for an appropriate optimality measure. In the smooth convex case, we derive for both algorithms, non-accelerated and A-RSD, sublinear convergence rates in the expected values of the objective function. Additionally, if the objective function satisfies a strong convexity type condition, both algorithms converge linearly in expectation. In special cases, where complexity bounds are known for some particular sketching algorithms, such as coordinate descent methods for optimization problems with a single linear coupled constraint, our theory recovers the best known bounds. Finally, we present several numerical examples to illustrate the performances of our new algorithms. 

   more » « less
2. On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems

   Muehlebach, Michael; Jordan, Michael I (July 2021, ArXivorg)

   null (Ed.)

   We introduce a class of first-order methods for smooth constrained optimization that are based on an analogy to non-smooth dynamical systems. Two distinctive features of our approach are that (i) projections or optimizations over the entire feasible set are avoided, in stark contrast to projected gradient methods or the Frank-Wolfe method, and (ii) iterates are allowed to become infeasible, which differs from active set or feasible direction methods, where the descent motion stops as soon as a new constraint is encountered. The resulting algorithmic procedure is simple to implement even when constraints are nonlinear, and is suitable for large-scale constrained optimization problems in which the feasible set fails to have a simple structure. The key underlying idea is that constraints are expressed in terms of velocities instead of positions, which has the algorithmic consequence that optimizations over feasible sets at each iteration are replaced with optimizations over local, sparse convex approximations. The result is a simplified suite of algorithms and an expanded range of possible applications in machine learning. 

   more » « less
3. Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence

   https://doi.org/10.1609/aaai.v36i6.20609  

   Ene, Alina; Nguyen, Huy L. (February 2022, AAAI Conference on Artificial Intelligence)

   We develop new adaptive algorithms for variational inequalities with monotone operators, which capture many problems of interest, notably convex optimization and convex-concave saddle point problems. Our algorithms automatically adapt to unknown problem parameters such as the smoothness and the norm of the operator, and the variance of the stochastic evaluation oracle. We show that our algorithms are universal and simultaneously achieve the optimal convergence rates in the non-smooth, smooth, and stochastic settings. The convergence guarantees of our algorithms improve over existing adaptive methods and match the optimal non-adaptive algorithms. Additionally, prior works require that the optimization domain is bounded. In this work, we remove this restriction and give algorithms for unbounded domains that are adaptive and universal. Our general proof techniques can be used for many variants of the algorithm using one or two operator evaluations per iteration. The classical methods based on the ExtraGradient/MirrorProx algorithm require two operator evaluations per iteration, which is the dominant factor in the running time in many settings. 

   more » « less
4. Data‐enabled extremum seeking: A cooperative concurrent learning‐based approach

   https://doi.org/10.1002/acs.3189  

   Poveda, Jorge I.; Benosman, Mouhacine; Vamvoudakis, Kyriakos G. (October 2020, International Journal of Adaptive Control and Signal Processing)

   Summary This paper introduces a new class of feedback‐based data‐driven extremum seeking algorithms for the solution of model‐free optimization problems in smooth continuous‐time dynamical systems. The novelty of the algorithms lies on the incorporation of memory to store recorded data that enables the use of information‐rich datasets during the optimization process, and allows to dispense with the time‐varying dither excitation signal needed by standard extremum seeking algorithms that rely on a persistence of excitation (PE) condition. The model‐free optimization dynamics are developed for single‐agent systems, as well as for multi‐agent systems with communication graphs that allow agents to share their state information while preserving the privacy of their individual data. In both cases, sufficient richness conditions on the recorded data, as well as suitable optimization dynamics modeled by ordinary differential equations are characterized in order to guarantee convergence to a neighborhood of the solution of the extremum seeking problems. The performance of the algorithms is illustrated via different numerical examples in the context of source‐seeking problems in multivehicle systems. 

   more » « less
5. Adaptive Gradient Methods for Constrained Convex Optimization and Variational Inequalities

   Ene, Alina; Nguyen, Huy L; Vladu, Adrian (May 2021, Proceedings of the AAAI Conference on Artificial Intelligence)

   null (Ed.)

   We provide new adaptive first-order methods for constrained convex optimization. Our main algorithms AdaACSA and AdaAGD+ are accelerated methods, which are universal in the sense that they achieve nearly-optimal convergence rates for both smooth and non-smooth functions, even when they only have access to stochastic gradients. In addition, they do not require any prior knowledge on how the objective function is parametrized, since they automatically adjust their per-coordinate learning rate. These can be seen as truly accelerated Adagrad methods for constrained optimization. We complement them with a simpler algorithm AdaGrad+ which enjoys the same features, and achieves the standard non-accelerated convergence rate. We also present a set of new results involving adaptive methods for unconstrained optimization and variational inequalities arising from monotone operators. 

   more » « less