Refine
Document Type
- In Proceedings (5)
- Article (2)
Language
- English (7)
Has Fulltext
- no (7)
Is part of the Bibliography
- no (7)
Institute
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.
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, §5.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).
In this work, we analyze two of the most fundamental algorithms in geodesically convex optimization: Riemannian gradient descent and (possibly inexact) Riemannian proximal point. We quantify their rates of convergence and produce different variants with several trade-offs. Crucially, we show the iterates naturally stay in a ball around an optimizer, of radius depending on the initial distance and, in some cases, on the curvature. Previous works simply assumed bounded iterates, resulting in rates that were not fully quantified. We also provide an implementable inexact proximal point algorithm and prove several new useful properties of Riemannian proximal methods: they work when positive curvature is present, the proximal operator does not move points away from any optimizer, and we quantify the smoothness of its induced Moreau envelope. Further, we explore beyond our theory with empirical tests.
Federated Learning (FL) algorithms using Knowledge Distillation (KD) have received increasing attention due to their favorable properties with respect to privacy, non-i.i.d. data and communication cost. These methods depart from transmitting model parameters and instead communicate information about a learning task by sharing predictions on a public dataset. In this work, we study the performance of such approaches in the byzantine setting, where a subset of the clients act in an adversarial manner aiming to disrupt the learning process. We show that KD-based FL algorithms are remarkably resilient and analyze how byzantine clients can influence the learning process. Based on these insights, we introduce two new byzantine attacks and demonstrate their ability to break existing byzantine-resilient methods. Additionally, we propose a novel defence method which enhances the byzantine resilience of KD-based FL algorithms. Finally, we provide a general framework to obfuscate attacks, making them significantly harder to detect, thereby improving their effectiveness.