pith. machine review for the scientific record.
sign in

arxiv: 2511.11237 · v2 · submitted 2025-11-14 · 💻 cs.DS · math.OC

An Efficient Algorithm for Minimizing Ordered Norms in Fractional Load Balancing

Daniel Blankenburg , Antonia Ellerbrock , Thomas Kesselheim , Jens Vygen This is my paper

Pith reviewed 2026-05-17 22:32 UTC · model grok-4.3

classification 💻 cs.DS math.OC
keywords ordered normsfractional load balancingapproximation algorithmsoracle-efficient methodsrandomized algorithmsmartingale analysissmooth approximationsresource prices
0
0 comments X

The pith

A randomized algorithm finds (1+ε)-approximate solutions for minimizing ordered norms of aggregated loads using O((n+d)(ε^{-2} + log log d) log(n+d)) linear oracle calls with high probability.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a randomized method to approximately solve fractional load balancing where n customers each pick a non-negative vector from their convex set X_c, and the objective is to minimize an ordered norm of the total load vector across d resources. This extends earlier multiplicative-weights techniques that handled only the infinity norm. The algorithm maintains a resource-price mechanism driven by smooth approximations to the chosen ordered norm. It equips each customer with an evolving cost budget that dictates step size and permits rejection of some oracle outputs. Non-uniform sampling combined with a martingale argument then guarantees enough expected progress per iteration to bound the total number of linear-minimization oracle calls.

Core claim

We devise a randomized algorithm that computes a (1+ε)-approximate solution to this problem and makes, with high probability, O((n+d)(ε^{-2} + log log d) log(n+d)) calls to oracles that minimize linear functions over X_c. The algorithm uses a resource price mechanism motivated by the follow-the-regularized-leader paradigm, and is expressed by smooth approximations of ordered norms. We need and show that these have non-trivial stability properties. For each customer, we define dynamic cost budgets, which evolve throughout the algorithm, to determine the allowed step sizes. This leads to non-uniform updates and may even reject certain oracle solutions. Using non-uniform sampling together with

What carries the argument

Resource price mechanism built from smooth approximations of ordered norms, together with per-customer dynamic cost budgets and non-uniform sampling.

If this is right

  • The method applies to every ordered norm, not merely the infinity norm.
  • The total number of linear oracle calls remains near-linear in n+d once ε is fixed.
  • Non-uniform updates that sometimes discard oracle answers are sufficient to maintain progress.
  • High-probability guarantees follow from a martingale concentration argument once stability is established.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The stability properties shown for smooth ordered-norm approximations may transfer to other non-smooth convex objectives in online or distributed optimization.
  • Dynamic budgets could be adapted to enforce fairness constraints or to handle stochastic customer arrivals.
  • Practical implementations could replace exact linear oracles with faster heuristics while preserving the same asymptotic call bound.

Load-bearing premise

The smooth approximations to ordered norms must possess non-trivial stability properties that let the resource-price mechanism steer the martingale progress argument.

What would settle it

An explicit instance of the load-balancing problem together with a concrete smooth approximation for which the stability properties fail, causing the observed number of oracle calls to exceed the stated high-probability bound.

read the original abstract

