Efficient Online-Bandit Strategies for Minimax Learning Problems

• URL: http://arxiv.org/abs/2105.13939v1
• Date: Fri, 28 May 2021 16:01:42 GMT
• Title: Efficient Online-Bandit Strategies for Minimax Learning Problems
• Authors: Christophe Roux, Elias Wirth, Sebastian Pokutta, Thomas Kerdreux
• Abstract summary: Several learning problems involve solving min-max problems, e.g., empirical distributional robust learning or minimization with non-standard aggregated losses. More specifically, these problems are convex-linear problems where the learning is carried out over the model parameters $winmathcalW$ and over the empirical distribution $pinmathcalK$ of the training set. To design efficient methods, we let an online learning algorithm play against a (combinatorial) bandit algorithm.
• Score: 21.300877551771197
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Several learning problems involve solving min-max problems, e.g., empirical distributional robust learning or learning with non-standard aggregated losses. More specifically, these problems are convex-linear problems where the minimization is carried out over the model parameters $w\in\mathcal{W}$ and the maximization over the empirical distribution $p\in\mathcal{K}$ of the training set indexes, where $\mathcal{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 $\mathcal{K}$ and propose two properties of $\mathcal{K}$ that facilitate designing efficient algorithms. We focus on a specific family of sets $\mathcal{S}_{n,k}$ encompassing various learning applications and provide high-probability convergence guarantees to the minimax values.

Related papers

• Learning to Solve the Constrained Most Probable Explanation Task in Probabilistic Graphical Models [10.603378323312809]
  We train a deep neural network that learns to output near-optimal solutions to the constrained most-probable explanation (CMPE) problem. We analyze the properties of our proposed method and experimentally demonstrate its efficacy on several benchmark problems.
  arXiv  Detail & Related papers  (2024-04-17T17:55:17Z)
• Solving a Class of Non-Convex Minimax Optimization in Federated Learning [84.98927714326908]
  The minimax problems arise throughout machine learning applications, ranging from machine learning training to large-scale learning. We propose a class of algorithms for non minimax problems (emphi) that reduce complexity to $varepsilon-6)$. We prove that FedSGDA-M has the best sample complexity of $O(kappa2-3)$ and the best-known communication of $O(kappa2-3)$.
  arXiv  Detail & Related papers  (2023-10-05T15:48:41Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Optimality of Robust Online Learning [4.21768682940933]
  We study an online learning algorithm with a robust loss function $mathcalL_sigma$ for regression over a reproducing kernel Hilbert space (RKHS) The proposed algorithm is then a robust alternative for online least squares regression aiming to estimate the conditional mean function.
  arXiv  Detail & Related papers  (2023-04-20T03:00:33Z)
• Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
  We propose an efficient adaptive minimax optimization algorithm (i.e., AdaFGDA) to solve these minimax problems. It builds our momentum-based reduced and localSGD techniques, and it flexibly incorporate various adaptive learning rates.
  arXiv  Detail & Related papers  (2022-11-14T12:32:18Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax Problems [26.24895953952318]
  We develop an algorithm to solve a class of non-gence minimax problems. They can also work with both single or two mini-batch derivatives.
  arXiv  Detail & Related papers  (2020-06-27T03:05:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.