Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applications

2022-02-24 · Bokun Wang, Tianbao Yang

This paper studies stochastic optimization for a sum of compositional functions, where the inner-level function of each summand is coupled with the corresponding summation index. We refer to this family of problems as finite-sum coupled compositional optimization (FCCO). It has broad applications in machine learning for optimizing non-convex or convex compositional measures/objectives such as average precision (AP), p-norm push, listwise ranking losses, neighborhood component analysis (NCA), deep survival analysis, deep latent variable models, etc., which deserves finer analysis. Yet, existing algorithms and analyses are restricted in one or other aspects. The contribution of this paper is to provide a comprehensive convergence analysis of a simple stochastic algorithm for both non-convex and convex objectives. Our key result is the improved oracle complexity with the parallel speed-up by using the moving-average based estimator with mini-batching. Our theoretical analysis also exhibits new insights for improving the practical implementation by sampling the batches of equal size for the outer and inner levels. Numerical experiments on AP maximization, NCA, and p-norm push corroborate some aspects of the theory.

📄 PDF Abstract BibTeX arXiv:2202.12396

Code (0)

등록된 구현이 없습니다.

Tasks

Meta-Learning Stochastic OptimizationSurvival Analysis

Methods 이 논문이 사용한 방법론

Softmax The Softmax output function transforms a previous layer's output into a vector of probabilities. It is commonly used for multiclass classification. Given an input vector $x$…

Efficient Smooth Non-Convex Stochastic Compositional Optimization via Stochastic Recursive Gradient Descent

2019-12-01 · NeurIPS 2019 12 · Huizhuo Yuan, Xiangru Lian, Chris Junchi Li, Ji Liu 외

Stochastic compositional optimization arises in many important machine learning tasks such as reinforcement learning and portfolio management. The objective function is the composition of two expectations of stochastic f…

Management Reinforcement Learning Stochastic Optimization

A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization

2023-12-04 · Bokun Wang, Tianbao Yang

This paper studies a class of convex Finite-sum Coupled Compositional Optimization (cFCCO) problems with applications including group distributionally robust optimization (GDRO) and learning with imbalanced data. To bett…

Learning-To-Rank Stochastic Optimization

Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization

2023-10-05 · NeurIPS 2023 11 · Quanqi Hu, Dixian Zhu, Tianbao Yang

This paper investigates new families of compositional optimization problems, called $\underline{\bf n}$on-$\underline{\bf s}$mooth $\underline{\bf w}$eakly-$\underline{\bf c}$onvex $\underline{\bf f}$inite-sum $\underlin…

Stochastic Recursive Variance Reduction for Efficient Smooth Non-Convex Compositional Optimization

2019-12-31 · Huizhuo Yuan, Xiangru Lian, Ji Liu

Stochastic compositional optimization arises in many important machine learning tasks such as value function evaluation in reinforcement learning and portfolio management. The objective function is the composition of two…

Management Reinforcement Learning Stochastic Optimization

A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequences

2022-06-21 · Han Shen, Tianyi Chen

Stochastic approximation (SA) with multiple coupled sequences has found broad applications in machine learning such as bilevel learning and reinforcement learning (RL). In this paper, we study the finite-time convergence…

Reinforcement Learning (RL)