We study the problem of minimizing an ordered norm of a load vector (indexed by a set of $d$ resources), where a finite number $n$ of customers $c$ contribute to the load of each resource by choosing a solution $x_c$ in a convex set $X_c \subseteq \mathbb{R}^d_{\geq 0}$; so we minimize $||\sum_{c}x_c||$ for some fixed ordered norm $||\cdot||$. We devise a randomized algorithm that computes a $(1+\varepsilon)$-approximate solution to this problem and makes, with high probability, $\mathcal{O}\left((n+d) (\varepsilon^{-2}+\log\log d)\log (n+d)\right)$ calls to oracles that minimize linear functions (with non-negative coefficients) over $X_c$. While this has been known for the $\ell_{\infty}$ norm via the multiplicative weights update method, existing proof techniques do not extend to arbitrary ordered norms. Our algorithm uses a resource price mechanism that is motivated by the follow-the-regularized-leader paradigm, and is expressed by smooth approximations of ordered norms. We need and show that these have non-trivial stability properties, which may be of independent interest. For each customer, we define dynamic cost budgets, which evolve throughout the algorithm, to determine the allowed step sizes. This leads to non-uniform updates and may even reject certain oracle solutions. Using non-uniform sampling together with a martingale argument, we can guarantee sufficient expected progress in each iteration, and thus bound the total number of oracle calls with high probability.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper studies minimizing an ordered norm of the aggregate load vector formed by n customers each selecting a point from a convex set X_c in R^d. It presents a randomized algorithm that returns a (1+ε)-approximate solution and, with high probability, makes only O((n+d)(ε^{-2} + log log d) log(n+d)) calls to linear-minimization oracles over the X_c. The algorithm maintains resource prices via smooth approximations to the ordered norm, uses dynamic per-customer cost budgets to control step sizes (allowing rejections), and analyzes progress via non-uniform sampling and a martingale concentration argument.

Significance. If the claimed stability properties of the smooth ordered-norm approximations hold uniformly, the result extends the multiplicative-weights-update technique from the ℓ_∞ case to general ordered norms while retaining a near-linear dependence on n+d and only logarithmic dependence on d. The explicit construction and proof of the required stability properties constitute a technical contribution that may be reusable in other regularized-leader or online-optimization settings.

