Dimension-Adaptive Accuracy Certificates for Convex Optimization
Abstract
Many convex optimization methods use affine lower models to certify that a candidate solution is near optimal. Keeping full gradients can be costly when the informative directions occupy a small, initially unknown subspace. We develop accuracy certificates that store projected affine minorants together with bounds on the discarded components. The certificates remain valid as the subspace, queries, and certificate weights are chosen adaptively. For quadratic regularization, we derive an exact correction that accounts for when each discarded component was recorded, and a compact problem for selecting certificate weights. We also characterize the strongest lower bound supported by the compressed records when an ambient direction remains unused. The certificates can be used as stopping criteria for methods that provide valid affine minorants. We also analyze an adaptive cutting-plane construction whose oracle bound depends on the discovered dimension. Experiments on kernel SVM and ν-SVR problems show reduced certificate communication and stopping times under an emulated bandwidth constraint.
Related
- Convex Optimization Is Free When Accuracy Is Expensive
- ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
- A simple adaptive accelerated optimistic dual averaging method for unconstrained convex optimization in p-norm geometry
- Adaptive Restart under Unknown KL Geometry in Stochastic Weakly-Convex Optimization
- Restarted Accelerated Primal-Dual Algorithms with Adaptive Stepsizes for Nonlinear Conic Constrained Convex Optimization
BibTeX
@misc{gladin2026dimensionadaptive,
title = {{Dimension-Adaptive Accuracy Certificates for Convex Optimization}},
author = {Egor Gladin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.11448},
eprint = {2610.11448},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.11448},
}
RIS
TY - UNPB
TI - Dimension-Adaptive Accuracy Certificates for Convex Optimization
AU - Egor Gladin
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.11448
UR - https://arxiv.org/abs/2610.11448
AB - Many convex optimization methods use affine lower models to certify that a candidate solution is near optimal. Keeping full gradients can be costly when the informative directions occupy a small, initially unknown subspace. We develop accuracy certificates that store projected affine minorants together with bounds on the discarded components. The certificates remain valid as the subspace, queries, and certificate weights are chosen adaptively. For quadratic regularization, we derive an exact correction that accounts for when each discarded component was recorded, and a compact problem for selecting certificate weights. We also characterize the strongest lower bound supported by the compressed records when an ambient direction remains unused. The certificates can be used as stopping criteria for methods that provide valid affine minorants. We also analyze an adaptive cutting-plane construction whose oracle bound depends on the discovered dimension. Experiments on kernel SVM and ν-SVR problems show reduced certificate communication and stopping times under an emulated bandwidth constraint.
ER -