Kernel Distributionally Robust Optimization
- URL: http://arxiv.org/abs/2006.06981v3
- Date: Sat, 27 Feb 2021 16:39:42 GMT
- Title: Kernel Distributionally Robust Optimization
- Authors: Jia-Jie Zhu, Wittawat Jitkrittum, Moritz Diehl, Bernhard Sch\"olkopf
- Abstract summary: We propose kernel distributionally robust optimization ( Kernel DRO) using insights from the robust optimization theory and functional analysis.
Our method uses kernel kernel (RKHS) to construct a wide range of convex ambiguity, which can be generalized to sets based on probability metrics and finite-order moment sets.
Using universal RKHSs, the theorem applies to a broad class of loss functions, lifting common limitations such as losses and knowledge of the Lipschitz constant.
- Score: 17.909696462645023
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose kernel distributionally robust optimization (Kernel DRO) using
insights from the robust optimization theory and functional analysis. Our
method uses reproducing kernel Hilbert spaces (RKHS) to construct a wide range
of convex ambiguity sets, which can be generalized to sets based on integral
probability metrics and finite-order moment bounds. This perspective unifies
multiple existing robust and stochastic optimization methods. We prove a
theorem that generalizes the classical duality in the mathematical problem of
moments. Enabled by this theorem, we reformulate the maximization with respect
to measures in DRO into the dual program that searches for RKHS functions.
Using universal RKHSs, the theorem applies to a broad class of loss functions,
lifting common limitations such as polynomial losses and knowledge of the
Lipschitz constant. We then establish a connection between DRO and stochastic
optimization with expectation constraints. Finally, we propose practical
algorithms based on both batch convex solvers and stochastic functional
gradient, which apply to general optimization and machine learning tasks.
Related papers
- Streamlining in the Riemannian Realm: Efficient Riemannian Optimization
with Loopless Variance Reduction [4.578425862931332]
This study focuses on the crucial reduction mechanism used in both Euclidean and Riemannian settings.
Motivated by Euclidean methods, we introduce R-based methods to replace the outer loop with computation triggered by a coin flip.
Using R- as a framework, we demonstrate its applicability to various important settings.
arXiv Detail & Related papers (2024-03-11T12:49:37Z) - Analysis of Kernel Mirror Prox for Measure Optimization [4.6080589718744305]
We study in a unified framework a class of functional saddle-point optimization problems, which we term the Mixed Functional Nash Equilibrium (MFNE)
We model the saddle-point optimization dynamics as an interacting Fisher-Rao-RKHS gradient flow.
We provide a unified convergence analysis of KMP in an infinite-dimensional setting for this class of MFNE problems.
arXiv Detail & Related papers (2024-02-29T21:55:17Z) - ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
We introduce an efficient single-loop primal-dual block-coordinate algorithm, dubbed ALEXR.
We establish the convergence rates of ALEXR in both convex and strongly convex cases under smoothness and non-smoothness conditions.
We present lower complexity bounds to demonstrate that the convergence rates of ALEXR are optimal among first-order block-coordinate algorithms for the considered class of cFCCO problems.
arXiv Detail & Related papers (2023-12-04T19:00:07Z) - Extrinsic Bayesian Optimizations on Manifolds [1.3477333339913569]
We propose an extrinsic Bayesian optimization (eBO) framework for general optimization problems on Euclid manifold.
Our approach is to employ extrinsic Gaussian processes by first embedding the manifold onto some higher dimensionalean space.
This leads to efficient and scalable algorithms for optimization over complex manifold.
arXiv Detail & Related papers (2022-12-21T06:10:12Z) - On a class of geodesically convex optimization problems solved via
Euclidean MM methods [50.428784381385164]
We show how a difference of Euclidean convexization functions can be written as a difference of different types of problems in statistics and machine learning.
Ultimately, we helps the broader broader the broader the broader the broader the work.
arXiv Detail & Related papers (2022-06-22T23:57:40Z) - Non-Convex Optimization with Certificates and Fast Rates Through Kernel
Sums of Squares [68.8204255655161]
We consider potentially non- optimized approximation problems.
In this paper, we propose an algorithm that achieves close to optimal a priori computational guarantees.
arXiv Detail & Related papers (2022-04-11T09:37:04Z) - Stability and Generalization for Randomized Coordinate Descent [19.687456295228156]
There is no work studying how the models trained by RCD would generalize to test examples.
In this paper, we initialize the generalization analysis of RCD by leveraging the powerful tool of algorithmic stability.
Our analysis shows that RCD enjoys better stability as compared to gradient descent.
arXiv Detail & Related papers (2021-08-17T02:52:50Z) - Optimization on manifolds: A symplectic approach [127.54402681305629]
We propose a dissipative extension of Dirac's theory of constrained Hamiltonian systems as a general framework for solving optimization problems.
Our class of (accelerated) algorithms are not only simple and efficient but also applicable to a broad range of contexts.
arXiv Detail & Related papers (2021-07-23T13:43:34Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
arXiv Detail & Related papers (2020-06-12T00:32:21Z) - Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
We consider distributed optimization problems where forming the Hessian is computationally challenging and communication is a bottleneck.
We develop unbiased parameter averaging methods for randomized second order optimization that employ sampling and sketching of the Hessian.
We also extend the framework of second order averaging methods to introduce an unbiased distributed optimization framework for heterogeneous computing systems.
arXiv Detail & Related papers (2020-02-16T09:01: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.