REVIEW 3 major objections 3 minor 1 cited by
Distribution free M-estimation
T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read This paper proves that convex M-estimation is distribution-free minimizable exactly when the loss is uniformly Lipschitz on every compact subset of the parameter interior, with a second condition handling unbounded spaces.
desk verdict A genuinely new dividing-line result for distribution-free convex M-estimation; the main caveat is that the multi-dimensional 'no loss of generality' for Assumption A.1 is not proved. 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 load-bearing objects are Condition C.1, Condition C.2, and the achievable set $\Theta_{\mathrm{ach}}$. Condition C.1 asks that on every compact subset $\Theta_0$ of the interior of $\Theta$, the losses $\ell_z(\cdot)$ share one Lipschitz constant; Condition C.2 adds that for every $\epsilon>0$ and every finitely supported distribution $Q$, some fixed compact set contains points within $\epsilon$ of the optimum of $L_Q$. The achievable set collects the points that could plausibly minimize $L_P$ for some $P$, and Assumption A.1 identifies it with $\Theta$. The lower-bound proofs convert optimization into testing via the distance $d_{\mathrm{opt}}(f_0,f_1)$ and the inequality $M^{\mathrm{low}}_n \ge \tfrac12 d_{\mathrm{opt}}(L_{P_0},L_{P_1})(1 - \|P_0^n - P_1^n\|_{\mathrm{TV}})$, using directable sets to place subgradients in the directions needed to separate two hard distributions.
What would settle it
Compute the minimax excess risk for the exponential loss $\ell_z(\theta)=e^{z\theta}$ with $Z=\{-1,1\}$ and $\Theta=\mathbb{R}$ at, say, $n=100$; the paper predicts that the minimum over estimators of the worst-case excess risk tends to zero, so any constant lower bound would falsify Proposition 2. Conversely, exhibit an estimator for the absolute loss on $\mathbb{R}$ whose uniform excess risk tends to zero, which would contradict Theorem 3.
Extended reading notes
Core claim
The central discovery is a precise equivalence: under the assumption that the achievable minimizer set is the whole parameter space, the minimax risk $M_n(\ell,Z,\Theta)$ tends to zero if and only if Condition C.1 holds when $\Theta$ is compact, and if and only if Condition C.2 holds when $\Theta$ may be unbounded. The positive direction is constructive: average stochastic subgradient steps over carefully chosen subsets $\Theta_n \uparrow \Theta$. The negative direction reduces estimation to a two-distribution testing problem: two nearly indistinguishable distributions are built whose population losses are separated by a constant in the optimization distance $d_{\mathrm{opt}}$, so any estimator with small excess risk would have to solve a statistically impossible test. Consequences include the log loss for multinomials being distribution-free minimizable despite its unbounded derivatives at the boundary, and the globally Lipschitz absolute loss for medians being not minimizable over $\mathbb{R}$.
Load-bearing premise
The main theorems stand on the assumption that the achievable minimizer set equals the whole parameter space, and if a problem's plausible minimizers form a proper subset, the dividing line must be applied to that subset rather than to the original space.
Editorial extensions
If this is right
- When Condition C.1 (and, for unbounded spaces, Condition C.2) holds, there exist estimators whose minimax excess risk tends to zero uniformly over all distributions; when it fails, every estimator has minimax excess risk bounded away from zero.
- The log loss for multinomials is distribution-free minimizable despite not being Lipschitz at the boundary of the simplex.
- The squared loss on a bounded interval with $Z=\mathbb{R}$, and the absolute-value loss for medians on $\mathbb{R}$, are not distribution-free minimizable even though the absolute loss is globally Lipschitz.
- No universal convergence rate exists: even with a two-point sample space, rates can be arbitrarily slow while Condition C.1 holds.
- Finding stationary points can be strictly easier than minimizing: for quantile losses, empirical minimizers give $O(1/\sqrt{n})$ stationarity guarantees even though distribution-free minimization is impossible.
Reading between the lines
- As an inference from the paper's logic, one can test minimizability of a concrete model without solving the minimax problem: check whether $\sup_{z \in Z} \|\partial \ell_z(\theta)\|$ explodes as $\theta$ approaches the boundary of $\Theta$ or infinity.
- I would expect the unbounded-domain condition to be expressible as a uniform recession condition on the family of losses, so Condition C.2 might relate to whether the recession functions of the losses are jointly bounded below.
- The stationary-point results suggest that the excess-loss objective is one of several optimality criteria; for problems such as quantile prediction, a stationarity metric is the right target and is attainable where loss minimization is not.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the minimax excess-risk M_n(ℓ,Z,Θ) for convex M-estimation when the sampling distribution P is completely unknown and only the loss ℓ, the sample space Z, and the parameter space Θ are fixed. The main results are a dichotomy: under Assumption A.1 (Θ = Θach, the set of achievable minimizers), Theorem 1 and Theorem 3 give lower bounds showing that the minimax risk is bounded away from zero when Conditions C.1 and C.2 fail, while Theorem 2 and Proposition 2 give upper bounds when these conditions hold. The examples (log loss, exponential loss, squared loss, and median/quantile losses) are used to argue that global Lipschitz continuity is neither necessary nor sufficient for distribution-free minimization. Section 4 changes the optimality criterion to stationarity and proves a concentration bound for empirical minimizers of Lipschitz losses.
Significance. If the characterization is correct, this is a substantial contribution: it replaces worst-case Lipschitz bounds with an instance-specific, parameter-free dichotomy that is distinct from uniform-convergence and VC-type learnability conditions, and the examples are instructive. The paper is otherwise careful: the lower-bound machinery via the optimization distance dopt and Le Cam inequalities is standard but applied with concrete constructions, and the proofs are unusually detailed. The main weakness is that the multi-dimensional justification of Assumption A.1 is incomplete, so the dichotomy is rigorously established only for the reduced problem on Θach unless the missing argument is supplied.
major comments (3)
- [Section 2.1.2 / Appendix A.2] Assumption A.1 is load-bearing in Lemma 3.7 and hence in the lower bounds of Theorems 1 and 3, but the claim that the assumption is "no loss of generality" is proved completely only in the one-dimensional case. Lemma A.3 shows that each unconstraining halfspace H satisfies L*_P(H ∩ Θ) = L*_P(Θ) for all P ∈ Pℓ, and the "trivial remark" in Appendix A.2 shows that for each finitely supported Q and each θ0 ∉ Θach there exists θ ∈ Θach with L_Q(θ) ≤ L_Q(θ0). The theorems require a stronger statement: that argmin_P L_P intersects Θach for every P, or equivalently that a single projection-like map onto Θach dominates every point. In d ≥ 2 the family of unconstraining halfspaces is not obviously closed under finite intersections, so Lemma A.3 alone does not imply this intersection property. Please supply the missing multi-dimensional argument (for example a Helly/FIP argument using compactness of the argmin sets) or explicitly state that Theorems 1 and 3 characterize the reduced problem on Θach rather than the original Θ.
- [Section 3.6.3] The hard-instance construction for Theorem 3 in the d-dimensional case uses the same symbol Q for two different distributions: the growth distribution from Lemma 3.17 and the distribution appearing in condition (i), which arises from the failure of Condition C.2'. As printed, P0 := Q and P1 := (1 − δ/n)Q + δ/n Q, so P0 = P1, and the derivative computation applies DL_Q twice. The intended construction evidently requires distinct distributions Q_bad (from condition (i)) and Q_growth (from Lemma 3.17), with P0 = Q_bad and P1 = (1 − δ/n)Q_bad + δ/n Q_growth. Please rewrite this paragraph with distinct notation and re-verify the displayed inequalities for the mixture.
- [Section 3.3] The proof of Theorem 2 chooses δ_n → 0 "slowly enough" so that δ_n M_{θ0} diam(Θ) + M(Θ_{δ_n}) diam(Θ)/√n → 0. This requires justification: M(Θδ) is finite for each δ > 0 but may grow without bound as δ ↓ 0, so the existence of a sequence δ_n → 0 with M(Θ_{δ_n}) = o(√n) is not automatic from the statement of Condition C.1. The gap is easily filled, for example by using the monotonicity of δ ↦ M(Θδ) and choosing δ_n = inf{δ : M(Θδ) ≤ √n/log n}, but as written the argument is an assertion rather than a proof.
minor comments (3)
- [Equation (18)] In the one-dimensional proof of Theorem 1, the displayed inequality "anδ/(2a + n) ≥ aδ" is false; the correct lower bound is anδ/(2a + n) ≥ aδ/2 for n ≥ 2a, which is all the subsequent argument needs.
- [Lemma 3.13] The separation argument in the proof of Lemma 3.13 separates the sub-optimality set Sϵ from Θ_t = Θ ∩ tB₂; this is not enough to contradict the assumed intersection with H_{u,t}. One should instead separate Sϵ from the full ball tB₂, which gives a direction u with H_{u,t} disjoint from Sϵ, and then invoke the assumption for that u.
- [Section 3.6.3] The phrase "As in Sec. 3.6" near the start of Section 3.6.3 appears to be a cross-reference error; it should presumably refer to Section 3.5.2, the one-dimensional elimination of infinite losses.
Circularity Check
No significant circularity: the paper's characterization is derived from stated convex-analytic conditions via standard minimax testing arguments; self-citations are to non-fitted, external results.
full rationale
I find no circular step. Theorems 1 and 3 prove lower bounds by explicitly constructing two finitely supported distributions P0 and P1, computing the optimization distance dopt(LP0, LP1) and the total-variation bound on the product measures, and then invoking the standard Le Cam reduction (13). Condition C.1 and C.2 are not defined in terms of the minimax risk; they are separate analytic conditions on the losses, and the paper proves both directions under Assumption A.1. Theorem 2 and Proposition 2 are constructive achievability results using stochastic subgradient averaging over chosen compact subsets, not restatements of the conclusion. The paper does not fit any parameter to data and then rename the fit as a prediction. The self-citations to the first author's lecture notes [17] for inequality (13) and to [18] for a quantile bound are not load-bearing in a circular sense: inequality (13) is a parameter-free, standard testing lower bound whose proof is not tailored to the present claim, and the quantile bound is a secondary comparison. The only potentially load-bearing uncontrolled point is Assumption A.1, that one may replace the parameter space by its achievable set with no loss of generality; the paper explicitly flags this as an assumption ('we make the following standing assumption ... with essentially no loss of generality except that we could replace theta in each theorem with theta_ach'), and the multidimensional verification in Appendix A is arguably thin. But this is a rigor or correctness concern, not circularity: the theorems are conditional on Assumption A.1, and the lower-bound proofs do not presuppose the minimax risk's answer. A missing proof or incomplete justification is not the same as a derivation that reduces to its input by construction.
Assumptions & free parameters
assumptions (6)
- standard math Standard convex analysis (subdifferentials, recession functions, epi-convergence, integral form of convex functions)
- domain assumption The loss ℓ_z is closed convex proper for each z, finite on int Θ, and measurable in z
- domain assumption Integrability condition (9) defining Pℓ
- ad hoc to paper Assumption A.1: The achievable set Θach equals Θ
- standard math Le Cam's inequalities and the optimization-to-testing reduction (13)
- standard math Epi-convergence of empirical risk processes
Cite this review
Pith. "Pith review of Distribution free M-estimation." pith.science (2026). https://pith.science/paper/WD6WWJBS
@misc{pith2026250522807,
author = {Pith},
title = {Pith review of: Distribution free M-estimation},
year = {2026},
howpublished = {\url{https://pith.science/paper/WD6WWJBS}},
note = {Machine review of arXiv:2505.22807}
}
read the original abstract
The basic question of delineating those statistical problems that are solvable without making any assumptions on the underlying data distribution has long animated statistics and learning theory. This paper characterizes when a convex M-estimation or stochastic optimization problem is solvable in such an assumption-free setting, providing a precise dividing line between solvable and unsolvable problems. The conditions we identify show, perhaps surprisingly, that Lipschitz continuity of the loss being minimized is not necessary for distribution free minimization, and they are also distinct from classical characterizations of learnability in machine learning.
Figures
Forward citations
Cited by 1 Pith paper
-
Finding a stationary point of a stochastic convex problem
For stochastic convex optimization, a randomized proximal-point algorithm achieves asymptotic ε-stationarity — the subdifferential genuinely contains a small element — without smoothness or Lipschitz-gradient assumptions.
Reference graph
Works this paper leans on
-
[1]
A. Agarwal, P. L. Bartlett, P. Ravikumar, and M. J. Wainwright. Information-theoretic lower bounds on the oracle complexity of convex optimization. IEEE Transactions on Information Theory, 58(5):3235–3249, 2012
work page 2012
-
[2]
N. Alon, S. Ben-David, N. Cesa-Bianchi, and D. Haussler. Scale-sensitive dimensions, uniform convergence, and learnability. Journal of the Association for Computing Ma- chinery, 44(4):615–631, 1997
work page 1997
-
[3]
A. Angelopoulos, E. Cand` es, and R. J. Tibshirani. Conformal PID control for time series prediction. In Advances in Neural Information Processing Systems 36 , 2023
work page 2023
-
[4]
A. N. Angelopoulos, M. I. Jordan, and R. J. Tibshirani. Gradient equilibrium in online learning: Theory and applications. arXiv:2501.08330 [cs.LG] , 2025
arXiv 2025
-
[5]
M. Anthony and P. Bartlet. Neural Network Learning: Theoretical Foundations . Cam- bridge University Press, 1999
work page 1999
-
[6]
Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming, Series A , 199:165–214, 2023
work page 2023
-
[7]
R. Bahadur and L. Savage. The nonexistence of certain statistical procedures in non- parametric problems. Annals of Mathematical Statistics , 27(4):1115–1122, 1956
work page 1956
-
[8]
R. F. Barber, E. J. Cand` es, A. Ramdas, and R. J. Tibshirani. The limits of distribution- free conditional predictive inference. Information and Inference , 10(2):455–482, 2021
work page 2021
Show all 43 references
-
[9]
P. L. Bartlett and S. Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research , 3:463–482, 2002
2002
-
[10]
D. P. Bertsekas. Stochastic optimization problems with nondifferentiable cost functionals. Journal of Optimization Theory and Applications , 12(2):218–231, 1973
1973
-
[11]
L. D. Brown. Fundamentals of Statistical Exponential Families. Institute of Mathematical Statistics, Hayward, California, 1986. 34
1986
-
[12]
Bubeck and D
S. Bubeck and D. Mikulincer. How to trap a gradient flow. In Proceedings of the Thirty Third Annual Conference on Computational Learning Theory , pages 940–960, 2020
2020
-
[13]
Chatterjee, J
S. Chatterjee, J. Duchi, J. Lafferty, and Y. Zhu. Local minimax complexity of stochastic convex optimization. In Advances in Neural Information Processing Systems 29 , 2016
2016
-
[14]
T. M. Cover and P. E. Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory , 13:21–27, 1967
1967
-
[15]
Devroye, L
L. Devroye, L. Gy¨ orfi, and G. Lugosi. A Probabilistic Theory of Pattern Recognition . Springer, 1996
1996
-
[16]
D. Donoho. One-sided inference about functionals of a density. Annals of Statistics , 16 (4):1390–1420, 1988
1988
-
[17]
J. C. Duchi. Introductory lectures on stochastic convex optimization. In The Mathematics of Data , IAS/Park City Mathematics Series. American Mathematical Society, 2018
2018
-
[18]
J. C. Duchi. A few observations on sample-conditional coverage in conformal prediction. arXiv:2503.00220 [math.ST] , 2025
2025 arXiv
-
[19]
J. C. Duchi, M. I. Jordan, and H. B. McMahan. Estimation, optimization, and parallelism when data is sparse. In Advances in Neural Information Processing Systems 26 , 2013
2013
-
[20]
Foster and R
D. Foster and R. Vohra. Asymptotic calibration. Biometrika, 85(2):379–390, 1998
1998
-
[21]
D. P. Foster and S. Hart. Forecast hedging and calibration. Journal of Political Economy, 129(12), 2021
2021
-
[22]
Gibbs and E
I. Gibbs and E. Cand` es. Adaptive conformal inference under distribution shift. In Advances in Neural Information Processing Systems 34 , 2021
2021
-
[23]
Gy¨ orfi, M
L. Gy¨ orfi, M. Kohler, A. Krzy˙ zak, and H. Walk.A Distribution-Free Theory of Nonpara- metric Regression. Springer, 2002
2002
-
[24]
Hiriart-Urruty and C
J. Hiriart-Urruty and C. Lemar´ echal. Convex Analysis and Minimization Algorithms I . Springer, New York, 1993
1993
-
[25]
Hiriart-Urruty and C
J. Hiriart-Urruty and C. Lemar´ echal.Convex Analysis and Minimization Algorithms II . Springer, New York, 1993
1993
-
[26]
J. D. Lee, M. Simchowitz, M. I. Jordan, and B. Recht. Gradient descent only converges to minimizers. In Proceedings of the Twenty Ninth Annual Conference on Computational Learning Theory, 2016
2016
-
[27]
J. Lei. Classification with confidence. Biometrika, 101(4):755–769, 2014
2014
-
[28]
Lei and L
J. Lei and L. Wasserman. Distribution-free prediction bands for non-parametric regres- sion. Journal of the Royal Statistical Society, Series B , 76(1):71–96, 2014
2014
-
[29]
J. Lei, M. G’Sell, A. Rinaldo, R. J. Tibshirani, and L. Wasserman. Distribution-free predictive inference for regression. Journal of the American Statistical Association , 113 (523):1094–1111, 2018. 35
2018
-
[30]
Nemirovski, A
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization , 19(4):1574–1609, 2009
2009
-
[31]
Nesterov
Y. Nesterov. How to make the gradients small. Optima, 88, 2012
2012
-
[32]
Raginsky and A
M. Raginsky and A. Rakhlin. Information-based complexity, feedback, and dynamics in convex programming. IEEE Transactions on Information Theory , 57(10):7036–7056, 2011
2011
-
[33]
R. T. Rockafellar. Convex Analysis. Princeton University Press, 1970
1970
-
[34]
Shalev-Shwartz, O
S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan. Learnability, stability and uniform convergence. Journal of Machine Learning Research , 11:2635–2670, 2010
2010
-
[35]
Shapiro, D
A. Shapiro, D. Dentcheva, and A. Ruszczy´ nski. Lectures on Stochastic Programming: Modeling and Theory . SIAM and Mathematical Optimization Society, second edition, 2014
2014
-
[36]
C. J. Stone. Consistent nonparametric regression. Annals of Statistics , 5(4):595–620, 1977
1977
-
[37]
A. B. Tsybakov. Introduction to Nonparametric Estimation . Springer, 2009
2009
-
[38]
A. W. van der Vaart. Superefficiency. In D. Pollard, E. Torgersen, and G. Yang, editors, Festschrift for Lucien Le Cam , chapter 27. Springer, 1997
1997
-
[39]
V. N. Vapnik. Statistical Learning Theory. Wiley, 1998
1998
-
[40]
V. Vovk. Conditional validity of inductive conformal predictors. Machine Learning, 92 (2):349–376, 2013. doi: 10.1007/s10994-013-5355-6. URL https://doi.org/10.1007/ s10994-013-5355-6
2013 doi
-
[41]
V. Vovk, A. Grammerman, and G. Shafer. Algorithmic Learning in a Random World . Springer, 2005
2005
-
[42]
M. J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint . Cam- bridge University Press, 2019
2019
-
[43]
M. J. Wainwright and M. I. Jordan. Graphical models, exponential families, and varia- tional inference. Foundations and Trends in Machine Learning , 1(1–2):1–305, 2008. A Properties of the set of achievable minimizers With the definitions of directional derivatives and associa...
2008
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.