Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss

04/08/2021

Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss

Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford

Keywords:

Abstract Paper Similar Papers

Abstract: We characterize the complexity of minimizing the maximum of 𝑁 convex, Lipschitz functions. For non-smooth functions, existing methods require O(𝑁𝜖⁻²) queries to a first-order oracle to compute an 𝜖-suboptimal point and Õ(𝑁𝜖⁻¹) queries if the functions are O(𝜖⁻¹)-smooth. We develop methods with improved complexity bounds Õ(𝑁𝜖⁻²/³ + 𝜖⁻⁸/³) in the non-smooth case and Õ(𝑁𝜖⁻²/³ + √𝑁𝜖⁻¹) in the O(𝜖⁻¹)-smooth case. Our methods consist of a recently proposed ball optimization oracle acceleration algorithm (which we refine), combined with careful implementation of said oracle for the softmax function. We also prove an oracle complexity lower bound scaling as 𝛺(𝑁𝜖⁻²/³), showing that our dependence on 𝑁 is optimal up to polylogarithmic factors.

0

0

0

0

Share

This is an embedded video. Talk and the respective paper are published at COLT 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment

no comments yet

Similar Papers

12/07/2020

Lower Complexity Bounds for Finite-Sum Convex-Concave Minimax Optimization Problems

Guangzeng Xie, Luo Luo, yijiang lian, Zhihua Zhang

Keywords Paper

Optimization - Convex

0

0

0

0

12:09

06/12/2020

Acceleration with a Ball Optimization Oracle

Yair Carmon, Arun Jambulapati, Qijia Jiang and
Yujia Jin, Yin Tat Lee, Aaron Sidford, Kevin Tian

Keywords Paper

0

0

0

0

3:19

06/12/2020

Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method

Kiran Thekumparampil, Prateek Jain, Praneeth Netrapalli, Sewoong Oh

Keywords Paper

0

0

0

0

3:23

04/08/2021

Frank-Wolfe with Nearest Extreme Point Oracle

Dan Garber, Noam Wolf

Keywords Paper

0

0

0

0

12:52

13/04/2021

Rate-improved inexact augmented lagrangian method for constrained nonconvex optimization

Zichong Li, Pin-Yu Chen, Sijia Liu and
Songtao Lu, Yangyang Xu

Keywords Paper

0

0

0

0

3:04

26/04/2020

Gradientless Descent: High-Dimensional Zeroth-Order Optimization

Daniel Golovin, John Karro, Greg Kochanski and
Chansoo Lee, Xingyou Song, Qiuyi Zhang

Keywords Paper

Zeroth Order Optimization

0

0

0

0

5:20

06/12/2021

Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness

Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif

Keywords Paper

optimization

0

0

0

0

15:36

13/04/2021

Efficient methods for structured nonconvex-nonconcave min-max optimization

Jelena Diakonikolas, Constantinos Daskalakis, Michael Jordan

Keywords Paper

0

0

0

0

3:33

22/06/2020

An improved cutting plane method for convex optimization, convex-concave games, and its applications

Haotian Jiang, Yin Tat Lee, Zhao Song, Sam Chiu-wai Wong

Keywords Paper

convex-concave games, cutting plane method, market equilibrium, fast rectangular matrix multiplication, convex optimization

0

0

0

0

23:51

09/07/2020

How to trap a gradient flow

Dan Mikulincer, Sebastien Bubeck

Keywords Paper

Non-convex optimization,

0

0

0

0

15:01

26/04/2020

Sign-OPT: A Query-Efficient Hard-label Adversarial Attack

Minhao Cheng, Simranjit Singh, Patrick H. Chen and
Pin-Yu Chen, Sijia Liu, Cho-Jui Hsieh

Keywords Paper

0

0

0

0

4:56

06/12/2021

Adapting to function difficulty and growth conditions in private optimization

Hilal Asi, Daniel Levy, John Duchi

Keywords Paper

optimization, privacy

0

0

0

0

11:30

06/12/2021

Three Operator Splitting with Subgradients, Stochastic Gradients, and Adaptive Learning Rates

Alp Yurtsever, Alex Gu, Suvrit Sra

Keywords Paper

optimization, machine learning

0

0

0

0

14:21

06/12/2020

Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits

Arya Akhavan, Massimiliano Pontil, Alexandre Tsybakov

Keywords Paper

Reinforcement Learning and Planning -> Reinforcement Learning, Applications -> Privacy, Anonymity, and Security

0

0

0

0

3:00

12/07/2020

Min-Max Optimization without Gradients: Convergence and Applications to Black-Box Evasion and Poisoning Attacks

Sijia Liu, Songtao Lu, Xiangyi Chen and
Yao Feng, Kaidi Xu, Abdullah Al-Dujaili, Mingyi Hong, Una-May O'Reilly

Keywords Paper

Optimization - Non-convex

0

0

0

0

11:59

06/12/2021

Unifying Width-Reduced Methods for Quasi-Self-Concordant Optimization

Deeksha Adil, Brian Bullins, Sushant Sachdeva

Keywords Paper

optimization

0

0

0

0

12:14

13/04/2021

Adaptive sampling for fast constrained maximization of submodular functions

Francesco Quinzan, Vanja Doskoc, Andreas Göbel, Tobias Friedrich

Keywords Paper

0

0

0

0

2:54

12/07/2020

Accelerated Stochastic Gradient-free and Projection-free Methods

