Optimal Algorithms for Stochastic Complementary Composite Minimization

• URL: http://arxiv.org/abs/2211.01758v2
• Date: Tue, 23 Jan 2024 12:29:23 GMT
• Title: Optimal Algorithms for Stochastic Complementary Composite Minimization
• Authors: Alexandre d'Aspremont, Crist\'obal Guzm\'an, Cl\'ement Lezane
• Abstract summary: Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization. We provide novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems.
• Score: 55.26935605535377
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization in the stochastic setting. This problem corresponds to the minimization of the sum of a (weakly) smooth function endowed with a stochastic first-order oracle, and a structured uniformly convex (possibly nonsmooth and non-Lipschitz) regularization term. Despite intensive work on closely related settings, prior to our work no complexity bounds for this problem were known. We close this gap by providing novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems. We conclude by providing numerical results comparing our methods to the state of the art.

Related papers

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  We propose algorithms with high-probability convergence results under less restrictive assumptions. These results justify the usage of the considered methods for solving problems that do not fit standard functional classes in optimization.
  arXiv  Detail & Related papers  (2023-02-02T10:37:23Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  We consider non-SBO problems that have many applications in machine learning. This paper proposes fast randomized algorithms for non-SBO problems.
  arXiv  Detail & Related papers  (2021-05-05T18:28:42Z)
• Complementary Composite Minimization, Small Gradients in General Norms, and Applications to Regression Problems [14.759688428864157]
  Composite minimization is a powerful framework in large-scale convex optimization. We introduce a new algorithmic framework for complementary composite minimization. We prove that the algorithms resulting from our framework are near-optimal in most of the standard optimization settings.
  arXiv  Detail & Related papers  (2021-01-26T19:21:28Z)
• Distributed Stochastic Consensus Optimization with Momentum for Nonconvex Nonsmooth Problems [45.88640334610308]
  This paper presents a new distributed optimization algorithm for non-smooth problems. We show that the proposed algorithm can achieve an overcal communication. Experiments are presented to illustrate the effectiveness of the proposed algorithms.
  arXiv  Detail & Related papers  (2020-11-10T13:12:21Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits [34.06611065493047]
  This paper proposes near-optimal algorithms for the pure-exploration linear bandit problem in the fixed confidence and fixed budget settings. We provide an algorithm whose sample complexity scales with the geometry of the instance and avoids an explicit union bound over the number of arms. We also propose the first algorithm for linear bandits in the the fixed budget setting.
  arXiv  Detail & Related papers  (2020-06-21T00:56:33Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  We study the problem of zero-order optimization of a strongly convex function. We consider a randomized approximation of the projected gradient descent algorithm. Our results imply that the zero-order algorithm is nearly optimal in terms of sample complexity and the problem parameters.
  arXiv  Detail & Related papers  (2020-06-14T10:42:23Z)
• Low-Rank Factorization for Rank Minimization with Nonconvex Regularizers [0.0]
  Minimizing the convex relaxation to the nuclear norm is of interest in recommender systems and robust principal component analysis. We develop efficient algorithms for the rank factorization of nuclear programs put forth by Buriro and nucleariro.
  arXiv  Detail & Related papers  (2020-06-13T19:04:37Z)
• Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities [21.13934071954103]
  We present a deterministic algorithm for non-in one-text variable Descent strongly-concave in the other. We show that under the SGC assumption, the complexities of the algorithms match that of existing algorithms. Results are presented in terms of oracle-texttZO-GDMSA and Numerical experiments are presented to support theoretical results.
  arXiv  Detail & Related papers  (2020-01-22T00:05:14Z)

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.