major comments (2)
  1. [§4] §4 (Stability of smooth approximations): the claimed uniform stability bounds (e.g., the Lipschitz constants and the control on the difference of subgradients) must be shown to remain independent of the current price vector and the dynamic budget state; otherwise the variance of the martingale increments is not uniformly bounded and the log log d term in the high-probability bound does not follow.
  2. [§5.2] §5.2 (Martingale argument): the proof that non-uniform sampling together with possible oracle rejections still yields sufficient expected progress per iteration relies on the stability constants derived in §4. If those constants depend on the current state, the concentration inequality invoked (presumably Azuma or Freedman's) must be re-verified with the state-dependent variance; the current sketch does not make this dependence explicit.
minor comments (2)
  1. [Introduction] The precise definition of the ordered norm (e.g., whether it is the Ky-Fan k-norm or a general symmetric norm) should be stated once in the introduction with a reference to the standard definition.
  2. [Algorithm 1] Figure 1 (algorithm pseudocode) would benefit from an explicit line indicating where the dynamic budget is updated and where a rejection occurs.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and constructive comments on our paper. The points raised regarding the uniformity of stability bounds and the martingale analysis are important for ensuring the rigor of our high-probability bounds. We address each major comment below and will incorporate clarifications and expansions in the revised version of the manuscript.

read point-by-point responses

  1. Referee: [§4] §4 (Stability of smooth approximations): the claimed uniform stability bounds (e.g., the Lipschitz constants and the control on the difference of subgradients) must be shown to remain independent of the current price vector and the dynamic budget state; otherwise the variance of the martingale increments is not uniformly bounded and the log log d term in the high-probability bound does not follow.

    Authors: We agree that the independence of the stability bounds from the price vector and budget state is crucial for the analysis. In Section 4 of the manuscript, we prove that the smooth approximations to the ordered norms satisfy Lipschitz continuity and subgradient difference bounds that depend only on the approximation parameter and d, and are independent of the specific price vector. The dynamic budgets influence the acceptance of updates but do not affect the stability properties of the price updates themselves. To address the referee's concern explicitly, we will add a dedicated lemma or remark in the revision that states the uniformity of these constants and verifies that they do not depend on the current state. revision: yes

  2. Referee: [§5.2] §5.2 (Martingale argument): the proof that non-uniform sampling together with possible oracle rejections still yields sufficient expected progress per iteration relies on the stability constants derived in §4. If those constants depend on the current state, the concentration inequality invoked (presumably Azuma or Freedman's) must be re-verified with the state-dependent variance; the current sketch does not make this dependence explicit.

    Authors: The martingale argument in Section 5.2 uses the uniform stability constants established in Section 4 to bound the variance of the increments uniformly, even with non-uniform sampling and rejections. The expected progress is shown to be at least a constant fraction of the potential decrease, and the bounded differences allow application of Freedman's inequality with a variance proxy that is independent of the state due to the uniform bounds. We acknowledge that the current presentation could make the dependence (or lack thereof) more explicit. In the revision, we will expand the proof sketch to include a detailed verification of the concentration bound, explicitly referencing the state-independent variance from the stability properties. revision: yes

Circularity Check

0 steps flagged

No significant circularity; analysis relies on external martingale and concentration tools

full rationale

The paper constructs a randomized algorithm for (1+ε)-approximating ordered-norm minimization over convex sets X_c, using a resource-price mechanism based on smooth ordered-norm approximations. It explicitly states and proves the required stability properties of these approximations, then applies non-uniform sampling and a martingale argument to bound oracle calls by O((n+d)(ε^{-2} + log log d) log(n+d)) with high probability. The derivation chain invokes standard external concentration inequalities and properties of convex sets rather than reducing the approximation guarantee or runtime bound to any fitted parameter, self-defined quantity, or self-citation chain inside the paper. No load-bearing step equates a claimed prediction or uniqueness result to an input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The result rests on the existence of smooth approximations to ordered norms that satisfy stability properties sufficient for the martingale argument, plus standard convex optimization oracles and concentration bounds.

axioms (2)
  • domain assumption Smooth approximations of ordered norms exist with non-trivial stability properties
    Invoked to justify the resource-price mechanism and progress bound
  • standard math Linear minimization oracles over each X_c are available
    Standard assumption for the fractional load-balancing model

pith-pipeline@v0.9.0 · 5594 in / 1362 out tokens · 22028 ms · 2026-05-17T22:32:36.833745+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

77 extracted references · 77 canonical work pages

  1. [1]

    Online linear optimization via smoothing

    Jacob Abernethy, Chansoo Lee, Abhinav Sinha, and Ambuj Tewari. Online linear optimization via smoothing. InProceedings of the 27th Conference on Learning Theory, pages 807–823. PMLR, 2014

    work page 2014

  2. [2]

    Nearly linear-time packing and covering LP solvers: Achieving width-independence andO(1/ε)-convergence.Mathematical Programming, 175:307– 353, 2019

    Zeyuan Allen-Zhu and Lorenzo Orecchia. Nearly linear-time packing and covering LP solvers: Achieving width-independence andO(1/ε)-convergence.Mathematical Programming, 175:307– 353, 2019

    work page 2019

  3. [3]

    The multiplicative weights update method: a meta-algorithm and applications.Theory of Computing, 8(1):121–164, 2012

    Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications.Theory of Computing, 8(1):121–164, 2012

    work page 2012

  4. [4]

    All-norm approximation algorithms.Journal of Algorithms, 52(2):120–133, 2004

    Yossi Azar, Leah Epstein, Yossi Richter, and Gerhard J Woeginger. All-norm approximation algorithms.Journal of Algorithms, 52(2):120–133, 2004

    work page 2004

  5. [5]

    Weighted sums of certain dependent random variables.Tohoku Mathematical Journal, Second Series, 19(3):357–367, 1967

    Kazuoki Azuma. Weighted sums of certain dependent random variables.Tohoku Mathematical Journal, Second Series, 19(3):357–367, 1967

    work page 1967

  6. [6]

    The isotonic regression problem and its dual.Journal of the American Statistical Association, 67(337):140–147, 1972

    Richard E Barlow and Hugh D Brunk. The isotonic regression problem and its dual.Journal of the American Statistical Association, 67(337):140–147, 1972

    work page 1972

  7. [7]

    The cyclic block conditional gradient method for convex optimization problems.SIAM Journal on Optimization, 25(4):2024–2049, 2015

    Amir Beck, Edouard Pauwels, and Shoham Sabach. The cyclic block conditional gradient method for convex optimization problems.SIAM Journal on Optimization, 25(4):2024–2049, 2015

    work page 2024

  8. [8]

    Smoothing and first order methods: A unified framework

    Amir Beck and Marc Teboulle. Smoothing and first order methods: A unified framework. SIAM Journal on Optimization, 22(2):557–580, 2012

    work page 2012

  9. [9]

    Iter- ative Bregman projections for regularized transportation problems.SIAM Journal on Scientific Computing, 37(2):A1111–A1138, 2015

    Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. Iter- ative Bregman projections for regularized transportation problems.SIAM Journal on Scientific Computing, 37(2):A1111–A1138, 2015

    work page 2015

  10. [10]

    Minimizing separable convex functions subject to simple chain constraints.SIAM Journal on Optimization, 10(3):658–672, 2000

    Michael J Best, Nilotpal Chakravarti, and Vasant A Ubhaya. Minimizing separable convex functions subject to simple chain constraints.SIAM Journal on Optimization, 10(3):658–672, 2000

    work page 2000

  11. [11]

    Approximating fractional packings and coverings in O(1/epsilon) iterations.SIAM Journal on Computing, 35(4):825–854, 2006

    Daniel Bienstock and Garud Iyengar. Approximating fractional packings and coverings in O(1/epsilon) iterations.SIAM Journal on Computing, 35(4):825–854, 2006

    work page 2006

  12. [12]

    Resource sharing revisited: Local weak duality and optimal convergence

    Daniel Blankenburg. Resource sharing revisited: Local weak duality and optimal convergence. InProceedings of the 30th Annual European Symposium on Algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. Article 20

    work page 2022

  13. [13]

    Braun, A

    Gábor Braun, Alejandro Carderera, Cyrille W Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Sebastian Pokutta. Conditional gradient methods.arXiv preprint arXiv:2211.14103, 2022

    work page arXiv 2022

  14. [14]

    Blended conditional gradients: the unconditioning of conditional gradients

    Gábor Braun, Sebastian Pokutta, Dan Tu, and Stephen Wright. Blended conditional gradients: the unconditioning of conditional gradients. InProceedings of the 36th International Conference on Machine Learning, pages 735–743. PMLR, 2019. 29

    work page 2019

  15. [15]

    Lev M Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming.USSR Computational Mathematics and Mathematical Physics, 7(3):200–217, 1967

    work page 1967

  16. [16]

    Legalizing a placement with minimum total movement.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 23(12):1597–1613, 2004

    Ulrich Brenner and Jens Vygen. Legalizing a placement with minimum total movement.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 23(12):1597–1613, 2004

    work page 2004

  17. [17]

    Iterative averaging of entropic projections for solving stochastic convex feasibility problems.Computational Optimization and Applications, 8:21–39, 1997

    Dan Butnariu, Yair Censor, and Simeon Reich. Iterative averaging of entropic projections for solving stochastic convex feasibility problems.Computational Optimization and Applications, 8:21–39, 1997

    work page 1997

  18. [18]

    Approximation algorithms for minimum norm and ordered optimization problems

    Deeparnab Chakrabarty and Chaitanya Swamy. Approximation algorithms for minimum norm and ordered optimization problems. InProceedings of the 51st Annual ACM SIGACT Sympo- sium on Theory of Computing, pages 126–137, 2019

    work page 2019

  19. [19]

    Simpler and better algorithms for minimum- norm load balancing

    Deeparnab Chakrabarty and Chaitanya Swamy. Simpler and better algorithms for minimum- norm load balancing. In27th Annual European Symposium on Algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. Article 27

    work page 2019

  20. [20]

    On multiplicative weight updates for concave and submodular function maximization

    Chandra Chekuri, TS Jayram, and Jan Vondrák. On multiplicative weight updates for concave and submodular function maximization. InProceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 201–210, 2015

    work page 2015

  21. [21]

    Accelerated approximate optimization of multi- commodity flows on directed graphs

    Li Chen, Andrei Graur, and Aaron Sidford. Accelerated approximate optimization of multi- commodity flows on directed graphs. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 2203–2212, 2025

    work page 2025

  22. [22]

    High-accuracy multicommodity flows via iterative refinement

    Li Chen and Mingquan Ye. High-accuracy multicommodity flows via iterative refinement. In 51st International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl– Leibniz-Zentrum für Informatik, 2024. Article 45

    work page 2024

  23. [23]

    Provablyfastandnear-optimum gate sizing.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 37(12):3163–3176, 2018

    SiadDaboul, NicolaiHähnle, StephanHeld, andUlrikeSchorr. Provablyfastandnear-optimum gate sizing.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 37(12):3163–3176, 2018

    work page 2018

  24. [24]

    Global interconnect optimiza- tion.ACM Transactions on Design Automation of Electronic Systems, 28(5):1–24, 2023

    Siad Daboul, Stephan Held, Bento Natura, and Daniel Rotter. Global interconnect optimiza- tion.ACM Transactions on Design Automation of Electronic Systems, 28(5):1–24, 2023

    work page 2023

  25. [25]

    Approximating fractional multicommodity flow independent of the number of commodities.SIAM Journal on Discrete Mathematics, 13(4):505–520, 2000

    Lisa K Fleischer. Approximating fractional multicommodity flow independent of the number of commodities.SIAM Journal on Discrete Mathematics, 13(4):505–520, 2000

    work page 2000

  26. [26]

    An algorithm for quadratic programming.Naval Research Logistics Quarterly, 3(1-2):95–110, 1956

    Marguerite Frank and Philip Wolfe. An algorithm for quadratic programming.Naval Research Logistics Quarterly, 3(1-2):95–110, 1956

    work page 1956

  27. [27]

    New analysis and results for the Frank–Wolfe method

    Robert M Freund and Paul Grigas. New analysis and results for the Frank–Wolfe method. Mathematical Programming, 155(1):199–230, 2016

    work page 2016

  28. [28]

    A decision-theoretic generalization of on-line learning and an application to boosting.Journal of Computer and System Sciences, 55(1):119–139, 1997

    Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting.Journal of Computer and System Sciences, 55(1):119–139, 1997

    work page 1997

  29. [29]

    Faster and simpler algorithms for multicommodity flow and other fractional packing problems.SIAM Journal on Computing, 37(2):630–652, 2007

    Naveen Garg and Jochen Könemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems.SIAM Journal on Computing, 37(2):630–652, 2007. 30

    work page 2007

  30. [30]

    Fast approximation schemes for convex pro- grams with many blocks and coupling constraints.SIAM Journal on Optimization, 4(1):86–107, 1994

    Michael D Grigoriadis and Leonid G Khachiyan. Fast approximation schemes for convex pro- grams with many blocks and coupling constraints.SIAM Journal on Optimization, 4(1):86–107, 1994

    work page 1994

  31. [31]

    Coordination complexity of parallel price- directive decomposition.Mathematics of Operations Research, 21(2):321–340, 1996

    Michael D Grigoriadis and Leonid G Khachiyan. Coordination complexity of parallel price- directive decomposition.Mathematics of Operations Research, 21(2):321–340, 1996

    work page 1996

  32. [32]

    Conditional gradient algorithms for norm-regularized smooth convex optimization.Mathematical Programming, 152(1):75–112, 2015

    Zaid Harchaoui, Anatoli Juditsky, and Arkadi Nemirovski. Conditional gradient algorithms for norm-regularized smooth convex optimization.Mathematical Programming, 152(1):75–112, 2015

    work page 2015

  33. [33]

    Global routing with timing constraints.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 37(2):406–419, 2017

    Stephan Held, Dirk Müller, Daniel Rotter, Rudolf Scheifele, Vera Traub, and Jens Vygen. Global routing with timing constraints.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 37(2):406–419, 2017

    work page 2017

  34. [34]

    Learning permutations with exponential weights

    David P Helmbold and Manfred K Warmuth. Learning permutations with exponential weights. Journal of Machine Learning Research, 10(7):1705–1736, 2009

    work page 2009

  35. [35]

    Tracking the best linear predictor.Journal of Machine Learning Research, 1:281–309, 2001

    Mark Herbster and Manfred K Warmuth. Tracking the best linear predictor.Journal of Machine Learning Research, 1:281–309, 2001

    work page 2001

  36. [36]

    On the global convergence of stochastic fictitious play.Econometrica, 70(6):2265–2294, 2002

    Josef Hofbauer and William H Sandholm. On the global convergence of stochastic fictitious play.Econometrica, 70(6):2265–2294, 2002

    work page 2002

  37. [37]

    A survey on multi-net global routing for integrated circuits

    Jiang Hu and Sachin S Sapatnekar. A survey on multi-net global routing for integrated circuits. Integration, 31(1):1–49, 2001

    work page 2001

  38. [38]

    Minimum-norm load balancing is (almost) as easy as minimizing makespan

    Sharat Ibrahimpur and Chaitanya Swamy. Minimum-norm load balancing is (almost) as easy as minimizing makespan. In48th International Colloquium on Automata, Languages, and Programming, pages 81:1–20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021

    work page 2021

  39. [39]

    Revisiting Frank–Wolfe: Projection-free sparse convex optimization

    Martin Jaggi. Revisiting Frank–Wolfe: Projection-free sparse convex optimization. InPro- ceedings of the 30th International Conference on Machine Learning, pages 427–435. PMLR, 2013

    work page 2013

  40. [40]

    Packing Steiner trees

    Kamal Jain, Mohammad Mahdian, and Mohammad R Salavatipour. Packing Steiner trees. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 266–274, 2003

    work page 2003

  41. [41]

    Faster approximation schemes for fractional multicommodity flow prob- lems.ACM Transactions on Algorithms, 4(1):1–17, 2008

    George Karakostas. Faster approximation schemes for fractional multicommodity flow prob- lems.ACM Transactions on Algorithms, 4(1):1–17, 2008

    work page 2008

  42. [42]

    An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity general- izations

    Jonathan A Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity general- izations. InProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 217–226. SIAM, 2014

    work page 2014

  43. [43]

    Faster approximate multicommodity flow using quadratically coupled flows

    Jonathan A Kelner, Gary L Miller, and Richard Peng. Faster approximate multicommodity flow using quadratically coupled flows. InProceedings of the 44th Annual ACM Symposium on Theory of Computing, pages 1–18, 2012

    work page 2012

  44. [44]

    Online and bandit algorithms beyond ℓp norms

    Thomas Kesselheim, Marco Molinaro, and Sahil Singla. Online and bandit algorithms beyond ℓp norms. InProceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1566–1593. SIAM, 2023. 31

    work page 2023

  45. [45]

    Supermodular approximation of norms and applications

    Thomas Kesselheim, Marco Molinaro, and Sahil Singla. Supermodular approximation of norms and applications. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1841–1852, 2024

    work page 2024

  46. [46]

    Lagrangian relaxation based algorithms for convex programming problems

    Rohit Khandekar. Lagrangian relaxation based algorithms for convex programming problems. PhD thesis, Department of Computer Science and Engineering, Indian Institute of Technology, Delhi, 2004

    work page 2004

  47. [47]

    Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts.SIAM Journal on Computing, 23(3):466–487, 1994

    Philip Klein, Serge Plotkin, Clifford Stein, and Eva Tardos. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts.SIAM Journal on Computing, 23(3):466–487, 1994

    work page 1994

  48. [48]

    On the number of iterations for Dantzig–Wolfe optimization and packing-covering approximation algorithms.SIAM Journal on Computing, 44(4):1154– 1172, 2015

    Philip Klein and Neal E Young. On the number of iterations for Dantzig–Wolfe optimization and packing-covering approximation algorithms.SIAM Journal on Computing, 44(4):1154– 1172, 2015

    work page 2015

  49. [49]

    Hedging structured concepts

    Wouter M Koolen, Manfred K Warmuth, and Jyrki Kivinen. Hedging structured concepts. In Proceedings of the 23rd Conference on Learning Theory, pages 93–105, 2010

    work page 2010

  50. [50]

    The method of randomized Bregman projections for stochastic feasibility problems.Numerical Algorithms, 93(3):1269–1307, 2023

    Vladimir R Kostić and Saverio Salzo. The method of randomized Bregman projections for stochastic feasibility problems.Numerical Algorithms, 93(3):1269–1307, 2023

    work page 2023

  51. [51]

    Batch Greenkhorn algorithm for entropic-regularized multimarginal optimal transport: Linear rate of convergence and iteration complexity

    Vladimir R Kostic, Saverio Salzo, and Massimiliano Pontil. Batch Greenkhorn algorithm for entropic-regularized multimarginal optimal transport: Linear rate of convergence and iteration complexity. InProceedings of the 39th International Conference on Machine Learning, pages 11529–11558. PMLR, 2022

    work page 2022

  52. [52]

    Telefoonverkeersrekening.De Ingenieur, 52:15–25, 1937

    J Kruithof. Telefoonverkeersrekening.De Ingenieur, 52:15–25, 1937

    work page 1937

  53. [53]

    On information and sufficiency.The Annals of Mathematical Statistics, 22(1):79–86, 1951

    Solomon Kullback and Richard A Leibler. On information and sufficiency.The Annals of Mathematical Statistics, 22(1):79–86, 1951

    work page 1951

  54. [54]

    Block-coordinate Frank–Wolfe optimization for structural SVMs

    Simon Lacoste-Julien, Martin Jaggi, Mark Schmidt, and Patrick Pletscher. Block-coordinate Frank–Wolfe optimization for structural SVMs. InProceedings of the 30th International Con- ference on Machine Learning, pages 53–61. PMLR, 2013

    work page 2013

  55. [55]

    Conditional accelerated lazy stochastic gradient descent

    Guanghui Lan, Sebastian Pokutta, Yi Zhou, and Daniel Zink. Conditional accelerated lazy stochastic gradient descent. InProceedings of the 34th International Conference on Machine Learning, pages 1965–1974. PMLR, 2017

    work page 1965

  56. [56]

    Cambridge University Press, 2020

    Tor Lattimore and Csaba Szepesvári.Bandit Algorithms. Cambridge University Press, 2020

    work page 2020

  57. [57]

    Fast approximation algorithms for multicommodity flow problems

    Tom Leighton, Clifford Stein, Fillia Makedon, Éva Tardos, Serge Plotkin, and Spyros Tragoudas. Fast approximation algorithms for multicommodity flow problems. InProceed- ings of the twenty-third annual ACM Symposium on Theory of Computing, pages 101–111, 1991

    work page 1991

  58. [58]

    Efficient Bregman projections onto the permutahedron and related polytopes

    Cong Han Lim and Stephen J Wright. Efficient Bregman projections onto the permutahedron and related polytopes. InArtificial Intelligence and Statistics, pages 1205–1213. PMLR, 2016

    work page 2016

  59. [59]

    Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms

    Aleksander Mądry. Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. InProceedings of the 42nd ACM Symposium on Theory of Computing, pages 121–130, 2010. 32

    work page 2010

  60. [60]

    Online and random-order load balancing simultaneously

    Marco Molinaro. Online and random-order load balancing simultaneously. InProceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1638–1650. SIAM, 2017

    work page 2017

  61. [61]

    Faster min-max resource sharing in theory and practice.Mathematical Programming Computation, 3(1):1–35, 2011

    Dirk Müller, Klaus Radke, and Jens Vygen. Faster min-max resource sharing in theory and practice.Mathematical Programming Computation, 3(1):1–35, 2011

    work page 2011

  62. [62]

    Excessive gap technique in nonsmooth convex minimization.SIAM Journal on Optimization, 16(1):235–249, 2005

    Yu Nesterov. Excessive gap technique in nonsmooth convex minimization.SIAM Journal on Optimization, 16(1):235–249, 2005

    work page 2005

  63. [63]

    Smooth minimization of non-smooth functions.Mathematical Programming, 103:127–152, 2005

    Yu Nesterov. Smooth minimization of non-smooth functions.Mathematical Programming, 103:127–152, 2005

    work page 2005

  64. [64]

    Efficiency of coordinate descent methods on huge-scale optimization problems

    Yu Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22(2):341–362, 2012

    work page 2012

  65. [65]

    Decompositionmethodsfordifferentiableoptimizationproblemsovercarte- sian product sets.Computational Optimization and Applications, 9:5–42, 1998

    MichaelPatriksson. Decompositionmethodsfordifferentiableoptimizationproblemsovercarte- sian product sets.Computational Optimization and Applications, 9:5–42, 1998

    work page 1998

  66. [66]

    Fast approximation algorithms for frac- tional packing and covering problems.Mathematics of Operations Research, 20(2):257–301, 1995

    Serge A Plotkin, David B Shmoys, and Éva Tardos. Fast approximation algorithms for frac- tional packing and covering problems.Mathematics of Operations Research, 20(2):257–301, 1995

    work page 1995

  67. [67]

    Fast deterministic approximation for the multicommodity flow problem.Math- ematical Programming, 78:43–58, 1996

    Tomasz Radzik. Fast deterministic approximation for the multicommodity flow problem.Math- ematical Programming, 78:43–58, 1996

    work page 1996

  68. [68]

    Tyrrell Rockafellar.Convex Analysis

    R. Tyrrell Rockafellar.Convex Analysis. Princeton University Press, 1970

    work page 1970

  69. [69]

    The maximum concurrent flow problem.Journal of the ACM, 37(2):318–334, 1990

    Farhad Shahrokhi and David W Matula. The maximum concurrent flow problem.Journal of the ACM, 37(2):318–334, 1990

    work page 1990

  70. [70]

    Online learning and online convex optimization.Foundations and Trends in Machine Learning, 4(2):107–194, 2012

    Shai Shalev-Shwartz. Online learning and online convex optimization.Foundations and Trends in Machine Learning, 4(2):107–194, 2012

    work page 2012

  71. [71]

    Generalizedpreconditioningandundirectedminimum-costflow

    JonahSherman. Generalizedpreconditioningandundirectedminimum-costflow. InProceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 772–780. SIAM, 2017

    work page 2017

  72. [72]

    A relationship between arbitrary positive matrices and doubly stochastic matrices.The Annals of Mathematical Statistics, 35(2):876–879, 1964

    Richard Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matrices.The Annals of Mathematical Statistics, 35(2):876–879, 1964

    work page 1964

  73. [73]

    Online prediction under submodular constraints

    Daiki Suehiro, Kohei Hatano, Shuji Kijima, Eiji Takimoto, and Kiyohito Nagano. Online prediction under submodular constraints. InInternational Conference on Algorithmic Learning Theory, pages 260–274. Springer, 2012

    work page 2012

  74. [74]

    Adeterministicalmost-lineartimealgorithm for minimum-cost flow

    Jan van den Brand, Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg, SushantSachdeva, andAaronSidford. Adeterministicalmost-lineartimealgorithm for minimum-cost flow. In64th Annual Symposium on Foundations of Computer Science, pages 503–514. IEEE, 2023

    work page 2023

  75. [75]

    Techniques for scalable and effective routability evaluation.ACM Transactions on Design Automation of Electronic Systems, 19(2):1–37, 2014

    Yaoguang Wei, Cliff Sze, Natarajan Viswanathan, Zhuo Li, Charles J Alpert, Lakshmi Reddy, Andrew D Huber, Gustavo E Tellez, Douglas Keller, and Sachin S Sapatnekar. Techniques for scalable and effective routability evaluation.ACM Transactions on Design Automation of Electronic Systems, 19(2):1–37, 2014. 33

    work page 2014

  76. [76]

    Neil E. Young. Sequential and parallel algorithms for mixed packing and covering. InPro- ceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pages 538–546, 2001. 34 A Relation to Follow-the-Regularized-Leader InsteadofusingthegradientsofanormapproximationΨaspricestodeterminethenextsolutions (t) with our minimization oraclefoverX, we co...

    work page 2001

  77. [77]

    attained an improved running time ofO(dlogd)by reduction to theIsotonic Optimization Problem[6], for which efficient algorithms were developed independently before, e.g., thePool Adjacent Violatorsalgorithm by Best, Chakravarti and Ubhaya [10], or theSingle Row Clumping Algorithmby Brenner and Vygen [16] in the completely different context of VLSI placement. 39

    work page