REVIEW 3 major objections 4 minor 39 references
Projection-Free Adaptive Gradients for Large-Scale Optimization
T0 review · 3 major / 4 minor · reviewed 2026-08-27 · deepseek-v4-flash
Pith's one-line read The paper demonstrates that AdaGrad-style adaptive gradients can be combined with stochastic Frank-Wolfe to yield projection-free algorithms that retain the O(1/t) convex rate and O(1/√t) nonconvex rate while accelerating practical…
desk verdict Clean new theoretical template with sound proofs, but the experiments run a configuration the theorems don't cover; the computational advantage is heuristic. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is the fixed-K Frank-Wolfe solver applied to the adaptive subproblem Q_t(x) = f(x_t) + ⟨g̃_t, x − x_t⟩ + (1/(2η_t))||x − x_t||²_{H_t}. Each inner iteration computes the gradient of this quadratic, calls a linear minimization oracle on the constraint set, and performs an exact line search along the resulting direction, so the subproblem is only partially solved. This lets the method inherit the adaptive, feature-specific step sizes of AdaGrad while preserving the projection-free outer loop of Frank-Wolfe.
What would settle it
Run AdaSFW on a strongly convex quadratic over the unit ball using the practical settings (γ_t = 1, constant η, K = 5) for $10^{4}$ iterations and record the objective gap; if it diverges or fails to decrease below some positive threshold while the decaying-step version converges, then the practical recipe used in the paper is not supported by the theory and the claimed advantage would need to be re-established on a case-by-case basis.
Extended reading notes
Core claim
The central discovery is that the non-Euclidean projection subproblem of AdaGrad, normally solved exactly by a projection onto the constraint set, can be replaced by K iterations of the Frank-Wolfe algorithm on that subproblem. With K fixed and small (around 5), the method stays projection-free and still leverages the adaptive metric H_t = diag(δ + $\sqrt$(sum of squared gradients)) to give feature-specific step sizes. Theorems 3.1, 3.3, 3.5, and 3.7 provide rates for the convex case of O(1/t) and for the nonconvex case of O(1/√t), with batch sizes $t^{2}$ for AdaSFW, t for AdaSVRF, and constant for AdaCSFW; the rates carry an extra factor κ = λ+0/λ−0 reflecting the conditioning of the adaptive metric.
Load-bearing premise
The convergence proofs require the outer step sizes γ_t to decay to zero and the learning rate η_t to equal λ−_t/L, but the implementation that produced the reported computational advantage sets γ_t = 1 and uses a constant learning rate, meaning the analyzed variant is not the one used in the experiments.
Editorial extensions
If this is right
- AdaSFW and its siblings achieve O(1/t) convergence on convex objectives and O(1/√t) on nonconvex objectives with the same batch-size scaling as their non-adaptive counterparts, so the theoretical cost of adding adaptivity is only the conditioning factor κ.
- For additively separable objectives, AdaCSFW can use a constant batch size per iteration, giving a projection-free method with O(1) gradient evaluations per step.
- In the reported neural-network experiments, the adaptive variants are the only projection-free methods that consistently outperform vanilla SFW in test accuracy.
- The generic template accepts any diagonal positive-definite H_t update and any stochastic gradient estimator, so it applies to future adaptive or variance-reduced variants without re-deriving the convergence analysis.
- The experiments indicate that the hybrid can beat both projection-free stochastic Frank-Wolfe methods and adaptive gradient methods on constrained problems, suggesting that partial subproblem solving is a viable way to make adaptive gradients projection-free.
Reading between the lines
- A natural testable extension is whether the constant-step implementation used in the experiments (γ_t = 1, constant learning rate) converges at a slower rate or with a bias term; the theory only covers decaying γ_t, so proving a convergence guarantee for the practical setting would close the gap between analysis and deployment.
- The fixed budget K acts as a cheap approximation of the adaptive descent direction; one could study how the optimal K depends on the condition number κ and the geometry of C, and whether an adaptive, stopping-criterion-based K would improve efficiency.
- If the method holds up, it suggests a general recipe: take any adaptive gradient algorithm that solves a proximal-type subproblem and replace exact solves with a fixed budget of conditional-gradient steps, yielding projection-free adaptive methods for arbitrary convex constraint sets.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes to combine adaptive gradients with stochastic Frank-Wolfe methods for constrained finite-sum minimization. The core idea is to replace the exact non-Euclidean projection used by AdaGrad with a small, fixed number K of inner Frank-Wolfe iterations on the quadratic subproblem, yielding projection-free methods AdaSFW, AdaSVRF, and AdaCSFW. The authors prove O(1/t) convergence for convex objectives (Theorems 3.1, 3.5, 3.7) and O(1/sqrt(T)) convergence for nonconvex objectives (Theorem 3.3), with proofs in Appendix D. They then report experiments on SVM classification, linear and logistic regression, and neural-network training, claiming computational advantages over stochastic FW baselines and over AdaGrad/AMSGrad for constrained problems. A momentum variant, AdamSFW, is introduced in Appendix A and used in the neural-network experiments.
Significance. If the results hold, the paper makes a useful contribution by transferring adaptive-gradient ideas, which are usually associated with unconstrained Euclidean updates, to the projection-free constrained setting while retaining the O(1/t) rates of stochastic FW. The theoretical derivations are self-contained and carefully written; the rates match those of standard SFW and explicitly track the dependence on the condition-number ratio κ and the number K of inner iterations. The paper is also honest in pointing out that the clipping assumption is needed in the theory. The main weakness is that the experimental implementation deliberately drops several theoretical requirements, and the nonconvex experiments partly rely on an unanalyzed momentum variant, so the paper's strongest practical claim is not backed by the convergence analysis and is not independently checkable without released code.
major comments (3)
- [§3.6 vs. §3.3–§3.5] The implementation used in Figures 1–5 is not covered by Theorems 3.1, 3.3, 3.5, or 3.7. Section 3.6 sets γ_t ← 1, uses a constant learning rate η_t, and does not clip the entries of H_t, whereas every theorem requires γ_t to decay (e.g., γ_t = 2/(t+2) or γ_t = 1/(t+1)^{1/2+ν}), requires η_t to equal λ^-_t/L (or mλ^-_t/(L||A||_2^2) for AdaCSFW), and requires the entries of H_t to be clipped to [λ^-_t, λ^+_t]. This gap is load-bearing: in the proof of Theorem 3.1, inequality (12) relies on the contraction factor (1−γ_t)E[ε_t] and on the summability of γ_t^2 LκD^2/2; with γ_t = 1 the contraction vanishes and the quadratic term becomes a constant, so the telescoping argument cannot produce E[ε_t] ≤ 2LD^2(K+1+κ)/(t+1). Similarly, inequality (8) uses the specific relation η_t = λ^-_t/L, and an unclipped H_t can make λ^+_t unbounded, invalidating κ = λ^+_0/λ^-_0. The reported computational advantage is therefore currently demonstrated only for a heuristic configuration whose convergence is not established by the paper's analysis. The authors should either extend the analysis to cover constant γ_t and η_t with unclipped H_t, prove a version under bounded adaptivity, or explicitly present the experiments as heuristic evidence outside the theoretical scope.
- [Appendix A and §4.2] The nonconvex neural-network experiments partly rely on AdamSFW (Algorithm 7), yet no convergence result is provided for AdamSFW: all theorems in Sections 3.3–3.5 concern AdaSFW, AdaSVRF, and AdaCSFW, and Appendix D does not analyze the momentum updates or the use of m_t in place of the gradient estimator in the inner subproblem. Since the paper's final remarks state that the proposed method is the only projection-free algorithm to improve on vanilla SFW in the neural-network experiments, and since those experiments include AdamSFW, the authors should either provide a convergence analysis for AdamSFW or clearly restrict the claim to AdaSFW and present AdamSFW as a purely heuristic extension.
- [§4 and reproducibility] No code or complete experimental configuration is made available, despite the paper's central claim being a demonstrated computational advantage of the proposed methods. This is especially problematic because the implemented variants are outside the assumptions of the theorems (see the first major comment), so the experiments are the only support for the practical claims. In addition, the captions of Figures 1–5 do not specify the horizontal axis (CPU time, iterations, or epochs), and the exact batch-size schedules and snapshot timings used for AdaSVRF and AdaCSFW are not fully stated. The authors should release code and provide complete configuration details, including all baseline hyperparameters, so that the reported improvements can be independently verified.
minor comments (4)
- [Appendix C, Fact C.1(i)] Fact C.1(i) states that the duality gap g(x) is strictly positive for all x ∈ C, but this is false at an interior stationary point where ∇f(x) = 0; the correct statement is g(x) ≥ 0. The proof of the fact also uses a strict inequality that does not follow when the gradient is zero. This does not affect the main theorems, which use the duality gap correctly, but it should be corrected.
- [§4.2 and Appendix B] The text says K ∼ 5 is a good default value, but the CIFAR-10 experiment uses K = 10 and the IMDB experiment uses K = 2; the sensitivity analysis in Appendix B shows that larger K can hurt CPU time. The authors should briefly explain how the per-experiment K values were selected and whether the reported differences are robust to the choice of K.
- [§4 and figure captions] The figure captions should state what is plotted on each axis and how the duality gap or test accuracy is computed; this information is currently missing and makes it difficult to compare the reported CPU-time advantages across algorithms.
- [Throughout] There are a few typographical and notational slips, such as 'contraint sets' in Section 5 and the use of γ_t ← 1 in Section 3.6 without a closing discussion of its relation to the theory; a careful proofreading pass is recommended.
Circularity Check
No circularity: the convergence analysis is self-contained and the experimental comparisons do not reduce to fitted inputs or self-cited premises.
full rationale
The derivation chain is self-contained. Theorems 3.1, 3.3, 3.5, and 3.7 are proved from standard smoothness and convexity inequalities, stochastic gradient variance bounds (Lemmas D.3, D.6, and D.8), and explicit step-size and batch-size choices; no conclusion is reused as an input. The constants L, G, D, and kappa are not fitted to the data and no parameter is renamed as a prediction. The self-citations to Combettes and Pokutta (2020, 2021) only motivate the design and are not load-bearing; no uniqueness theorem or ansatz is imported from them to force the result. Section 3.6 does reveal a gap between the analyzed configuration (decaying gamma_t, eta_t = lambda^-_t/L, clipped H_t) and the experiments (gamma_t = 1, tuned constant eta_t, no clipping). This is a coverage/reproducibility concern rather than circularity, because the experimental speedups are comparative measurements and are not derived from the theorems. Accordingly, no circular step is present.
Assumptions & free parameters
free parameters (2)
- learning rate eta =
10^-3/2 to 10^2 depending on experiment
- number of inner FW steps K =
2, 5, or 10 per experiment
assumptions (6)
- domain assumption Each f_i is L-smooth on C with Lipschitz gradients.
- domain assumption Gradients are bounded: max_i max_x ||grad f_i(x)|| <= G.
- domain assumption C is compact and convex.
- domain assumption For convex theorems, the functions f_i are convex.
- domain assumption For AdaCSFW, the objective is additively separable in data samples.
- standard math A linear minimization oracle over C is available.
Cite this review
Pith. "Pith review of Projection-Free Adaptive Gradients for Large-Scale Optimization." pith.science (2026). https://pith.science/paper/FHCVZKH4
@misc{pith2026200914114,
author = {Pith},
title = {Pith review of: Projection-Free Adaptive Gradients for Large-Scale Optimization},
year = {2026},
howpublished = {\url{https://pith.science/paper/FHCVZKH4}},
note = {Machine review of arXiv:2009.14114}
}
read the original abstract
The complexity in large-scale optimization can lie in both handling the objective function and handling the constraint set. In this respect, stochastic Frank-Wolfe algorithms occupy a unique position as they alleviate both computational burdens, by querying only approximate first-order information from the objective and by maintaining feasibility of the iterates without using projections. In this paper, we improve the quality of their first-order information by blending in adaptive gradients. We derive convergence rates and demonstrate the computational advantage of our method over the state-of-the-art stochastic Frank-Wolfe algorithms on both convex and nonconvex objectives. The experiments further show that our method can improve the performance of adaptive gradient algorithms for constrained optimization.
Figures
Figures from the paper (7 more)
Reference graph
Works this paper leans on
-
[1]
A. Argyriou, M. Signoretto, and J. A. K. Suykens. Hybrid conditional gradient-smoothing algorithms with applications to sparse and low rank regularization. In Regularization, Optimization, Kernels, and Support Vector Machines, pages 53--82. Chapman & Hall/CRC, 2014
work page 2014
-
[2]
T. Bertin-Mahieux, D. P. W. Ellis, B. Whitman, and P. Lamere. The M illion S ong dataset. In Proceedings of the 12th International Conference on Music Information Retrieval, 2011
work page 2011
-
[3]
L. Biewald. Experiment tracking with weights and biases, 2020. Software available at https://www.wandb.com
work page 2020
-
[4]
C.-C. Chang and C.-J. Lin. LIBSVM : A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2 0 (3): 0 1--27, 2011
work page 2011
-
[5]
C. W. Combettes and S. Pokutta. Boosting F rank- W olfe by chasing gradients. In Proceedings of the 37th International Conference on Machine Learning, pages 2111--2121, 2020
work page 2020
-
[6]
C. W. Combettes and S. Pokutta. Complexity of linear minimization and projection on some sets. arXiv preprint arXiv:2101.10040, 2021
work page Pith review arXiv 2021
-
[7]
A. Cutkosky and F. Orabona. Momentum-based variance reduction in non-convex SGD . In Advances in Neural Information Processing Systems, volume 32, pages 15236--15245, 2019
work page 2019
-
[8]
J. Dean, G. Corrado, R. Monga, K. Chen, M. Devin, M. Mao, M. Ranzato, A. Senior, P. Tucker, K. Yang, Q. V. Le, and A. Y. Ng. Large scale distributed deep networks. In Advances in Neural Information Processing Systems, volume 25, pages 1223--1231, 2012
work page 2012
Show all 39 references
-
[9]
Defazio and L
A. Defazio and L. Bottou. On the ineffectiveness of variance reduced optimization for deep learning. In Advances in Neural Information Processing Systems, volume 32, pages 1755--1765, 2019
2019
-
[10]
J. C. Duchi. Introductory lectures on stochastic optimization. In The Mathematics of Data. American Mathematical Society, 2018
2018
-
[11]
J. C. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12 0 (61): 0 2121--2159, 2011
2011
-
[12]
C. Fang, C. J. Li, Z. Lin, and T. Zhang. SPIDER : Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, volume 31, pages 689--699, 2018
2018
-
[13]
Frank and P
M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3 0 (1-2): 0 95--110, 1956
1956
-
[14]
Hazan and H
E. Hazan and H. Luo. Variance-reduced and projection-free stochastic optimization. In Proceedings of the 33rd International Conference on Machine Learning, pages 1263--1271, 2016
2016
-
[15]
M. Jaggi. Revisiting F rank- W olfe: Projection-free sparse convex optimization. In Proceedings of the 30th International Conference on Machine Learning, pages 427--435, 2013
2013
-
[16]
Johnson and T
R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, volume 26, pages 315--323, 2013
2013
-
[17]
N. S. Keskar and R. Socher. Improving generalization performance by switching from A dam to SGD . arXiv preprint arXiv:1712.07628, 2017
2017 arXiv
-
[18]
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations, 2015
2015
-
[19]
Krizhevsky
A. Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, 2009
2009
-
[20]
Lacoste-Julien
S. Lacoste-Julien. Convergence rate of F rank- W olfe for non-convex objectives. arXiv preprint arXiv:1607.00345, 2016
2016 arXiv
-
[21]
Lan and Y
G. Lan and Y. Zhou. Conditional gradient sliding for convex optimization. SIAM Journal on Optimization, 26 0 (2): 0 1379--1409, 2016
2016
-
[22]
E. S. Levitin and B. T. Polyak. Constrained minimization methods. USSR Computational Mathematics and Mathematical Physics, 6 0 (5): 0 1--50, 1966
1966
-
[23]
D. D. Lewis, Y. Yang, T. G. Rose, and F. Li. RCV1 : A new benchmark collection for text categorization research. Journal of Machine Learning Research, 5: 0 361--397, 2004
2004
-
[24]
L. Luo, Y. Xiong, Y. Liu, and X. Sun. Adaptive gradient methods with dynamic bound of learning rate. In Proceedings of the 7th International Conference on Learning Representations, 2019
2019
-
[25]
A. L. Maas, R. E. Daly, P. T. Pham, D. Huang, A. Y. Ng, and C. Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 1, pages 142--150, 2011
2011
-
[26]
H. B. McMahan and M. Streeter. Adaptive bound optimization for online convex optimization. In Proceedings of the 23rd Annual Conference on Learning Theory, 2010
2010
-
[27]
N \'e giar, G
G. N \'e giar, G. Dresdner, A. Y.-T. Tsai, L. El Ghaoui, F. Locatello, R. M. Freund, and F. Pedregosa. Stochastic F rank- W olfe for constrained finite-sum minimization. In Proceedings of the 37th International Conference on Machine Learning, pages 7253--7262, 2020
2020
-
[28]
B. T. Polyak. Introduction to Optimization. Optimization Software, 1987
1987
-
[29]
S. J. Reddi, S. Sra, B. P \'o czos, and A. Smola. Stochastic F rank- W olfe methods for nonconvex optimization. In 54th Annual Allerton Conference on Communication, Control, and Computing, pages 1244--1251, 2016
2016
-
[30]
S. J. Reddi, S. Kale, and S. Kumar. On the convergence of A dam and beyond. In Proceedings of the 6th International Conference on Learning Representations, 2018
2018
-
[31]
Schmidt, N
M. Schmidt, N. Le Roux, and F. Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162 0 (1-2): 0 83--112, 2017
2017
-
[32]
Z. Shen, C. Fang, P. Zhao, J. Huang, and H. Qian. Complexities in projection-free stochastic non-convex minimization. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, pages 2868--2876, 2019
2019
-
[33]
Tieleman and G
T. Tieleman and G. Hinton. Lecture 6e -- rmsprop: divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 4 0 (2): 0 26--31, 2012
2012
-
[34]
A. C. Wilson, R. Roelofs, M. Stern, N. Srebro, and B. Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, volume 30, pages 4148--4158, 2017
2017
-
[35]
J. Xie, Z. Shen, C. Zhang, H. Qian, and B. Wang. Efficient projection-free online methods with stochastic recursive gradient. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, pages 6446--6453, 2020
2020
-
[36]
Yurtsever, S
A. Yurtsever, S. Sra, and V. Cevher. Conditional gradient methods via stochastic path-integrated differential estimator. In Proceedings of the 36th International Conference on Machine Learning, pages 7282--7291, 2019
2019
-
[37]
M. D. Zeiler. Ada D elta: An adaptive learning rate method. arXiv preprint arXiv:1212.5701, 2012
2012 arXiv
-
[38]
Zhang, M
L. Zhang, M. Mahdavi, and R. Jin. Linear convergence with condition number independent access of full gradients. In Advances in Neural Information Processing Systems, volume 26, pages 980--988, 2013
2013
-
[39]
Zhang and F
T. Zhang and F. J. Oles. Text categorization based on regularized linear classification methods. Information Retrieval, 4: 0 5--31, 2001
2001
Reviewed August 27, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.