Online Mirror Descent for Tchebycheff Scalarization in Multi-Objective Optimization

• URL: http://arxiv.org/abs/2410.21764v2
• Date: Mon, 11 Nov 2024 16:17:07 GMT
• Title: Online Mirror Descent for Tchebycheff Scalarization in Multi-Objective Optimization
• Authors: Meitong Liu, Xiaoyuan Zhang, Chulin Xie, Kate Donahue, Han Zhao,
• Abstract summary: We propose an online mirror descent algorithm for Tcheche scalarization, which we call OMD-TCH. We show the effectiveness of OMD-TCH on both synthetic problems and federated learning tasks under fairness constraints.
• Score: 14.970965673760427
• License:
• Abstract: The goal of multi-objective optimization (MOO) is to learn under multiple, potentially conflicting, objectives. One widely used technique to tackle MOO is through linear scalarization, where one fixed preference vector is used to combine the objectives into a single scalar value for optimization. However, recent work (Hu et al., 2024) has shown linear scalarization often fails to capture the non-convex regions of the Pareto Front, failing to recover the complete set of Pareto optimal solutions. In light of the above limitations, this paper focuses on Tchebycheff scalarization that optimizes for the worst-case objective. In particular, we propose an online mirror descent algorithm for Tchebycheff scalarization, which we call OMD-TCH. We show that OMD-TCH enjoys a convergence rate of $O(\sqrt{\log m/T})$ where $m$ is the number of objectives and $T$ is the number of iteration rounds. We also propose a novel adaptive online-to-batch conversion scheme that significantly improves the practical performance of OMD-TCH while maintaining the same convergence guarantees. We demonstrate the effectiveness of OMD-TCH and the adaptive conversion scheme on both synthetic problems and federated learning tasks under fairness constraints, showing state-of-the-art performance.

Related papers

• LoKO: Low-Rank Kalman Optimizer for Online Fine-Tuning of Large Models [21.889177019111525]
  Training large models with millions or even billions of parameters from scratch incurs substantial computational costs. We use Low-Rank Adaptation (LoRA) to adapt only a reduced number of parameters to specific tasks with gradient-baseds. We propose robust approaches that work well across a vast range of well-established computer vision and language models.
  arXiv  Detail & Related papers  (2024-10-15T12:41:31Z)
• Zeroth-Order Fine-Tuning of LLMs in Random Subspaces [66.27334633749734]
  As language models grow in size, memory demands for backpropagation increase. Zeroth-order (ZOZO) optimization methods offer a memory-efficient alternative. We show that SubZero enhances fine-tuning and achieves faster results compared to standard ZOZO approaches.
  arXiv  Detail & Related papers  (2024-10-11T17:01:43Z)
• Traversing Pareto Optimal Policies: Provably Efficient Multi-Objective Reinforcement Learning [14.260168974085376]
  This paper investigates multi-objective reinforcement learning (MORL) It focuses on learning optimal policies in the presence of multiple reward functions. Despite MORL's success, there is still a lack of satisfactory understanding of various MORL optimization targets and efficient learning algorithms.
  arXiv  Detail & Related papers  (2024-07-24T17:58:49Z)
• Correcting the Mythos of KL-Regularization: Direct Alignment without Overoptimization via Chi-Squared Preference Optimization [78.82586283794886]
  We present a new offline alignment algorithm, $chi2$-Preference Optimization ($chi$PO) $chi$PO implements the principle of pessimism in the face of uncertainty via regularization. It is provably robust to overoptimization and achieves sample-complexity guarantees based on single-policy concentrability.
  arXiv  Detail & Related papers  (2024-07-18T11:08:40Z)
• Decoding-Time Language Model Alignment with Multiple Objectives [116.42095026960598]
  Existing methods primarily focus on optimizing LMs for a single reward function, limiting their adaptability to varied objectives. Here, we propose $textbfmulti-objective decoding (MOD)$, a decoding-time algorithm that outputs the next token from a linear combination of predictions. We show why existing approaches can be sub-optimal even in natural settings and obtain optimality guarantees for our method.
  arXiv  Detail & Related papers  (2024-06-27T02:46:30Z)
• Sparsity-Constraint Optimization via Splicing Iteration [1.3622424109977902]
  We develop an algorithm named Sparsity-Constraint Optimization via sPlicing itEration (SCOPE) SCOPE converges effectively without tuning parameters. We apply SCOPE to solve quadratic optimization, learn sparse classifiers, and recover sparse Markov networks for binary variables. Our open-source Python package skscope based on C++ implementation is publicly available on GitHub.
  arXiv  Detail & Related papers  (2024-06-17T18:34:51Z)
• 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)
• An Empirical Evaluation of Zeroth-Order Optimization Methods on AI-driven Molecule Optimization [78.36413169647408]
  We study the effectiveness of various ZO optimization methods for optimizing molecular objectives. We show the advantages of ZO sign-based gradient descent (ZO-signGD) We demonstrate the potential effectiveness of ZO optimization methods on widely used benchmark tasks from the Guacamol suite.
  arXiv  Detail & Related papers  (2022-10-27T01:58:10Z)
• Efficient first-order predictor-corrector multiple objective optimization for fair misinformation detection [5.139559672771439]
  Multiple-objective optimization (MOO) aims to simultaneously optimize multiple conflicting objectives and has found important applications in machine learning. We propose a Gauss-Newton approximation that only scales linearly, and that requires only first-order inner-product per iteration. The innovations make predictor-corrector possible for large networks.
  arXiv  Detail & Related papers  (2022-09-15T12:32:15Z)
• Provable Stochastic Optimization for Global Contrastive Learning: Small Batch Does Not Harm Performance [53.49803579981569]
  We consider a global objective for contrastive learning, which contrasts each positive pair with all negative pairs for an anchor point. Existing methods such as SimCLR requires a large batch size in order to achieve a satisfactory result. We propose a memory-efficient optimization algorithm for solving the Global Contrastive Learning of Representations, named SogCLR.
  arXiv  Detail & Related papers  (2022-02-24T22:16:53Z)
• Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization [8.90548944387431]
  In this paper, we consider multi-objective optimization, where $f(x)$ outputs a vector of possibly competing objectives. We show that any provably convergent single-objective optimization process can be effortlessly converted to a multi-objective optimization process with provable convergence guarantees.
  arXiv  Detail & Related papers  (2020-06-08T15:00:30Z)

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.