Convex Optimization

Follow this topic Ask about this topic

Recent momentum

+22%

11 papers in the last 28 days · 0.2% of indexed attention

Twelve weeks of publication activity for this topic as it is defined today.

Weekly history

Recent digests

What was published in this topic, kept on the site without email delivery.

Period ending 2026-09-21

5 new papers

A weekly snapshot of new work published in Convex Optimization.

Period ending 2026-09-14

5 new papers

A weekly snapshot of new work published in Convex Optimization.

Period ending 2026-09-07

2 new papers

A weekly snapshot of new work published in Convex Optimization.

102 papers

Latest in Convex Optimization

Browse all topics →

Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization
Sep 21, 2026Dan GarberConvex Optimization Sharp Joint-Kl Oracle Theory
Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates
Sep 17, 2026David Martínez-Rubio, Cristóbal GuzmánConvex Optimization Lipschitz Constant
The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings
Sep 17, 2026David Martínez-Rubio, Brian Bullins, Cristóbal Guzmán +1Convex Optimization Lipschitz Constant
Near-Optimal Pure Single-Loop Extragradient Method for Strongly Convex--Strongly Concave Minimax Optimization
Sep 17, 2026Minhao Zhang, Zi XuConvex Optimization Proximal Gradient Descent
Matching Multi-Loop Complexities with a Single Loop: Optimal Optimization Stationarity and Best-Known Game Stationarity in Nonconvex--Concave Minimax Optimization
Sep 16, 2026Minghao Zhang, Zi XuConvex Optimization Stationarity
Near-Optimal Nonconvex Matrix Completion
Sep 15, 2026Jian-Feng Cai, Xiliang Lu, Juntao YouTensor Completion Convex Optimization
Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions
Sep 11, 2026Rahul VazeConvex Optimization O(T^Β)$ Simultaneous Regret
Certifying Lower Bounds for Risk-Sensitive Reinforcement Learning under Adversarial State Perturbations
Sep 11, 2026Tong Li, Saunak Kumar Panda, Yisha XiangReinforcement Learning With Verifiable Reward Certification
How to Make the Gradient Mapping Small for Constrained Stochastic Min-Max Problems and Beyond
Sep 8, 2026Ahmet AlacaogluConvex Optimization Stochastic Optimization
Sparse Data Augmentation for Optimization with Provable Guarantees
Sep 8, 2026Behrooz Tahmasebi, Melanie WeberConvex Optimization Augmentation
Constrained Online Learning with Noisy Constraint Values
Sep 7, 2026Vaneet AggarwalConvex Optimization Learning-Augmented Algorithms
Operational Regimes in Non-Convex Optimization: A Multiplier-Based Taxonomy
Aug 31, 2026Seyed Mohsen Kazemi, Ali Movaghar, Shaahin hessabiConvex Optimization Norm
Nonlinear Model Predictive Control via Sequential Convex Programming for Drone-to-Drone Docking
Aug 11, 2026Neeraj Balachandar, Shriram Hari, Vishnu R. UnniModel Predictive Control Trajectory Optimization
A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise
Aug 10, 2026Jikai JinStochastic Smooth Convex Optimization Stochastic Optimization
An Inertial Block Proximal Linearized Method with Adaptive Momentum for Nonconvex and Nonsmooth Optimization
Aug 6, 2026Weifeng YangConvex Optimization Nonconvex
The Condition-Number Barrier in Sparse Least Squares
Aug 3, 2026Honghao Lin, Vahab Mirrokni, David P. WoodruffConvex Optimization Least Squares
Towards joint scaling laws with optimal batch size schedules
Jul 30, 2026Jiaxiang Li, Zhiqi Bu, Shiyun XuBatch Size Large Models
The Convergence Behavior of Adam under Heavy-Tailed Noise
Jul 29, 2026Yijiang PangAdam Convergence Analysis
Parameter-Free Dynamic Regret under Heavy-Tailed Noise
Jul 29, 2026Vaneet AggarwalLinear Regret Convex Optimization
Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization
Jul 28, 2026Zhaojun PengStochastic Smooth Convex Optimization Convex Optimization
Data-Dependent Regret and Polyak Corrections for Constrained Online Convex Optimization
Jul 28, 2026Wentao ZhangConvex Optimization O(T^Β)$ Simultaneous Regret
Graph-Based Correlation Matrix Generation: A Convex Optimization Approach
Jul 24, 2026Ali Fakhar, K{é}vin Polisano, Ir{è}ne Gannaz +1Tensor Completion Exponential Random Graph Models
Online Optimization of Difference-of-Convex Compositions with Smooth Mappings
Jul 21, 2026Jingwei Ji, Jong-Shi Pang, Renyuan XuConvex Optimization Proximal Gradient Descent
The Price of Hidden Curvature: An $\widetildeΩ (d^{5/4} \sqrt{T})$ Lower Bound for Bandit Convex Optimization
Jul 21, 2026Nived RajaramanO(T^Β)$ Simultaneous Regret Convex Optimization
Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory
Jul 21, 2026Michael Menart, Aleksandar Nikolov, Ohad ShamirConvex Optimization Lower Bounds
Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles
Jul 20, 2026Haichen Hu, David Simchi-LeviConvex Optimization Stochastic Smooth Convex Optimization
Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)
Jul 12, 2026Haricharan Balasundaram, Karthick Krishna Mahendran, Rahul VazeConvex Optimization O(T^Β)$ Simultaneous Regret
Understanding Schedule-Free Methods in Nonconvex Optimization: Rate Guarantees and Escaping Saddles
Jul 10, 2026Jiseok Chae, Donghwan KimConvex Optimization Convergence Analysis
Decentralized Stochastic Subgradient-type Methods with Communication Compression for Nonsmooth Nonconvex Optimization
Jul 2, 2026Siyuan Zhang, Nachuan Xiao, Xin LiuStochastic Smooth Convex Optimization Convex Optimization
Revisiting Decentralized Online Convex Optimization with Compressed Communication
Jul 2, 2026Hao Zhou, Xiaoyu Wang, Chang Yao +2Convex Optimization O(T^Β)$ Simultaneous Regret
Constrained Online Convex Optimization without Slater's Condition
Jun 30, 2026Kihyun Yu, Junehee Lee, Dabeen LeeConvex Optimization Stochastic Optimization
Privacy-Preserving Decentralized Cooperative Localization with Range-Only Measurements: A Convex Optimization Based Approach
Jun 29, 2026Nitesh Kumar, Reyshwanth Ganeshan, Sixu Li +2Robust Localization Collaborative Perception
Second-Order KKT Guarantees for Bregman ADMM in Nonconvex and Non-Lipschitz Optimization
Jun 26, 2026Shuang Li, Zhihui Zhu, Qiuwei LiConvex Optimization Nonconvex
Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RL
Jun 23, 2026Ankur Naskar, Swetha Ganesh, Vaneet AggarwalConstrained Reinforcement Learning Soft Actor-Critic
Adam Converges in Nonsmooth Nonconvex Optimization
Jun 21, 2026Zijian LiuAdam Convex Optimization
Deep-Unfolded Coordination
Jun 18, 2026Hunter Kuperman, Minchan Jung, Rahul V. Ghosh +2Multi-Agent Coordination Deep Unfolding Networks
Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses
Jun 18, 2026Zhuoyu Cheng, Kohei Hatano, Eiji TakimotoConvex Optimization Convex Sets
Semiglobal Input-Delay Tolerance Algorithm for Distributed Nonconvex Optimization of Networked Nonlinear Systems
Jun 18, 2026Jing-Zhe Xu, Zhi-Wei Liu, Ming-Feng Ge +2Convex Optimization Convergence Analysis
Transformer-Based Warm-Starting for Feasible and Optimal Terminal Approach to Tumbling Objects with Space Manipulators
Jun 15, 2026Yuji Takubo, Maximilian Adang, Mac Schwager +1Trajectory Optimization Cold-Start
Accelerated Convex Optimization via Hamiltonian Dynamics with Deterministic Integration Time
Jun 15, 2026Xiuyuan Wang, Vishwak Srinivasan, Qiang Fu +3Convex Optimization Invertible Flows
Optimal Hidden-Target Learning for Online Inventory Optimization on General Convex Sets
Jun 12, 2026Anthony Pineci, Yunzong XuMonotonic Inventory Estimation Convex Optimization
Online Convex Optimization with Sublinear Noisy Probes
Jun 12, 2026Simone Di Gregorio, Anupam Gupta, Stefano Leonardi +1O(T^Β)$ Simultaneous Regret Convex Optimization
Last-Iterate Convergence of Optimistic Multiplicative Weight Update
Jun 10, 2026Francesco OrabonaConvex Optimization Convergence
Capacity-Constrained Online Convex Optimization with Delayed Feedback
Jun 10, 2026Alexander Ryabchenko, Idan Attias, Daniel M. RoyO(T^Β)$ Simultaneous Regret Convex Optimization
LEAF: A Learning-Enabled ADMM Framework for Accelerated Convex Optimization
Jun 8, 2026Binh Nguyen, Trinh Tran, Truong X. NghiemConvex Optimization Alternating Direction Method Of Multiplier
Noise-Adaptive High-Probability Regret Bounds for Online Convex Optimization
Jun 6, 2026Wentao Zhang, Yutong Zhang, Wentao MoConvex Optimization Linear Regret
Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization
Jun 5, 2026Ming Sun, Kun YuanStochastic Smooth Convex Optimization Stochastic Gradient Descent
Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leader
Jun 4, 2026Jongyeong Lee, Junya Honda, Shinji Ito +1Learning Rates Bandits
Robust and sparse support vector machine via hybrid truncated loss for supervised classification
Jun 4, 2026Yuliang Yang, Chen Chen, Yuxiang Liu +1Support Vector Machines Multi-View
Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization
Jun 3, 2026Dongruo ZhouConvex Optimization Lower Bounds
Analytical Evaluation of DCA Convergence Properties for Minimizing Prediction Functions of Gaussian RBF Support Vector Regression
Jun 2, 2026Yohei Kakimoto, Yuto Omae, Hirotaka TakahashiConvex Optimization Radial Basis Function
From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization
Jun 1, 2026Moses Charikar, Chirag Pabbaraju, Ambuj TewariConvex Optimization Curvature-Aware Quadratic Banks
In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise
May 30, 2026Zijian LiuStochastic Smooth Convex Optimization Stochastic Gradient Descent
MoSSP: A Momentum-Based Single-Loop Stochastic Penalty Method for Nonconvex Constrained DC-Regularized Optimization
May 28, 2026Luxuan Li, Chunfeng Cui, Xiao WangConvex Optimization Penalties
Decentralized Parameter-Free Online Learning with Compressed Gossip
May 27, 2026Tomas Ortega, Hamid JafarkhaniLearning-Augmented Algorithms Near-Optimal Regret Guarantees
Convergence of Spectral Descent for Non-smooth Optimization
May 26, 2026Yixuan Yang, Yuqing He, Song LiMuon Optimizer Convex Optimization
Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback
May 25, 2026Anas Barakat, Andreas Kontogiannis, Vasilis Pollatos +2O(T^Β)$ Simultaneous Regret Convex Optimization
Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise
May 23, 2026Zhuanghua Liu, Luo LuoStochastic Smooth Convex Optimization Convex Optimization
Convex Optimization for Alignment and Preference Learning on a Single GPU
May 22, 2026Miria Feng, Mert PilanciPreference Alignment Direct Preference Optimization
Bandit Convex Optimization with Gradient Prediction Adaptivity
May 21, 2026Shuche Wang, Adarsh Barik, Vincent Y. F. TanConvex Optimization Bandits

Sep 21, 2026 · math.OCJ/K move · Enter open · S save

Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization

Dan Garber

We consider a standard convex composite optimization problem with either smooth or nonsmooth objective function, and under quadratic growth. In recent years, several works gave algorithms based on a \textit{weak proximal oracle} (WPO) that essentially match in oracle complexities proximal (sub)gradient methods relying on exact prox operations. Importantly, such WPOs, which relax the strong optimality condition of the standard prox operator, may admit much more efficient implementation in terms of runtime when optimal solutions have some sparse structure. A question remained if such WPO-based methods can be accelerated (in the sense of Nesterov's accelerated gradient). In this work we provide a negative answer by establishing lower bounds against both deterministic and randomized methods. Thus, while WPOs can substantially reduce the cost of individual oracle calls, this comes with an inherent loss in oracle complexity. We also provide a new upper-bound for WPO-based nonsmooth convex composite optimization, nearly matching the proximal subgradient method.

Convex Optimization Sharp Joint-Kl Oracle Theory

Open paper Ask about it PDF

Recent momentum

Neighbouring directions

Recent digests

5 new papers

5 new papers

2 new papers

Latest in Convex Optimization