Cover Image

Tight Lower Bounds for the Bit and Inner Product Oracle for Constrained Convex Optimization

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Basu, Amitabh, Kerger, Phillip, Molinaro, Marco
Format:	Preprint
Published:	2025
Subjects:	Optimization and Control
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Universal Transfer Theorem for Convex Optimization Algorithms Using Inexact First-order Oracles
by: Kerger, Phillip, et al.
Published: (2024)

Sample Complexity of Stochastic Optimization with Integer Variables
by: Cheng, Hongyu, et al.
Published: (2026)

Lower Bounds for Linear Minimization Oracle Methods Optimizing over Strongly Convex Sets
by: Grimmer, Benjamin, et al.
Published: (2026)

Lower Complexity Bounds for Nonconvex-Strongly-Convex Bilevel Optimization with First-Order Oracles
by: Ji, Kaiyi
Published: (2025)

Tight Bounds for Online Convex Optimization with Adversarial Constraints
by: Sinha, Abhishek, et al.
Published: (2024)

Theoretical Challenges in Learning for Branch-and-Cut
by: Cheng, Hongyu, et al.
Published: (2026)

Tight Lower Bounds under Asymmetric High-Order Hölder Smoothness and Uniform Convexity
by: Bai, Cedar Site, et al.
Published: (2024)

Tight Lower Bounds and Optimal Algorithms for Stochastic Nonconvex Optimization with Heavy-Tailed Noise
by: Fradin, Adrien, et al.
Published: (2025)

Weak Proximal Newton Oracles for Composite Convex Optimization
by: Garber, Dan
Published: (2025)

Generalization Guarantees for Learning Branch-and-Cut Policies in Integer Programming
by: Cheng, Hongyu, et al.
Published: (2025)

Learning Cut Generating Functions for Integer Programming
by: Cheng, Hongyu, et al.
Published: (2024)

Lower Bounds for Frank-Wolfe on Strongly Convex Sets
by: Halbey, Jannis, et al.
Published: (2026)

Online Convex Optimization with a Separation Oracle
by: Mhammedi, Zakaria
Published: (2024)

Revisiting Stochastic Gradient Descent for Strongly Convex Objectives: Tight Uniform-in-Time Bounds
by: Chen, Kang, et al.
Published: (2025)

FICA: Faster Inner Convex Approximation of Chance Constrained Grid Dispatch with Decision-Coupled Uncertainty
by: Zhou, Yihong, et al.
Published: (2025)

New Lower Bounds for Stochastic Non-Convex Optimization through Divergence Decomposition
by: Saad, El Mehdi, et al.
Published: (2025)

Computing Lower Bounds on the Nonnegative Rank via Non-Convex Optimization Solvers
by: Baeckelant, Timothy, et al.
Published: (2026)

Tight Bounds on Polynomials and Its Application to Dynamic Optimization Problems
by: Vila, Eduardo M. G., et al.
Published: (2024)

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

Model Construction for Convex-Constrained Derivative-Free Optimization
by: Roberts, Lindon
Published: (2024)

Tight Generalization Bounds for Noiseless Inverse Optimization
by: Fatemi, Pouria, et al.
Published: (2026)

A Taylor-Bernstein Inner Approximation Algorithm for Path-Constrained Dynamic Optimization
by: Chang, Yuan, et al.
Published: (2026)

HUANet: Hard-Constrained Unrolled ADMM for Constrained Convex Optimization
by: Tran, Trinh, et al.
Published: (2026)

An Adaptive Parameter-free and Projection-free Restarting Level Set Method for Constrained Convex Optimization Under the Error Bound Condition
by: Lin, Qihang, et al.
Published: (2020)

Complexity Analysis of Convex Majorization Schemes for Nonconvex Constrained Optimization
by: Wang, Nuozhou, et al.
Published: (2025)

Guaranteed Feasibility in Differentially Private Linearly Constrained Convex Optimization
by: Benvenuti, Alexander, et al.
Published: (2024)

Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks
by: Kovalev, Dmitry, et al.
Published: (2024)

Solving Convex Smooth Function Constrained Optimization Is Almost As Easy As Unconstrained Optimization
by: Zhang, Zhe, et al.
Published: (2022)

Constructing Tight Quadratic Relaxations for Global Optimization: II. Underestimating Difference-of-Convex (D.C.) Functions
by: Strahl, William R., et al.
Published: (2024)

Constructing Tight Quadratic Relaxations for Global Optimization: I. Outer-Approximating Twice-Differentiable Convex Functions
by: Strahl, William R., et al.
Published: (2024)

Probabilistic analysis of dual decomposition on two-stage stochastic integer programs
by: Dey, Santanu S., et al.
Published: (2026)

Non-Monotonicity of Branching Rules with respect to Linear Relaxations
by: Shah, Prachi, et al.
Published: (2024)

Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization
by: Jiang, Ruichen, et al.
Published: (2024)

On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms
by: Kovalev, Dmitry, et al.
Published: (2024)

Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut
by: Cheng, Hongyu, et al.
Published: (2024)

Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization
by: Armacki, Aleksandar, et al.
Published: (2026)

Lower Complexity Bounds of First-order Methods for Affinely Constrained Composite Non-convex Problems
by: Liu, Wei, et al.
Published: (2025)

A Discretization Approach for Bilevel Optimization with Low-Dimensional and Non-Convex Lower-Level
by: Jiang, Xiaotian, et al.
Published: (2025)

An Exact Penalty Approach for Equality Constrained Optimization over a Convex Set
by: Xiao, Nachuan, et al.
Published: (2025)

Beyond Convexity: Proximal-Perturbed Lagrangian Methods for Efficient Functional Constrained Optimization
by: Moon, Sang Bin, et al.
Published: (2024)