Imagen de Portada

Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Blanchard, Moise
Formato:	Preprint
Publicado:	2024
Materias:	Optimization and Control Computational Complexity Data Structures and Algorithms Machine Learning
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Efficient Convex Optimization Requires Superlinear Memory
por: Marsden, Annie, et al.
Publicado: (2022)

Unifying Formal Explanations: A Complexity-Theoretic Perspective
por: Bassan, Shahaf, et al.
Publicado: (2026)

A Control-Theoretic Perspective on Optimal High-Order Optimization
por: Lin, Tianyi, et al.
Publicado: (2019)

A Continuous-Time Perspective on Global Acceleration for Monotone Equation Problems
por: Lin, Tianyi, et al.
Publicado: (2022)

Negative Stepsizes Make Gradient-Descent-Ascent Converge
por: Shugart, Henry, et al.
Publicado: (2025)

Solving convex QPs with structured sparsity under indicator conditions
por: Bienstock, Daniel, et al.
Publicado: (2024)

Centrality of shortest paths: Algorithms and complexity results
por: Phosavanh, Johnson, et al.
Publicado: (2024)

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank
por: Kurpisz, Adam, et al.
Publicado: (2026)

A note on the complexity of the picker routing problem in multi-block warehouses and related problems
por: Prunet, Thibault, et al.
Publicado: (2023)

Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
por: Chen, Shengminjie, et al.
Publicado: (2026)

Algorithms for Standard-form ILP Problems via Komlós' Discrepancy Setting
por: Gribanov, Dmitry, et al.
Publicado: (2026)

Delta-modular ILP Problems of Bounded Codimension, Discrepancy, and Convolution (new version)
por: Cherniavskii, M., et al.
Publicado: (2024)

Oracle-based Uniform Sampling from Convex Bodies
por: Dang, Thanh, et al.
Publicado: (2025)

Computational-Statistical Tradeoffs from NP-hardness
por: Blanc, Guy, et al.
Publicado: (2025)

Grams: Gradient Descent with Adaptive Momentum Scaling
por: Cao, Yang, et al.
Publicado: (2024)

Min-Max Optimization Requires Exponentially Many Queries
por: Bernasconi, Martino, et al.
Publicado: (2026)

Convex Optimization with Nested Evolving Feasible Sets
por: M., Karthick Krishna, et al.
Publicado: (2026)

Gradient Testing and Estimation by Comparisons
por: Tao, Xiwen, et al.
Publicado: (2024)

A Θ(m^9) ternary minimum-cost network flow LP model of the Assignment Problem polytope with applications to hard combinatorial optimization problems
por: Diaby, Moustapha
Publicado: (2016)

Near Optimal Alphabet-Soundness Tradeoff PCPs
por: Minzer, Dor, et al.
Publicado: (2024)

Simultaneous Network Design with Restricted Link Usage
por: Kakimura, Naonori, et al.
Publicado: (2025)

Semidefinite programming and linear equations vs. homomorphism problems
por: Ciardo, Lorenzo, et al.
Publicado: (2023)

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
por: Kunisky, Dmitriy, et al.
Publicado: (2022)

Gradient-Free Method for Heavily Constrained Nonconvex Optimization
por: Shi, Wanli, et al.
Publicado: (2024)

Online Bilevel Optimization: Regret Analysis of Online Alternating Gradient Methods
por: Tarzanagh, Davoud Ataee, et al.
Publicado: (2022)

Accelerating Proximal Gradient Descent via Silver Stepsizes
por: Bok, Jinho, et al.
Publicado: (2024)

Optimal Scalarizations for Sublinear Hypervolume Regret
por: Zhang, Qiuyi
Publicado: (2023)

Stepsize Hedging: an Alternative Mechanism for Accelerating Gradient Descent
por: Altschuler, Jason M., et al.
Publicado: (2026)

Learning-Augmented Algorithms for the Bahncard Problem
por: Zhao, Hailiang, et al.
Publicado: (2024)

Online Convex Optimization with Switching Cost with Only One Single Gradient Evaluation
por: Shah, Harsh, et al.
Publicado: (2025)

Optimal Decentralized Smoothed Online Convex Optimization
por: Bhuyan, Neelkamal, et al.
Publicado: (2024)

Optimal Bounds for Adversarial Constrained Online Convex Optimization
por: Ferreira, Ricardo N., et al.
Publicado: (2025)

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
por: Chen, Sitan, et al.
Publicado: (2026)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
por: Garg, Sumegha, et al.
Publicado: (2026)

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
por: Alman, Josh, et al.
Publicado: (2024)

Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems
por: Grigorescu, Elena, et al.
Publicado: (2024)

Complexity of Classical Acceleration for $\ell_1$-Regularized PageRank
por: Fountoulakis, Kimon, et al.
Publicado: (2026)

AdaBoost is not an Optimal Weak to Strong Learner
por: Høgsgaard, Mikael Møller, et al.
Publicado: (2023)

On the Hardness of Approximation of the Fair k-Center Problem
por: Thejaswi, Suhas
Publicado: (2026)

The Sample Complexity of Replicable Realizable PAC Learning
por: Larsen, Kasper Green, et al.
Publicado: (2026)