Feihu Huang, Lue Tao, Songcan Chen

Keywords Paper

Optimization - Non-convex

0

0

0

0

13:05

09/07/2020

Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations

Yossi Arjevani, Yair Carmon, John Duchi and
Dylan Foster, Ayush Sekhari, Karthik Sridharan

Keywords Paper

Non-convex optimization, Stochastic optimization

0

0

0

0

11:57

03/05/2021

The Role of Momentum Parameters in the Optimal Convergence of Adaptive Polyak's Heavy-ball Methods

Wei Tao, sheng long, Gaowei Wu, Qing Tao

Keywords Paper

optimal convergence, convex optimization, momentum methods, Deep learning, adaptive heavy-ball methods

0

0

0

0

5:16

06/12/2021

Convergence of adaptive algorithms for constrained weakly convex optimization

Ahmet Alacaoglu, Yura Malitsky, Volkan Cevher

Keywords Paper

optimization

1

1

0

0

9:31

06/12/2020

Hybrid Variance-Reduced SGD Algorithms For Minimax Problems with Nonconvex-Linear Function

Quoc Tran Dinh, Deyi Liu, Lam Nguyen

Keywords Paper

0

0

0

0

3:07

06/12/2020

Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems

Luo Luo, Haishan Ye, Zhichao Huang, Tong Zhang

Keywords Paper

0

0

0

0

2:00

06/12/2020

One Ring to Rule Them All: Certifiably Robust Geometric Perception with Outliers

Heng Yang, Luca Carlone

Keywords Paper

0

0

0

0

3:24

26/04/2020

A Stochastic Derivative Free Optimization Method with Momentum

Eduard Gorbunov, Adel Bibi, Ozan Sener and
El Houcine Bergou, Peter Richtarik

Keywords Paper

derivative-free optimization, stochastic optimization, heavy ball momentum, importance sampling

0

0

0

0

4:51

06/12/2020

An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits

Julian Katz-Samuels, Lalit Jain, zohar karnin, Kevin Jamieson

Keywords Paper

0

0

0

0

3:20

09/07/2020

Approximation Schemes for ReLU Regression

Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar and
Adam Klivans, Mahdi Soltanolkotabi

Keywords Paper

PAC learning, Approximation algorithms, Convex optimization, Neural networks/deep learning

0

0

0

0

15:20

12/07/2020

Sparse Convex Optimization via Adaptively Regularized Hard Thresholding

Kyriakos Axiotis, Maxim Sviridenko

Keywords Paper

Optimization - General

0

0

0

0

13:44

09/07/2020

How Good is SGD with Random Shuffling?

Itay M Safran, Ohad Shamir

Keywords Paper

Convex optimization,

0

0

0

0

11:50

13/04/2021

Finding first-order nash equilibria of zero-sum games with the regularized nikaido-isoda function

Ioannis Tsaknakis, Mingyi Hong

Keywords Paper

0

0

0

0

3:10

06/12/2021

High Probability Complexity Bounds for Line Search Based on Stochastic Oracles

Billy Jin, Katya Scheinberg, Miaolan Xie

Keywords Paper

optimization

0

0

0

0

14:53

06/12/2020

Variance Reduction via Accelerated Dual Averaging for Finite-Sum Optimization

Chaobing Song, Yong Jiang, Yi Ma

Keywords Paper

Algorithms -> Boosting and Ensemble Methods; Applications -> Hardware and Systems; Applications -> Natural Language Processing;, Applications -> Privacy, Anonymity, and Security

0

0

0

0

3:23

12/07/2020

Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization

Quoc Tran-Dinh, Nhan Pham, Lam Nguyen

Keywords Paper

Optimization - Non-convex

0

0

0

0

12:35

06/12/2021

Novel Upper Bounds for the Constrained Most Probable Explanation Task

Tahrima Rahman, Sara Rouhani, Vibhav Gogate

Keywords Paper

optimization, adversarial robustness and security, graph learning, interpretability

0

0

0

0

13:19

06/12/2021

Stochastic $L^\natural$-convex Function Minimization

Haixiang Zhang, Zeyu Zheng, Javad Lavaei

Keywords Paper

optimization

0

0

0

0

14:34

18/07/2021

Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums

Chaobing Song, Stephen Wright, Jelena Diakonikolas

Keywords Paper

Optimization, Convex Optimization

0

0

0

0

18:04

06/12/2021

Instance-Dependent Bounds for Zeroth-order Lipschitz Optimization with Error Certificates

Francois Bachoc, Tom Cesari, Sébastien Gerchinovitz

Keywords Paper

theory, optimization

0

0

0

0

14:51

06/12/2020

Projection Robust Wasserstein Distance and Riemannian Optimization

Darren Lin, Chenyou Fan, Nhat Ho and
Marco Cuturi, Michael Jordan

Keywords Paper

Optimization -> Non-Convex Optimization; Optimization -> Stochastic Optimization, Deep Learning -> Optimization for Deep Networks

0

0

0

1

3:01

06/12/2020

Escaping the Gravitational Pull of Softmax

Jincheng Mei, Chenjun Xiao, Bo Dai and
Lihong Li, Csaba Szepesvari, Dale Schuurmans

Keywords Paper

0

0

0

0

3:27

06/12/2020

A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization

Digvijay Boob, Qi Deng, Guanghui Lan, Yilin Wang

Keywords Paper

0

0

0

0

2:54