@article{CardereraPokutta2020, author = {Carderera, Alejandro and Pokutta, Sebastian}, title = {Second-order Conditional Gradient Sliding}, year = {2020}, abstract = {Constrained second-order convex optimization algorithms are the method of choice when a high accuracy solution to a problem is needed, due to their local quadratic convergence. These algorithms require the solution of a constrained quadratic subproblem at every iteration. We present the \emph{Second-Order Conditional Gradient Sliding} (SOCGS) algorithm, which uses a projection-free algorithm to solve the constrained quadratic subproblems inexactly. When the feasible region is a polytope the algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations. Once in the quadratic regime the SOCGS algorithm requires O(log(log1/ε)) first-order and Hessian oracle calls and O(log(1/ε)log(log1/ε)) linear minimization oracle calls to achieve an ε-optimal solution. This algorithm is useful when the feasible region can only be accessed efficiently through a linear optimization oracle, and computing first-order information of the function, although possible, is costly.}, language = {en} } @article{MathieuCardereraPokutta2022, author = {Mathieu, Besan{\c{c}}on and Carderera, Alejandro and Pokutta, Sebastian}, title = {FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and Conditional Gradients}, volume = {34}, journal = {INFORMS Journal on Computing}, number = {5}, doi = {10.1287/ijoc.2022.1191}, pages = {2383 -- 2865}, year = {2022}, abstract = {We present FrankWolfe.jl, an open-source implementation of several popular Frank-Wolfe and conditional gradients variants for first-order constrained optimization. The package is designed with flexibility and high performance in mind, allowing for easy extension and relying on few assumptions regarding the user-provided functions. It supports Julia's unique multiple dispatch feature, and it interfaces smoothly with generic linear optimization formulations using MathOptInterface.jl.}, language = {en} } @inproceedings{CriadoMartinezRubioPokutta2022, author = {Criado, Francisco and Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Fast Algorithms for Packing Proportional Fairness and its Dual}, volume = {36}, booktitle = {Proceedings of the Conference on Neural Information Processing Systems}, year = {2022}, abstract = {The proportional fair resource allocation problem is a major problem studied in flow control of networks, operations research, and economic theory, where it has found numerous applications. This problem, defined as the constrained maximization of sum_i log x_i, is known as the packing proportional fairness problem when the feasible set is defined by positive linear constraints and x ∈ R≥0. In this work, we present a distributed accelerated first-order method for this problem which improves upon previous approaches. We also design an algorithm for the optimization of its dual problem. Both algorithms are width-independent.}, language = {en} } @inproceedings{CardereraPokuttaMathieu2021, author = {Carderera, Alejandro and Pokutta, Sebastian and Mathieu, Besan{\c{c}}on}, title = {Simple steps are all you need: Frank-Wolfe and generalized self-concordant functions}, booktitle = {Thirty-fifth Conference on Neural Information Processing Systems, NeurIPS 2021}, year = {2021}, abstract = {Generalized self-concordance is a key property present in the objective function of many important learning problems. We establish the convergence rate of a simple Frank-Wolfe variant that uses the open-loop step size strategy 𝛾𝑡 = 2/(𝑡 + 2), obtaining a O (1/𝑡) convergence rate for this class of functions in terms of primal gap and Frank-Wolfe gap, where 𝑡 is the iteration count. This avoids the use of second-order information or the need to estimate local smoothness parameters of previous work. We also show improved convergence rates for various common cases, e.g., when the feasible region under consideration is uniformly convex or polyhedral.}, language = {en} } @article{Kerdreuxd'AspremontPokutta2021, author = {Kerdreux, Thomas and d'Aspremont, Alexandre and Pokutta, Sebastian}, title = {Local and Global Uniform Convexity Conditions}, year = {2021}, abstract = {We review various characterizations of uniform convexity and smoothness on norm balls in finite-dimensional spaces and connect results stemming from the geometry of Banach spaces with scaling inequalities used in analysing the convergence of optimization methods. In particular, we establish local versions of these conditions to provide sharper insights on a recent body of complexity results in learning theory, online learning, or offline optimization, which rely on the strong convexity of the feasible set. While they have a significant impact on complexity, these strong convexity or uniform convexity properties of feasible sets are not exploited as thoroughly as their functional counterparts, and this work is an effort to correct this imbalance. We conclude with some practical examples in optimization and machine learning where leveraging these conditions and localized assumptions lead to new complexity results.}, language = {en} } @inproceedings{CardereraDiakonikolasLinetal.2021, author = {Carderera, Alejandro and Diakonikolas, Jelena and Lin, Cheuk Yin and Pokutta, Sebastian}, title = {Parameter-free Locally Accelerated Conditional Gradients}, booktitle = {ICML 2021}, year = {2021}, abstract = {Projection-free conditional gradient (CG) methods are the algorithms of choice for constrained optimization setups in which projections are often computationally prohibitive but linear optimization over the constraint set remains computationally feasible. Unlike in projection-based methods, globally accelerated convergence rates are in general unattainable for CG. However, a very recent work on Locally accelerated CG (LaCG) has demonstrated that local acceleration for CG is possible for many settings of interest. The main downside of LaCG is that it requires knowledge of the smoothness and strong convexity parameters of the objective function. We remove this limitation by introducing a novel, Parameter-Free Locally accelerated CG (PF-LaCG) algorithm, for which we provide rigorous convergence guarantees. Our theoretical results are complemented by numerical experiments, which demonstrate local acceleration and showcase the practical improvements of PF-LaCG over non-accelerated algorithms, both in terms of iteration count and wall-clock time.}, language = {en} } @article{RouxPokuttaWirthetal.2021, author = {Roux, Christophe and Pokutta, Sebastian and Wirth, Elias and Kerdreux, Thomas}, title = {Efficient Online-Bandit Strategies for Minimax Learning Problems}, year = {2021}, abstract = {Several learning problems involve solving min-max problems, e.g., empirical distributional robust learning [Namkoong and Duchi, 2016, Curi et al., 2020] or learning with non-standard aggregated losses [Shalev- Shwartz and Wexler, 2016, Fan et al., 2017]. More specifically, these problems are convex-linear problems where the minimization is carried out over the model parameters w ∈ W and the maximization over the empirical distribution p ∈ K of the training set indexes, where K is the simplex or a subset of it. To design efficient methods, we let an online learning algorithm play against a (combinatorial) bandit algorithm. We argue that the efficiency of such approaches critically depends on the structure of K and propose two properties of K that facilitate designing efficient algorithms. We focus on a specific family of sets Sn,k encompassing various learning applications and provide high-probability convergence guarantees to the minimax values.}, language = {en} } @article{KerdreuxRouxd'Aspremontetal.2021, author = {Kerdreux, Thomas and Roux, Christophe and d'Aspremont, Alexandre and Pokutta, Sebastian}, title = {Linear Bandits on Uniformly Convex Sets}, volume = {22}, journal = {Journal of Machine Learning Research}, number = {284}, pages = {1 -- 23}, year = {2021}, abstract = {Linear bandit algorithms yield O~(n√T) pseudo-regret bounds on compact convex action sets K⊂Rn and two types of structural assumptions lead to better pseudo-regret bounds. When K is the simplex or an ℓp ball with p∈]1,2], there exist bandits algorithms with O~(√n√T) pseudo-regret bounds. Here, we derive bandit algorithms for some strongly convex sets beyond ℓp balls that enjoy pseudo-regret bounds of O~(√n√T), which answers an open question from [BCB12, \S5.5.]. Interestingly, when the action set is uniformly convex but not necessarily strongly convex, we obtain pseudo-regret bounds with a dimension dependency smaller than O(√n). However, this comes at the expense of asymptotic rates in T varying between O(√T) and O(T).}, language = {en} } @inproceedings{WirthPokutta2022, author = {Wirth, Elias and Pokutta, Sebastian}, title = {Conditional Gradients for the Approximately Vanishing Ideal}, volume = {151}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {2191 -- 2209}, year = {2022}, abstract = {The vanishing ideal of a set of points X is the set of polynomials that evaluate to 0 over all points x in X and admits an efficient representation by a finite set of polynomials called generators. To accommodate the noise in the data set, we introduce the Conditional Gradients Approximately Vanishing Ideal algorithm (CGAVI) for the construction of the set of generators of the approximately vanishing ideal. The constructed set of generators captures polynomial structures in data and gives rise to a feature map that can, for example, be used in combination with a linear classifier for supervised learning. In CGAVI, we construct the set of generators by solving specific instances of (constrained) convex optimization problems with the Pairwise Frank-Wolfe algorithm (PFW). Among other things, the constructed generators inherit the LASSO generalization bound and not only vanish on the training but also on out-sample data. Moreover, CGAVI admits a compact representation of the approximately vanishing ideal by constructing few generators with sparse coefficient vectors.}, language = {en} } @inproceedings{MartinezRubioPokutta2023, author = {Mart{\´i}nez-Rubio, David and Pokutta, Sebastian}, title = {Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties}, volume = {195}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {359 -- 393}, year = {2023}, abstract = {We propose a globally-accelerated, first-order method for the optimization of smooth and (strongly or not) geodesically-convex functions in a wide class of Hadamard manifolds. We achieve the same convergence rates as Nesterov's accelerated gradient descent, up to a multiplicative geometric penalty and log factors. Crucially, we can enforce our method to stay within a compact set we define. Prior fully accelerated works \emph{resort to assuming} that the iterates of their algorithms stay in some pre-specified compact set, except for two previous methods of limited applicability. For our manifolds, this solves the open question in (Kim and Yang, 2022) about obtaining global general acceleration without iterates assumptively staying in the feasible set.In our solution, we design an accelerated Riemannian inexact proximal point algorithm, which is a result that was unknown even with exact access to the proximal operator, and is of independent interest. For smooth functions, we show we can implement the prox step inexactly with first-order methods in Riemannian balls of certain diameter that is enough for global accelerated optimization.}, language = {en} }